45

´ n, Septiembre 2008 Castello

Paralelizaci´on y Optimizaci´on a bajo nivel de algoritmos de tratamiento de im´agenes Jose Mar´ıa Castillo Secilla1 , Jos´e Manuel Palomares Mu˜ noz2 , Juan G´omez Luna, Jos´e Manuel Soto Hidalgo y Joaqu´ın Olivares Bueno Resumen— Se presentan cuatro algoritmos de tratamiento de im´ agenes, como son el algoritmo de Correlaci´ on 1D enventanada, Correlaci´ on 2D enventanada, Convoluci´ on y el algoritmo de Batchelor y Wilkins. Este trabajo se divide en dos fases. En la primera de ellas se lleva a cabo un estudio de las mejores t´ ecnicas de optimizaci´ on y paralelizaci´ on sobre los algoritmos de Correlaci´ on 1D enventanada, Correlaci´ on 2D enventanada y Convoluci´ on. En base a los resultados obtenidos en esta primera fase se ha llevado a cabo la paralelizaci´ on y optimizaci´ on del algoritmo de Batchelor y Wilkins en la fase II. Palabras clave— SSE, Pthreads, OpenMP, procesamiento de im´ agenes, clasificaci´ on de colores, hilos de ejecuci´ on.

´n I. Introduccio

L

O s algoritmos que se utilizan para el procesamiento de im´agenes tienen una alta demanda de CPU, lo cual se traduce en un elevado consumo de tiempo de procesamiento. Es por ello que a lo largo de la historia de la inform´atica se ha intentado optimizar el tiempo de ejecuci´on del software mediante una gran cantidad de t´ecnicas diferentes: aumento de la frecuencia de procesamiento, aumento del n´ umero de elementos de procesamiento, ampliaciones del n´ umero de niveles y tama˜ no de la cach´e, etc. Todos estos aspectos han conseguido que puedan llevarse a cabo procesamiento de datos en tiempo real. Centr´andonos en las t´ecnicas utilizadas en este art´ıculo, cabe destacar la utilizaci´on de sistemas SIMD en los procesadores de prop´osito general. Con esto hacemos referencia a las extensiones MMX/SSE/SSE2 de los procesadores Intel x86, por citar un ejemplo. Gracias a estos conjuntos de extensiones se tiene la capacidad de procesar un mayor n´ umero de datos en un mismo ciclo de reloj, lo cual aumenta significativamente el rendimiento en funci´on del n´ umero de unidades de procesamiento que tenga cada uno de los procesadores que se utilicen. El l´ımite te´orico en cuanto al aumento de rendimiento que puede conseguirse por medio de estas t´ecnicas viene dado por el n´ umero de registros que pueden procesarse al mismo tiempo, sin embargo, en la pr´actica influyen otros aspectos como pueden ser la distribuci´on de los datos en memoria, el n´ umero y tiempo de los diferentes reemplazos, etc. El uso de estas extensiones requiere una gran labor de dise˜ no por parte del investigador, pues la arquitectura de los algoritmos se ve amplia1 Dpto. de Arquitectura y Tecnolog´ ıa de Computadores, Universidad de C´ ordoba, e-mail: [email protected]. 2 Dpto. de Arquitectura y Tecnolog´ ıa de Computadores, Universidad de C´ ordoba, e-mail: [email protected].

mente modificada. Otro de los grandes avances llevados a cabo por los fabricantes de microprocesadores, ha sido la incorporaci´on de m´as de una CPU en los procesadores de prop´osito general. Este hecho ha propiciado un gran aumento en el rendimiento as´ı como la necesidad de desarrollar nuevas t´ecnicas de optimizaci´on que aprovechen eficazmente el hardware disponible. Entre la t´ecnicas disponibles para llevar a la optimizaci´ on en este tipo de procesadores encontramos los hilos de ejecuci´on, los cuales nos permiten dividir la carga de procesamiento entre las diferentes unidades de procesamiento disponibles en la m´aquina sobre la que se realizan las pruebas. Entre las diferentes librer´ıas de hilos de ejecuci´on las m´as utilizadas son OpenMP y Pthreads [1] [2] : OpenMP es una API que permite a˜ nadir concurrencia a las aplicaciones mediante paralelismo con memoria compartida. Se basa en la creaci´on de hilos de ejecuci´on paralelos compartiendo las variables del proceso padre que los crea. OpenMP se basa en el modelo fork-join, paradigma que proviene de los sistemas Unix, gracias al cual puede dividirse la tarea a realizar por un proceso en K hilos de ejecuci´on (fork). Una vez que los K hilos han finalizado se recopilar´an sus datos y se tendr´a el resultado final. Pthreads es una librer´ıa que cumple los est´andares POSIX y que permite trabajar con distintos hilos de ejecuci´ on al mismo tiempo. El art´ıculo se organiza de la siguiente manera. En la Sec. II se describen los algoritmos de procesamiento de im´agenes que se van a tratar a lo largo de este trabajo y muestran las formulas que los rigen. En la Sec. III se muestran las optimizaciones llevadas a cabo. En la Sec. IV se indican las t´ecnicas que se han utilizado. En la Sec. V se muestran los resultados obtenidos por los diferentes algoritmos y las distintas configuraciones. Para finalizar, en la Sec. VI se muestran las conclusiones a las que se ha llegado tras este estudio. II. Algoritmos de procesamiento de ´ genes ima Se han considerado tres algoritmos de tratamiento de im´agenes (correlaci´on 1D enventanada, correlaci´ on 2D enventanada y convoluci´ on) [3] [4] [5] [6] [7] para determinar qu´e t´ecnicas de optimizaci´on resultan mejores de cara a optimizar un algoritmo de tratamiento de im´agenes utilizado de manera pr´ actica, el Algoritmo de Batchelor y Wilkins [8], el cual es ampliamente utilizado para resolver el pro-

Actas de las XIX Jornadas de Paralelismo, pp. 45-50, 2008. ISBN: 978-84-8021-676-0

46

XIX Jornadas de Paralelismo

blema de agrupamiento de colores dominantes. A. Correlaci´ on 1D Enventanada La correlaci´on 1D enventanada (Ec. 1) muestra lo parecidas que son dos im´agenes entre s´ı, sin embargo, la segunda imagen no se toma tal cual, sino que dado un radio de ventana se procesa sobre un vector de t´erminos enventanados de una imagen. Una vez definido un radio de ventana, se calcula el valor de cada p´ıxel sumando todos los elementos a radio p´ıxeles a derecha e izquierda del p´ıxel base. P corr (H1 , H2 ) =

(H1 (b) · W (H2 (b))) N T1 · N T2

(1)

B. Correlaci´ on 2D Enventanada La correlaci´on 2D enventanada (Ec. 2) sigue la misma filosof´ıa que la correlaci´on 1D enventanada normalizada, s´olo que ahora el vector de t´erminos enventanados (W) se obtiene a partir de aquellos elementos que se encuentren a una distancia radio menor del p´ıxel de origen dado, tanto en horizontal como en vertical o en diagonal. Para obtener el resultado deseado se aplica la siguiente f´ormula: P P corr2D(H1 , H2 ) =

i

j (H1 [i][j]

· W (H2 [i][j]))

N T1 · N T2

sX X (H1 [i][j])2 N T1 = i

(2) (3)

(4)

j

C. Convoluci´ on La aplicaci´on de un algoritmo de convoluci´on sobre una imagen requiere dos elementos b´asicos para poder llevarla a cabo, una imagen y un filtro. El filtro se aplicar´a a todos y cada uno de los elementos que forman la imagen con el fin de provocar sobre la imagen el efecto deseado, como por ejemplo un cambio en alguno de los colores componentes del RGB de cada uno de los pixels que forman una imagen. La expresi´on que define la aplicaci´on de un filtro sobre una determinada imagen viene dada por la Ec. 5:

y(n) =

M X

Fig. 1. Efecto Umbral

j

sX X N T2 = (H2 [i][j])2 i

D. Algoritmo de Batchelor y Wilkins Este algoritmo propuesto por los investigadores Batchelor y Wilkins es tambi´en conocido como m´etodo de m´axima distancia. Se trata de un m´etodo heur´ıstico incremental que emplea un u ´nico par´ ametro para determinar la distancia m´axima entre las diferentes clases utilizando un par´ametro Umbral que determinar´a la distancia m´axima que debe tener un patr´on para pertenecer a una determinada clase. Las l´ıneas generales del algoritmo son las siguientes: Se crea un agrupamiento si la distancia de un patr´ on al agrupamiento m´as cercano supera el valor umbral. El algoritmo se ejecuta de manera iterativa creando todas las clases posibles y agrupando a los diferentes patrones en cada una de ellos en funci´on de la distancia que los separa. El algoritmo finaliza cuando todos los elementos pertenecen a alguna de las clases generadas durante el proceso.

bk x(n − k)

(5)

k=0

Donde x(n) representa el vector de entrada de tama˜ no “n”, y(n) representa el vector de salida de tama˜ no “n” y, por u ´ltimo, bk es el k-´esimo coeficiente de los M que forman el filtro que se quiere aplicar a la imagen. Como puede observarse tras el estudio de la expresi´on, el filtro ha de ser aplicado a todos y cada uno de los elementos que forman la imagen a convolucionar.

III. Algoritmos optimizados para MMX/SSE y procesamiento en Core2Duo Para aumentar el rendimiento de los algoritmos que se han mostrado en el apartado anterior, se han adaptado a la tecnolog´ıa MMX/SSE combinada con la utilizaci´on de hilos de ejecuci´on con el fin de hacer un uso ´optimo de dos procesadores. A.Correlaci´ on 1D enventanada MMX El algoritmo de correlaci´on 1D enventanada ha sido completamente adaptado para poder hacer uso del conjunto de librer´ıas MMX as´ı como para poder llevar a cabo su ejecuci´on haciendo uso de separaci´on de datos a trav´es del procesamiento con hilos de ejecuci´ on en un procesador de doble n´ ucleo. En el caso de obtener el vector de t´erminos enventanados, cada procesador calcula ocho registros de cada una de las filas que forman el conjunto de datos de la imagen en la memoria. Haciendo este tipo de separaci´on de datos se optimiza el rendimiento minimizando el n´ umero de fallos de cach´e. B.Correlaci´ on 2D enventanada SSE Bas´ andonos en la t´ecnica anterior, se ha optimizado este algoritmo permitiendo el c´alculo de los t´erminos enventanados en 2D (v´ease Fig. 2). Cada una de las l´ıneas de sumas horizontales es calculada

47

´ n, Septiembre 2008 Castello en un procesador (l´ıneas pares procesador I, impares procesador II), una vez que los dos procesadores han realizado le c´alculo de todas las l´ıneas se lleva a cabo la suma.

junto de im´agenes de prueba.

Fig. 3. Im´ agenes de entrada. Algoritmo de B&W

Fig. 2. Correlaci´ on 2D enventanada SSE Fig. 4. Im´ agenes de salida Algoritmo de B&W

C.Convoluci´ on SSE La convoluci´on optimizada para SSE puede observarse en la nos permite llevar a cabo la multiplicaci´ on de grupos de ocho valores de datos simult´ aneamente. Esta decisi´on de dise˜ no se ha complementado haciendo uso de hilos de ejecuci´on, lo cual nos permite llevar a cabo la tarea de convolucionar una imagen en base a un filtro en el menor tiempo posible tal y como se indice en la secci´on de resultados. ´cnicas utilizadas IV. Te La idea principal de este trabajo ha sido la de encontrar un conjunto de m´etodos que nos permitan llevar a cabo la optimizaci´on del Algoritmo de Batchelor y Wilkins de la manera m´as ´optima posible. Para ello, haciendo uso de los algoritmos de Correlaci´on 1D enventanada, Correlaci´on 2D enventanada y Convoluci´ on, se han llevado a cabo un conjunto de pruebas que nos han determinado la mejor configuraci´on de t´ecnicas de entre las disponibles. Estas t´ecnicas se distribuyen de la siguiente manera: Divisi´on de la carga de procesamiento utilizando procesadores de doble n´ ucleo. – Gracias a este tipo de procesamiento, se ha tenido la capacidad de separar el procesamiento de los datos de manera que se optimice el uso de los recursos. • Paralelizaci´ on software – Este tipo de paralelizaci´on requiere la utilizaci´on de conjuntos de instrucciones que proporcionan la posibilidad de ejecutar determinadas l´ıneas de c´odigo de manera paralela. Las t´ecnicas utilizadas en este trabajo han sido: ∗ Paralelizaci´on utilizando hilos de procesamiento (Pthreads y OpenMP) ∗ Paralelizaci´on utilizando funciones de tipo SIMD ∗ Conjuntos de instrucciones Intel MMX ∗ Conjuntos de instrucciones Intel SSE •

En las figuras 3 y 4, puede verse el resultado de aplicar el algoritmo de Batchelor y Wilkins a un con-

V. Resultados Los experimentos se han realizado sobre un Intel Core 2 Duo con una frecuencia de reloj de 2.0GHz (32Kbytes cach´e L1 y 4MBytes cach´e L2), 1024MBytes de memoria RAM sobre un Sistema Operativo Linux Fedora (n´ ucleo 2.6), compilador GCC versi´ on 4.1.2. Los resultados se han dividido en dos fases, la primera fase incluye todos los datos relativos a las pruebas realizadas con los algoritmos de Correlaci´on 1D enventanada, Correlaci´on 2D enventanada y Convoluci´ on. Estas pruebas han sido llevadas a cabo con todas las t´ecnicas citadas en el apartado anterior. La segunda fase de pruebas contiene a aquellas pruebas realizadas con el Algoritmo de Batchelor y Wilkins haciendo uso de las t´ecnicas que aportaron mejores resultados en la primera fase. Fase I: Estudio de las diferentes t´ecnicas de paralelizaci´ on Para llevar a cabo los experimentos sobre los sistemas desarrollados para cada uno de los algoritmos se han seleccionado un conjunto de tama˜ nos de imagen que han sido catalogadas en im´agenes peque˜ nas, im´agenes medianas e im´agenes grandes, como se muestra en la tabla (tabla I). TABLA I ˜ os de imagen. Fase I Taman

Peque~ nas 32x32 64x64 128x128 256x256 320x240

Medianas 400x400 640x480 800x600 1024x768 1280x1024

Grandes 1600x1200 1920x1080 2000x1800 2576x1935 2916x2112

Con el fin de garantizar que las pruebas se llevan a cabo de la manera m´as ´optima y equitativa posible entre todos los algorimos se ha generado el c´odigo fuente haciendo uso de la opci´on de compilaci´on O2 del compilador GCC. Con esta opci´on el propio

48

XIX Jornadas de Paralelismo

compilador se encarga de llevar a cabo todas las optimizaciones posibles sobre el c´odigo fuente sin llegar a desenrollar bucles. El sistema sobre el que se han llevado a cabo las pruebas, adem´as de ser multiproceso, es multitarea por lo que no podemos asegurar que el tiempo de ejecuci´ on que nos ofrecen los resultados sea completamente “real”. Para mitigar estos efectos, se han tomado una serie de precauciones. Se han deshabilitado todos los procesos residentes de la m´aquina, salvo los estrictamente necesarios del Sistema Operativo y el proceso del propio experimento. A la tarea encargada de llevar a cabo la ejecuci´ on del algoritmo de la prueba se le ha dado prioridad m´axima en el planificador de tareas del sistema operativo. Se ha desconectado el equipo de la red y se han dejado sin actividad interactiva todos los perif´ericos, para evitar que se generasen interrupciones y que tuvieran que ser tratadas por el Sistema Operativo. Se han repetido 10000 veces cada uno de los experimentos, realizando una limpieza de la cach´e a trav´es de una llamada de bajo nivel desde el propio c´odigo fuente desarrollado. De cada conjunto de experimentos, se han extra´ıdo los siguientes datos estad´ısticos: • • •

•

Media de ciclos de ejecuci´on en serie Media de ciclos de ejecuci´on en paralelo Speedup: Medida de la ganancia media de un algoritmo respecto al algoritmo base (algoritmo secuencial). Speedup pr´actico: Es la medida de la ganancia teniendo en cuenta los tama˜ nos m´as habituales, es decir, las im´agenes medianas y grandes.

A.Correlaci´ on 1D enventanada En las figuras 5 y 6, pueden observarse tanto los tiempos como los valores de speedup para el conjunto de experimentos realiados sobre el algoritmo de Correlaci´on 1D enventanada en sus diferentes versiones. Adem´as, con el fin de completar los resultados mostrados por las figuras, se tiene la tabla II, donde se muestran los resultados obtenidos.

Fig. 6. Speedup Correlaci´ on 1D enventanada. TABLA II ´ n 1D enventanada MMX Speedup Correlacio

Pthreads Separaci´ on Funcional OpenMP Separaci´ on Funcional Pthreads Separaci´ on Datos OpenMP Separaci´ on Datos Pthreads Separaci´ on Datos MMX OpenMP Separaci´ on Datos MMX

1.68 1.51 1.89 1.80 4.35 4.37

valores de speedup para el conjunto de experimentos realiados sobre el algoritmo de Correlaci´on 2D enventanada en sus diferentes versiones. Adem´as, con el fin de completar los resultados mostrados por las figuras, se tiene la tabla III, donde se muestran los resultados obtenidos.

Fig. 7. Tiempos Correlaci´ on 2D enventanada.

TABLA III ´ n 2D enventanada SSE Speedup Correlacio

Pthreads Separaci´ on Funcional OpenMP Separaci´ on Funcional Pthreads Separaci´ on Datos OpenMP Separaci´ on Datos Pthreads Separaci´ on Datos SSE OpenMP Separaci´ on Datos SSE

0.85 0.83 2.79 3.24 18.09 18.23

Fig. 5. Tiempos Correlaci´ on 1D enventanada.

B. Correlaci´on 2D enventanada Al igual que en los resultados de la Correlaci´on 1D enventanada, se tiene dos figuras (Fig. 7 y Fig. 8), donde pueden observarse tanto los tiempos como los

C. Convoluci´ on Las figuras (Fig. 9 y Fig. 10) muestran los resultados obtenidos por el algoritmo de Convoluci´ on en sus diferentes versiones. Adem´as, con el fin de completar los resultados mostrados por las figuras, se tiene la tabla IV, donde se muestran los resultados obtenidos.

49

´ n, Septiembre 2008 Castello •

Se ha utilizado separaci´on de datos en el tratamiento de los diferentes pixeles que forman la imagen.

Para llevar a cabo esta bater´ıa de pruebas se han utilizado los tama˜ nos de imagen de la tabla V. TABLA V ˜os de imagen. Fase II Taman

Fig. 8. Speedup Correlaci´ on 2D enventanada.

Peque~ nas 32x32 64x64 128x128 256x256

Medianas 320x240 400x400 512x512 640x480

Grandes 800x600 1024x768 1280x1024

Fig. 9. Tiempos Convoluci´ on

Fase II: Resultados Algoritmo de Batchelor y Wilkins En funci´on de los resultados obtenidos en la primera fase de pruebas, se ha desarrollado el Algoritmo de Batchelor y Wilkins paralelizado haciendo uso de las mejores t´ecnicas de la fase anterior: • • •

Fig. 11. Tiempos Algoritmo de Batchelor y Wilkins

Utilizaci´on de la librer´ıa OpenMP para generar los hilos de ejecuci´on Los bucles han sido optimizados y paralelizados mediante el conjunto de instrucciones SSE. Se ha hecho uso de la t´ecnica de separaci´on funcional para llevar a cabo diversas tareas en los dos procesadores al mismo tiempo. Fig. 12. Speedup Algoritmo de Batchelor y Wilkins

En la tabla VI pueden observarse los valores de Speedup obtenidos (en media) durante las diferentes ejecuciones del algoritmo de Batchelor y Wilkins haciendo uso de todos los tama˜ nos de imagen seleccionados en este trabajo (v´ease tabla V). VI. Conclusiones

Fig. 10. Speedup Convolucion SSE

Pthreads Separaci´ on Datos OpenMP Separaci´ on Datos Pthreads Separaci´ on Datos SSE OpenMP Separaci´ on Datos SSE TABLA IV ´n Speedup Convolucio

1.70 1.71 8.42 7.96

A.Conclusiones de la Fase I Las librer´ıas de hilos utilizadas han proporcionado resultados satisfactorios. Ambas proporcionan resultados muy similares, sin embargo, debido a la facilidad de uso de la librer´ıa OpenMP recomendamos su utilizaci´on para cualquier tipo de desarrollo multihilo. Haciendo uso de la tecnolog´ıa SSE junto con las t´ecnicas de separaci´on de datos y separaci´on funcional se han obtenido resultados m´as que satisfactorios. En el caso de la convoluci´ on, haciendo uso de OpenMP y la tecnolog´ıa SSE se ha conseguido una

50

XIX Jornadas de Paralelismo TABLA VI Speedup Algoritmo Batchelor y Wilkins

Tama~ no 32x32 64x64 128x128 256x256 320x240 400x400 512x512 640x480 800x600 1024x768 1280x1024

Speedup 2.29 1.91 2.21 2.11 1.96 1.96 1.88 1.85 1.99 1.88 1.84

mejora de rendimiento del 865%, llegando al 2155% en el algoritmo de Correlaci´on 2D enventanada haciendo uso de la librer´ıa de hilos citada. B.Conclusiones de la Fase II Los resultados obtenidos en el Algoritmo de Batchelor y Wilkins no han sido tan espectaculares como en la fase I debido a la naturaleza de este algoritmo, cuyo tratamiento de los datos no es tan altamente iterativo como en el caso de la Correlaci´on y Convoluci´ on. El Speedup que se ha conseguido ha sido del 101.07%, lo cual se traduce en un aumento de velocidad de algo m´as del doble. Referencias [1] OPENMP, Sitio web oficial de OpenMP, Documentaci´ on t´ ecnica para llevar a cabo la optimizaci´ on de software, as´ı como los compiladores necesarios dependiendo del sistema ´ operativo a utilizar por el desarrollador. Ultima visita Mayo 2008. URL: http://www.openmp.org [2] Nichols, B., Buttlar, D., Proulx, F., Pthreads Programming, A posix standard for Better Multiprocessing. 1o Edici´ on. Sebastopol (United States of America). Ed. O’Reilly. A˜ no 1996. 267 pags. ISBN: 1-56592-115-1. [3] Castillo Secilla, J.M., Paralelizaci´ on y optimizaci´ on a bajo nivel de algoritmos de tratamiento de im´ agenes, Proyecto Fin de Carrera. Universidad de C´ ordoba. 2007. [4] Castillo Secilla, J.M., Optimizaci´ on de algoritmos de c´ alculo num´ erico utilizando MMX y SSE., Proyecto Fin de Carrera. Universidad de C´ ordoba. 2005. [5] Jose M. Castillo Secilla, Edmundo S´ aez Pe˜ na, Jose M. ´ Palomares, Manuel A. Ortiz L´ opez y Miguel Angel Montijano Vizca´ıno ”Optimizaci´ on de algoritmos de procesamiento de im´ agenes utilizando SSE y el impacto en el rendimiento seg´ un compiladores” In Proceedings of the XVII Jornadas de Paralelismo, Albacete (Espa˜ na): 473478. Septiembre, 2006. [6] Saez, E. Benavides, J.I. Guil, N., Reliable real time scene change detection in mpeg compressed video, IEEE Symposium Proceedings of the International Conference of Image Processing (ICIP-2004), Singapur, pags. 2231-2234. Octubre 2004. [7] Saez, E. Benavides, J.I. Guil, N., Combining luminance and edge based metrics for robust temporal video segmentation, IEEE Symposium Proceedings of the International Conference Multimedia and Expo (ICME-2004), Taipei(Taiwan), pags. 2231-2234. Junio 2004. [8] Cortijo Bon, F.J., T´ ecnicas no supervisadas, m´ etodos de agrupamiento, Documento acerca de las principales t´ ecnicas de clasificaci´ on de patrones. Universidad de Granada. Noviembre 2001.