Explo ación de acele ado es y ha dwa e g á ico de
o ma amigable
Nelson Ma ín Viei es y Jo ge Collado Ga cía
GRADO EN INGENIERÍA DE COMPUTADORES
FACULTAD DE INFORMÁTICA
DEPARTAMENTO DE ARQUITECTURA DE COMPUTADORES Y
AUTOMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
TRABAJO FIN DE GRADO EN INGENIERÍA DE COMPUTADORES
Mad id, 20 de junio de 2014
Di ec o es:
Guille mo Bo ella Juan y Ca los Ga cía Sánchez
II
III
Au o ización de di usión y u ilización
Noso os Nelson Ma ín Viei es y Jo ge Collado Ga cía au o es de es e documen o
au o izamos a la Uni e sidad Complu ense de Mad id a la di usión y u ilización del mismo.
Nelson Ma ín Viei es Jo ge Collado Ga cía
DNI: 11854940-G DNI: 505549-E
Mad id, 20 de junio de 2014
IV
V
A mi he mano Bo ja, ya que sin su ayuda no
hubie a conseguido odo lo que he log ado es os
años y po que él es uno de los mo i os po los
que sé que debo segui supe ándome. A mis
pad es Manuela y Ja ie po habe c eído
siemp e en mí y consegui que inalmen e yo
ambién lo hicie a. A mi no ia Sa a po
apoya me en odo momen o y da me ese úl imo
empujón cuando no me c eía capaz de algo
Nelson
A mis “compis” de biblio eca, esos
con los que a los cinco minu os de sen a e e
ibas a la calle a hace nada. A aquellos que e
obligaban a es udia po las noches, bajo
amenaza. A odos ellos y a mi amilia, que
g acias a ellos es oy hoy donde es oy
Jo ge

VI
VII
Ag adecimien os
Quisié amos mos a nues o más since o ag adecimien o a nues os u o es de p oyec o
Guille mo Bo ella Juan y Ca los Ga cía Sánchez, ya que sin ellos hubie a sido imposible la
ealización del mismo. Nos han apoyado y mo i ado desde el p ime momen o
consiguiendo que nos in e esá amos cada día más po la emá ica del p oyec o, al igual que
han es ado siemp e a nues a disposición pa a odo aquello que hemos necesi ado.
Po supues o ag adece a nues as amilias, pa ejas y amigos el apoyo dia io que nos han
dado du an e odos es os años has a llega aquí.
VIII
IX
Índice
Índice de igu as/ ablas ......................................................................................................... XI
Resumen ............................................................................................................................. XIII
Abs ac ............................................................................................................................. XIV
Capí ulo 1. In oducción ..........................................................................................................1
1.1 Es imación de mo imien o y lujo óp ico. .....................................................................1
1.1.1 Es ímulos. ...............................................................................................................1
1.1.2 Mé icas. .................................................................................................................3
1.2 Clasi icación de algo i mos. ..........................................................................................5
1.2.1 Modelos de g adien e. .............................................................................................5
1.2.2 Modelos de ene gía. ................................................................................................6
1.2.3 Modelos de ma ching. .............................................................................................6
1.3 Algo i mo Lucas&Kanade. ............................................................................................7
1.4 Mo i ación. ....................................................................................................................9
1.5 Obje i os. .....................................................................................................................10
Capí ulo 2. Ha dwa e asociado y pa adigmas de p og amación ...........................................13
2.1 Unidades de p ocesamien o g á ico. ............................................................................13
2.1.1 His o ia..................................................................................................................13
2.1.2 Es ado del a e. ......................................................................................................14
2.1.3 O as unidades.......................................................................................................17
2.2 Mé odos de P og amación basados en di ec i as ........................................................19
2.2.1 OpenMP ................................................................................................................20
2.2.2 OpenACC..............................................................................................................22
Capí ulo 3. Me odología y esul ados ....................................................................................27
3.1 Implemen ación de L&K. ............................................................................................27
3.1.1 OpenMP. Op imizaciones y ans o maciones. ....................................................31
3.1.2 OpenACC. Op imizaciones y ans o maciones. ..................................................33
3.2 Resul ados ob enidos. Rendimien o espec o al modelo o iginal en C. ......................36
3.2.1 En o no de abajo. ................................................................................................36
3.2.2 Resul ados de p ecisión. .......................................................................................36
3.2.3 Resul ados de endimien o. Modelo o iginal en C s OpenMP s OpenACC. ....44
2
A con inuación, desc ibi emos b e emen e algunos de los es ímulos más conocidos y que
hemos u ilizado en es e p oyec o:
Las anslaciones de ondas sinusoidales en dis in as ecuencias y di ecciones pe mi en
ap ecia los pa ones de mo imien o.
Figu a 1: Es ímulo sin é ico que simula la anslación de un seno.
Los es ímulos T ansla ing T ee y Di e ging T ee
1
(Da id Flee , Uni e sidad de To on o)
ep esen an espec i amen e el mo imien o de anslación ho izon al de un á bol y el e ec o
de zoom de una cáma a. Ambos es ímulos ienen unas dimensiones de 150x150 pixeles. En
el caso del “Di e ging T ee” se iene un ango de elocidades p ác icamen e nulo en el
cen o de la imagen que a c eciendo a medida que se ap oxima a los ex emos, simulando
así el e ec o de zoom an es mencionado. Pa a el “T ansla ing ee” el ango de elocidades
a a iando a lo la go del eje x, siendo di e en es en el bo de izquie do y de echo.
Figu a 2: Tex u a de los es ímulos T ansla ing ee y Di e ging ee con sus espec i os g ound u h.
.
1
Es ímulos disponibles en: h p://www.csd.uwo.ca/ acul y/ba on/FTP/TESTDATA/TREE_DATA/

3
Un es ímulo muy conocido es el de la secuencia de Yosemi e
2
(Lynn Quam, S an o d
Resea ch Ins i u e), siendo es e más complejo que los an e io es, ep esen a el mo imien o
de una cascada en el pa que nacional de Yosemi e en Es ados Unidos. Dependiendo de la
zona de la imagen, encon amos mo imien o en dis in as di ecciones y di e en es
elocidades. La exis encia de aliasing
3
en la pa e in e io de la imagen, di icul a las
mediciones en muchos algo i mos.
Figu a 3: Tex u a del es ímulo Yosemi e y lujo óp ico eal.
1.1.2 Mé icas.
Pa a medi la p ecisión de la implemen ación ealizada se necesi an mé icas de e o que
pe mi an comp oba la a iación en e el mo imien o eal del es ímulo y el mo imien o
es imado.
Una de las mé icas más u ilizadas pa a lujo óp ico es la de John Ba on [1]. Es a es una
medida de e o angula . La elocidad puede desc ibi se como el desplazamien o po unidad
de iempo = (u, ) pixels/ ame o como un ec o di ección espacio- empo al (u, , 1) en
unidades (pixel, pixel, ame). Cuando la elocidad es is a como o ien ación espacio
iempo, se puede medi el e o como la des iación angula desde la o ien ación espacio-
empo al co ec a. Po lo an o, deja la elocidad ep esen ada como un ec o 3D uni a io
que incluye módulo y ase en un único alo educiendo el e o pa a elocidades pequeñas.
Es e ec o se ep esen a en la ecuación (1).
2
Disponible en: h p://cs.b own.edu/~black/images.h ml
3
En compu ación g á ica, el aliasing es el a e ac o g á ico ca ac e ís ico que hace que en una pan alla
cie as cu as y líneas inclinadas p esen en un e ec o isual ipo "sie a" o "escalón". El aliasing ocu e
cuando se in en a ep esen a una imagen con cu as y líneas inclinadas en una pan alla, amebu e
o imagen, pe o que debido a la esolución ini a del sus a o esul a que és e sea incapaz de ep esen a la
cu a como al, y po an o dichas cu as se mues an en pan alla den adas al es a compues as po
pequeños cuad ados (los píxeles).
4
𝜐= 1
√𝑢2+𝜐2+1 (𝑢,𝜐,1)Τ (1)
El e o angula en e la elocidad co ec a 𝜐𝑐 y la elocidad es imada 𝜐𝑒 iene dado en la
ecuación (2).
𝜓Ε= 𝑎𝑟𝑐 𝑐𝑜𝑠 (𝜐
󰇍

𝑐⋅𝜐
󰇍

𝑒) (2)
5
1.2 Clasi icación de algo i mos.
Exis en es modelos o ca ego ías de algo i mos y écnicas de lujo óp ico que son los
modelos de g adien e, de ene gía y de ma ching o empa ejamien o. Se elegi á uno u o o
dependiendo de la aplicación que se les quie a da y eniendo en cuen a cuál se ajus a mejo
al llamado p oblema global de la co espondencia, con o mado po los p oblemas de
aliasing y ape u a.
1.2.1 Modelos de g adien e.
Los modelos de g adien e o di e enciales basan su me odología en aplica de i adas
espacio- empo ales, sob e las in ensidades de los pixeles de la imagen y de es a o ma
ob ene los ec o es elocidad que con o man el lujo óp ico. Es os ec o es elocidad se
ob ienen a pa i de cocien es sob e las de i adas espaciales y empo ales calculadas
an e io men e. Es e en oque, en líneas gene ales, p opo ciona una buena es imación.
El modelo de g adien e iene un en oque con a io al de los modelos de ene gía y ma ching
que se án explicados de alladamen e más adelan e. El en oque de es os modelos
básicamen e u iliza plan illas pa a ob ene un ajus e en e el mo imien o y la plan illa.
Además es os mé odos ienen una g an dependencia del con as e, lo que implica añadi
e apas de no malización cos osas. También cabe menciona que la elocidad se calcula en
o a e apa ex a ya que las plan illas no p opo cionan el mo imien o.
Po consiguien e, podemos e que el en oque de los mé odos basados en g adien e ienen
un meno núme o de e apas, pues o que las elocidades son calculadas di ec amen e como
un cocien e de las de i adas espacio- empo ales de cada pixel de la imagen. Es o ambién
iene el bene icio de que el con as e a ía de la misma o ma en el nume ado y en el
denominado , po lo an o no es necesa io una e apa adicional de no malización del
con as e pa a las imágenes.
Como incon enien e a es os mé odos encon amos que es necea io un il ado p e io al
p ocesamien o que implica in e i g andes ma ices como ocu e con el algo i mo
Lucas&Kanade [2, 3].
6
1.2.2 Modelos de ene gía.
El mecanismo de los modelos de ene gía consis e en u iliza il os o ien ados espacio-
empo ales que esponden de mane a óp ima a cie as elocidades. Es e p ocesado se lle a a
cabo con il os en pa alelo ac i ados pa a un cie o ango de alo es. La elección del
diseño de los il os es una de las p incipales di e encias en e los dis in os algo i mos de
es e modelo.
La es imación de mo imien o se plan ea como un p oblema de es imación global bayesiano,
se busca maximiza la p obabilidad del campo de mo imien o obse ando la in ensidad en
la siguien e ama. Se u ilizan dos unciones de densidad de p obabilidad, una es la
p obabilidad condicional de la in ensidad de la imagen obse ada a pa i del campo de
mo imien o, y la o a la p obabilidad a p io i de los ec o es de mo imien o.
Un incon enien e de es e modelo es el iempo que necesi an sus cálculos, ya que se
segmen a el campo de mo imien o en egiones, p ocesando pixel a pixel e incluyendo una
dis ibución de elocidades a cada uno.
Es a amilia se asemeja al modelo de g adien e en la u ilización de il os espacio-
empo ales, pe o di e gen en su u ilización. En los modelos de ene gía los il os esponden
a o ien aciones espacio- empo ales especí icas, mien as que en los de g adien e se ealiza
un cocien e con los il os.
1.2.3 Modelos de ma ching.
El en oque de es e modelo es uno de los más in ui i os, su me odología se esume en
compa a egiones de la imagen en e sucesi os ames, pa a así ob ene el mo imien o
obse ando los cambios en e egiones. Es e modelo ambién es conocido como “de
empa ejamien o” o “Block Ma ching”.
Las egiones en que se di ide cada imagen de la secuencia se llaman mac obloques. Se
busca el mo imien o en e las imágenes compa ando es os mac obloques. Se compa an los
bloques del ame ac ual con los del an eceso , deslizando es os sob e una egión de pixeles
del ame des ino. Los cambios in ie en la elocidad debido a que ha habido un cambio en
el iempo.
7
Figu a 4: Rep esen ación g á ica de un modelo de ma ching.
Algunos de los c i e ios de semejanza en e bloques más comunes son, el de Suma o io de
Di e encias Absolu as (SAD), Co elación C uzada No malizada (NCC) y Clasi icación po
Di e encia de Pixel (PDC). Es os c i e ios se enca gan de busca el bloque más adecuado
(mayo simili ud) de los que se encuen an en la en ana de búsqueda del ame des ino. Si
el bloque elegido se encuen a desplazado quie e deci que hay mo imien o, y es e
desplazamien o o ma á el ec o desplazamien o que se asigna á po igual a odos los
pixeles del bloque. Los bloques coinciden es en e ames no se án exac amen e iguales
debido al uido.
El incon enien e de es os algo i mos es la len i ud, es o es debido a una ejecución i e a i a
y a una búsqueda exhaus i a que equie en muchos ecu sos. Una imagen de amaño M
end ía una plan illa de amaño N y una en ana de amaño L, lo que en o den de
complejidad de cómpu o da ía luga a MxNxL. Hay a ian es de es os algo i mos que a an
de minimiza es a búsqueda exhaus i a FST (Full Sea ch Technique) como TSST (Th ee
S ep Sea ch Technique), LOGST (2D Loga i hm Sea ch Technique), DS (Diamond Sea ch),
CSA (C oss Sea ch Algo i hm) y 4SST (Fou S ep Sea ch Technique).
Como i ud, es des acable su simplicidad, de ahí su amplia aplicación en sec o es
indus iales o en es ánda es de codi icación y comp esión de ideo.
1.3 Algo i mo Lucas&Kanade.
Hay muchos es udios sob e algo i mos de lujo óp ico en los cuales sus au o es abo dan el
ema de la p ecisión de és os sob e es ímulos sin é icos ya que, a p io i, el lujo óp ico en
es ímulos eales es desconocido.
El algo i mo de Lucas&Kanade es un clásico en los modelos de g adien e y di e sos
es udios [3, 4, 5] des acan en él un buen balance en e p ecisión y e iciencia, equi iendo

8
unos ecu sos compu aciones abo dables. Es os son ac o es impo an es a la ho a de decidi
que en oque es más adecuado pa a implemen a un sis ema que sea capaz de p ocesa en
iempo eal.
A con inuación, desc ibi emos b e emen e los cálculos y ecuaciones en los cuales es á
basado el en oque de Lucas&Kanade. Se puede encon a in o mación más de allada en [1,
2, 6].
El algo i mo pe enece a las écnicas de g adien e, las cuales se ca ac e izan po la búsqueda
del g adien e sob e de i adas espaciales y empo ales. En el supues o de alo es de
iluminación cons an es a a és del iempo, la ecuación de g adien e de p ime o den se
ob iene con la ecuación (3).
∇xy𝐼(𝑥,𝑦,𝑡)⋅(𝑣𝑥,𝑣𝑦)+𝐼𝑡(𝑥,𝑦,𝑡)= 0 (3)
Es a ecuación solo pe mi e es ima la elocidad en la di ección del g adien e máximo, es
deci , en la di ección no mal de las supe icies de mo imien o. Pa a supe a es e
incon enien e, el modelo cons uye una es imación de mo imien o basada en las de i adas
de p ime o den de la imagen. Po medio del ajus e de mínimos cuad ados, el modelo ex ae
la es imación de mo imien o bajo la hipó esis de que las elocidades en la ecindad de un
pixel cen al son simila es. Es o se desc ibe en la exp esión (4),
𝑚𝑖𝑛∑𝑊2
𝑥∈Ω (𝑥)[𝐼(𝑥,𝑦,𝑡)⋅(𝑣𝑥,𝑣𝑦)+𝐼𝑡(𝑥,𝑦,𝑡)]2 (4)
donde W(x) son los pesos que se án asignados a los pixeles de la ecindad espacial Ω, ya
que en la p ác ica, es mejo da le más p io idad a los pixeles si uados más ce ca del
pixel cen al que se es á a ando.
La solución al p oblema iene dada en la ecuación (5),
𝑣= [𝐴𝑇𝑊2𝐴]−1 𝐴𝑇𝑊2𝑏
󰇍

(5)
donde:
𝐴𝑇𝑊2𝐴= [ ∑𝑊2𝐼𝑥
2
𝑥∈Ω ∑𝑊2𝐼𝑥𝐼𝑦𝑥∈Ω
∑𝑊2𝐼𝑥𝐼𝑦𝑥∈Ω ∑𝑊2𝐼𝑦
2
𝑥∈Ω ] (6)
𝐴𝑇𝑊2𝑏
󰇍

=[−∑𝑊2𝐼𝑥𝐼𝑡𝑥∈Ω
−∑𝑊2𝐼𝑦𝐼𝑡𝑥∈Ω ] (7)
9
Una limi ación de es e modelo se p oduce en las si uaciones en las que se p oduce el
llamado p oblema de ape u a. En es os casos la ma iz de la exp esión (6) no se puede
in e i , y po lo an o no se puede ob ene una es imación de mo imien o en ese pun o.
Pa a conclui la es imación de mo imien o en e dos imágenes consecu i as, iene dada la
ecuación (5), siendo 𝑣= (𝑣𝑥,𝑣𝑦) el ec o elocidad, que se á calculado como la
mul iplicación de la ma iz 2x2 de la ecuación (6) in e ida y la ma iz 2x1 de la
ecuación (7).
1.4 Mo i ación.
El cálculo del lujo óp ico es un p oblema, que como hemos is o has a aho a iene un cos e
compu acional conside able. Además po la na u aleza del p oblema es deseable que la
es imación sea lo más p ecisa posible. Po ello es necesa io busca un equilib io en e
p ecisión y e iciencia. Con p ecisión nos e e imos a la exac i ud de los esul ados y con
e iciencia a los ecu sos empleados y iempo in e ido en ob ene los. Las écnicas más
p ecisas implican mayo eque imien o compu acional. Dependiendo de las écnicas
u ilizadas end emos implemen aciones len as y p ecisas o más ápidas y con menos ni el
de p ecisión.
Pa a el es udio de es e p oyec o hemos elegido el mé odo de Lucas&Kanade, el cual
pe enece a la amilia de los modelos de g adien e. Su elección es debido a que ya exis en
a ias implemen aciones sob e acele ado es g á icos, algunas de las cuales ci a emos a
con inuación, donde se demues a la e ec i idad y la alidez de es e mé odo que posee un
buen comp omiso en e p ecisión y e iciencia, ob eniendo alo es den o de lo conside ado
iempo eal (a pa i de 25 ps).
Au o
ps
(Resolución)
GPU
Año
Ma za [7]
47 (316x252)
Tesla C870
2009
Du enhage [8]
30 (512x512)
GTX 285
2010
Ohmu a [9]
40 (512x384)
Tesla 1060
2011
Tabla 1: Implemen aciones del algo i mo Lucas-Kanade sob e GPUs.
10
En el abajo de Ma za se implemen a una e sión pi amidal del Lucas&Kanade sob e la
a qui ec u a CUDA, ob eniendo una ganancia en elocidad de 100x sob e la
implemen ación secuencial sob e CPU.
Du enhage lle a a cabo su implemen ación sob e GPU u ilizando el lenguaje OpenGL
Shading Language
4
(GLSL), con el obje i o de aplica lo en el campo de es abilización de
imágenes. Alcanzando en su con igu ación op ima 30 ps sob e esoluciones de 512x512.
El es udio ealizado po Ohmu a u iliza la es imación de mo imien o a a és del
Lucas&Kanade, pa a un p og ama que simula el p ocesamien o isual del ce eb o humano.
Es a implemen ación se lle a a cabo sob e un clus e de GPUs, in oduciendo como mejo as
la asignación de da os en e las memo ias compa ida y global de la GPU, además del
epa o de con oluciones en e las dis in as GPUs pa a los mismos da os de en ada.
1.5 Obje i os.
El obje i o p incipal de es e abajo Fin de G ado es e alua el compo amien o de un
algo i mo de es imación de mo imien o basado en el mé odo de Lucas&Kanade haciendo
uso de los acele ado es g á icos. La decisión de emplea dicha implemen ación iene
mo i ada po la amplia acep ación de es e algo i mo de g adien e en e la comunidad
cien í ica.
Debido a las necesidades compu aciones del mé odo el uso de acele ado es ha dwa e pa a
comple a equisi os de iempo eal ha sido una al e na i a conside ada con éxi o po la
comunidad. Sin emba go en la ac ualidad el uso de acele ado es conlle a la codi icación ad-
hoc dependiendo del ipo de acele ado conside ado. CUDA y OpenCL son los es ánda es
de ac o pa a sis emas basados en p ocesado es g á icos que son empleados como
cop ocesado es. El uso de es os in e aces de p og amación lle a asociado la eesc i u a
comple a de la aplicación. En e las p incipales des en ajas podemos des aca po abilidad
limi ada de la aplicación desa ollada y la a dua a ea de e-codi icación mo i ada po al a
de he amien as.
Bajo es e con ex o en los úl imos años su gen inicia i as que pe mi an hace uso de es as
ecnologías sin necesidad de eesc ibi el código uen e o al menos educi las
modi icaciones. En e los esul ados con mayo u u o des acamos la p og amación po
medio de di ec i as que es una solución in e media en e la e-codi icación en CUDA u
OpenCL, y una he amien a au omá ica que pe mi a su comple a po abilidad.
Conside amos que OpenMP
5
po su eco ido en el ámbi o de los sis emas con memo ia
4
h p://www.opengl.o g/documen a ion/glsl/
5
h p://openmp.o g/wp/
11
compa ida es un buen candida o a inc emen a sus p es aciones y amplia su uso a es os
sis emas. También podemos des aca la inicia i a que aglu ina OpenACC
6
que iene
bas an es isos de asen a se como es ánda de p og amación po medio de di ec i as pa a
acele ado es g á icos.
Los obje i os de es e abajo los podemos esumi en:
 Desa olla una codi icación del algo i mo de Lucas&Kanade en un lenguaje de
Al o Ni el como C.
 Es udia su compo amien o y p ecisión a la ho a de de ec a mo imien o empleado
como casos de p ueba una se ie de es ímulos de en ada ampliamen e acep ado po
la comunidad.
 E alua las pa es más cos osas del algo i mo que se án candida as a op imiza .
 Desa olla las e siones op imizadas del algo i mo haciendo uso de pa alelización
po medio de di ec i as. Inicialmen e se desa olla á una e sión pa a un sis ema
mul ico e desa ollada con OpenMP y pos e io men e se desa olla á su e sión
homónima pa a acele ado es median e di ec i as OpenACC.
 Po úl imo se e alua án las ganancias en iempo de ejecución haciendo uso de
ambas op imizaciones.
6
h p://www.openacc.o g/
18
 Modo symme ic "simé ico": las ca gas de abajo se compa en en e el p ocesado
an i ión y el cop ocesado .
 Modo na i e "na i o": la ca ga de abajo eside comple amen e en el cop ocesado
y ac úa undamen almen e como un nodo in o má ico independien e.
 Modo o load "desca ga": la ca ga de abajo eside en el p ocesado an i ión y
pa es de es a se en ían al cop ocesado según sea necesa io.
La emp esa AMD/ATI es á cen ada en la ab icación de p ocesado es con un ele ado
núme o de núcleos y con una in eg ación o al en e el p opio mic op ocesado y la a je a
g á ica. Es el p ime ab ican e que u iliza el concep o de APU en ez del de CPU, es deci ,
es el p ime o que in eg a p ocesado es g á icos y co es de CPU en el mismo chip. Con es o
in en an o ece una unidad de p ocesamien o capaz de abaja con da os complejos de
o ma e sá il.
En el e eno g á ico, la adquisición de la emp esa ATI po pa e de AMD ha p opiciado
que es a úl ima se dis ancie de su compe ido In el en el me cado de las a je as g á icas
in eg adas. G acias a que las a je as g á icas es án pensadas pa a abaja con da os en
pa alelo, cie o ipo de aplicaciones se pueden bene icia de una mayo in eg ación del
mic op ocesado y la a je a g á ica. Po ejemplo, la gene ación de imágenes
idimensionales o el p ocesado de imágenes o og á icas se pueden ealiza en meno
iempo g acias a es e nue o diseño.
Figu a 8: Ca ac e ís icas de las APUs de AMD.

19
La úl ima APU desa ollada po AMD es la denominada Ka e i, una nue a gene ación de
chips pa a o denado es de sob emesa y po á iles con cua o núcleos de CPU y ocho
núcleos de GPU. La lexibilidad de la a qui ec u a Ka e i pe mi e que odos los núcleos se
epa an la ca ga de abajo de o ma e icien e, eliminando las ba e as que han exis ido
his ó icamen e en e el ha dwa e in eg ado de p ocesamien o g á ico y los núcleos de
p ocesamien o cen al.
La nue a línea que es á desa ollando AMD es el concep o de núcleos de cálculo,
p ocesado es cuyas capacidades de cálculo g á ico y de da os gene ales se án o almen e
in e cambiables y que lo hagan en igualdad de condiciones, más allá de su p opia
especialización. Un ejemplo de es o es que la GPU pueda accede a la memo ia del sis ema
di ec amen e pa a asumi a eas de p ocesamien o in ensi o cuando la CPU in eg ada no
pueda hace se ca go de ellas.
Según AMD, la APU A10-7850K
13
o ece un endimien o bas an e pa ejo con el Co e i5-
4670K
14
de In el usando una a je a g á ica AMD R9 270X
15
y los pa áme os g á icos de
cada ideojuego al máximo.
2.2 Mé odos de P og amación basados en di ec i as
El uso de mé odos de p og amación basados en di ec i as no es nue o, exis en mul i ud de
compilado es que sopo an es e sis ema de di ec i as, las cuales son u ilizadas pa a guia al
compilado a la ho a de gene a código e icien e y acili a la po abilidad de código. Uno
de los mé odos más des acados en di ec i as es el pa adigma de p og amación pa alela
OpenMP, el cual gene a código pa alelo en sis emas de memo ia compa ida. OpenMP
apa ece en su e sión pa a C/C++ en o no al año 2000. T a a de se un es ánda pa a
uni ica las soluciones de odos los ab ican es de sis emas de memo ia compa ida. En el
ámbi o de p og amación po di ec i as pa a GPU hay que des aca OpenACC, cuya p ime a
especi icación apa ece en no iemb e de 2011 y a a de consolida se como es ánda de
p og amación basado en di ec i as pa a acele ado es independien emen e de la pla a o ma,
siguiendo la línea que lle o OpenMP en sus inicios.
13
h p://www.amd.com/es-es/p oduc s/p ocesso s/desk op/a-se ies-apu
14
h p://a k.in el.com/es-es/p oduc s/75048/In el-Co e-i5-4670K-P ocesso -6M-Cache-up- o-3_80-GHz
15
h p://www.amd.com/es-es/p oduc s/g aphics/desk op/ 9
20
2.2.1 OpenMP
Es un modelo de p og amación po able y escalable que p opo ciona a los p og amado es
un API pa a aplicaciones pa alelas en sis emas de memo ia compa ida. Es á disponible en
a ias a qui ec u as y pe mi e añadi concu encia a p og amas esc i os en Fo an y C/C++.
Se compone de un conjun o de di ec i as de compilado , u inas de biblio eca y a iables de
en o no. También se puede u iliza con ex ensiones de OpenMP o jun o con MPI
16
pa a
clus e s de compu ado es en sis emas de memo ia dis ibuida.
El o ma o de una di ec i a de OpenMP [15] pa a C/C++ es el siguien e:
#p agma omp <di ec i a> [cláusula [ , ...] ...]
En cuan o al modelo de ejecución de OpenMP, sigue el pa adigma o k-join p o enien e de
los sis emas Unix, que consis e en di idi ( o k) una a ea en N h eads (hilos), uniendo
(join) en el hilo p incipal los esul ados que llegan de uel a de cada h ead cuando inaliza.
Cuando se in oduce una di ec i a OpenMP sob e una egión de código, es e bloque
queda a ma cado como pa alelo y se inclui á una sinc onización sob e él po medio de
ba e as a la inalización de los dis in os hilos. Es e compo amien o se puede al e a po
medio de la di ec i a nowai .
Pa a cada h ead se gene a un iden i icado , que puede se accedido en iempo de ejecución
po medio de la unción omp_ge _ h ead_num(). Po no ma gene al, al hilo p incipal o
mas e se le asigna el id (iden i icado ) 0. Se puede con ola median e unciones o a iables
de en o no como OMP_NUM_THREADS el núme o de hilos que se desea ejecu a en las
egiones pa alelas.
Figu a 9: Modelo de ejecución en OpenMP.
16
h p://www.mcs.anl.go / esea ch/p ojec s/mpi/
21
La di ec i a que de ine el comienzo de una sección de código pa alela que se á ejecu ada
po a ios h eads iene el siguien e o ma o.
#p agma omp pa allel [clause [[,]clause]..] new-line
{S uc u ed block}
Las Wo ksha ing cons uc s o cons ucciones de abajo compa ido de ine como se
dis ibuye la ejecución en e los dis in os hilos. Algunas de es as di ec i as son o , que
indica que las i e aciones de un bucle se án ejecu adas en pa alelo po di e sos h eads. O a
cons ucción que ejecu a un conjun o de bloques es uc u ados de código, que no son
ejecu ados de o ma i e a i a sino que cada bloque de código es ejecu ado po uno de los
h eads se de ine con la di ec i a sec ions. La di ec i a single obliga a que la egión de
código sea ejecu ada po un solo h ead y no obliga o iamen e po el h ead mas e . En
cambio la di ec i a mas e si obliga a que el bloque de código sea ejecu ado po el hilo
p incipal, el mas e .
Se pueden anida di ec i as, po ejemplo, pa a una egión de código que con enga un bucle
pa alelizable se usa ía la siguien e di ec i a, #p agma omp pa allel o .
En cuan o al modelo de memo ia en OpenMP se a a de un modelo de memo ia
compa ida. Po lo an o odos los h eads ienen acceso pa a almacena y e i a
in o mación de es a memo ia. OpenMP de ine po medio de cláusulas de compa ición de
da os dos ámbi os pa a las a iables sha e y p i a e. Las a iables sha e son compa idas
po odos los h eads sob e la a iable o iginal, po lo que hay que ene especial cuidado.
Po ejemplo, en el caso de un a ay, con ola que no exis an dependencias de da os y que
no accedan a ios h eads a las mismas posiciones de memo ia, o ene un p oblema de
sinc onización de h eads lo que causa ía esul ados inespe ados. En el caso de las a iables
de inidas como p i a e, cada h ead c ea una copia p i ada de la a iable inicial pe o sin
inicializa , a la que solo pod á accede el p opio h ead. Du an e la egión de código
pa alela cada h ead e e encia a su copia p i ada de la a iable. La cláusula i s p i a e
indica que las copias p i adas de las a iables se inicializan con el alo de la a iable
o iginal. En cambio las p i a e ue za a que la a iable enga, al sali de la egión p i ada,
el alo que end ía en una ejecución secuencial. Po úl imo la cláusula educ ion pe mi e
hace una educción de los alo es que hayan calculado a ios h eads y uni los en una sola
a iable.
La úl ima e sión OpenMP 4.0 ue lanzada en ma zo de 2013. En e o as no edades es a
e sión incluye sopo e pa a desca ga egiones de código en disposi i os acele ado es. La
egión des ino se c ea como un h ead. Po medio de la cons ucción a ge se c ea el
en o no de ejecución en el disposi i o. La di ec i a map (pa a mapeo de da os) acep a las
clausulas alloc (pa a ese a memo ia), o (copia el alo inicial del hos ), om (de uel e
el alo modi icado en el de ice al hos ) y o om ( ealiza copia de en ada y salida). La
nue a di ec i a upda e pe mi e la ac ualización de alo es en e el hos y el de ice. O as
22
no edades son las cons ucciones eams, que de inen equipos (conjun os) de h eads
ag upados; y dis ibu e, que pe mi e la dis ibución de i e aciones de a eas en e eams. En
es a e sión ambién se ha añadido la cons ucción SIMD pa a ec o iza bucles
pa alelizables y bucles en se ie haciendo uso de ins ucciones SIMD (Single Ins uc ion
Mul iple Da a).
2.2.2 OpenACC
Ac ualmen e OpenACC [16] es uno de los modelos de p og amación de di ec i as más
des acados, ya que in en a consolida se como un es ánda en compu ación pa alela pa a
di e sos acele ado es. Fue desa ollado po un g upo de compañías PGI, CAPS, NVDIA y
CRAY. Su obje i o es simpli ica la p og amación en sis emas he e ogéneos CPU/GPU,
acili a la mig ación de código y se un in e medio en e la pa alelización au omá ica y la
pa alelización manual.
Sigue la misma p emisa que OpenMP, p opo ciona un conjun o de di ec i as pa a el
compilado que indican bucles, egiones de código y egiones de da os pa alelizables que
se án en iadas al disposi i o acele ado en o ma de ke nels. En endemos como hos a la
CPU, que se á la que lle e el lujo del p og ama secuencial; y de ice o disposi i o al
acele ado que ecibi á las egiones de código que se pueden ejecu a en pa alelo. Las
di ec i as se pueden aplica sob e p og amas esc i os en C, C++ o Fo an.
La es uc u a del p og ama y los da os ma cados po las di ec i as se án analizados po los
compilado es de OpenACC de mane a que la codi icación ecae á en es os y asigna á los
bucles de o ma que se op imice y se saque el máximo endimien o a las capacidades
ha dwa e de los hilos y a las capacidades SIMD de los acele ado es.
Figu a 10: Modelo de ejecución en OpenACC.
23
Figu a 11: Modelo de ejecución en OpenMP s OpenACC.
En cuan o al modelo de ejecución de OpenACC, sigue la misma iloso ía que OpenCL o
CUDA; hay una conexión en e el hos y el disposi i o, el lujo de abajo lo lle a el hos y
el de ice se enca ga de ejecu a las egiones pa alelas. El hos se enca ga de la ese a de
memo ia en el disposi i o, del en ío de da os, de la desca ga de código en el acele ado y
del en ío de los a gumen os eque idos en la egión pa alela. También se eca ga á de
man ene una cola con el código que se á ejecu ado en el acele ado pa a ae de uel a los
da os y loa esul ados al hos .
El p og amado es esponsable de conoce los di e sos ni eles de pa alelismo que o ecen
los disposi i os (g ano ino, g ano g ueso, SIMD u ope aciones ec o iales). En caso de
bucles sin dependencias y o almen e pa alelizables, se puede u iliza pa alelización de
g ano g ueso. En cambio en el caso de que exis an dependencias, hay que di idi los bucles
o u iliza pa alelización de g ano ino o secuencial.
Exis en dos di ec i as pa a de ini egiones pa alelas (nomencla u a pa a C):
 Cons ucción ke nel. Median e es a di ec i a indicamos al compilado que
que emos gene a un ke nel que se á en iado al disposi i o. Es amos indicando que
es a egión con iene código pa alelizable y se á el compila el enca gado de
ges iona y decidi cuál es la mane a más óp ima de lle a a cabo la pa alelización.
#p agma acc ke nels [clause [[,] clause]…] new-line
{Región pa alela}

24
 Cons ucción pa allel. Es amos indicando al compilado que es o a egión de
código pa alelo que se á en iado al disposi i o. La di e encia es que con es a
sen encia el p og amado puede añadi clausulas adicionales que pe mi en un mayo
con ol sob e cómo se ap o echa á el ha dwa e disponible pa a lle a a cabo la
pa alelización.
#p agma acc pa allel [clause [[,] clause]…] new-line
{Región pa alela}
Es e con ol sob e el pa alelismo que pe mi e OpenACC median e las clausulas an es
mencionadas iene dado po los concep os de gangs, wo ke s y ec o . Es os concep os
pueden a ia dependiendo del compilado y de la a qui ec u a. Es os concep os,
compa adoss con la a qui ec u a CUDA, se mues an en la abla 2. Usando el compilado
PGI
17
se ía equi alen e a deci que un ec o es equi alen e a un CUDA h ead; y un
wo ke a un wa p de CUDA. Sin emba go, en el compilado de CAPS
18
, es a simili ud
se ía jus o al con a io. Dependiendo del compilado , un gang se ía un conjun o de wo ke s
o ec o s. Aplicando es os concep os a los ni eles de pa alelismo de los disposi i os
an e io men e mencionados, el pa alelismo de g ano g ueso es a ni el de gang, pudiendo
se ejecu ados N gangs en el disposi i o indicándose median e la cláusula adicional
num_gangs de la cons ucción pa allel. Siguiendo la de inición de wo ke s y ec o s de
CAPS, el pa alelismo de g ano ino es a ni el de wo ke s y el pa alelismo a ni el de
ope aciones ec o iales y SIMD de un wo ke es a ni el de ec o s. Pa a ajus a el núme o
de wo ke s en el disposi i o se u iliza la cláusula num_wo ke s.
CUDA
OpenACC
hos
hos
h ead
ec o
block
gang
wa p
wo ke
de ice
de ice
Tabla 2: Equi alencia de concep os CUDA y OpenACC según la de inición del compilado PGI.
Al ejecu a se código en el de ice se lanzan uno o más gangs compues os de uno o más
wo ke s, que a su ez pueden es a compues os po una o más u as ec o iales.
17
Compilado PGI: h p://www.pg oup.com/ esou ces/accel.h m
18
Compilado CAPS: h p://www.caps-en ep ise.com/p oduc s/caps-compile s
25
Figu a 12: Relación en e gang, wo ke y ec o de OpenACC según el compilado PGI.
La cons ucción loop se coloca an es de un bucle o un conjun o de bucles anidados. Indica
al compilado que enemos un bucle que que emos manda a la GPU o al disposi i o
acele ado que es emos usando. Dispone de dis in as cláusulas que indican como se a a á
es e bucle en el disposi i o. La cláusula independen indica que no exis en dependencias en
el bucle y que po lo an o puede se pa alelizado; po el con a io la cláusula seq, indica
que el bucle se á ejecu ado de o ma secuencial den o del acele ado , no malmen e po que
con iene algún ipo de dependencia de da os. Podemos usa la cláusula collapse(n) pa a
indica al compilado que puede pa aleliza los n bucles anidados que suceden a la di ec i a
de OpenACC, es o se ía equi alen e a coloca un acc loop independen an es de cada uno
de los n bucles. También se pueden aplica a la cons ucción loop las clausulas gang,
wo ke y ec o pa a un mayo con ol. Po úl imo, en e las clausulas más habi uales es a
educ ion, que es empleada pa a ealiza una ope ación de educción sob e los da os
esul an es del bucle.
#p agma acc loop [clause [[,] clause]…] new-line
{Bucle o conjun o de bucles anidados}
Respec o al modelo de memo ia en OpenACC, hay que des aca la di e encia en e un
p og ama que es ejecu ado solo en hos o solo en CPU y un p og ama ejecu ado en un
sis ema he e ogéneo hos y de ice. En los sis emas con acele ado es gene almen e se
dispone de memo ias sepa adas, po un lado la memo ia accesible desde el hos y po o o
lado la memo ia del disposi i o que es independien e. No pueden lee ni esc ibi
di ec amen e la una en la o a, po lo que son necesa ias ans e encias de da os en e el hos
y el de ice. No malmen e se ealizan po DMA, siendo es e p oceso el que p o oca el
mayo cuello de bo ella en la aplicación. Po es o hay que es udia con de enimien o que
da os son necesa ios ans e i y en qué momen o pa a minimiza el núme o de
ans e encias, ya que un núme o ele ado de es as pod ía hace que no uese en able la
pa alelización.
26
Median e la cons ucción da a, de inimos una egión (ence ada en e co che es) donde los
da os se án isibles po la GPU. Es a cons ucción ambién dispone de a ias cláusulas que
modi ica án el a amien o de los da os. Median e la cláusula copy(da os), indicamos que
los da os se án en iados a la GPU a la en ada de la egión delimi ada po la di ec i a da a
y de uel os al hos al inal de la egión, en el cie e de los co che es. Es o implica dos
ans e encias en e el hos y el de ice, con la co espondien e la encia que implican es e
ipo de ansacciones. Pa a e i a es o, cuando sea posible, exis en las clausulas copyin y
copyou pa a en ia da os del hos al disposi i o y la ope ación in e sa espec i amen e.
También disponemos de la cláusula c ea e pa a indica que que emos ese a memo ia en
la GPU, la cual es a á accesible mien as du e la egión delimi ada po la di ec i a da a y se
libe a á a la inalización de la misma. Se ía simila a hace un cudamalloc. Con la cláusula
p esen le indicamos al compilado que los da os ya es án p esen es en la GPU y no
necesi an se anspo ados.
#p agma acc da a [clause [[,] clause]…] new-line
{Región codigo}
A con inuación, un pequeño agmen o de código en C (algo i mo 1) que ealiza una
mul iplicación de ma ices y mues a algunas de las cons ucciones explicadas du an e es e
capí ulo.
Algo i mo 1:
#p agma acc ke nels c ea e ( a[0:size] [0:size], b[0:size] [0:size] )
copyou ( c[0:size] [0:size] )
{ // Inicialización de ma ices.
#p agma acc loop independen
o (i = 0; i < size; i++)
{ #p agma acc loop independen
o (j = 0; j < size; j++) {
a[i][j] = ( loa )i + j;
b[i][j] = ( loa )i - j;
c[i][j] = 0.0 ;
}
}
// Calcula la mul iplicación de ma ices
#p agma acc loop independen
o (i = 0; i < size; ++i)
{ #p agma acc loop independen
o (j = 0; j < size; ++j) {
#p agma acc loop seq
o (k = 0; k < size; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
}
27
Capí ulo 3. Me odología y esul ados
En es e capí ulo, explica emos la implemen ación ealizada sob e el algo i mo de lujo
óp ico elegido, el Lucas&Kanade, cuyos mo i os ue on expues os con an e io idad.
P incipalmen e podemos des aca el buen comp omiso en e e iciencia y p ecisión, además
de, cómo se explicó en el apa ado 1.4, se un algo i mo que ha sido obje o de nume osos
es udios ob eniendo buenos esul ados y quedando demos ado así el po qué de su elección.
Mos a emos los de alles más ele an es de la implemen ación lle ada a cabo y
ejempli ica emos la elación en e el modelo compu acional y el modelo ma emá ico
de allado en el apa ado 1.3 de es a memo ia. Pos e io men e se explica án las
ans o maciones inc emen ales necesa ias en el código pa a ob ene un mejo endimien o
en las dos implemen aciones lle adas a cabo pa a su acele ación po medio de OpenMP y
OpenACC.
Po úl imo, se mos a án los esul ados ob enidos en cuan o a p ecisión y una compa a i a
de endimien o en e las es e siones (la se ie en la CPU, la pa alela en un p ocesado
mul ico e y la pa alela en el acele ado GPU de NVIDIA).
3.1 Implemen ación de L&K.
La implemen ación ha sido lle ada a cabo en el lenguaje de p og amación C, po se jun o
a Fo an, los lenguajes sopo ados en los modelos de p og amación de di ec i as (OpenMP
y OpenACC). El algo i mo end á como en ada una secuencia de imágenes y se aplica á la
écnica de Lucas&Kanade pa a es ima el lujo óp ico en e cada pa de ames consecu i os
de la secuencia.
En el algo i mo 2 se de alla un pseudocódigo con el esquema gene al del mé odo. Un o
que eco a odas los ames de la secuencia y que encie e los siguien es elemen os, dos
pun e os (uno que apun e al ame ac ual y o o al suceso ) y el conjun o de llamadas a las
unciones necesa ias (las cuales calculan los da os in e medios y el sis ema de ecuaciones
inal).
En la p ime a ase del algo i mo se calcula án las de i adas espaciales pa a los ejes x e y, a
con inuación se calcula án las de i adas empo ales y po úl imo se calcula án los
suma o ios de los p oduc os de las de i adas, necesa ios pa a o ma las ma ices necesa ias
pa a esol e el sis ema (ecuaciones de inidas en el pun o 1.3).
34
En el algo i mo 8 de allamos la decla ación de la egión de da os y la especi icación de las
ans e encias. También se mues a el con enido de la egión, que son las llamadas que
calculan el Lucas&Kanade pa a cada pa eja de ames consecu i os de la secuencia. Nó ese
que han sido ob iadas las unciones que calculan los cuad ados o los p oduc os en e
de i adas.
La segunda op imización ele an e sob e la implemen ación de OpenMP a ec a a las
con oluciones del cálculo de de i adas y al suma o io de ecindades. Al igual que en
OpenMP, se ealizó un isionado de bucles pa a e i a sal os condicionales. Se ha podido
comp oba que es a ác ica en OpenACC no es e icien e; es o es debido a que pa a cada
bucle isionado que se quie e pa aleliza se debe gene a un Ke nel de OpenACC. Los
bucles que ealizaban el cómpu o de los bo des de las imágenes con enían muy poca ca ga
compu acional en compa ación con los que calculan el in e io , de mane a que se es án
gene ando ke nels que p ác icamen e no an a ene abajo. En consecuencia, es menos
e icien e gene a ke nels sin ca ga de abajo que ene uno solo, aunque con enga sal os
condicionales.
Algo i mo 9:
#p agma acc ke nels p esen ( ameAc [0:NF*NC], il e X[0:FS], Ix[0:NF*NC])
{
#p agma acc loop independen
o (i=0; i<NF; i++){
#p agma acc loop independen
o (j=0; j<NC; j++){
Ix[i*NC+j] = 0.0;
i (j<FS/2) {
#p agma acc loop seq
o (k=(FS/2)-j; k<FS; k++)
Ix[i*NC+j] += ameAc [i*NC+( j+k-FS/2)] * il e X [k];
} else i (j>=NC- FS/2){
#p agma acc loop seq
o (k=0; k< FS/2+(NC-j); k++)
Ix[i*NC+j] += ameAc [i*NC+( j+k-FS/2)] * il e X [k];
} else {
#p agma acc loop seq
o (k=0; k<FS; k++)
Ix[i*NC+j] += ameAc [i*NC+( j+k-FS/2] * il e X [k];
}
}
}
}

35
En el algo i mo 9 se mues a la con olución del cálculo de la de i ada en el eje x con la
op imización del usionado de bucles, ol iendo a ealiza se odo el cómpu o en una
cons ucción de bucles o anidados con sal os condicionales pa a a a el il ado en los
bo des. Además de es o, se mues a un ejemplo de de inición de una cons ucción ke nel y
de cómo se indica median e la cláusula p esen que los da os solici ados ya se encuen an en
la GPU. Se indica al compilado que los bucles son o almen e pa alelizables con la
di ec i a #p agma acc loop independen , de igual mane a, se indica que un bucle se debe
ejecu a de o ma secuencial debido a alguna dependencia de da os en su in e io con la
di ec i a #p agma acc loop seq.
Po úl imo, cabe menciona dos ans o maciones más que ienen dadas po es icciones
del compilado usado pa a OpenACC. La p ime a es ealiza un inlining o inline expansion
(coloca el código en luga de la llamada a la unción) de unciones den o de los ke nel, ya
que el compilado no sopo a llamadas a unciones den o de es as cons ucciones. Es a
modi icación se lle ó a cabo en el ke nel que esuel e el sis ema de ecuaciones de LK,
haciendo inlining de la unción que calcula la in e sa de una ma iz y la unción que ealiza
la mul iplicación de las ma ices que esuel en el lujo óp ico. La segunda ans o mación
ue, en el mismo ke nel que esuel e el sis ema, decla a los elemen os de la ma iz C 2x2 y
el ec o B de longi ud 2 como escala es en ez de en o ma ma icial ya que el compilado
da p oblemas a la ho a de decla a ma ices y ec o es es á icos.
36
3.2 Resul ados ob enidos. Rendimien o espec o al modelo o iginal en C.
En es e apa ado p esen a emos los esul ados que se han ob enido a pa i del conjun o de
p uebas ealizadas sob e la implemen ación lineal y sob e las implemen aciones pa alelas
(po medio de OpenMP y OpenACC) del algo i mo de lujo óp ico Lucas&Kanade. En
p ime luga mos a emos un es udio sob e la p ecisión del algo i mo u ilizando dis in as
con igu aciones de il os espaciales y a iando el amaño de en ana en los suma o ios de
ecindades de pixeles. En una segunda ase mos a emos los esul ados ob enidos en cuan o
a endimien o y en cuan o a la mejo a ob enida en los modelos pa alelos sob e el modelo
lineal.
3.2.1 En o no de abajo.
Pa a la ealización de p uebas sob e la implemen ación desa ollada en OpenMP se ha
u ilizado un sis ema con dos p ocesado In el Xeon E5530
19
de 4 co es cada uno, a
2.40GHz, con 8MB de caché y ecnología Hype h eading; ealizando las p uebas en
con igu aciones de 2, 4, 8 y 16 co es y haciendo uso del compilado gcc en su e sión 4.7.2.
En cuan o a la implemen ación ealizada de OpenACC, el acele ado usado ha sido una
GPU Tesla K20c de NVIDIA
20
, la cual cuen a con un p ocesado g á ico Keple GK110,
con 2496 CUDA co es, 5GB GDDR5 de memo ia y un endimien o en pun o lo an e de
3.52T lops; y haciendo uso del compilado pa a OpenACC pgcc de PGI, en su e sión 14.6.
3.2.2 Resul ados de p ecisión.
A con inuación mos a emos los esul ados ob enidos en cuan o a p ecisión pa a la
implemen ación en C del algo i mo Lucas&Kanade. Pa a medi el e o se ha u ilizado la
mé ica de Ba on (de allada en el pun o 1.1.2) sob e los es ímulos sin é icos “Di e ging
T ee” y “T ansla ing T ee” (apa ado 1.1.1).
Realizamos el es udio de p ecisión usando dis in as con igu aciones, a iando el amaño de
los il os espaciales pa a los amaños 3, 5, 7 y 9 y p obando cada uno de es os il os sob e
una en ana de amaños 5, 9, 15, 19, 26 y 30 pa a ealiza los suma o ios de la ecindad de
cada pixel. Además, es udia emos la p ecisión pa a di e en es densidades de cálculo, es
deci , medi emos el e o pa a la imagen comple a (densidad 100%), medi emos el e o
pa a la imagen eliminando el amaño del il o espacial en los bo des (po lo que pa a una
esolución de 150x150 con un il o de amaño 5, end emos una densidad del 93% según el
siguien e cálculo (150-5)^2/150^2=0.93 ) y po úl imo medi emos el e o eliminando el
amaño de la en ana en los bo des (po ejemplo pa a una esolución de 150x150 con un
amaño de en ana de 15, la densidad ob enida es del 81%).
19
h p://a k.in el.com/es-es/p oduc s/37103/In el-Xeon-P ocesso -E5530-8M-Cache-2_40-GHz-5_86-
GTs-In el-QPI
20
h p://www.n idia.com/objec / esla-se e s.h ml
37
El mo i o pa a ealiza las mediciones en dis in as densidades es la al a de in o mación en
los bo des de las imágenes pa a ealiza la es imación de lujo óp ico, lo que da á luga en
es as egiones a las es imaciones más imp ecisas. Cuan o más nos alejemos de es as zonas
hacia el in e io de la imagen pa a medi el e o global, ob end emos esul ados más
p ecisos pe o como con apa ida se comp ome e la densidad. Po odo ello busca emos en
es e es udio un equilib io en e p ecisión y densidad. A pa i de aho a habla emos de e o
sin co ección (pa a e e i nos a una densidad del 100%, po lo que conside amos odos los
bo des), e o con co ección en il o (eliminamos el amaño de il o de los bo des de la
imagen) y e o con co ección en bloque (donde eliminamos el amaño de en ana en los
bo des de la imagen).
El e o calculado se ob iene como media del e o po pixel en e el lujo óp ico es imado y
el eal dado po el g ound u h de la secuencia. Dado que el e o se ob iene po pixel, se
calcula un e o medio pa a oda la imagen, ob eniendo pos e io men e una media de los
e o es de es imación ob enidos pa a cada ame de la secuencia comple a. Po lo an o, los
esul ados mos ados a con inuación son un e o p omedio de la es imación de mo imien o
en oda la secuencia de imágenes.
Figu a 13: G á ica del e o de Ba on pa a Di e gingT ee con co ección en il o y sin co ección.
0,000
0,050
0,100
0,150
0,200
0,250
0,300
0,350
0,400
0,450
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
E o Ba on sin co ección s co ección en il o
Di e ging T ee esolución 150x150 40 ames
E o co ección en il o Inc emen o
38
En la igu a 13 se mues a un g á ico donde se ap ecia el e o sin co ección (ba a
comple a) como la suma del e o con co ección en il o (ba a na anja) más el inc emen o
del e o sin co ección (ba a g is) en o ma o acumulado, (e o según mé ica de Ba on
en adianes), pa a la secuencia Di e gingT ee en dis in as con igu aciones ( amaños de
en ana y il o).
Figu a 14: G á ica del e o de Ba on pa a Di e gingT ee con co ección en bloque y sin co ección.
En la igu a 14 enemos un g á ico simila al an e io pe o la di e encia adica en que se
mues a el e o con co ección en bloque (ba a azul) más el inc emen o del e o sin
co ección (ba a g is) ep esen ando inalmen e el e o sin co ección (ba a comple a) en
o ma o acumulado.
Analizando las dos g a icas de las igu as 13 y 14 podemos ex ae la siguien e
in o mación:
0,000
0,050
0,100
0,150
0,200
0,250
0,300
0,350
0,400
0,450
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
E o Ba on sin co ección s co ección en bloque
Di e ging T ee esolución 150x150 40 ames
E o co ección en bloque Inc emen o
39
Se ap ecia en el caso del e o sin co ección, que al disminui el amaño de en ana el e o
se a educiendo paula inamen e encon ando su ope en la en ana de amaño 15 ya que a
pa i de és a no sigue mejo ando. Respec o al compo amien o de los il os el de amaño 3
mues a los peo es esul ados, seguido del il o 9, el il o 7 y po úl imo el il o 5 que es el
que mejo es es imaciones p oduce.
Pa a el caso en que se calcula el e o con co ección en il o (g a ico na anja) iene un
compo amien o simila en cuando a con igu ación, el aumen a el amaño de bloque educe
el e o llegando a su lími e en el bloque 15 y en cuan o a il os la peo es imación la
ealiza el il o 3 seguido de los il os 5, 7 y 9 siendo es e úl imo el más p eciso. Además
como e a de espe a educe el e o en odos los casos espec o al es udio de e o sin
co ección.
En el e o po co ección en bloque (g a ico azul), se ob ienen los mejo es esul ados pe o
a cos a de mayo es densidades. En cuan o en su compo amien o, espec o a las di e en es
con igu aciones obse amos como el aumen a el amaño de bloque educe el e o , yendo
es a educción de más a menos con endencia a desapa ece pa a bloques supe io es a los
mos ados. Respec o a los il os siguen el mismo compo amien o que en el es udio de
e o sin co ección, siendo el il o 3 el más imp eciso seguido del 9, 7 y 5 siendo es e
úl imo el mejo .
Po úl imo se mues a en la abla 3 los mejo es esul ados pa a cada es udio del e o de
Ba on jun o con sus densidades, concluyendo que la co ección po il o es la más
adecuada po se la que mejo comp omiso mues a en e e o y densidad de pun o.
Tipo
Bloque
Fil o
E o angula
E o adianes
Densidad
Sin co ección
15
5
14.46
0.25239
100%
Co ección po il o
15
9
11.67
0.20375
89%
Co ección po bloque
30
5
5.70
0.09945
64%
Tabla 3: E o mé ica de Ba on en Di e gingT ee pa a dis in as co ecciones jun o con sus densidades.
A con inuación mos amos los esul ados del mismo es udio pa a la secuencia T ansla ing
T ee, ambién en esolución 150x150 con 40 ames. En la igu a 15 se mues a el e o sin
co ección de o ma acumulada (e o con co ección en il o –na anja- más inc emen o del
e o sin co ección –g is-) y en la igu a 16 lo mismo pe o subs i uyendo el e o con
co ección en il o po el e o con co ección en bloque (azul).

40
Figu a 15: G á ica del e o de Ba on pa a T ansla ingT ee con co ección en il o y sin co ección.
Figu a 16: G á ica del e o de Ba on pa a T ansla ingT ee con co ección en bloque y sin co ección.
0,000
0,100
0,200
0,300
0,400
0,500
0,600
0,700
0,800
0,900
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
E o Ba on sin co ección s co ección en il o
T ansla ing T ee esolución 150x150 40 ames
E o co ección en il o Inc emen o
0,000
0,100
0,200
0,300
0,400
0,500
0,600
0,700
0,800
0,900
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
E o Ba on sin co ección s co ección en bloque
T ansla ing T ee esolución 150x150 40 ames
E o co ección en bloque Inc emen o
41
De es as dos g a icas ( igu as 15 y 16), en cuan o al compo amien o de las dis in as
con igu aciones (elección de il o y amaño de en ana) obse amos que siguen el mismo
pa ón en los es es udios de co ección (sin co ección, co ección en il o –g a ico
na anja- y co ección en bloque –g a ico azul-) de o ma que el aumen o en el amaño de
bloque disminuye el e o , siendo es a educción meno a alo es mayo es de bloque con
endencia a desapa ece en alo es muy g andes. Respec o al compo amien o de los il os
ambién siguen el mismo pa ón en odos los es udios, siendo el il o 3 el más ine icien e
seguido del il o 9 y il o 7, mos ándose en odos los casos el il o 5 como el más
p eciso.
Tipo
Bloque
Fil o
E o angula
E o adianes
Densidad
Sin co ección
30
5
26.21
0.45747
100%
Co ección po il o
30
5
25.11
0.43829
93%
Co ección po bloque
30
5
15.86
0.27683
64%
Tabla 4: E o mé ica de Ba on en T ansla ingT ee pa a dis in as co ecciones jun o con sus densidades.
La abla 4 mues a como en el es udio an e io los meno es e o es de Ba on pa a cada ipo
de co ección. Vol iendo a mos a se el e o po co ección en il o el que mues a un
mayo comp omiso en e e o y densidad de pun o.
Po úl imo, se ha ob enido un p omedio o al de los e o es ob enidos en las secuencias
Di e ging T ee y T ansla ing T ee. Los esul ados se mues an g á icamen e en las igu as
17 y 18, mos ando la p ime a el e o p omedio sin co ección de los dos es ímulos en un
g á ico acumulado ( o mado po el e o con co ección po il o –na anja- más el
inc emen o del e o sin co ección -g is-); y mos ando la segunda el p omedio en e los
dos es ímulos del e o sin co ección ( o mado po el e o con co ección po bloque -
azul- más el inc emen o del e o sin co ección –g is-).
Obse ando los g á icos de las igu as 17 y 18 podemos ap ecia que en gene al la
con igu ación o mada po el bloque 15 y el il o5 mues a un buen compo amien o.
Co ige el e o an o si se hace una co ección po il o como una co ección po bloque,
man eniendo un buen comp omiso con la densidad que se encuen a en 93% y 81%
espec i amen e. Conside amos po an o es a con igu ación la más ap opiada, ya que a
pa i de es e amaño de bloque aunque se mejo e la p ecisión se e comp ome ida en
exceso la densidad.
42
Figu a 17: G á ica del p omedio del e o de Ba on con co ección en il o y sin co ección en e
T ansla ingT ee y Di e gingT ee.
Figu a 18: G á ica del p omedio del e o de Ba on con co ección en bloque y sin co ección en e
T ansla ingT ee y Di e gingT ee.
0,000
0,100
0,200
0,300
0,400
0,500
0,600
0,700
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
P omedio del e o de Ba on sin co ección s co ección
po il o en e Di e gingT ee y Tansla ingT ee
E o co ección en il o Inc emen o
0,000
0,100
0,200
0,300
0,400
0,500
0,600
0,700
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Fil e 3
Fil e 5
Fil e 7
Fil e 9
Block 5 Block 9 Block 15 Block 19 Block 26 Block 30
E o adianes Ba on
P omedio del e o de Ba on sin co eción s co ección
po bloque en e Di e gingT ee y Tansla ingT ee
E o co ección en bloque Inc emen o
43
En las igu as 19 y 20 podemos obse a una ep esen ación g á ica po medio de ec o es
de la es imación de lujo óp ico ealizada po nues o algo i mo y la ep esen ación
equi alen e del lujo óp ico eal (g ound u h) pa a los es ímulos Di e ging T ee y
T ansla ing T ee espec i amen e.
Figu a 19: Flujo Óp ico es imado (izquie da) y eal (de echa) de Di e ging T ee.
Figu a 20: Flujo Óp ico es imado (izquie da) y eal (de echa) de T ansla ing T ee.
Se puede obse a g á icamen e lo comen ado al p incipio de es e pun o, sob e como los
e o es más conside ables se encuen an en los bo des de la secuencia debido a la al a de
in o mación en es as zonas pa a es ima el mo imien o. Algunas implemen aciones oman
como con enio ealiza una cons ucción simé ica en los bo des, eplicando el con enido de
la imagen pa a que en los il os y en las con oluciones se disponga de esa in o mación
adicional. En cualquie caso en es e abajo se ha ealizado el es udio de e o a ando los
bo des sin co ección, con co ección en il os y con co ección en bloque o en ana.
50
Después de es e abajo c eemos que OpenACC es una opción muy in e esan e a ene en
cuen a ya que ha dado muy buenos esul ados, siendo su ap endizaje asequible y pudiendo
mig a un código en C de mane a cómoda sin ene que ealiza demasiadas modi icaciones.
Quizás lo más cos oso haya sido consegui ene una implemen ación óp ima en C, pe o una
ez conseguida, la mig ación no esul ó di icul osa.
Pa a inaliza , podemos deci que OpenACC o ece buenos esul ados, iendo el es udio
ealizado en el capí ulo 3, donde ob enemos “speedups” de has a 40x cuando en OpenMP
lo máximo que hemos log ado es á ce ca de 10x. En cuan o al endimien o en ps,
OpenACC ha sido la única implemen ación que ha log ado esul ados en iempo eal en
esoluciones de has a 1200x1200 y quedándose muy ce ca en esolución FullHD
(1920x1080). Puede que en implemen aciones ealizadas en CUDA los esul ados sean más
e icien es, pe o si enemos en cuen a la cu a de ap endizaje, conside amos que es una se ia
opción a ene en cuen a.
4.2 Posibles abajos u u os.
El es udio ealizado sob e el algo i mo Lucas&Kanade y las múl iples aplicaciones de la
es imación de mo imien o pe mi en pensa en con inua a ias líneas de in es igación sob e
él, como po ejemplo a iaciones de es e modelo que p opo cionen más in o mación sob e
el lujo óp ico o ealicen es imaciones más p ecisas. En e las líneas u u as que pod ían
plan ea se debe ían ene se en cuen a las siguien es ideas:
Un posible abajo u u o se ía ealiza una implemen ación sob e el modelo pi amidal del
algo i mo Lucas&Kanade. En es e ipo de implemen ación, el lujo óp ico es es imado po
p ime a ez sob e la imagen de meno esolución, luego, dicha imagen a c eciendo en un
ac o de 2 has a llega a su amaño de adquisición, es deci , el de mayo esolución posible.
Figu a 27: Fo ma pi amidal del algo i mo de Lucas&Kanade.

51
El modelo pi amidal es ima p ime o el lujo óp ico sob e el ni el 0 (Figu a 27) en e las
imágenes I y J, encon ando el desplazamien o d0, de un pun o especí ico, sob e una imagen
de baja esolución y una en ana pequeña. Luego ubica en la imagen I del ni el 1 el pun o
encon ado an e io men e y es ima de nue o el lujo óp ico en e I y J pa a el ni el 1,
encon ando el desplazamien o d1 sob e la misma en ana. Es os pasos se epi en has a
alcanza el ni el n, ob eniendo el desplazamien o o al del pun o.
O a ía de in es igación pod ía se cen a se en la es imación del mo imien o en es é eo
median e el Lucas&Kanade. El p oblema que a a de esol e una implemen ación en
es é eo es el de de e mina la es uc u a idimensional de una escena eniendo dos o más
imágenes ob enidas desde a ias pe spec i as. Visión en es é eo, a a de usa dos cáma as y
ob ene dos imágenes sob e un mismo pun o en una escena conc e a, como se mues a en la
igu a 28. Lo que que emos consegui es ene in o mación sob e la p o undidad de los
obje os de la imagen y no solo sob e el mo imien o en 2D (planos ho izon al y e ical)
como enemos con el modelo básico de Lucas&Kanade. Pa a lle a lo a cabo, hab ía que
ejecu a en pa alelo el algo i mo desde dos disposi i os, cada uno oma ía la imagen desde
un pun o, po lo que pod ía calcula se la dis ancia y la p o undidad.
Figu a 28: Ob ención de una imagen idimensional del “Scene Poin ” a pa i de dos imágenes omadas
con dos cáma as.
O a posible aplicación se ía lle a es os algo i mos a pla a o mas mó iles, ya que los
sma phones y able s de úl ima gene ación, que es án en pleno auge, con ienen sis emas
pa a cap u a ideo e imágenes. Además, en la ac ualidad la endencia ambién es que
cuen en con disposi i os g á icos como los NVIDIA Teg a
21
, po lo que se con ie en en
buenos candida os pa a ab i un campo de es udio sob e es as pla a o mas.
21
h p://www.n idia.com/objec / eg a.h ml
52
53
Chap e 4. Conclusions and u u e wo k
4.1 Summa y and conclusions.
The s a emen s in his wo k cla i y, i s ly, he impo ance o he p oblems on mo ion
es ima ion in compu e ision and in digi al ideo p ocessing. We ha e e i ied ha his is a
ield wi h many applica ions in eal wo ld and o g ea in e es o esea che s, a e seeing
he g ea numbe o p ojec s and s udies we ha e ound while we we e documen ing o his
memo y.
Mo eo e , we ha e seen in e es in making mo e e icien implemen a ions o algo i hms
ha calcula e he op ical low, since he ime equi ed o sol e such p oblems inc eases wi h
he quali y and esolu ion o he inpu images. The end is o ha e mo e and mo e a highe
esolu ion in ideos and images, as we can app ecia e in he new esolu ion 4K which
quad uples he esolu ion o he cu en gene a ion FullHD.
In Chap e 1, models o op ical low algo i hms we e classi ied, and i was also emphasized
ha he main ac o o deciding among hem is o ind a balance be ween accu acy and
e iciency. I was concluded ha Lucas&Kanade algo i hm om g adien -based amily was
a good candida e o ou pu poses.
Because o he need on achie ing mo e e iciency in implemen a ions and due o he
in insic pa allelism ound in he images (which can be exploi ed on accele a o s) he nex
s ep was o lea n mo e abou hem and conside he cu en ends. We ha e checked how,
ini ially, he g aphic p ocesso s only had he pu pose o p ocessing g aphics, bu his high
compu ing powe made hem e ol e in o a mo e gene al pu pose, being able o exploi i s
pe o mance in scien i ic ields and pa allel compu ing. Fu he mo e, he cu en end is
ha accele a o s a e no jus g aphic p ocesso s, bu also he e ogeneous sys ems as APUs
om AMD o In el Xeon Phi om In el.
We ha e no iced ha one o he main obs acles so ha he use o accele a o s has wide
accep ance by unskilled p og amme s, is he complexi y o ha ing o know mo e speci ic
a chi ec u es like CUDA o OpenCL, ha ha e a long lea ning cu e. Fo his eason he
models o p og amming by di ec i es me hod as he s anda d OpenMP and ecen ly a
hope ul s anda d OpenACC, designed o exploi accele a o s independen ly o he
a chi ec u e.
54
A e doing his wo k, we belie e ha OpenACC is a e y in e es ing op ion o conside ,
since i has p oduced good esul s, being a o dable i s lea ning and being able o mig a e C
code in a com o able way wi hou making oo many modi ica ions. Pe haps, he mos
di icul pa has been o ha e an op imal implemen a ion on C, bu once achie ed,
mig a ion was no di icul .
Finally, we can es ablished ha OpenACC p o ides good esul s, seeing he s udy made in
Chap e 3, whe e we ob ained “speedups” o up o 40x when in OpenMP he maximum we
achie ed is close o 10x. In e ms o pe o mance in ps, OpenACC has been he only
implemen a ion ha has achie ed esul s in eal ime in esolu ions o up o 1200x1200, and
being so close in FullHD esolu ion (1920x1080). Maybe in implemen a ions de eloped in
CUDA, he esul s a e mo e e icien , bu i we conside he lea ning cu e, we come o he
conclusion ha i is a se ious op ion o conside .
4.2. Possible u u e wo k.
The s udy on Lucas&Kanade algo i hm and mul iple applica ions o mo ion es ima ion
allow us o hink abou ca ying ou se e al lines o in es iga ion on i , such as a ia ions o
his model ha p o ide mo e in o ma ion on op ical low o can pe o m mo e accu a e
es ima ions. Among he u u e lines ha could be conside ed he ollowing ideas should be
aken in o accoun :
A possible u u e wo k would be o pe o m an implemen a ion o he py amid model o
Lucas&Kanade algo i hm. In his ype o implemen a ion, op ical low is es ima ed o he
i s ime on he lowe esolu ion image, hen, he image g ows by a ac o o 2 o each i s
acquisi ion size, ha is, he highes esolu ion possible.
Figu e 27: Py amid o m o he Lucas&Kanade algo i hm.
55
The py amid model es ima es i s he op ical low on he le el 0 (Figu e 27) be ween he
images I and J, inding he d0 displacemen , on a speci ic poin , in a low- esolu ion image
and a small window. Then i places in he image I on he le el 1, he poin p e iously ound
and es ima es again he op ical low be ween I and J o he le el 1, inding he
displacemen d1 in he same window. These s eps a e epea ed un il he le el n will be
eached, ob aining he o al displacemen o he poin .
Ano he line o esea ch could be o ocus on he mo ion es ima ion in s e eo ough
Lucas&Kanade. The p oblem ha ies o sol e an implemen a ion in s e eo is o de e mine
he h ee dimensional s uc u e o a scene wi h wo o mo e images aken om di e en
pe spec i es. S e eo ision ies o use wo came as and o ob ain wo images on he same
poin in a pa icula scene, as i is shown in Figu e 28. Wha we wan o achie e is ha ing
he in o ma ion abou he dep h o he objec s in he image and no only abou he 2D
mo emen (ho izon al and e ical planes) as we ha e wi h he basic model o
Lucas&Kanade. To ca y i ou , he algo i hm should be un in pa allel om bo h de ices,
each one o hem would ake he image om a di e en poin , which could compu e he
dis ance and dep h.
Figu e 28: Ge ing a h ee-dimensional image o he “Scene Poin ” om wo images aken wi h wo
came as.
Ano he possible applica ion would be expo hese algo i hms o mobile pla o ms, as la es
gene a ion sma phones able s, ha a e booming, con ain sys ems o cap u e ideo and
images. Fu he mo e, nowadays, he endency is o hem o ha e g aphic de ices as
NVIDIA Teg a, so ha hey become good candida es o open a ield s udy on hese
pla o ms.

56
57
Apo ación indi idual al p oyec o
Nelson Ma ín Viei es.
La apo ación al p oyec o ha sido conjun a, no se ha hecho una di e enciación cla a de
a eas con excepción de la pa e de documen ación, en la cual cada componen e del g upo
se ha especializado más en un á ea, pudiendose deci que mi apo ación indi idual es á
p esen e en odos los ámbi os del p oyec o. A con inuación, se desc ibe dicha apo ación
de alladamen e, que a g andes asgos se puede di ide en dos pa es; documen ación y
expe imen ación, las cuales a su ez con ienen di e en es e apas.
Podemos di e encia dos e apas en el p oceso de documen ación, la inicial ue si ua se en el
con ex o de la es imación de mo imien o, el lujo óp ico y el algo i mo a u iliza . La
segunda e apa se cen a en el es udio de acele ado es, p og amación pa alela y
me odologías de p og amación po el mé odo de di ec i as. En cuan o a la pa e de
expe imen ación podemos di e encia cua o subapa ados. Los dos p ime os se lle a on a
cabo de o ma pa alela ya que e an complemen a ios, siendo es os el desa ollo en C del
algo i mo y la oma de con ac o con Oc a e
22
pa a el a amien o de imágenes y
isualización de esul ados; llegando en úl imo luga a las e apas de pa alelización po
medio de OpenMP y OpenACC con sus espec i os es udios y oma de esul ados.
La p ime a pa e del p oyec o ue documen a se sob e el lujo óp ico, los ipos de
algo i mos de es imación de mo imien o y sus espec i as amilias, p o undiza en los
modelos de g adien e y en el algo i mo Lucas&Kanade ya que ue el mé odo elegido pa a
implemen a en el p oyec o. En es a p ime a e apa ambién ue necesa io documen a se
sob e los es ímulos sin é icos que se iban a u iliza , las mé icas de e o disponibles pa a
medi la p ecisión de la es imación y ealiza un es ado del a e de implemen aciones
ealizadas sob e acele ado es g á icos del algo i mo elegido (Lucas&Kanade). También,
una pa e del iempo ue des inada a conoce Oc a e y sus comandos básicos pa a la
manipulación de imágenes y iche os, pa a pode ep esen a g á icamen e los esul ados.
G an pa e de oda es a documen ación inicial nos ue acili ada po nues os u o es del
p oyec o, ademas, o a uen e de consul a en es e comienzo ino dada po la esis doc o al
de Fe mín Ayuso [17].
En es a p ime a e apa del p oyec o, una ez que ya se habían adqui ido los conocimien os
esenciales pa a empeza a abaja sob e el algo i mo, se comenzó con los dos p ime os
subapa ados de la ase de expe imen ación: la implemen ación en lenguaje C del algo i mo
de Lucas&Kanade y la expe imen ación en Oc a e pa a pode isualiza g á icamen e los
esul ados.
22
h p://www.gnu.o g/so wa e/oc a e/
58
Una ez inalizada una implemen ación básica en C del algo i mo, y habiendo adqui ido los
conocimien os básicos en lo e e en e a la es imación de mo imien o, se pasó a la segunda
ase del p oyec o. Es a ase comenzó con la documen ación sob e el ema de los
acele ado es g á icos y con comp ende el concep o de p og amación pa alela, pa a luego
pasa a p o undiza en los dos modelos de p og amación basados en di ec i as usados en el
p oyec o, OpenMP y OpenACC. Después de es udia los concep os básicos de es os
modelos, con el in de comenza con la mig ación del código o iginal dado que los dos
ienen concep os simila es, se decidió que cada componen e p o undiza a más po sepa ado
en las pa icula idades de cada uno de ellos, cen ándome yo más en el es udio de
OpenACC.
Po úl imo, llegó la pa e de expe imen ación y ecolección de esul ados sob e las
implemen aciones pa alelas y el es udio de p ecisión sob e la implemen ación base de C. En
el es udio de p ecisión se analizó en un p ime momen o como a ec aban las dis in as
con igu aciones (elección de il o y en ana), es udiándose en segundo luga como podían
educi se es os e o es aplicando co ecciones y man eniendo un comp omiso en e e o y
densidad de pun o. Pa a el es udio de endimien o en las implemen aciones pa alelas,
p ime o se ealiza on las op imizaciones pe inen es seguidas de la mig ación a OpenMP; y
en úl imo luga se ealizó el mismo p oceso sob e OpenACC. También se ealiza on
p uebas u ilizando a ios compilado es pa a OpenACC, aunque inalmen e el que mejo
uncionó ue el compilado elegido, el pgcc de PGI. Pa a la ealización del p oyec o hemos
enido a nues a disposición odos los medios y el ha dwa e necesa io en los labo a o ios del
depa amen o de A qui ec u a de Compu ado es y Au omá ica de la acul ad de Físicas.
Una ez que se e minó con la pa e p ác ica y de documen ación del p oyec o, se p ocedió
a la ealización de la p esen e memo ia, donde se ha seguido el siguien e p oceso: ecopila
el con enido, ecupe a la documen ación consul ada du an e el cu so, sin e iza los
esul ados ob enidos en la ase de expe imen ación, y po úl imo, la edacción y pos e io
e isión del documen o.
59
Jo ge Collado Ga cía.
La emá ica del abajo nos ha obligado a abaja jun os desde el comienzo del mismo has a
inal. Únicamen e du an e la pa e de documen ación, nos hemos di idido
especializándonos cada uno más en un á ea dis in a. Podemos di idi el desa ollo del
p oyec o en dos g andes apa ados cla amen e dis in os donde hemos enido que dedica le
iempo a la documen ación y expe imen ación po pa es iguales. Es os dos g andes
apa ados se ían po una pa e el desa ollo del p opio algo i mo Lucas&Kanade en C y el
es udio cen ado en GPUs y p og amación pa alela.
Pa a la p ime a pa e del p oyec o hemos enido que documen a nos sob e el lujo óp ico,
los dis in os modelos de g adien e, ipos de algo i mos ya exis en es pa a la es imación de
mo imien o y, po supues o, el concep o del algo i mo Lucas&Kanade. En es a e apa del
p oyec o, hemos enido que documen a nos ace ca de o os concep os no menos
impo an es pa a el desa ollo del abajo como son los es ímulos sin é icos, su uso y las
mé icas de e o exis en es pa a medi la p ecisión de la es imación del mo imien o.
Des aca ambién que una pa e de nues o iempo dedicado a la documen ación ue pa a
conoce los comandos básicos del Oc a e pa a pode ep esen a g á icamen e los
esul ados de nues o algo i mo. G an pa e de oda es a documen ación inicial nos ue
acili ada po nues os u o es de p oyec o, o a uen e de consul a en es e comienzo ino
dada po la esis doc o al de Fe mín Ayuso [17].
Respec o al p ime apa ado de desa ollo del p oyec o, podemos di idi nues a
expe imen ación en dos e apas dis in as:
 Implemen ación del algo i mo p opues o, Lukas&Kanade, en C.
 Expe imen ación, en es a e apa p ocedimos a p oba el algo i mo con di e en es
es ímulos sin é icos pa a es udia y hace una compa a i a de esul ados ob enidos.
Una ez e minado el desa ollo y la expe imen ación con el algo i mo, pasamos a la
segunda pa e de nues o p oyec o. Comenzamos es e apa ado es udiando los concep os
básicos de p og amación pa alela y los dos es ánda es de p og amación basados en
di ec i as que hemos usado a usa pa a nues o abajo de in de g ado (OpenMP y
OpenACC). Pos e io men e nos dedicamos a mig a el código o iginal del algo i mo que
ob u imos en la p ime a e apa de nues o p oyec o. Al se los dos es ánda es muy simila es,
decidimos que cada uno p o undiza a más en uno pa a hace más lle ade o el abajo. Po
mi pa e comen a que mi a ea ue la de conoce en mayo p o undidad el es ánda
OpenMP y mi compañe o se dedicó al es udio p o undo del o o es ánda que eníamos,
OpenACC.
En esumen, cada uno p o undizó más en el es udio del es ánda que había elegido, no
obs an e a la ho a de comple a el código, ue de mane a conjun a ya que muchas de las