Programación de múltiples dispositivos heterogéneos: El caso de Optical Flow

Programaci´on de m´ultiples dispositivos heterog´eneos: El caso de Optical Flow Sergio Alonso Pascual1, Arturo Gonzalez-Escribano2 Resumen— Los sistemas paralelos actuales son cada vez m´as heterog´eneos, con dispositivos de diferentes tipos y capacidades de c´omputo. Explotar m´ultiples dispositivos diferentes para una misma aplicaci´on sigue siendo un reto donde intervienen desde problemas t´ecnicos relacionados con sincronizar y comunicar diferentes dispositivos hasta problemas de reparto de carga y flexibilidad para ajustar el c´omputo a los recursos de la plataforma. En este trabajo estudiamos la programaci´on y adaptaci´on a plataformas heterog´eneas de HSOpticalFlow, una aplicaci´on de streaming orientada a estimar el movimiento aparente de objetos en una secuencia de im´agenes. Partiendo del c´odigo original en CUDA, presentamos la metodolog´ıa para implementarlo en forma de pipeline entre m´ultiples dispositivos utilizando el modelo de programaci´on Controller, y para introducir un mecanismo de reparto de carga que permite el ajuste cuando las capacidades de c´omputo son distintas. Esto permite no solo construir soluciones paralelas muy eficientes entre dispositivos similares, sino tambi´en aprovechar dispositivos de poca capacidad de c´omputo para aliviar la carga y aumentar la productividad de dispositivos mucho m´as potentes. Presentamos resultados de un estudio experimental utilizando varias GPUs de NVIDIA de diferentes arquitecturas y generaciones que muestran que nuestra soluci´on permite explotar de forma combinada varios dispositivos para reducir los tiempos de ejecuci´on y conseguir un mejor ratio de fotogramas por segundo. En concreto, los resultados muestran aceleraciones de 2x utilizando dos GPUs NVIDIA V100 y hasta 1,37x con una GPU NVIDIA A100 y tres GPUs Titan Black, que son aproximadamente 8 veces m´as lentas para esta aplicaci´on. Palabras clave— Programaci´on heterog´enea, Streaming, Equilibrio de carga, Flujo ´optico I. Introducci´ on ES cada vez m´as frecuente encontrar sistemas paralelos con un alto nivel de heterogeneidad. Tanto en grandes plataformas de c´omputo como en sistemas integrados on-chip. Aunque disponemos cada vez de un mayor n´umero de herramientas y propuestas para programar y manejar dispositivos heterog´eneos desde un ´unico c´odigo fuente (por ejemplo SYCL [1], Controller [2], o OpenH [3]), en la mayor´ıa de los casos a´un no est´an lo suficientemente maduras para explotar todo el potencial de estos sistemas con facilidad. A´un hay cuestiones complejas relacionadas con el movimiento eficiente y transparente de datos entre dispositivos de diferentes arquitecturas, la sincronizaci´on, el solapamiento de c´omputo y transferencias de dato, y carencias importantes en el reparto de carga y asignaci´on de recursos para ajustar el c´omputo a la plataforma de ejecuci´on. En general los modelos actuales nos aportan herramientas 1Dpto. de Inform´atica, Universidad de Valladolid, e-mail: [email protected] 2Dpto. de Inform´atica, Universidad de Valladolid, e-mail: [email protected] de programaci´on de prop´osito general, que deben ser utilizadas por el programador para construir sus soluciones a los problemas de reparto y equilibrio de carga teniendo en cuenta la estructura de la aplicaci´on y la plataforma objetivo. Un tipo de aplicaciones especialmente interesante y exigente para explotar sistemas altamente heterog´eneos son las aplicaciones de streaming o flujo de datos. Estas aplicaciones se caracterizan por recibir como entrada un stream, un canal por el que se reciben datos, que generalmente representan m´ultiples instancias de una estructura del mismo tipo. Por ejemplo, los frames o fotogramas de un flujo de v´ıdeo. Estas aplicaciones realizan una serie de tareas sobre cada instancia de datos, que muchas veces tiene diferente granularidad o necesidades de c´omputo. Adaptar estas aplicaciones a plataformas heterog´eneas aprovechando sus recursos puede resultar complejo. Hemos escogido como caso de estudio y motivaci´on la aplicaci´on HSOpticalFlow [4]. Se trata de una aplicaci´on de streaming orientada a estimar el movimiento aparente de objetos en una secuencia de im´agenes. Esta aplicaci´on est´a desarrollada en CUDA y est´a incluida en los ejemplos de dominio espec´ıfico suministrados con el toolkit de desarrollo [5]. HSOpticalFlow presenta un ejemplo sencillo pero caracter´ıstico de la estructura de aplicaciones basadas en ILS (Iterative Loop Stencil) multinivel, tambi´en conocidos como m´etodos multi-grid [6], [7]. Esta clase engloba todo un conjunto de aplicaciones cient´ıficas basadas en m´etodos finitos y resoluci´on de ecuaciones diferenciales parciales con m´etodos iterativos en varios niveles, que presentan estructuras similares a HSOpticalFlow, o con recorridos de niveles m´as complejos. En concreto lo que se conoce como ciclos VoW, donde el flujo sube y baja a trav´es de los niveles para conseguir una mayor precisi´on con una convergencia m´as r´apida. En cada nivel se trabaja con estructuras de datos m´as y m´as grandes con un nivel de detalle m´as fino. Por tanto la carga de trabajo de las tareas depende del nivel. HSOpticalFlow es un buen ejemplo y caso de estudio para investigar el reparto de carga y la adaptaci´on a sistemas heterog´eneos de esta clase de programas aplicados a una secuencia de entradas. En este trabajo presentamos la metodolog´ıa y t´ecnicas necesarias para introducir en aplicaciones de streaming y m´etodos multi-grid (como HSOpticalFlow) un mecanismo flexible de reparto y equilibrio de carga en plataformas heterog´eneas con dispositivos de diferentes capacidades de c´omputo. La soluci´on est´a dise˜nada para integrarse con facilidad en la estructura de c´odigos de streaming ya existentes, explotando las posibilidades de solapamiento de c´omputos y movimientos de memoria propios del pipeline paralelo t´ıpico en este tipo de aplicaciones. El mecanismo propuesto permite al programador decidir las etapas y carga que asigna a cada dispositivo simplemente cambiando valores en una matriz de asignaci´on de recursos. La comunicaci´on entre dispositivos y el solapamiento de c´omputo y comunicaci´on se realizan de forma transparente. La soluci´on propuesta permite equilibrar la carga de trabajo no s´olo en sistemas con dispositivos similares, sino tambi´en aprovechar dispositivos de poca capacidad de c´omputo para aliviar la carga de dispositivos mucho m´as potentes, aumentando la productividad y el ratio de entradas por segundo procesadas. Presentamos un estudio experimental comparando nuestra implementaci´on prototipo con la versi´on de referencia implementada directamente en CUDA. Se realizan comparaciones en una plataforma con dos GPUs iguales y en otra con GPUs de diferentes generaciones y capacidades de c´omputo. Los resultados muestran en concreto mejoras sobre la aplicaci´on de referencia de 2x utilizando dos GPUs NVIDIA V100 y hasta 1,37x con una GPU NVIDIA A100 y tres GPUs Titan Black, que son aproximadamente 8 veces m´as lentas para esta aplicaci´on, obteniendo eficiencias superiores al 90 % en la explotaci´on del paralelismo entre dispositivos. El resto del trabajo se organiza de la siguiente forma. La secci´on 2 comenta trabajo relacionado. La secci´on 3 presenta la propuesta y la implementaci´on de un prototipo usando el caso de estudio HSOpticalFlow. En la secci´on 4 se describe el estudio experimental desarrollado y se discuten los resultados del mismo. La secci´on 5 presenta las conclusiones y posible trabajo futuro. II. Background y trabajo relacionado Existen en la actualidad diversas propuestas de modelos de programaci´on paralela heterog´enea de alto nivel. Estos modelos intentan facilitar la programaci´on de aplicaciones portables a diferentes tipos de dispositivos y simplificar la utilizaci´on combinada de varios de ellos. Algunas propuestas parten de la idea de utilizar un c´odigo ´unico que se compila y adapta a diferentes plataformas. Por ejemplo, propuestas como el est´andar SYCL [1] se est´an consolidando gracias a la evoluci´on de los compiladores que lo implementan, como AdaptiveCpp [8] o el lenguaje DPC++ integrado en Intel oneAPI [9]. Sin embargo, estos compiladores no ofrecen a´un un soporte completo del est´andar y la eficiencia de los mecanismos utilizados, especialmente los relacionados con la migraci´on o interoperabilidad entre dispositivos de diferente naturaleza a´un no est´a garantizada. Un caso parecido lo presentan las implementaciones de las ´ultimas versiones del est´andar OpenMP, que en general necesitan extensiones conceptuales y nuevos sistemas de ejecuci´on espec´ıficos para sistemas heterog´eneos [10]. Otras propuestas menos conocidas o del ´ambito acad´emico incluyen por ejemplo el modelo Controller [2]. Todos estos modelos proveen de las herramientas necesarias para programaci´on de prop´osito general y soportan m´ultiples dispositivos heterog´eneos. Sin embargo, es responsabilidad del programador analizar la estructura de sus aplicaciones y generar el c´odigo adecuado para repartir y equilibrar la carga, adapt´andola a un sistema con diferentes tipos de dispositivos, en especial con diferentes capacidades de c´omputo. Algunos modelos, como FastFlow [11] o SkePU [12], se focalizan en generar desde expresiones de alto nivel el c´odigo para aplicaciones con diferentes patrones paralelos. Algunos de estos modelos, como FastFlow, incluyen patrones basados en la estructura de pipeline y streaming. Sin embargo, el reparto y equilibrio de carga para estructuras de tipo pipeline multinivel sobre dispositivos heterog´eneos de diversa naturaleza sigue siendo problem´atico. Algunos modelos de programaci´on heterog´enea, como Sigmoid [13], OpenH [3] o las extensiones anteriormente comentadas para OpenMP [10], incluyen soluciones para el reparto y equilibrio de carga integrados en el propio modelo o mecanismo de ejecuci´on. En general, estas soluciones gen´ericas est´an orientadas a equilibrar la carga partiendo el c´omputo en subtareas y reparti´endolas de forma din´amica bajo demanda con en esquema maestro-trabajadores o granja de tareas. En muchos casos, la sobrecarga del sistema din´amico de reparto y el trasiego de datos asociados a cada subtarea puede ser menos eficiente que una soluci´on adaptada a la aplicaci´on o plataforma. Especialmente en el caso de aplicaciones de streaming donde existe una estructura de ejecuci´on y dependencias preestablecida y conocida. Uno de los objetivos de este trabajo es que la soluci´on propuesta pueda integrarse con facilidad en la estructura de c´odigos de streaming ya existentes, utilizando tareas y transferencias con la misma granularidad del c´odigo original y explotando las posibilidades de solapamiento de c´omputos y movimientos de memoria propios de la estructura de pipeline paralelo t´ıpico en estas aplicaciones. Para ello nos apoyaremos en un modelo de programaci´on heterog´enea de prop´osito general, en concreto Controller. Este modelo ofrece funcionalidades parecidas a SYCL, pero utiliza un mecanismo para integrar directamente kernels escritos en los modelos de programaci´on de m´as bajo nivel suministrados por el vendedor de los dispositivos, c´omo por ejemplo CUDA, OpenCL, Hip, u OpenMP. El modelo incluye un sistema para detectar en tiempo de ejecuci´on las dependencias entre tareas y realizar de forma transparente las transferencias de memoria entre dispositivos necesarias para mantener la coherencia. Su sistema de ejecuci´on incluye un mecanismo muy eficiente de gesti´on de las sincronizaciones y transferencias de memoria entre dispositivos de diferente naturaleza [2], [14]. Controller es un sistema de programaci´on muy adecuado para construir sobre sus funcionalidades mecanismos de reparto y equilibrio de carga, que pueden integrar- Listado 1: Pseudoc´odigo del algoritmo usado para calcular el HSOpticalFlow. Las llamadas a funciones equivalen a lanzamientos de kernel (salvo swap). Los argumentos en azul son de entrada y los rojos de salida. 1// Crear versiones de menor resoluci ´on de ambas imagenes ( src y tgt) 2for ( lvl = nlvls - 1; lvl > 0; lvl --){ 3Downscale (src[lvl],src[lvl-1]); 4Downscale (tgt[lvl],tgt[lvl-1]); 5} 6// La estimaci ´on inicial (u, v) comienza en 0 7for ( lvl = 0; lvl < nlvls ; lvl ++) { 8for ( warp = 0, warp < nwarps ; warp ++) { 9// Distorsionar imagen objetivo en base a estimaci ´on actual (u, v) 10 WarpImage (tgt[lvl], u, v,dist); 11 // Calcular matrices de la ecuaci ´on a resolver 12 ComputeDerivatives(src[lvl], dist,Ix, Iy, Iz); 13 // Resolver la ecuaci ´on para du , dv 14 for (i = 0; i < nsolves ; i++) { 15 JacobiSolve (du0, dv0, Ix, Iy, Iz,du1, dv1); 16 swap (du0 , du1 ) 17 swap (dv0 , dv1 ) 18 } 19 // Actualizar estimaci ´on actual 20 add (u, du0,u); 21 add (v, dv0,v); 22 } 23 if(lvl < nlvls - 1){ 24 // Escalar soluci ´on (u, v) para usar en el siguiente nivel 25 Upscale(u,nu); 26 Upscale(v,nv); 27 swap (u , nu); 28 swap (v , nv); 29 } 30 } se en las aplicaciones de partida con poco esfuerzo de desarrollo. III. Propuesta de soluci´ on Esta secci´on describe la propuesta para incluir una abstracci´on simple y extrapolable a otros casos que permita al programador escoger c´omo se realiza en un sistema heterog´eneo el reparto de las tareas de una aplicaci´on de streaming en la que cada instancia en el flujo de datos se procesa con m´etodos iterativos, potencialmente con m´ultiples kernels y niveles de iteraci´on. A. Caso de estudio En este trabajo hemos escogido como caso de estudio y motivaci´on la aplicaci´on HSOpticalFlow, inclu´ıda en los ejemplos de dominio espec´ıfico suministrados con el toolkit de desarrollo de CUDA. Es en una implementaci´on de un m´etodo de flujo ´optico en 2D conocido como Hierarchical Horn and Schunck [4]. En el listado 1 se muestra el pseudoc´odigo del algoritmo aplicado por HSOpticalFlow. Este algoritmo minimiza una funci´on de energ´ıa mediante una aproximaci´on de diferencias finitas de la ecuaci´on de Euler-Lagrange correspondiente a este problema espec´ıfico. Emplea una estrategia multinivel, de grano grueso a fino, calculando primero la soluci´on para versiones de menor resoluci´on de las im´agenes y luego escalando sucesivamente la soluci´on obtenida en cada nivel para ser usada como punto de partida en el c´alculo del siguiente, con im´agenes de mayor resoluci´on. Para cada uno de estos niveles de Fig. 1: Diagrama de flujo de HSOpticalFlow. resoluci´on se realizan lo que en la terminolog´ıa del problema se denominan iteraciones de warp. En cada una de ellas partimos de una estimaci´on inicial de la soluci´on y calculamos el incremento necesario para mejorar esta estimaci´on. El c´alculo consiste en un n´umero fijo de iteraciones de un m´etodo de Jacobi, implementado como un ILS (Iterative Loop Stencil). Se aplica de forma paralela en cada punto un c´alculo que depende de los valores anteriores en los puntos vecinos. En la figura 1 se puede ver una representaci´on del flujo de tareas para comparar un par de fotogramas, utilizando cinco niveles de resoluci´on y tres iteraciones de warp en cada nivel. En el caso de la implementaci´on de referencia, las iteraciones de Jacobi que realiza cada iteraci´on de warp se puede configurar como argumento del programa. El c´omputo comienza en el nivel de resoluci´on m´as bajo (nivel 0), donde realiza de forma encadenada las iteraciones de warp con ese nivel de resoluci´on. Se utiliza una funci´on prolongation oupscale para generar, a partir del resultado de la ´ultima iteraci´on de warp, una imagen de mayor resoluci´on. Esta ´ultima es la entrada de la primera iteraci´on de warp del siguiente nivel. B. Reparto de carga La estructura iterativa y multinivel de HSOpticalFlow, cuando trabaja sobre una secuencia de im´agenes, proporciona oportunidades para repartir la carga de trabajo de diferentes formas entre varios dispositivos. La secuencia de im´agenes crea un flujo de datos continuo o pipeline a trav´es de la estructura de niveles e iteraciones de warp de HSOpticalFlow. Esta estructura de pipeline puede distribuirse entre varios dispositivos, repartiendo el trabajo a realizar para cada par de fotogramas entre ellos. De esta forma, cuando un dispositivo termina con su parte le pasa el resultado al siguiente dispositivo y puede comenzar con su parte de c´alculo para el siguiente par de fotogramas. Un adecuado reparto de la estructura del pipeline permite adem´as que el c´omputo y los movimientos de las estructuras de datos entre dispo- Listado 2: Ejemplo de la matriz de reparto de carga correspondiente a la asignaci´on mostrada en la figura 1. 1int lw2cid [ nlvls ][ nwarps ] = { 2{1, 1, 1} , 3{1, 1, 1} , 4{1, 1, 1} , 5{2, 3, 0} , 6{0, 0, 0}}; sitivos se solapen usando comunicaciones as´ıncronas. De esta forma, una vez que el pipeline est´a lleno las latencias de los movimientos de datos pueden quedar parcial o totalmente ocultas. En la figura 1 se muestra un posible ejemplo de reparto de carga asignando diferentes iteraciones de warp de diferentes niveles a cada dispositivo. Cada nivel tiene una carga de trabajo diferente y creciente con el ´ındice del nivel. La decisi´on m´as importante para esta aproximaci´on es elegir los puntos de corte en los que se cambia de un dispositivo a otro. Para ello hay b´asicamente tres opciones que implican una creciente complejidad de implementaci´on pero tambi´en una granularidad m´as fina para el control del equilibrio de carga entre dispositivos. 1. Partir s´olo entre niveles. 2. Partir entre iteraciones de warp en cualquier nivel. 3. Partir entre iteraciones de jacobi dentro de una iteraci´on de warp. Nuestras pruebas experimentales preliminares indican que repartiendo niveles enteros entre dispositivos de diferentes capacidades de c´omputo la granularidad es demasiado gruesa y el desequilibrio entre niveles no permite conseguir un buen equilibrio de carga en muchas situaciones. Por otra parte, la complejidad de programar un cambio de dispositivo entre iteraciones de Jacobi es alta. En este trabajo estudiamos el reparto de iteraciones de warp completas (segunda opci´on) que demuestra ser un punto intermedio en cuanto a complejidad de implementaci´on, pero permitiendo al mismo tiempo un control razonable de la carga en cada dispositivo. En nuestra soluci´on incluimos un sencillo mecanismo, a trav´es de la declaraci´on de una matriz de mapping o asignaci´on de recursos, con el que el programador puede escoger en qu´e dispositivo se ejecuta cada iteraci´on de warp de cada nivel. Para el caso de HSOpticalFlow la matriz tiene dos dimensiones. La primera tiene la cardinalidad del n´umero de niveles y la segunda el n´umero de iteraciones de warp por nivel. En el listado 2 se muestra un ejemplo de dicha matriz, en la que cada valor es el ´ındice de uno de los dispositivos disponibles en la m´aquina objetivo. C. Movimiento de datos Las iteraciones de warp que se ejecutan en dispositivos diferentes deben trabajar sobre espacios de memoria diferentes. Esto permite que puedan solaparse las diferentes partes del pipeline. Sin embargo, en los puntos de corte del pipeline, cuando dos iteraciones de warp consecutivas se han asignado a Listado 3: Pseudoc´odigo del pipeline de fotogramas usado. Las llamadas a funciones equivalen a lanzamientos de kernel (salvo swap). Los argumentos en azul son de entrada y los rojos de salida. 1tgt = loadFrame ( 0 ); 2for (i = 1; i < nFrames ; i++){ 3src = tgt ; 4tgt = loadFrame ( i ); 5ComputeFlow (src, tgt,u, v, ...) ; 6Norm(u, v); 7} dispositivos diferentes, los resultados parciales de la primera deben moverse o comunicarse de un dispositivo al siguiente. En nuestra soluci´on, las iteraciones de warp del mismo nivel asignadas al mismo dispositivo reutilizan la misma estructura de datos como entrada y salida. En un cambio de nivel dentro del mismo dispositivo la estructura de salida es diferente porque el tama˜no es distinto, y es la estructura que se utiliza como entrada en el siguiente nivel. En el caso de que dos iteraciones de warp consecutivas est´en asignadas a dispositivos diferentes, la salida de la primera es una estructura de datos diferente que se usa como entrada en la siguiente iteraci´on. Estas estructuras de datos de paso entre dispositivos son las ´unicas que tendr´an duplicado su espacio de memoria en ambos dispositivos y en el host. Esta ´ultima se utilizar´a como intermediario para realizar la transferencia de datos entre las im´agenes de memoria de los dos dispositivos. En la figura 2 se muestra un ejemplo. Para integrar esto en el c´odigo de una forma sencilla, utilizamos una matriz de punteros con valores para todos los niveles e iteraciones de warp. Cada iteraci´on utiliza el puntero correspondiente a su nivel y n´umero de iteraci´on como entrada y el puntero de su nivel y siguiente n´umero de iteraci´on como salida. En el caso de un cambio de nivel la salida es el puntero correspondiente a la primera iteraci´on del siguiente nivel. Al crear las estructuras de datos se inicializan estos punteros para que apunten a la estructura de datos correspondientes. D. Implementaci´on usando Controller Para construir un prototipo experimental que pueda trabajar f´acilmente con m´ultiples dispositivos heterog´eneos hemos trabajado con el modelo de programaci´on Controller [2]. D.1 Preparaci´on Partimos del c´odigo original de HSOpticalFlow provisto por NVIDIA en los ejemplos del toolkit de desarrollo de CUDA. La versi´on de referencia de CUDA utiliza extensivamente la memoria de texturas de las GPUs por sus beneficios relacionados con: (1) el modo de direccionamiento en espejo que solucionan problemas en el c´alculo de derivadas y accesos en los contornos; (2) la interpolaci´on bilineal que se utiliza en las operaciones de restricci´on, prolongaci´on y warping; y (3) mejorar la localidad de datos gracias a las cach´es de texturas [4]. Hemos incorporado al Fig. 2: Diagrama de las estructuras de datos usadas en cada iteraci´on de warp cuando la siguiente iteraci´on est´a asignada al mismo dispositivo y cuando est´a asignado a otro. modelo Controller funcionalidades para trabajar con este tipo de memorias. El c´odigo original est´a preparado para ejecutarse s´olo con un par de fotogramas de entrada. Para tener la aplicaci´on de streaming completa que trabaja sobre una secuencia de im´agenes, a˜nadimos un bucle externo para leer fotogramas (ver el listado 3). Para medir con m´as exactitud los tiempos de trabajo del algoritmo principal, en lugar de escribir los resultados en un fichero, simplemente calculamos la norma del resultado de cada par de fotogramas. Esto permite que en cualquier versi´on que se modifique a partir de esta se pueda comprobar la correcci´on con un buen nivel de confianza haciendo una sencilla comparaci´on con los resultados de las normas en la versi´on de referencia. D.2 Portar kernels Para portar un kernel de CUDA al modelo Controller lo primero es cambiar los punteros a estructuras de datos que representan las matrices en el kernel por HitTiles. Este tipo representa una estructura utilizada en el modelo Controller para manejar estructuras de datos junto con metadatos que las describen e informaci´on sobre el estado de la memoria en el host o el dispositivo. Esto permite al modelo Controller detectar la necesidad de movimientos de datos para mantener la coherencia entre las diferentes copias de la memoria de un HitTile en el host o en diversos dispositivos. En los prototipos de los kernels en el modelo Controller se indica informaci´on sobre el rol de entrada o salida de un par´ametro HitTile para poder detectar de forma impl´ıcita la necesidad de dichos movimientos. El segundo paso consiste en sustituir los ´ındices nativos de CUDA por su contrapartida en Controller y lo mismo para los accesos a la memoria, que en Controller se realizan con unas macro funciones que reciben como par´ametros el HitTile y los ´ındices. En general, esto resulta en una ligera simplificaci´on del c´odigo del kernel al estar los tama˜nos de los espacios de memoria integrados en las HitTiles y los ´ındices de hilo globales calculados impl´ıcitamente por Controller. D.3 Portar c´odigo de host Portar el algoritmo principal a Controller es bastante directo. Controller provee de un objeto para acceder y manejar cada dispositivo disponible en la plataforma que se haya declarado visible en el momento de ejecutar el programa. Se crean objetos HitTile para cada estructura de datos, asociando im´agenes de memoria en el host y en cada dispositivo donde sea necesaria para realizar c´omputos. Para cada par de fotograma tenemos dos operaciones que se ejecutan en el host (la carga del nuevo fotograma y el c´alculo de la norma). Para asegurar que estas operaciones sean independientes y que las operaciones del pipeline se puedan solapar debidamente, lanzamos una de estas operaciones como host task y la otra como un kernel de CPU en modo tarea. Este mecanismo de Controller permite utilizar parte de los cores de la CPU como un dispositivo m´as, independiente del flujo de ejecuci´on del host. Implementar el mecanismo de reparto de carga en la versi´on de Controller es sencillo. Con un bucle que recorre la matriz de reparto se van creando los HitTiles guardando punteros a los mismos en un array de dos dimensiones con tama˜nos similares a la matriz de reparto. Los HitTiles se generan con im´agenes en memoria s´olo en un dispositivo, o en el host y dos dispositivos cuando haya una transici´on entre dos iteraciones de warp asociadas a dos dispositivos diferentes. Las llamadas a los kernels usan el array de punteros y los ´ındices adecuados para escoger los par´ametros de entrada y salida adecuados al nivel e iteraci´on de warp en cada llamada. El mecanismo de movimiento de datos impl´ıcito de Controller realiza autom´aticamente los movimientos de memoria necesarios de forma as´ıncrona para permitir el solapamiento de c´omputo y comunicaciones de una forma eficiente [2]. IV. Estudio experimental En esta secci´on se describe un estudio experimental realizado para verificar la eficiencia de la soluci´on propuesta. 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 3 0 0 0 0 1 1 1 1 1 1 2 3 0 0 Fig. 3: Matrices de reparto de carga utilizadas en la experimentaci´on. Las filas son niveles y las columnas iteraciones de warp. El n´umero indica el identificador de dispositivo. En manticore los 2 dispositivos son V100 y en gorg´on el 0 es la A100 y el resto Titan Blacks A. Entorno y dise˜no de experimentos El estudio experimental se ha llevado a cabo en las m´aquinas manticore ygorg´on del cl´uster de investigaci´on del grupo Trasgo, que tienen las siguientes caracter´ısticas: Manticore:  Procesador: 2x Intel(R) Xeon(R) Platinum 8160 CPU @ 2,10 GHz  Memoria RAM total: 512 GB DDR4.  2x NVIDIA Tesla V100 32 GB HBM2 GPU.  2x AMD Vega 10 XT Radeon PRO WX 9100 GPU. Gorg´on:  Procesador: 2x AMD EPYC 7713 CPU @ 2,0 GHz  Memoria RAM total: 512 GB DDR4.  1x NVIDIA A100 40 GB HBM2 GPU.  3x NVIDIA GeForce GTX Titan Black 6 GB GDDR5 GPU. El sistema operativo de las m´aquinas es la distribuci´on de Linux CentOS versi´on 7.9.2009. Todos los programas se compilan con NVCC y GCC v10.3 y se lanzan desde un frontend usando slurm. La versi´on de CUDA instalada es 11.3. El estudio experimental se realiza sobre secuencias de diferente longitud en fotogramas de un video en resoluci´on 8K (7680×4320), midiendo el tiempo que se tarda en calcular el flujo ´optico entre pares de fotogramas consecutivos. Se realizan pruebas usando las diferentes versiones de la aplicaci´on y con diferentes configuraciones de dispositivos que se detallan a continuaci´on: Ref: Versi´on de CUDA basada en la referencia, usa un solo dispositivo. Ref Pinned: Igual que la anterior, pero reservando la memoria del host como pinned para obtener transferencias de memoria m´as r´apidas Ctrl: Versi´on utilizando el modelo Controller. Estudiamos ejecuciones con un solo dispositivo y con m´ultiples dispositivos realizando reparto de carga. Para los experimentos se utilizan primero los valores de niveles e iteraciones de warp por defecto de la aplicaci´on original, cinco y tres respectivamente, y 500 iteraciones de Jacobi en cada iteraci´on de warp. En un segundo experimento se usan 5 niveles, 2 iteraciones de warp y 750 iteraciones de Jacobi. Para los casos de m´ultiples dispositivos se han usado estas matrices de reparto indicadas en la figura 3. Para cada escenario se ejecutan 30 repeticiones, 1 10 100 1000 2 5 10 20 40 Time log scale (sec) N log scale (Frames) Ref V100 Ref Pinned V100 Ctrl 1xV100 Ctrl 2xV100. HSOpticalFlow (2 x V100) Fig. 4: Tiempos de ejecuci´on respecto al n´umero de fotogramas en manticore usando las V100 ya que este es un tama˜no de muestra suficientemente grande para que el Teorema Central del L´ımite se considere aplicable. Los resultados presentados son la media de los tiempos de ejecuci´on tras haber eliminado los outliers, es decir, aquellos resultados por debajo o por encima de la media ±1,5×IQR (rango intercuart´ılico). En esta aplicaci´on y para la resoluci´on usada, la ocupaci´on y uso de los recursos de una GPU es pr´acticamente completa. Hemos comprobado experimentalmente que intentar usar la misma GPU para computar varios pares de fotogramas simult´aneamente no reporta beneficios. B. Resultados En esta secci´on discutimos las observaciones obtenidas a la vista de los resultados. Para mostrarlos de forma resumida presentamos gr´aficas con el n´umero de fotogramas de la secuencia en el eje x y tiempo de ejecuci´on (con escala logar´ıtmica) en el eje y. En la figura 4 se muestran los tiempos de ejecuci´on de las diferentes versiones de HSOpticalFlow en la m´aquina manticore, dotada con dos GPUs NVIDIA V100. Las versiones de referencia pueden aprovechar s´olo uno de los dos dispositivos. La versi´on de referencia que usa memoria pinned siempre es ligeramente m´as eficiente que la original, ya que las transferencias de memoria son menos costosas. Esto se observa en las ejecuciones de la versi´on de referencia en todos los escenarios. Se observa que la versi´on con Controller es ligeramente menos eficiente para un s´olo par de fotogramas, ya que la construcci´on del pipeline es innecesario y no hay posibilidades de solapar ning´un c´omputo. Sin embargo, en cuanto hay un mayor n´umero de fotogramas en la secuencia, incluso la versi´on de Controller que s´olo explota un dispositivo es ligeramente m´as eficiente que la referencia con memoria pinned, hasta un 5 % menos de tiempo de ejecuci´on total. Al contrario que en la versi´on de referencia, con el modelo de controller se est´an solapando las tareas de lectura de fotograma y c´alculo de la norma de resultado en el host con el c´omputo en el dispositivo. Adem´as, Controller usa internamente un mecanismo de comunicaciones as´ıncronas en diferentes streams controlados por eventos que es muy 1 10 100 1000 2 5 10 20 40 Time log scale (sec) N log scale (Frames) Ref Pinned TB Ctrl 1xTB Ref A100 Ref Pinned A100 Ctrl 1xA100 Ctrl 1xA100 + 3xTB HSOpticalFlow (1 x A100, 3 x Titan Black) Fig. 5: Tiempos de ejecuci´on respecto al n´umero de fotogramas en gorg´on usando una A100, una Titan Black, o la A100 con tres Titan Black eficiente. En la tabla izquierda de la figura 3, se muestra la matriz de asignaci´on de dispositivos utilizada en los experimentos con las dos V100 de manticore. En la figura 8 se muestran la aceleraci´on obtenida al usar las 2 V100 en comparaci´on con la versi´on de Controller que usa una sola GPU, se observa como a partir de un m´ınimo n´umero de fotogramas, aproximadamente cinco, el pipeline ya est´a lleno y a partir de ese momento la versi´on que explota los dos dispositivos consigue un muy buen equilibrio de carga y un muy buen solapamiento de c´omputo y transferencias de memoria. Se consigue una aceleraci´on de 1,85x con los dos dispositivos, lo que indica una eficiencia del 92,5 % en la explotaci´on del paralelismo entre dispositivos. Comparado con la versi´on de referencia con memoria pinned se consigue una mejora de m´as de 2x, debido a las mejoras introducidas por el solapamiento de las tareas de host con el c´omputo del dispositivo y el mecanismo interno de Controller para la gesti´on de los streams y eventos. En la figura 5 se muestran los tiempos de ejecuci´on de las diferentes versiones de HSOpticalFlow en la m´aquina gorg´on, dotada con una GPU NVIDIA A100 y tres antiguas GPUs NVIDIA Titan Black de arquitectura Kepler. En los resultados se puede observar que tanto en la versi´on de referencia como en la de Controller la ejecuci´on en una ´unica Titan Black es unas 8 veces m´as lenta que en la A100. Concretamente, la referencia con la Titan Black tarda 462,38 segundos y con la A100 tarda 58,64 segundos para 40 fotogramas. Al igual que en el caso de utilizar una ´unica V100 en manticore, la ejecuci´on de la versi´on de Controller con s´olo la A100 en cuanto hay un n´umero m´ınimo de fotogramas en la secuencia para llenar el pipeline es ligeramente m´as eficiente que las versiones de referencia. En el caso de intentar utilizar tanto la A100 como las tres Titan Black con el reparto indicado en ta tabla central de la figura 3, para s´olo dos fotogramas el resultado es, como era esperable, mucho peor. Se est´an procesando etapas en las GPUs Titan Black, mucho m´as lentas que la A100, sin posibilidad de explotar en paralelo o solapar ninguna otra acci´on. De nuevo, en cuanto hay una secuencia m´ıni1 10 100 2 5 10 20 40 Time log scale (sec) N log scale (Frames) Ref Pinned A100 Ctrl 1xA100 Ctrl 1xA100 + 3xTB HSOpticalFlow Alt Params (1 x A100, 3 x Titan Black) Fig. 6: Tiempos de ejecuci´on respecto al n´umero de fotogramas, versi´on con par´ametros alternativos (5 niveles 2 warp 750 solves) en gorg´on ma (cinco fotogramas o m´as) el pipeline est´a lleno y se pueden explotar las posibilidades de ejecuci´on paralela y mecanismos de solapamiento de c´omputo y transferencias de memoria. Como se puede ver en la figura 7, esto resulta en una aceleraci´on sostenida con respecto a la versi´on de Controller que usa la A100 de 1,2x. Al ser las Titan Black unas 8 veces m´as lentas que la A100, el pico te´orico de aceleraci´on ser´ıa aproximadamente 1,35x. La mejora obtenida no es ideal, con una eficiencia del 89 %. Esto se debe a que el equilibrio de carga no es demasiado bueno, ya que para el grado de granularidad escogido la carga de las iteraciones de warp en cada nivel no permite dividir la computaci´on de forma perfectamente equilibrada. Se puede aplicar un peque˜no cambio en la configuraci´on de los niveles e iteraciones de warp por nivel, como se muestra en la tabla de reparto de carga que se muestra a la derecha de la figura 3. Con esta configuraci´on se consigue un nivel de convergencia similar a la obtenida con la configuraci´on anterior, sin alterar significativamente los tiempos de ejecuci´on de la referencia (menos del 0,5 %). En la figura 6 se muestran los tiempos de ejecuci´on de las diferentes versiones de HSOpticalFlow en la m´aquina gorg´on con la nueva configuraci´on de niveles e iteraciones de warp por nivel. Con esta configuraci´on se puede conseguir un mejor equilibrio de carga. En la figura 7 podemos ver que con estos par´ametros alternativos se alcanza una aceleraci´on de 1,26x en comparaci´on con usar solo la A100 en Controller, lo que corresponde a una eficiencia del 93,5 %. Esto equivale a una mejora de 1,37x con respecto a la aplicaci´on de referencia usando la A100 y memoria pinned. V. Conclusiones En este trabajo se presenta una sencilla metodolog´ıa y mecanismos para introducir la explotaci´on de m´ultiples dispositivos heterog´eneos, potencialmente con diferentes capacidades de c´omputo. Esta propuesta permite equilibrar la carga de trabajo en una clase representativa de aplicaciones de streaming o flujo de datos basadas en m´etodos multi-grid. Se ha utilizado como caso de estudio la aplicaci´on HSOpticalFlow, que estima el movimiento aparente de obje- 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 2 5 10 20 40 Speedup N log scale (Frames) alt params def params HSOpticalFlow Alt Params speedup (1 x A100, 3 x Titan Black) Fig. 7: Incremento de aceleraci´on respecto al n´umero de fotogramas en gorg´on usando la A100 y las Titan Black en comparaci´on con la versi´on de Controller usando solo la A100 0.8 1 1.2 1.4 1.6 1.8 2 2 5 10 20 40 Speedup N log scale (Frames) Ctrl 2xV100 HSOpticalFlow speedup (2 x V100) Fig. 8: incremento de aceleraci´on respecto al n´umero de fotogramas en manticore usando las dos V100 en comparaci´on con la versi´on de Controller usando solo una V100 tos en una secuencia de im´agenes. Se describe como modificar la aplicaci´on para introducir los mecanismos propuestos e implementarla con el modelo de programaci´on heterog´enea Controller. La aplicaci´on resultante permite ejecutar la aplicaci´on como un pipeline, escogiendo con una sencilla configuraci´on qu´e fases del c´omputo se realizan en cada posible dispositivo. Esto permite al programador equilibrar la carga entre los diferentes elementos de c´omputo. El mecanismo propuesto y el modelo de programaci´on Controller crean un eficiente solapamiento de c´omputo y comunicaciones de forma transparente. Se presenta un estudio experimental usando como punto de partida la aplicaci´on de referencia incluida en el toolkit de desarrollo de CUDA y una versi´on programada con Controller y los mecanismos propuestos. Los resultados muestran que la estructura de pipeline y el mecanismo de reparto de carga introducidos permiten conseguir una excelente explotaci´on del paralelismo entre dispositivos a partir de un n´umero muy reducido de fotogramas en la secuencia. Adem´as, los mecanismos internos del modelo de programaci´on Controller para la sincronizaci´on y movimientos de datos, no s´olo son transparentes y simplifican el desarrollo de este tipo de soluciones, sino que adem´as son muy eficientes y permiten aprovechar las posibilidades de solapamiento de c´omputo y comunicaciones sin necesidad de una intervenci´on por parte del programador. Como trabajo futuro se ha planteado estudiar la aplicaci´on de los mecanismos propuestos en otras aplicaciones y contextos, explorar su uso con otros modelos de programaci´on heterog´enea y considerar la introducci´on transparente de diferentes niveles de granularidad para permitir una mayor precisi´on en el equilibrio de carga. Agradecimientos El presente trabajo es parte de la actuaci´on PID2022-142292NB-I00 (Proyecto de Generaci´on de Conocimiento 2022), financiada por MICIU/AEI /10.13039/501100011033 y por FEDER, UE. Tambi´en se ha recibido el soporte del Programa Investigo del Servicio P´ublico de Empleo Estatal, Convocatoria para la Contrataci´on de Personal Investigador, financiado por la Uni´on Europea-NextGenerationEU. Las plataformas de experimentaci´on han sido financiadas parcialmente por el programa NVIDIA Academic Hardware Grant Program. Referencias [1] The Khronos SYCL Working Group, “Sycl 2020 specification (revision 8),” Tech. Rep., The Khronos Group, 2023. [2] Yuri Torres, Francisco J. And´ujar, Arturo GonzalezEscribano, and Diego R. Llanos, “Supporting efficient overlapping of host-device operations for heterogeneous programming with ctrlevents,” Journal of Parallel and Distributed Computing, vol. 179, pp. 104708, 2023. [3] Simon Farrelly, Ravi Reddy Manumachu, and Alexey L. Lastovetsky, “Openh: A novel programming model and api for developing portable parallel programs on heterogeneous hybrid servers,” IEEE Access, vol. 12, pp. 23666– 23694, 2024. [4] M. Smirnov, “Optical flow estimation with cuda,” White paper, NVIDIA, 2013. [5] NVIDIA, “Cuda samples: Hsopticalflow,” GitHub, on https://github.com/NVIDIA/cuda-samples/tree/ master/Samples/5_Domain_Specific/HSOpticalFlow. [6] M.T. Heath, Scientific Computing: An Introductory Survey, McGraw Hill, 1997. [7] M.J. Quinn, Parallel Computing: Theory and Practice, McGraw-Hill, 1993. [8] AdaptiveCPP contributors, “Adaptivecpp,” GitHub, on https://github.com/AdaptiveCpp/AdaptiveCpp. [9] James Reinders, Ben Ashbaugh, James Brodman, Michael Kinsner, John Pennycook, and Xin Tian, “Data parallel c++,” 2023. [10] Marc Gonz´alez Tallada and Enric Morancho, “Compute units in openmp: Extensions for heterogeneous parallel programming,” Concurrency and Computation: Practice and Experience, vol. 36, no. 1, pp. e7885, 2024. [11] Marco Danelutto, Tiziano De Matteis, Daniele De Sensi, Gabriele Mencagli, Massimo Torquati, Marco Aldinucci, and Peter Kilpatrick, “The rephrase extended pattern set for data intensive parallel computing,” International Journal of Parallel Programming, vol. 47, no. 1, pp. 74– 93, Feb. 2019. [12] August Ernstsson, Lu Li, and Christoph Kessler, “Skepu 2: Flexible and type-safe skeleton programming for heterogeneous parallel systems,” International Journal of Parallel Programming, vol. 46, no. 1, pp. 62–80, feb 2018. [13] Borja P´erez, Esteban Stafford, Jos´e Luis Bosque, and Ramon Beivide, “Sigmoid: An auto-tuned load balancing algorithm for heterogeneous systems,” Journal of Parallel and Distributed Computing, vol. 157, no. C, pp. 30–42, nov 2021. [14] Sergio Alonso Pascual, “Modelo de ejecuci´on y sincronizaci´on en m´ultiples dispositivos heterog´eneos,” Trabajo fin de m´aster (master thesis), Departamento de Inform´atica, Facultad de Inform´atica de A Coru˜na, Marzo 2023.