Codificador de v´ıdeo basado en Wavelet 3D usando OpenMP y Pthreads Ricardo Fern´andez, Jos´e M. Garc´ıa, Gregorio Bernab´e y Manuel E. Acacio Resumen— En este art´ıculo se estudian dos alternativas para la implementaci´ on de un algoritmo paralelo de codificaci´ on de v´ıdeo basado en la Wavelet 3D usando OpenMP y Pthreads desde el punto de vista de la velocidad de ejecuci´ on y la facilidad de implementaci´ on y mantenibilidad del c´ odigo obtenido. Se parte de un codificador 3D-FWT secuencial y se paraleliza usando OpenMP y Pthreads, llegando a la conclusi´ on de que es posible obtener con OpenMP una velocidad de ejecuci´ on casi ´ optima sin tener que sacrificar la mantenibilidad del c´ odigo usando Pthreads. Palabras clave— OpenMP, Pthreads, Transformada Wavelet, Codificaci´ on de V´ıdeo.

´n I. Introduccio

L

AS tendencias actuales en arquitectura de computadores buscan explotar cada vez m´as el paralelismo a todos los niveles. Cada vez resulta m´as normal que las estaciones de trabajo sean multiprocesadores de memoria compartida o dispongan de un procesador capaz de ejecutar varios hilos a la vez mediante Simultaneous Multithreading (SMT [1] [2]). El aprovechamiento eficaz de estas arquitecturas requiere el uso de varios hilos o procesos, lo que obliga a replantearse la implementaci´on de muchos algoritmos. Existen varios enfoques a la hora de obtener algoritmos paralelos a partir de otros secuenciales. La paralelizaci´on autom´atica ([3] [4]) resulta atractiva y prometedora para algunas aplicaciones, pero es incapaz de obtener buenos resultados en muchas otras. Cuando se requiere un conocimiento de alto nivel de la aplicaci´on es necesario recurrir a la intervenci´on manual para paralelizar el c´odigo directamente. Las aplicaciones multimedia tienen una importancia cada vez mayor en diversas a´reas. Un ejemplo es el v´ıdeo m´edico, cuyos requisitos de calidad son muy altos y existen regulaciones que obligan a almacenarlo durante un tiempo determinado, haciendo necesaria una compresi´on eficaz. Los requisitos de calidad hacen que suelan usarse t´ecnicas de compresi´on sin p´erdida (JPEG-LS [5]), pero esto no resulta pr´actico debido a las bajas tasas de compresi´on posibles con ellas. Por otro lado, la transformada Wavelet tridimensional permite codificar v´ıdeo con gran calidad y grandes tasas de compresi´on, haciendo atractivo el uso de un codificador basado en ella [6] [7] y obteniendo mejores resultados que otros algoritmos de prop´osito m´as general (MPEG [8], MPEG-4 [9] [10]). Uno de los principales problemas al trabajar con la Departamento de Ingenieria y Tecnologia de ComputadoresFacultad de Informatica. Universidad de Murcia. Campus de Espinardo - 30080 Murcia (Espa˜ na). Correo electr´ onico: {r.fernandez,jmgarcia,gbernabe,meacacio}@ditec.um.es

secuencia de v´ıdeo como una se˜ nal tridimensional es que se tiene que manejar una gran cantidad de datos y los accesos a memoria ralentizan la ejecuci´on del algoritmo. En el caso de la paralelizaci´on de un codificador de v´ıdeo los m´etodos autom´aticos a nuestro alcance no obtienen ning´ un resultado. Es necesario la intervenci´on manual, especialmente para aprovechar la tecnolog´ıa HyperThreading [11]. La paralelizaci´on manual a˜ nade una complejidad considerable al desarrollo del software. Ser´ıa deseable que ese aumento de complejidad fuera el m´ınimo posible. Existen varias alternativas a la hora de implementar un algoritmo paralelo, cada una con distinto grado de dificultad de uso, mantenibilidad y flexibilidad. En este art´ıculo se pretende evaluar la aplicaci´on de dos de esas alternativas, OpenMP [12] y Pthreads [13], a la implementaci´on de un codificador de v´ıdeo paralelo usando la transformada Wavelet 3D desde el punto de vista de la velocidad del programa resultante, dificultad de implementaci´on, mantenibilidad y reusabilidad del c´odigo obtenido. En este art´ıculo se presentan cuatro implementaciones del codificador paralelo descrito en [11] y se compara su tiempo de ejecuci´on, la dificultad de implementaci´on y mantenibilidad del programa resultante. En la secci´on II se presentan los fundamentos de la transformada Wavelet 3D y de las tecnolog´ıas a utilizar para la implementaci´on (OpenMP y Pthreads). La secci´on III discute el trabajo previo realizado en el codificador secuencial y las estrategias de paralelizaci´on estudiadas. La secci´on IV expone las implementaciones realizadas de la paralelizaci´on seg´ un las cuatro estrategias de implementaci´on. Finalmente, la secci´on V estudia el tiempo de ejecuci´on de cada implementaci´on y los compara con la implementaci´on secuencial, y la secci´on VI presenta las conclusiones del trabajo. II. Fundamentos y trabajo relacionado A. OpenMP OpenMP [12] es una especificaci´on que permite la implementaci´on de programas portables en arquitecturas de multiprocesadores de memoria compartida usando C, C++ o FORTRAN. La programaci´on usando OpenMP se basa en el uso de directivas que indican al compilador qu´e secciones debe paralelizar y c´omo. Estas directivas permiten crear secciones paralelas, indicar bucles paralelos y definir secciones cr´ıticas. Cuando se define una secci´on o bucle paralelo el programador debe especificar qu´e variables son privadas a cada hilo, compartidas o usadas para reducciones. El programador

no tiene que especificar si no quiere cu´antos hilos se usar´an o c´omo se planificar´a la ejecuci´on de un bucle paralelo, ya que OpenMP incluye diversas pol´ıticas aplicables en tiempo de ejecuci´on. OpenMP permite una paralelizaci´on incremental de programas, por lo que resulta especialmente adecuado para a˜ nadir paralelismo a programas escritos de forma secuencial. En la mayor´ıa de los casos es posible tener el mismo c´odigo para versiones secuenciales y paralelas del programa, tan s´olo es necesario ignorar las directivas OpenMP para compilar el programa secuencial. Esto es especialmente u ´til en las fases de desarrollo del programa para permitir una depuraci´on m´as f´acil. B. Pthreads Pthreads (POSIX threads, [13]) es un API muy portable y extendido para la programaci´on de multiprocesadores con memoria compartida. Este API es de m´as bajo nivel que OpenMP por lo que permite un mayor control de c´omo se realiza la concurrencia a costa de una mayor dificultad de uso. El modelo de programaci´on de Pthreads se basa en la creaci´on de hilos mediante llamadas a funciones de la librer´ıa. El programador debe crear expl´ıcitamente todos los hilos y encargarse de todas las labores de sincronizaci´on necesarias. Pthreads incluye un rico conjunto de primitivas de sincronizaci´on, que incluye cerrojos (mutex), sem´aforos y variables de condici´on. C. SMT e HyperThreading Con SMT [1] [2], un s´olo procesador es capaz de ejecutar simult´aneamente dos hilos, compartiendo la mayor´ıa de los recursos hardware tales como las cach´es, unidades de ejecuci´on, predictores de salto, etc. y duplicando aquellos recursos necesarios para almacenar el estado de los procesos. De esta forma, un s´olo procesador f´ısico parece al sistema operativo y las aplicaciones como dos procesadores virtuales independientes. La compartici´on de recursos permite un mejor aprovechamiento de los recursos del procesador, permitiendo que un hilo se ejecute mientras otro est´a detenido por un fallo de cach´e o de predicci´on de saltos. r ha introducido una implementaci´on de Intel SMT denominada HyperThreading [14] en sus nuevos procesadores (XeonTM , PentiumTM IV) obteniendo mejoras en el tiempo de ejecuci´on de cerca del 30% en algunos casos [15]. D. Transformada Wavelet R´ apida La transformada Wavelet descompone la se˜ nal extrayendo la informaci´on presente a varias resoluciones [16]. La transformada Wavelet r´apida se implementa usando un par de filtros QMF (Quadrature Mirror Filter). Para calcular la transformada de una se˜ nal discreta se calcula la convoluci´on de la se˜ nal con cada filtro y se submuestrea por 2. Uno de los filtros, H, es un filtro pasa baja que extrae la informaci´on

de grano grueso de la se˜ nal, mientras que el otro, G, es un filtro pasa alta que se encarga de extraer los detalles de la se˜ nal. De esta forma obtenemos dos se˜ nales, low y high, con la mitad de muestras de la original cada una. La transformada se puede aplicar varias veces a la parte de grano grueso, lo que permite conseguir mejores tasas de compresi´on sacrificando la calidad de la se˜ nal reconstruida. Para generalizar la transformada Wavelet a dos o m´as dimensiones se aplica sucesivamente la transformada en cada dimensi´on. Por ejemplo, en el caso de dos dimensiones se aplica primero la transformada Wavelet unidimensional a cada una de las filas y despu´es se aplica a cada una de las columnas de la imagen resultante. III. Trabajo Previo Estamos interesados en aplicar el algoritmo r´apido de la transformada Wavelet 3D (3D-FWT) a la compresi´on de v´ıdeo m´edico de tama˜ no 512 × 512 en escala de grises (8 bits por pixel) y en secuencias de 64 frames. A partir de un trabajo anterior [7], hemos obtenido que los mejores par´ametros son usar como Wavelet madre la Daubechies de 4 coeficientes y realizar dos pasadas en cada una de las dimensiones. En el codificador que hemos desarrollado, despu´es de la transformada Wavelet se aplica un paso de umbralizaci´on en el que se descartan los valores cuyo valor absoluto es menor que una constante determinada. Tras la umbralizaci´on se realiza el paso m´as costoso en cuanto a tiempo de CPU del codificador: la cuantizaci´on, en la que los coeficientes de la transformada se convierten en enteros sin signo. Por u ´ltimo, se realiza una codificaci´on entr´opica utilizando codificaci´on run-length 3D y se comprime el resultado usando un compresor aritm´etico. En trabajos anteriores [7] [17] [18] se han desarrollado varias t´ecnicas que mejoran el tiempo de ejecuci´on del codificador secuencial. Estas t´ecnicas incluyen una estrategia de blocking rectangular con solapamiento y reuso de operaciones, vectorizaci´on manual usando instrucciones SSE y vectorizaci´on por columnas para aprovechar la localidad en el c´alculo de la dimensi´on Y. Por tanto, la versi´on secuencial de la que partimos para vectorizar est´a tan optimizada como nos ha sido posible sin recurrir a la paralelizaci´on. ´n IV. Paralelizacio En [11] se presentan dos formas de paralelizar la transformada Wavelet enfocadas especialmente a aprovechar la tecnolog´ıa HyperThreading: usando descomposici´on por datos y usando descomposici´on funcional. La descomposici´on por datos aplica simult´aneamente la transformada a dos bloques de frames independientes de la secuencia. Esta estrategia permite un buen balanceo de la carga y tiene muy poca comunicaci´on, pero el conjunto de trabajo aumenta al doble y ambos hilos realizan funciones

Hilo principal

Hilo esclavo

1ª pasada 3D-FWT

2ª pasada 3D-FWT

Cuantización alta

Cuantización baja

Fig. 1. Primer esquema de paralelizaci´ on.

similares, lo que causa contenci´on en la unidades funcionales del procesador y hace dicha t´ecnica no apropiada para arquitecturas HyperThreading. La descomposici´on funcional aprovecha fases independientes del codificador para realizarlas en paralelo. Se pueden realizar simult´aneamente las fases de la transformada y la cuantizaci´on del codificador, pero la transformada Wavelet tarda menos de la mitad en ejecutarse que la cuantizaci´on, por lo que la carga de trabajo est´a desbalanceada. Adem´as, aumentan los requerimientos de memoria al igual que en la descomposici´on por datos, debido a que es necesario copiar los resultados de la transformada para usarlos en la fase de cuantizaci´on sin que sean sobreescritos por las siguientes operaciones. Es posible obtener una divisi´on funcional m´as adecuada fij´andose en c´omo se realiza la codificaci´on. Cuando la primera pasada de la transformada se ha aplicado a un bloque de v´ıdeo en la dimensi´on T, la mitad de los frames representan las frecuencias bajas y la otra mitad las altas. Despu´es de aplicar la transformada en todos los ejes, s´olo la octava parte de los pixels son necesarios para la segunda pasada de la transformada. En el nuevo esquema de paralelizaci´on un hilo se encarga de la transformada Wavelet y la cuantizaci´on de la parte baja mientras que el otro se encarga de la cuantizaci´on de la parte alta. El segundo hilo puede empezar cuando se ha realizado la primera pasada. Por tanto, el solapamiento se produce entre la transformada Wavelet junto con la cuantizaci´on baja y la cuantizaci´on alta. Esta estrategia est´a mejor balanceada que la anterior y adem´as no requiere de ninguna copia de datos. La implementaci´on efectiva de la estrategia descrita se puede realizar usando varias tecnolog´ıas. A continuaci´on se describen las implementaciones realizadas y se comparan desde el punto de vista de la mantenibilidad y reusabilidad del c´odigo obtenido y su velocidad de ejecuci´on. En la figura 1 se muestra un esquema de las primeras dos implementaciones (openmp1 y pthreads1 ) de la codificaci´on de un bloque. En cada iteraci´on para cada bloque de 32 × 512 × 16 se realiza la cuantizaci´on de la parte alta en un hilo esclavo independiente, mientras que el hilo principal continua realizando la segunda pasada de la transformada Wavelet y la cuantizaci´on de la parte baja. La umbralizaci´on la realiza el mismo hilo que la transfor-

for (...) /* bucle exterior */ { /* 1a pasada 3D-FWT */ #pragma omp sections { #pragma omp section { /* 2a pasada 3D-FWT */ /* cuantizaci´ on baja */ } #pragma omp section { /* cuantizaci´ on alta */ } } } Fig. 2. Fragmento de c´ odigo del esquema openmp1.

mada para conseguir un mejor balanceo de la carga. A. Usando OpenMP La primera implementaci´on paralela realizada parte de la implementaci´on secuencial del algoritmo y la paraleliza seg´ un se ha descrito anteriormente (ver figura 1) usando OpenMP. Los cambios que ha sido necesario realizar con respecto al c´odigo de la versi´on secuencial son m´ınimos gracias al alto nivel expresivo de OpenMP. En particular, no ha sido necesario utilizar ninguna primitiva de sincronizaci´on expl´ıcitamente. Concretamente, se han utilizado simplemente una directiva #pragma omp parallel sections que define varios bloques que se ejecutan paralelamente por varios hilos. Cada una de estos bloques se especifica con la directiva #pragma omp section. Uno de los bloques (hilo principal) contendr´a el c´odigo de la segunda pasada de la 3D-FWT y la cuantizaci´on baja y el otro (hilo esclavo) contendr´a la cuantizaci´on alta. El resultado se muestra en la figura 2. El c´odigo resultante es muy similar a la implementaci´on secuencial inicial. De hecho, si ignoramos las directivas OpenMP, ser´ıa posible ejecutarlo secuencialmente obteniendo resultados correctos. Esto prueba la sencillez de la paralelizaci´on con OpenMP y que no introduce problemas de mantenibilidad o reusabilidad. B. Usando Pthreads El mismo esquema de la figura 1 se ha implementado usando Pthreads (pthreads1 ). Se ha partido de la versi´on anterior y se ha realizado una versi´on equivalente que usa Pthreads en lugar de OpenMP. Los principales cambios realizados han sido: •

•

Extraer el c´odigo relativo al hilo esclavo y ponerlo en una funci´on independiente. Esto es necesario porque Pthreads requiere que el punto de entrada de cada nuevo hilo sea una funci´on. Crear una estructura de datos auxiliar para el paso de par´ametros. Las funciones a utilizar como punto de entrada de un hilo en Pthreads deben tener una signatura determinada. En particular, tan s´olo pueden recibir un par´ametro y ´este debe ser un puntero a void. El patr´on habitual para pasar m´as par´ametros consiste en

struct thr data { int f, r, c, ...

};

Hilo principal

Hilo esclavo

lock(mutex1)

int hilo esclavo (struct thr data *data) { /* cuantizaci´ on alta */ } void fwt (int rows, int cols, int frames, ...) { for (...) /* bucle exterior */ { struct thr data data; pthread t hilo; /* 1a pasada 3D-FWT */ data.f = f; data.r = r; data.c = c; ...; pthread create (&hilo, NULL, hilo esclavo, &data); /* 2a pasada 3D-FWT */ /* cuantizaci´ on baja */ pthread join (hilo, NULL); } }

1ª pasada 3D-FWT

lock(mutex2) unlock(mutex1)

unlock(mutex2), excepto 1ª iteración lock(mutex1)

2ª pasada 3D-FWT

Cuantización alta

Cuantización baja

lock(mutex2) unlock(mutex1)

unlock(mutex2) lock(mutex1)

unlock(mutex2)

unlock(mutex1)

Fig. 3. Fragmento de c´ odigo del esquema pthreads1. Fig. 4. Segundo esquema de paralelizaci´ on.

crear una estructura auxiliar con un campo por cada par´ametro necesario y pasar un puntero a dicha estructura. Este es nuestro caso, ya que al extraer el c´odigo del hilo esclavo a una funci´on independiente en necesario comunicarle informaci´on que antes se almacenaba en variables locales. El c´odigo que se obtiene despu´es de las transformaciones manuales anteriores es bastante diferente a la versi´on secuencial, como puede verse en la figura 3. La implementaci´on no resulta muy complicada por tratarse de cambios de la estructura del c´odigo siguiendo patrones conocidos, pero las nuevas estructuras de datos y funciones creadas con el u ´nico fin de permitir la paralelizaci´on dificultan la legibilidad y el mantenimiento del c´odigo. C. Usando Pthreads m´ as eficientemente El uso de Pthreads implica una programaci´on a m´as bajo nivel que OpenMP, lo que permite un mayor control y flexibilidad a la hora de decidir c´omo paralelizar un programa. La implementaci´on descrita en la secci´on anterior no aprovecha este hecho. Concretamente, se crea y se destruye un nuevo hilo para cada bloque, lo que podr´ıa resultar costoso. Se ha dise˜ nado un esquema alternativo (pthreads2 ) que evita la creaci´on de varios hilos y usa u ´nicamente dos para todos los bloques. Estos dos hilos se crean al principio del proceso de codificaci´on y se usan candados para conseguir la sincronizaci´on entre ellos. No es suficiente con el uso de una regi´on cr´ıtica protegida por un candado, ya que es necesario que ambos hilos se ejecuten parcialmente en orden, es decir, el segundo hilo no puede comenzar con un nuevo bloque hasta que el hilo principal haya completado la primera pasada de la transformada Wavelet del bloque previo y el hilo principal no puede comenzar con un nuevo bloque hasta que el esclavo haya acabado el actual. Para conseguir esta ordenaci´on parcial se han utilizado dos candados que se adquieren alternativa-

mente por ambos hilos. Tambi´en se podr´ıa haber utilizado sem´aforos en su lugar. En la figura 4 se muestra un esquema de dicha implementaci´on. Los cambios realizados al c´odigo respecto a la versi´on secuencial para esta implementaci´on son mucho mayores que en los casos anteriores. Por ejemplo, hay que duplicar los bucles del codificador en cada hilo, adem´as de a˜ nadir las estructuras de datos y funciones adicionales descritas en la secci´on anterior. Estos cambios implican una reestructuraci´on profunda del c´odigo con el consiguiente deterioro de la legibilidad y mantenibilidad del c´odigo. El nuevo c´odigo, que se puede ver en la figura 5, es muy distinto al secuencial, y no resulta obvio para un programador que no haya seguido el proceso de desarrollo qu´e aspectos son relativos al algoritmo en s´ı y cu´ales a la paralelizaci´on. D. Usando OpenMP como Pthreads OpenMP tambi´en permite el uso de regiones cr´ıticas y candados. Por tanto, es posible utilizar el mismo esquema anteriormente descrito e implementar el algoritmo con OpenMP seg´ un la figura 4 (openmp2 ). Sin embargo, este enfoque es poco natural y el resultado es m´as dif´ıcil de comprender. Para conseguir esta implementaci´on, es necesario realizar parte de las transformaciones manuales utilizadas para el esquema anterior. No es necesario crear nuevas estructuras y tampoco hace falta extraer el c´odigo del hilo esclavo a otra funci´on. Sin embargo, sigue siendo necesario duplicar los bucles, reestructurando el c´odigo considerablemente, como se puede ver en la figura 6. La necesidad de reestructuraci´on y la introducci´on de los candados provoca la p´erdida de una de las ventajas de OpenMP: que el c´odigo paralelizado pueda ejecutarse secuencialmente ignorando las directivas OpenMP obteniendo resultados correctos. De hecho, el resultado es un c´odigo m´as similar a la versi´on pthreads2 que a openmp1 en cuanto a estructura y con problemas similares de legibilidad.

struct thr data { int rows, cols, frames, ... }; pthread mutex t mutex1 = PTHREAD MUTEX INITIALIZER; pthread mutex t mutex2 = PTHREAD MUTEX INITIALIZER;

void fwt (int rows, int cols, int frames, ...) { omp lock t lock1; omp lock t lock2; omp set lock (&lock1); #pragma omp sections { #pragma omp section { for (...) /* bucle exterior */ { /* 1a pasada 3D-FWT */ omp set lock (&lock2); omp unset lock (&lock1); /* 2a pasada 3D-FWT */ /* cuantizaci´ on baja */ omp unset lock (&lock2); omp set lock (&lock1); } omp unset lock (&lock1); } #pragma omp section { for (...) /* bucle exterior */ { if (/* no es la primera pasada*/) { omp unset lock (&lock2); } omp set lock (&lock1); /* cuantizaci´ on alta */ omp set lock (&lock2); omp unset lock (&lock1); } omp unset lock (&lock2); } } }

int hilo esclavo (struct thr data *data) { for (...) /* bucle exterior */ { if (/* no es la primera iteraci´ on */) { pthread mutex unlock (&mutex2); } pthread mutex lock (&mutex1); /* cuantizaci´ on alta */ pthread mutex lock (&mutex2); pthread mutex unlock (&mutex1); } pthread mutex unlock (&mutex2); } void fwt (int rows, int cols, int frames, ...) { struct thr data data; pthread t hilo; pthread mutex lock (&mutex1); data.rows = rows; data.cols = cols; ...; pthread create (&hilo, NULL, (hilo esclavo, &data); for (...) /* bucle exterior */ { /* 1a pasada 3D-FWT */ pthread mutex lock (&mutex2); pthread mutex unlock (&mutex1); /* 2a pasada 3D-FWT */ /* cuantizaci´ on baja */ pthread mutex unlock (&mutex2); pthread mutex lock (&mutex1); } pthread mutex unlock (&mutex1); pthread join (hilo, NULL); }

Fig. 6. Fragmento de c´ odigo del esquema openmp2.

Fig. 5. Fragmento de c´ odigo del esquema pthreads2.

´ n y ana ´ lisis V. Evaluacio Estamos interesados en evaluar el rendimiento de cada una de las t´ecnicas anteriores tanto en cuanto al tiempo de ejecuci´on como en la facilidad de implementaci´on y la mantenibilidad del c´odigo. En la figura 7 se muestra el tiempo de ejecuci´on de las distintas implementaciones usando dos procesadores independientes, y usando un s´olo procesador con HyperThreading. r v7.1 Se ha usado el compilador de C++ de Intel para compilar y evaluar las distintas versiones del algoritmo. Para las pruebas con multiprocesadores se r XeonTM a 2 GHz con 2 proceha utilizado un Intel sadores. Para las pruebas con HyperThreading se ha utilizado el mismo equipo activando la capacidad de HyperThreading de uno de los dos procesadores y desactivando completamente el otro. En primer lugar, observamos que cuando obtenemos una mejora en las prestaciones usando varios procesadores tambi´en la obtenemos usando HyperThreading, y aunque la mejora es siempre mucho menor no deja de ser significativa. Como se ha mencionado en la secci´on IV, el esquema de paralelizaci´on utilizado permite que sea as´ı al realizar operaciones de distinto tipo para evitar contenci´on en las unidades funcionales compartidas del procesador. Las implementaciones openmp1 y pthreads1 ob-

Q

OP N LM IJ K

" ! "# "!  % ! "# % ! $ ! "# $!   ! "#  !  ! "# ! 

! "#

! 

% ! %& % ! %& $ !  ! % $



  

" ! 

')(* + , -. /0132 465/6. 7986-13. :


 

$ !  ! % 

 
   ?A@ BDC