Mecatronica

45

´
Castellon, Septiembre 2008

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

´
I. Introduccion

L

O s algoritmos que se utilizan para el procesamiento de im´genes tienen una alta demanda
a
de CPU, lo cual setraduce en un elevado consumo
de tiempo de procesamiento. Es por ello que a
lo largo de la historia de la inform´tica se ha ina
tentado optimizar el tiempo de ejecuci´n del softo
ware mediante una gran cantidad de t´cnicas difere
entes: aumento de la frecuencia de procesamiento,
aumento del n´mero de elementos de procesamiento,
u
ampliaciones del n´mero de niveles y tama˜o de la
u
n
cach´,etc. Todos estos aspectos han conseguido que
e
puedan llevarse a cabo procesamiento de datos en
tiempo real. Centr´ndonos en las t´cnicas utilizadas
a
e
en este art´
ıculo, cabe destacar la utilizaci´n de siso
temas SIMD en los procesadores de prop´sito geno
eral. Con esto hacemos referencia a las extensiones
MMX/SSE/SSE2 de los procesadores Intel x86, por
citar un ejemplo.
Gracias aestos conjuntos de extensiones se tiene
la capacidad de procesar un mayor n´mero de datos
u
en un mismo ciclo de reloj, lo cual aumenta significativamente el rendimiento en funci´n del n´mero
o
u
de unidades de procesamiento que tenga cada uno
de los procesadores que se utilicen. El l´
ımite te´rico
o
en cuanto al aumento de rendimiento que puede conseguirse por medio de estas t´cnicas vienedado por el
e
n´mero de registros que pueden procesarse al mismo
u
tiempo, sin embargo, en la pr´ctica influyen otros asa
pectos como pueden ser la distribuci´n de los datos
o
en memoria, el n´mero y tiempo de los diferentes
u
reemplazos, etc. El uso de estas extensiones requiere
una gran labor de dise˜o por parte del investigador,
n
pues la arquitectura de los algoritmos se ve amplia1Dpto. de Arquitectura y Tecnolog´ de Computadores,
ıa
Universidad de C´rdoba, e-mail: i22casej@uco.es.
o
2 Dpto. de Arquitectura y Tecnolog´ de Computadores,
ıa
Universidad de C´rdoba, e-mail: jmpalomares@uco.es.
o

mente modificada.
Otro de los grandes avances llevados a cabo por
los fabricantes de microprocesadores, ha sido la incorporaci´n de m´s de una CPU en los procesadores
o
ade prop´sito general. Este hecho ha propiciado un
o
gran aumento en el rendimiento as´ como la necesiı
dad de desarrollar nuevas t´cnicas de optimizaci´n
e
o
que aprovechen eficazmente el hardware disponible.
Entre la t´cnicas disponibles para llevar a la optie
mizaci´n en este tipo de procesadores encontramos
o
los hilos de ejecuci´n, los cuales nos permiten dio
vidir la carga deprocesamiento entre las diferentes
unidades de procesamiento disponibles en la m´quina
a
sobre la que se realizan las pruebas.
Entre las diferentes librer´ de hilos de ejecuci´n
ıas
o
las m´s utilizadas son OpenMP y Pthreads [1] [2] :
a
OpenMP es una API que permite a˜adir concurn
rencia a las aplicaciones mediante paralelismo con
memoria compartida. Se basa en la creaci´n de hilos
o
de...