Explotación de aceleradores y hardware gráfico de forma amigable

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