Planificador de tareas para un modelo de programación de memoria global disjunta para

clusters con aceleradores basados en FPGAs

Juan Antonio López Mendoza

Director: Daniel Jimenez Gonzalez Co-Director: Carlos Alvarez Martinez Ponente: Xavier Martorell Bofill

Facultad de Informática de Barcelona (FIB) Universidad Politécnica de Cataluña (UPC) - BarcelonaTech

Abril 2018

Glosario Acelerador: Dispositivo hardware diseñado para mejorar el rendimiento general de un computador, permitiendo ejecutar tareas que de otra forma serían una carga para el resto de componentes. Un buen ejemplo es una unidad de procesamiento gráfico (GPU). FPGA: Field-programmable gate array. Circuito integrado a ser configurado por el usuario o un diseñador después de su producción. La configuración de un FPGA se hace generalmente mediante el uso de un lenguaje de descripción hardware. HPC: High performance computing. Se refiere a la práctica de agrupar poder de cómputo de tal forma que se pueda obtener un mejor rendimiento de lo que se podría obtener mediante el uso de un computador corriente, esto se hace con la intención de resolver problemas grandes. Worker: Es el proceso dentro de un cluster que se encarga de ejecutar las tareas que se le asignen. Un computador o cluster tiene lo que es llamado un pool de workers por los cuales va distribuyendo las tareas. En el caso de un cluster un worker no es necesariamente un nodo del sistema, puede haber más de uno por nodo. Y lo mismo pasa para cada thread físico del nodo, un worker tampoco tiene que estar asignado a un thread aunque sí es ideal que no hayan dos workers compartiendo un mismo thread. Pragma: Es una construcción del lenguaje de programación que permite especificarle al compilador cómo procesar las líneas de código especificadas. Task dependency graph (TDG): Es un grafo acíclico dirigido donde cada arista del grafo representa precedencia entre dos nodos del grafo. Como condición para que suceda un evento sobre un nodo tiene que haberse cumplido el evento para todos los nodos predecesores. En este trabajo el evento sería poder ejecutar la tarea en un worker.

Resumen Debido al costo de los sistemas de cómputo de alto rendimiento, es necesario desarrollar herramientas y nuevos métodos para reducir este gasto lo más posible. Un componente prometedor para aumentar el rendimiento de estos sistemas son los FPGAs. Gracias a sus características de reconfiguración de su propio Hardware, se pueden implementar aceleradores que reduzcan el tiempo de ejecutar aplicaciones específicas. De esta forma, aunque para una configuración similar un FPGA sea menos eficiente que un acelerador de un solo propósito, no hace falta afrontar los costes prohibitivos de fabricarlos. Este trabajo tiene como finalidad mejorar las herramientas disponibles para el uso de FPGAs en entornos de computación distribuida. Otro objetivo del trabajo es estudiar distintas políticas de planificación estáticas de tareas y analizar los resultados.

Abstract Given the high cost of high performance computing systems (HPCs), there is a need to develop new tools and methods that enable the creation of low-cost alternatives. Field programmable gate arrays are a promising component to increase the performance of these systems. Thanks to their self-reconfiguration hardware properties, we can implement accelerators the reduce the execution time of specific applications. This way, even if the FPGA is less efficient then single purpose accelerators for specific applications, we can bypass the prohibitive costs of fabrication. The aim of this work is to improve the tools available for the use of FPGA in distributed computation environments. Another objective is to study the different statistic planification politics and analyze their results.

Contenido 1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Evolución del mercado HPC . . . . . . . . . . . . . . 1 1.1.2 OmpSs y otros modelos de programación . . . . . . . 4 1.1.5 OmpSs y grafos de dependencias de tareas . . . . . . . 5 1.2 Actores implicados . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1 Desarrollador . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Beneficiarios . . . . . . . . . . . . . . . . . . . . . . 7

2 Formulación del problema y objetivos . . . . . . . . . . . . . 8 2.1 Formulación del problema y objetivos . . . . . . . . . . . . 8

2.2 Diseño de políticas de planificación . . . . . . . . . . . . . 8 2.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Alcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Obstáculos . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Metodología y rigor . . . . . . . . . . . . . . . . . . . . . . . 12 4.1 Métodos de trabajo . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Herramientas de seguimiento . . . . . . . . . . . . . . . . . 12 4.3 Método de validación . . . . . . . . . . . . . . . . . . . . . 12

5 Programa de trabajo . . . . . . . . . . . . . . . . . . . . . . . 13 5.1 Etapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.1.1 Integrar OmpSs@FPGA y OmpSs@Cluster . . . . . . 13 5.1.2 Familiarizarse con el planificador de OmpSs . . . . . 14 5.1.3 Hacer un modelo de cluster para emular ejecuciones . 14 5.1.4 Diseñar políticas de planificación sobre el modelo. . . 15 5.1.5 Redacción de la memoria y documentación . . . . . . 15 5.2 Desviaciones eventuales en la planificación . . . . . . . . . 16 5.3 Valoración temporal . . . . . . . . . . . . . . . . . . . . . 16 5.3.1 Tiempo estimado . . . . . . . . . . . . . . . . . . . 17 5.3.2 Tiempo real . . . . . . . . . . . . . . . . . . . . . . 17 5.3.4 Diagrama GANTT estimado . . . . . . . . . . . . . . 18 5.3.4 Diagrama GANTT real . . . . . . . . . . . . . . . . . 18

6 Identificación y estimación de los costos . . . . . . . . . . . . . 19 6.1 Presupuesto del proyecto . . . . . . . . . . . . . . . . . . . . 19 6.1.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . 19 6.1.2 Software . . . . . . . . . . . . . . . . . . . . . . . . 20 6.1.3 Recursos humanos. . . . . . . . . . . . . . . . . . . . 20 6.1.4 Costos inesperados. . . . . . . . . . . . . . . . . . . . 21 6.1.5 Costos indirectos . . . . . . . . . . . . . . . . . . . . 21 6.1.6 Presupuesto total . . . . . . . . . . . . . . . . . . . . 22 6.2 Control de la gestión de costos . . . . . . . . . . . . . . . . 23 6.2.1 Desviación del presupuesto de recursos humanos . . . . 23 6.2.2 Desviación del presupuesto de gastos indirectos . . . . 24

7 Sostenibilidad y compromiso social . . . . . . . . . . . . . . . 25 7.1 Dimension social . . . . . . . . . . . . . . . . . . . . . . . . 25 7.2 Dimension economica . . . . . . . . . . . . . . . . . . . . . 25 7.3 Dimension ambiental . . . . . . . . . . . . . . . . . . . . . . 26

8 Entorno de trabajo . . . . . . . . . . . . . . . . . . . . . . . . 27 8.1 Grafos de prueba . . . . . . . . . . . . . . . . . . . . . . . . 27 8.2 Modelo de cluster . . . . . . . . . . . . . . . . . . . . . . . . 30

9 Políticas de planificación . . . . . . . . . . . . . . . . . . . . . 33 9.1 Políticas agnósticas a la arquitectura . . . . . . . . . . . . . . . 34

9.1.1 Algoritmos de selección de recursos . . . . . . . . . . . . 34 9.1.2 Politica basica . . . . . . . . . . . . . . . . . . . . . . 36

9.1.2.1 Resultados . . . . . . . . . . . . . . . . . . . . 36 9.1.3 Políticas de prioridad . . . . . . . . . . . . . . . . . . . 39

9.1.3.1 Prioridad por camino critico . . . . . . . . . . . . 39 9.1.3.2 Prioridad por trabajo restante . . . . . . . . . . . 40 9.1.3.3 Resultados . . . . . . . . . . . . . . . . . . . . . 41 9.2 Políticas conscientes de la arquitectura . . . . . . . . . . . . . 44 9.2.1 Políticas de búsqueda global . . . . . . . . . . . . . . . . 44 9.2.1.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . 47 10 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 11 Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 12 Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Lista de figuras 1.1 La brecha tecnológica . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Tipos de supercomputadores en el Top 500 (2014) . . . . . . . . 2

1.3 Grafo de dependencia de tareas de un programa wavefront . . . 6 1.4 TDG y una planificación generada por el emulador de cluster . 9 5.1 GANTT inicial . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 GANTT real . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.1.1 TDG de un algoritmo wavefront . . . . . . . . . . . . . . . . 27 8.1.2 TDG de un algoritmo de factorización de cholesky . . . . . . 28 8.1.3 TDG de un algoritmo de multiplicación de matrices . . . . . 29 8.2.1 Política solapada sobre una topología de cholesky . . . . . . 31 8.2.2 Visualización política en cluster sobre una topología de cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 9.1.1 Comparación entre selección de nodos usando la política básica sobre una topología de wavefront . . . . . . . . . . . 36 9.1.2 Comparación entre selección de nodos usando la política básica sobre una topología de multiplicación de matrices . . 37 9.1.3 Comparación entre selección de nodos usando la política básica sobre una topología de cholesky . . . . . . . . . . . . 37 9.1.4 Comparación entre selección de nodos usando la política básica sobre una topología de cholesky aumentando el tamaño de los datos con 4961 tareas . . . . . . . . . . . . . . . . . . 38 9.1.5 Comparación entre selección de nodos usando políticas de prioridad sobre una topología de wavefront . . . . . . . . . 41 9.1.6 Comparación entre selección de nodos usando políticas de prioridad sobre una topología de multiplicación de matrices . 42 9.1.7 Comparación entre selección de nodos usando políticas de prioridad sobre una topología de factorización de cholesky . 42 9.1.8 Comparación entre selección de nodos usando políticas de prioridad sobre una topología de factorización de cholesky con aumento de datos con 4961 tareas . . . . . . . . . . . . 43 9.2.1 Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella. Topología wavefront 47 9.2.2 Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella cuando el tiempo de transferencia de datos aumenta. Topología wavefront 9 tareas. . . . . . . . . . . . . . . . . 48 9.2.2 Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella cuando el tiempo de

transferencia de datos aumenta. Topología cholesky 11 tareas 48

Introducción

1.1 Contexto 1.1.1 Evolución del mercado HPC En los últimos años, la demanda de procesamiento de las aplicaciones ha sobrepasado ampliamente la capacidad de cómputo que unidades de procesamiento de propósito general pueden ofrecer [1], lo que a generado una brecha tecnológica entre demanda y capacidad como se representa en la Figura 1.1. Para acortar esta brecha, el diseño de preferencia de los sistemas HPC actuales consiste en hacer uso de sistemas multiprocesadores. Figura 1.1. Brecha tecnológica

Los sistemas multiprocesadores se pueden dividir en dos categorías dependiendo de cómo estén interconectados entre ellos con la memoria del sistema. Los sistemas de memoria compartida son aquellos donde las CPUs pueden acceder a toda la memoria disponible en el sistema, y por lo tanto, son capaces comunicarse entre ellas a través de las regiones de memoria compartida. Los sistemas de memoria distribuida son aquellos donde cada conjunto de CPUs solo puede acceder a sus respectivas regiones de memoria privada, para comunicarse entre ellos hace falta un subsistema de comunicación que los interconecte y así pasar información a lo largo del sistema.

1

Con el paso del tiempo los computadores más potentes del mundo han estado cambiando hacia diseños de memoria distribuida. Esto es así dado que el rendimiento de los sistemas de memoria compartida no son económicos, no escalan bien en términos de precio con respecto a la capacidad de cómputo proporcionada. Figura 1.2. Tipos de supercomputadores en el Top 500 (2014)

Recientemente se han estado añadiendo aceleradores al diseño de supercomputadores para llevar un paso más allá a estos sistemas. Estos aceleradores tienen un conjunto de instrucciones distinto del procesador principal que permite optimizar tareas específicas. Tal es el caso de las GPUs, hasta hace poco cuatro de los supercomputadores en el top 10 tenían un sistema basado en GPUs [3].

2

El caso de las GPUs es particular porque sirven para optimizar tipos de tareas muy comunes. Tener un acelerador por cada tipo de aplicación no es viable, la diversidad de aplicaciones y el tiempo para fabricar aceleradores hacen este enfoque no viable económicamente. No obstante, existen dispositivos llamados Field-Programmable Gate Array (FPGA) que representan una alternativa prometedora para implementar flexiblemente aceleradores. Estos dispositivos disponen de un hardware reprogramable para cambiar el conjunto de instrucciones, de esta forma se puede programar aceleradores dinámicamente. La utilidad de aceleradores basados en FPGAS es un tema de investigación reciente [4].

3

1.1.2 OmpSs y otros modelos de programación Sólo algunos programadores muy especializados poseen el conocimiento para ejecutar códigos de producción en sistemas distribuidos. Es por esta razón que existen distintos modelos de programación para facilitar el trabajo a los desarrolladores. Un modelo de programación puede ser un lenguaje o una extensión de uno ya existente, su finalidad es hacer más fácil la programación de aplicaciones distribuidas por medio de instrucciones abstractas. La calidad de un lenguaje de programación puede ser medido por el rango de problemas que puede expresar, las diferentes arquitecturas que soporta y su rendimiento. Algunos modelos de programación facilitan la comunicación entre nodos pero aún dejan mucho por hacer a manos del programador, tal es el caso de MPI [7]. Este tipo de modelos es propenso a errores ya que se necesita un buen conocimiento de conceptos de programación distribuida, otro inconveniente es que tanto la distribución de datos y sincronización debe ser manejada explícitamente. Hay un intercambio entre control y facilidad de programación. Otros modelos de programación fueron planeados con la intención de hacer transparente varios elementos de la programación distribuida. Dos tipos de modelos de programación con este enfoque son Software Distributed Shared Memory (SDSM) [19] y Partitioned Global Address Space (PGAS) [20]. Los modelos que hacen uso de SDSM crean una memoria virtual global sobre la memoria distribuida, la ventaja está en que permite ejecutar aplicaciones secuenciales sin modificación alguna, este tipo de soluciones suele afectar el desempeño dado que se proporciona muy poca información. Los modelos basados en PGAS ofrecen un entorno con un espacio de direcciones global distribuido en el sistema, en contraste con SDSM en el programa se debe expresar el paralelismo e información del sistema. OmpSs y UPC [8] son algunos de los ejemplos de PGAS existentes actualmente. La mayor diferencia entre OmpSs y otros modelos PGAS radica en que OmpSs ofrece transparencia del tipo de distribución de datos, cosa que los demás carecen. OmpSs sigue la filosofía de OpenMP [6], ambas proveen una forma de paralelizar código secuencial por medio de anotaciones en el código. Las anotaciones no tienen ningún significado semántico en el lenguaje, sólo cobran significado cuando se compila con OmpSs. Esta propiedad permite al programador hacer cambios incrementales sin tener que hacer grandes cambios en el código.

4

1.1.3 OmpSs y grafos de dependencia de tareas Para ejecutar programas en OmpSs de forma paralela, el modelo de programación ofrece pragmas para expresar cuando comienza y termina una tarea. Para expresar el comienzo de una nueva tarea basta con usar el pragma omp task, esto especifica que el siguiente bloque de código es una tarea. El pragma depend permite especificar qué datos necesita la tarea para poder ejecutarse y que datos modificara al ser ejecutada, es necesario saber qué datos se cambian al ejecutar una tarea para notificarle al resto de tareas una vez la tarea esté lista. Por último, otra funcionalidad relevante es poder especificar el dispositivo de ejecución de la tarea por medio del pragma device(<device>), donde <device> puede ser SMP, FPGA o GPU. #define N 2 #define BS 16 void compute_block(int i, int j){} void wavefront(long m[N][N][BS][BS]) {

int i, j; {

for (i=0; i<=N; i++) { for (j=0; j<=N; j++) { if (i==0 && j==0) { // Initial block #pragma omp task depend(inout:m[i][j]) device(fpga) onto(0,1) compute_block(i, j); }

else if (i == 0) { // Blocks in the upper edge #pragma omp task depend(in:m[i][j-1], inout:m[i][j]) compute_block(i, j); }

else if (j == 0) { // Blocks in the left edge #pragma omp task depend(in:m[i-1][j], inout:m[i][j]) compute_block(i, j); }

else { // Internal blocks #pragma omp task depend(in:m[i-1][j], in:m[i][j-1],

in:m[i-1][j-1], inout:m[i][j]) compute_block(i, j); }

}

}

}

}

5

Nuevas versiones del compilador de OmpSs ahora permite pasar de la especificación de un programa a un grafo de dependencias de tareas. El grafo de la Figura 1.3 es la representación en tareas del programa anterior. Figura 1.3. Grafo de dependencia de tareas de un programa wavefront

Esta forma de grafo directo acíclico es conocida como forma de diamante y es común en problemas de matrices, donde la matriz se separa en subbloques y se empaqueta como tarea para ser ejecutada. En este caso la matriz se separa en nueve subbloques y para ejecutar la tarea ligada a esa porción de datos hace falta que el bloque superior y el bloque del lado izquierdo hayan terminado.

6

1.2 Actores implicados Al ser una herramienta de programación la cantidad de personas que potencialmente usarán el software es impredecible y la variedad de usos que se le puede dar es potencialmente infinito. 1.2.1 Desarrollador El proyecto será de gran utilidad para aquellas personas con necesidad de ejecutar aplicaciones que usen FPGAs en clusters. El programa está hecho precisamente con el objetivo de reducir el tiempo de desarrollo. 1.2.2 Beneficiarios OmpSs forma parte del proyecto europeo AXIOM [15], cuyo objetivo primario es proveer tecnología con buen rendimiento y bajo gasto energético para dirigirse a las necesidades los sistemas inteligentes actuales y futuros. Los principales beneficiarios serán los partners del proyecto Axiom: Barcelona Supercomputing Center (BSC), EVIDENCE, FORTH, HERTA, SECO, UNISI y VIMAR. No obstante, cualquier empresa en posesión de un cluster o en el campo de Cyber-Physical Systems [12] se verá beneficiada.

7

2 Formulación del problema y objetivos

2.1 Integración de dispositivos FPGA con Cluster El coste es cada vez más importante al momento de diseñar un supercomputador. El uso eléctrico de los sistemas HPC impone restricciones en la instalación y el uso de estos sistemas. A medida que el consumo eléctrico del sistema baja, menor cantidad de gastos de enfriamiento se tiene. Los aceleradores son una opción ideal, ejecutan de manera más eficiente algunos tipos de aplicaciones en comparación con un CPU de propósito general. Para añadir nuevos dispositivos al sistema, como un acelerador, se requiere que ocupen poco espacio, sean fáciles de instalar, tengan buen rendimiento, bajo consumo energético y sean económicos. Las FPGAs representan una buena solución a estos problemas dada a su enorme capacidad de adaptabilidad con respecto a otros aceleradores como las GPUs [8]. El problema radica en que la dificultad de programar y usar FPGA sigue siendo elevada, aunque más fácil que fabricar un acelerador, y por eso el uso dado a las FPGA es bajo actualmente [11]. Dar soporte al uso de FPGAs en modelos de programación de memoria distribuida es necesario para promover una adopción amplia por los desarrolladores en códigos de producción ejecutados en clusters.

2.2 Diseño de políticas de planificación Las políticas de planificación son algoritmos que buscan minimizar el tiempo de ejecución total de un programa. Cada programa que se quiere ejecutar de forma paralela se debe primero dividir en tareas separadas, lo cual en este caso se hace con pragmas de OmpSs. Cada una de estas tareas puede tener dependencias con tareas anteriores e incluso tener la necesidad de recibir datos de ellas. Es por esto que es importante respetar la precedencia de las tareas. Estas tareas están ordenadas por medio de un grafo directo cíclico donde cada arista representa la precedencia de una tarea padre a una tarea hija, por lo que una tarea estará lista para ser ejecutada únicamente cuando todos sus predecesores han sido ejecutados y los datos estén disponibles en el worker donde esta se va a ejecutar.

8

Las políticas están encargadas principalmente de orquestar la ejecución de las tareas dentro del computador. En el caso de un Cluster los nodos no suelen tener memoria compartida y existen gastos de transferencia por red no despreciables que se debe tomar en cuenta. Dentro del grafo de dependencias se encuentra por cada nodo cuando tarda en ejecutarse la tarea y por cada arista cuál es el tamaño de los datos que se deben enviar al sucesor. Para calcular el tiempo solo hace falta hacer uso de una función que pase a partir de un tamaño de datos y un ancho de bandas a segundos de espera. Figura 1.4. TDG y una planificación generada por el emulador de cluster.

El grafo de la izquierda es el grafo acíclico de tareas con sus dependencias (los colores representan si es FPGA o SMP). El grado de la derecha representa una planificación del grafo de tareas, cada color representa un nodo distinto. Se puede ver que en la política de la derecha se espera que el programa termine en 290 ms. Las políticas de planificación también pueden ser dinámicas o estáticas. Las dinámicas no conocen el grafo de tareas previo a la ejecución del programa, van decidiendo el lugar de ejecución de las tareas a medida que el programa se va ejecutando. En el caso de las políticas estáticas se puede elegir donde ejecutar las

9

tareas antes de la ejecución del programa, estas políticas poseen menor overhead y son capaces de generar políticas más sofisticadas. El problema de planificación de tareas con dependencias es fuertemente NP-Completo [25], inclusive sin coste de transferencia de datos. Por lo tanto, no existe un algoritmo de tiempo polinómico que retorne una solución óptima al problema. Es importante notar que a diferencia de un problema débilmente NP-Completo, como por ejemplo knapsack, este tipo de problemas no se puede resolver por medio de programación dinámica de forma sostenible debido a los requerimientos de memoria. Para representar el estado de una solución parcial en programación dinámica hay que saber como mínimo qué tareas se han ejecutado y cuanto espacio ocupado hay en cada nodo. La forma más eficiente de representar qué tareas ya se han asignado es usando un bit por tarea, el bit es uno si la tarea ya ha sido asignada y cero en el caso contrario. Esto significa que para n tareas necesitamos 2^n para representar el estado, junto con el espacio necesario para representar el estado de cada nodo sería inviable para un ordenador de 4GB de RAM resolver un grafo de quince tareas con cuatro nodos.

2.3 Objetivos Los objetivos de este proyecto son: hacer los cambios necesarios a OmpSs para poder ejecutar aplicaciones que hacen uso de FPGAs en clusters, diseñar distintas políticas de planificación en tiempo de compilación para un de cluster homogéneo con nodos de un solo worker.

10

3 Alcance El primer objetivo de este proyecto es lograr que OmpSs ejecute tareas sobre FPGAs en un cluster homogéneo multi-arquitectura. Actualmente hay dos versiones paralelas de OmpSs de interés para la realización de este proyecto, OmpSs@Cluster [2] y OmpSs@FPGA [10]. OmpSs@Cluster permite ejecutar programas de forma distribuida en un cluster con dispositivos SMP y GPU, existen varias versiones estables y está abierta al público. OmpSs@FPGA es más reciente y solo puede ejecutar tareas en dispositivos SMP o FPGA siempre y cuando sean en un solo nodo, soporte para distribuir tareas a lo largo del cluster aun no esta soportado correctamente. La segunda fase del proyecto es la implementación de planificadores estáticos por medio de los grafos de dependencias que podría generar OmpSs. Al finalizar el proyecto, se habrán probado al menos cuatro políticas de planificación.

3.1 Obstáculos Aun disponiendo de un plan de trabajo definido, en todo proyecto pueden surgir imprevistos, sobre todo en un código fuente tan denso y que lidia con llamadas a sistemas. El obstáculo más grande de este trabajo estará en el surgimiento de imprevistos al integrar FPGAs en OmpSs@Cluster, ya sea porque el código base asume ciertas condiciones o simplemente porque al trabajar con la memoria y threads de otros dispositivos es fácil cometer errores. La parte del planificador debería dar menos problemas.

11

4 Metodología y rigor

4.1 Método de trabajo El proyecto se desarrollará con una metodología ágil iterativa para poder probar resultados en cada iteración y desviar el camino acorde a los descubrimientos que se hagan en cada paso. De esta forma también es más sencillo saber cuál es la causa de un problema dado, si una iteración empieza a dar problemas con el mismo juego de pruebas está claro que el bug fue introducido en esa iteración. Lo fundamental de este tipo de metodologías es que aunque se acabe el tiempo asignado al proyecto habrá como mínimo una versión básica funcionando de lo que inicialmente se quería lograr. Esto es especialmente importante para proyecto de una duración considerable, como lo es un TFG. A partir de reuniones semanales con los responsables de supervisar este trabajo, entre otras breves reuniones con los miembros encargados de los modelos de programación, se tomarán decisiones para cumplir con los objetivos del proyecto a corto y largo plazo con tal de que el producto final satisfaga las necesidades del BSC.

4.2 Herramientas de seguimiento Las principales herramientas para el seguimiento de la evolución del proyecto serán Git [13] y GitLab [14]. Git es un controlador de versiones, con su uso se puede monitorizar la evolución de un proyecto, teniendo la libertad de cometer errores sabiendo que esto la historia de cambios permanece y log de anotaciones con los motivos por lo que se hicieron cada uno de los cambios. GitLab es la herramienta utilizada en el BSC para guardar la evolución oficial de proyecto, es accesible por todo el equipo, provee herramientas de comunicación entre los miembros del equipo para conservar las decisiones y facilita la programación automática de juegos prueba.

4.3 Método de validación Parte de la validación vendrá dada por el paso con éxito de los juegos de prueba ya existentes en los respectivos repositorios donde están alojadas las fuentes OmpSs. Luego de asegurarse que no se ha roto nada, el resto de la validación se encontrará en la aprobación del tutor por medio de nuevos juegos prueba.

12

5 Programa de trabajo

5.1 Etapas Para aumentar la probabilidad de éxito de llevar a cabo un proyecto conviene describir las tareas que éste contempla y planificarlas realisticamente en el tiempo disponible. Es importante tomar en cuenta que a medida que va evolucionando el proyecto la planificación de tareas puede cambiar. Cabe denotar que los recursos para todas las etapas son los mismos. Se usará un cluster homogéneo de placas ARM con un dispositivo FPGA integrado como requerimiento hardware. En cuanto a requerimientos software se evitará agregar nuevas dependencias a OmpSs, las dependencias actuales tanto para compilación como ejecución son Vivado [21], GASNet [22], GCC [23] y MPICH [24]. Este proyecto está contemplado entre las fechas del 15 de septiembre hasta el 26 de enero, fecha límite para entregar la memoria. Por lo tanto, el plan de trabajo debe contemplar un tiempo estimado cercano a los 4 meses. Las tareas necesarias para la realización de este proyecto son las siguientes:

● Integrar OmpSs@FPGA y OmpSs@Cluster (OmpSs@FPGA+Cluster) ● Familiarizarse con el planificador de OmpSs ● Hacer un modelo de cluster para emular ejecuciones ● Diseñar políticas de planificación sobre el modelo ● Redacción de la memoria y documentación

Cada tarea es dependiente de la anterior por lo que solo existe un orden absoluto para realizarlas, a excepción de la memoria. A continuación se provee una descripción más detallada de cada una: 5.1.1 Integrar OmpSs@FPGA y OmpSs@Cluster Dando un poco de contexto, OmpSs se ejecuta de forma distinta cuando es en un solo dispositivo o en varios. Esto se debe a la historia del modelo de programación, OmpSs comenzó como un modelo de programación para un solo dispositivo extendiendo las capabilidades de OpenMP.

13

Se debe compilar OmpSs especificando si se deben ejecutar los programas en un cluster o en un solo dispositivo, también se debe especificar que tipo de dispositivo habrán en el sistema (SMP, FPGA, etc). Cuando se desarrolló el soporte para FPGAs la prioridad era que funcionase para un solo dispositivo, los cambios necesarios para que también funcionarán en cluster se fueron ignorando. Hoy en dia OmpSs no compila cuando se especifica que debe funcionar tanto en clusters con FPGA, cualquier otra combinación de dispositivos con cluster si funciona. En esta etapa se debe asegurar primero que OmpSs se compile correctamente y luego probar que la ejecución funcione tal y como se espera. Será necesario verificar con los juegos de prueba existentes que el comportamiento de OmpSs para otra especificación de dispositivos no fue corrompido. Al momento de la planificación del trabajo, OmpSs@Cluster+FPGA compilaba correctamente pero la ejecución no era la esperada, con estas integraciones es difícil anticipar los problemas que pueden surgir; dicho esto, se estima que en el primer mes del proyecto se haya finalizado. 5.1.2 Familiarizarse con el planificador de OmpSs Para hacer el modelo necesito conocer mas o menos como un planificador orquestra, cuales son los costos asociados y que se podría mejorar en el modelo dentro de las comunicaciones para hacer que las planificaciones se ejecuten con menores costes. El planificador de OmpSs solo acepta políticas de planificación dinámicas, no tiene capacidad de ejecución para planificaciones hechas antes de la ejecución. Esta fase debería llevar poco tiempo para realizarse. Con dos semanas debería ser suficiente para entender. 5.1.3 Hacer un modelo de cluster para emular ejecuciones Para hacer los análisis de las distintas políticas de planificación se desarrollará un modelo de cluster homogéneo, que permita la ejecución de tareas en dispositivos FPGA y SMP. El modelo debe ser configurable para poder calcular los gastos que corresponde a enviar tareas por la red, encargándose de saber cuando una transferencia comienza y termina si la tarea queda en otro nodo del cluster. Esta etapa se debería completar en un mes.

14

La intención de esta tarea es proveer una interfaz para el fácil acceso de estos parámetros y que se puedan hacer planificadores ricos en información del sistema, estos son:

● Coste de envío

● Coste de cómputo

● Coste de sincronización

● Ocupación actual de cada nodo

● Localización de datos

● Logs de las tareas ejecutadas

El modelo diseñado vendrá incluido con formas de visualizar las planificaciones hechas, cuánto tiempo tardaron, como estan ocupados los nodos, en cuáles dispositivos se ejecutó las tareas y cuáles fueron los costes de red.

5.1.4 Diseñar políticas de planificación sobre el modelo En esta etapa se diseñará políticas de planificación que aprovechen al máximo la información aportada por el modelo del cluster para hacer planificaciones informadas sobre los grafos de dependencias de tareas. El tiempo otorgado a esta fase será el tiempo restante que no sea necesaria para las etapas anteriores. 5.1.5 Redacción de la memoria y documentación Al finalizar un proyecto formal, debe quedar para posterioridad una documentación técnica adecuada y un documento detallando los motivos, el proceso y los resultados del trabajo. La documentación es de especial importancia para los desarrolladores que modifiquen o necesiten entender esa parte del código en un futuro. La memoria se realizará en paralelo con la fase anterior. Hacerla en paralelo con los experimentos le otorgara una mejor calidad, dejarlo para después puede conllevar el riesgo de olvidar detalles.

15

5.2 Desviaciones eventuales en la planificación Se han hecho grandes desviaciones de la planificación inicial. Se subestimó el tiempo que podría llegar a pasar para integrar OmpSs@Cluster con OmpSs@FPGA. No tomó 30 días como se esperaba sino que se terminó de integrar a finales de enero del 2018. En gran parte esto se debe a lo complejo y grande que es el código fuente de OmpSs así como problemas inesperados del entorno de trabajo. Como ejemplo, en ocasiones al compilar con OmpSs se retornaba, lo cual no se debía al código cambiando sino al mal funcionamiento de una de las librerías cargadas. Sino fuera por la constante ayuda de miembros del BSC esto me hubiese tardado mucho más. También hubo desviaciones en el tiempo de integración con FPGA; por lo que en la evaluación de seguimiento se decidió posponer la entrega del trabajo hasta finalizar la integración. Una vez integrado, se decidió enfocar en planificadores estáticos y esto se debe a que recientemente se ha añadido a OmpSs la posibilidad de generar grafos de dependencias de tareas en momento de compilación. Esto permite analizar los grafos antes de que se ejecuten los programas y poder encontrar planificaciones que de otra forma no sería posible por falta de información. Con esta información nueva se pueden hacer políticas más complejas que con una dinámica, lo cual se tomó bastante en consideración debido a como el trabajo se estaba alejando tanto de la rama de computación. Una tarea extra que se quería hacer pero no fue posible, es la integración de OmpSs para que acepte planificaciones estáticas. Después de intentarlo se concluyó que no valía la pena por un coste temporal alto, tampoco se quería que sucedieran los mismos costes inesperados que ocurrieron con la integración con FPGA. Por esta razón todo el análisis de políticas de planificación se hizo separado de OmpSs completamente, en un programa desarrollado en Python.

16

5.3 Valoración temporal 5.3.1 Tiempo estimado

Nombre Duración estimada

Integrar OmpSs@FPGA y OmpSs@Cluster 30d

Familiarizarse con el planificador de OmpSs 15d

Hacer un modelo de cluster para emular ejecuciones 30d

Diseñar políticas de planificación sobre el modelo 45d

Redacción de la memoria y documentación 7d

Retoques finales 3d

5.3.2 Tiempo real

Nombre Duración estimada

Integrar OmpSs@FPGA y OmpSs@Cluster 120d

Familiarizarse con el planificador de OmpSs 15d

Hacer un modelo de cluster para emular ejecuciones 30d

Diseñar políticas de planificación sobre el modelo 30d

Redacción de la memoria y documentación 13d

Retoques finales 2d

17

5.3.3 Diagrama GANTT estimado Figura 5.1. Gantt inicial

5.3.4 Diagrama GANTT real Figura 5.2. Gantt real

18

6 Identificación y estimación de los costos

6.1 Presupuesto del proyecto Para un estudio completo de presupuesto hay que tomar en cuenta el coste de los recursos necesarios para su correcto desarrollo. En este caso los recursos están divididos en tres categorías: software, hardware y recursos humanos. La intención de este apartado es especificar los costes de cada componente, tomando en cuenta costes indirectos e inesperados que pueden encarecer la realización del trabajo. En el siguiente estudio del presupuesto se calculará el presupuesto en base al costo esperado de llevarlo a cabo. Si todos los eventos inesperados ocurriesen, de seguro el coste sería mayor al presupuesto asignado. No se puede esperar que al finalizar el proyecto el coste haya sido exactamente igual al presupuesto, lo mejor que se puede hacer es que el coste real sea lo más parecido al estimado. 6.1.1 Hardware Se necesita un ordenador para implementar los cambios necesarios y un cluster de placas para probar que funciona correctamente y hacer los respectivos benchmarks. Un servidor es también necesario para mandar tareas al cluster y hacer hosting de GitLab. Producto Precio Vida útil Amortización

Ordenador 800 € 5 años 50 €

Cluster (4 placas) 360 € 7 años 14 €

Servidor (GitLab, SLURM) 400 € 7 años 16 €

Total 1.560 € - 80 €

19

6.1.2 Software Este proyecto será llevado a cabo con el uso de herramientas de software gratis, en su mayoría free software [1]. Por lo que el coste total será igual a cero. Producto Precio Vida útil Amortización Ubuntu 16.04 LTS 0 € - 0 € LaTeX 0 € - 0 € Git 0 € - 0 € GitLab 0 € - 0 € Gnu Debugger (gdb) 0 € - 0 € Gnu C Compiler (gcc) 0 € - 0 € Message Passing Interface (mpi) 0 € - 0 € SLURM 0 € - 0 € Vivado 16.3 0 € - 0 € GASNet 0 € - 0 € Atom 0 € - 0 € Vim 0 € - 0 € TeamGantt 0 € - 0 € Google Docs 0 € - 0 € Google Drive 0 € - 0 €

Total 0 € - 0 € 6.1.3 Recursos humanos En este proyecto habrá una sola persona cumpliedo todas las funciones necesarias. Tomando días de trabajo de 3 horas (7 días a las semana), tenemos la siguiente distribución de tiempo: Rol Días Precio por dia Coste Cabeza de proyecto 28 d 75 € 2.100 € Desarrollador 87 d 60 € 5.220 € Tester 15 d 54 € 810 €

Total 130 d - 8.130 €

20

Etapa Duración (d) Cabeza de proyecto

Desarrollador Tester

Integrar OmpSs@FPGA y OmpSs@Cluster

30 d 5 d 20 d 5 d

Familiarizarse con el planificador de OmpSs

15 d 3 d 12 d 0 d

Hacer un modelo de cluster para emular ejecuciones

30 d 4 d 21 d 5 d

Diseñar políticas de planificación sobre el modelo

45 d 10 d 30 d 5 d

Redacción de la memoria y documentación

7 d 4 d 3 d 0 d

Retoques finales 3 d 2 d 1 d 0 d

Total 130 d 28 d 87 d 15 d

Distribución de 130 días equivalentes a un total de 390 horas.

6.1.4 Costos inesperados Siempre es recomendable un asignación extra de recursos en caso de desviaciones en la planificación. Sesenta horas extras respetando la proporción de trabajo de las tablas anteriores. Rol Horas Precio por hora Coste Cabeza de proyecto 12 h 25 € 300 € Desarrollador 40 h 20 € 800 € Tester 8 h 18 € 144 €

Total 60 h - 1.244 €

6.1.5 Costos indirectos Costos indirectos que surgen por el uso de los componentes necesarios. Producto Precio Uso Coste Electricidad 0.129 € /kW 2400 kW 309,6 € Fibra 35 € /mes 4 meses 140 €

Total - - 349,6 €

21

6.1.6 Presupuesto total La causa más probable de desviaciones, como en la mayoría de proyectos, es una subestimación del tiempo. Se añade un fondo de contingencia del 10% para la suma de costes directos e indirectos. Las otras causas de retraso son muy poco probables, y por ende, para no ser excesivamente riguroso no se tomarán en cuenta. Concepto Coste estimado Hardware 1.560 € Software 0 € Recursos humanos 8.130 € Costes indirectos 349,6 €

Subtotal 10.039,6 €

Contingencia (10%) 1.003,96 €

Costes inesperados 1.244 €

Total 12.287,56 €

22

6.2 Control de gestión de los gastos Además del proceso inicial se hará un control sobre el gasto estimado y el gasto real. Este control se llevará a cabo durante el transcurso del proyecto hasta su término, las desviaciones por cada tipo de coste son las siguientes:

● Coste de una tarea: coste real - coste total estimado. ● Horas de una tarea: (consumo de horas reales - consumo de horas

estimadas) * coste estimado. ● Coste de un recurso: (coste real - coste estimado) * consumo real.

6.2.1 Desviación del presupuesto en recursos humanos Rol Días Precio por dia Coste Cabeza de proyecto 40 d 75 € 3.000 € Desarrollador 142 d 60 € 8.520 € Tester 28 d 54 € 1.512 €

Total 210 d - 13.032 €

Diferencia estimado +80 d - 4.902 €

Etapa Duración (d) Cabeza de

proyecto Desarrollador Tester

Integrar OmpSs@FPGA y OmpSs@Cluster

120 d 20 d 80 d 20 d

Familiarizarse con el planificador de OmpSs

15 d 3 d 12 d 0 d

Hacer un modelo de cluster para emular ejecuciones

30 d 4 d 21 d 5 d

Diseñar políticas de planificación sobre el modelo

30 d 7 d 20 d 3 d

Redacción de la memoria y documentación

13 d 5 d 8 d 0 d

Retoques finales 2 d 1 d 1 d 0 d

Total 210 d 40 d 142 d 28 d

Diferencia estimado +80 d +12 d +55 d +13 d

Distribución de 210 días equivalentes a un total de 630 horas.

23

6.2.2 Desviación del presupuesto en costos indirectos Producto Precio Uso Coste Electricidad 0.129 € /kW 4200 kW 541,8 € Fibra 35 € /mes 7 meses 245 €

Total - - 786,8 €

Diferencia estimado - - +437,2 €

24

7 Sostenibilidad y compromiso social

Se evaluará la sostenibilidad del proyecto en base a tres aspectos: económico, social y ambiental. El rango de sostenibilidad total del proyecto es de 62. Tipo PPP Vida útil Riesgo Social 8/10 14/20 -1/-20 Económica 5/10 19/20 -6/-20 Ambiental 8/10 17/20 -2/-20 Rango de sostenibilidad 21/30 50/60 -9/-60

7.1 Dimensión social El proyecto será desarrollado en Cataluña. La situación política y social podría llegar a complicarse con el movimiento independentista, se llegue a un acuerdo o no entre Cataluña y España es muy poco probable que este afecte al proyecto. Tanto el BSC como AXIOM están financiados por la unión europea y es la única razón por la que se menciona este asunto. La realización de este proyecto no afecta de ninguna forma la situación social, excepto para los que tienen una necesidad real del proyecto como ya fue explicado dentro del apartado de beneficiarios del proyecto. La calidad de vida de los usuarios se verá afectada positivamente al hacer su trabajo menos monótono y propenso a errores. Hasta ahora, se desconoce de alguna causa que pueda hacer a este proyecto perjudicial a otros.

7.2 Dimensión económica Esta es la parte más importante a considerar en todo proyecto. El costo es viable económicamente si ha de ser competitivo, dado que OmpSs es el modelo de programación más cercano a tener implementado lo que se quiere hacer en el proyecto. Comenzar una solución propia desde cero es inviable, los otros modelos de programación tienen distintos intereses y prioridades por lo que tampoco sería muy buena idea comenzar modificando sus códigos base. Este proyecto está asociado al proyecto AXIOM de la unión europea.

25

7.3 Dimensión ambiental Se usa únicamente los recursos necesarios para desarrollar el proyecto y probarlo. Todos los equipos serán usados a lo largo de su vida útil por parte del BSC, a excepción de el portatil personal que puede ser descartado con anterioridad. Al completar este proyecto se habrá progresado en el uso de FPGAs en la industria, estos dispositivos consumen menos energía que otras unidades de cómputo de uso general. La contaminación provocada por la fabricación de los componentes utilizados no se puede evitar. Es muy difícil rastrear el origen de todos los componentes de un producto hoy en dia y solo podemos esperar que su extracción o producción haya sido etica.

26

8 Entorno de trabajo

8.1 Grafos de prueba Dentro de los programas que se pueden ejecutar de forma paralela, existen algunos que son bastantes comunes y generan grafos de dependencia de tareas estándar. En las pruebas del trabajo usaremos específicamente los grafos de dependencias generados por los algoritmos: multiplicación de matrices, factorización de cholesky y wavefront. Se han escogido tres por tener tipologías muy distintas y ser algoritmos comunes. Los tres son algoritmos de matrices y la forma de ejecutarlos de forma paralela es dividiendo los datos en bloques o filas. La topología de un TDG generado por un algoritmo wavefront siempre tiene forma de diamante y se caracteriza por no tener que pasar mucha información entre tareas. Figura 8.1.1. TDG de un algoritmo wavefront

27

En cambio la topología de un TDG generado por una factorización cholesky no tiene una forma tan regular o simétrica. Figura 8.1.2. TDG de un algoritmo de factorización de cholesky

28

Por último está la topología del grafo generado por la multiplicación de matrices. Este es particular por ser más fácil de paralelizar que otros algoritmos. Figura 8.1.3. TDG de un algoritmo de multiplicación de matrices

Los nodos están coloreados de acuerdo al dispositivo donde se van a ejecutar, ya sea SMP o FPGA. La diferencia más relevante entre ejecutar una tarea en una CPU en vez de en una FPGA es que en este último se necesitan hacer transferencias de datos desde la memoria del procesador a la memoria de la FPGA y viceversa para poder obtener el resultado. Este costo de transferencias de datos se traduce un tiempo añadido a las tareas que se quieran ejecutar en FPGA que se puede saber previamente. Como se puede sabes donde que dispositivo es mejor usar antes de aplicar cualquier política de planificación. Con un preprocesamiento se puede saber en qué dispositivo es mejor ejecutar cada tarea. Por este motivo es el generador del grafo, y no el planificador, que se encarga de elegir el dispositivo donde será ejecutado.

29

8.2 Modelo del cluster Se ha desarrollado un modelo de cluster similar al que se suele usar junto con OmpSs@Cluster+FPGA en entornos de prueba. El modelo es necesario para poder emular una ejecución de las políticas de planificación en un cluster y calcular un estimado del tiempo total de ejecución. Sin el emulador sería poco práctico desarrollar algoritmos de búsqueda, para saber si una planificación es mejor que otra sería necesario ejecutar el programa que genera el grafo de dependencias dos veces. El modelo está definido por medio de cuatro propiedades: tipo de nodo, número de nodos, ancho de banda y tiempo de sincronización. En este caso se desarrolló únicamente un tipo de nodo con un solo worker, es decir, un nodo no puede ejecutar más de una tarea simultáneamente. Por lo tanto, a lo largo del trabajo un nodo y un worker serán efectivamente lo mismo. El tiempo de sincronización ocurre cada vez que una tarea termina, este tiempo representa lo que un nodo tarda en saber información global de ejecución como lo puede ser sabes que otras tareas han terminado de ejecutarse. Una vez inicializado el modelo, una política de planificación puede simular la ejecución de un programa indicando en orden al simulador en que nodo se tiene que ejecutar cada tarea. Para poder ejecutar la tarea, esta debe tener especificada un tiempo de ejecución, dispositivo (SMP o FPGA), predecesores, sucesores y peso de los datos que hay que transmitir una vez terminada la tarea. Al intentar ejecutar una tarea el modelo verifica que las tareas predecesoras han terminado y comienza a ejecutar la tarea en el tiempo en que las transferencias hayan terminado, el tiempo de transferencia se calcula como el tamaño de los datos dividido por el ancho de banda. El tiempo inicial de una tarea se calcula como el máximo entre el tiempo de finalización de las transferencias y el tiempo en el que terminó la última tarea ejecutada en el nodo sumado con el tiempo de sincronización. A su vez, el tiempo de finalización de las transferencias se calcula como el máximo del conjunto de tiempos resultantes de la suma de el tiempo de finalización de las tareas precedentes.

El costo computacional de ejecutar una tarea en un nodo es igual al número de predecesores y sucesores de la tarea, al multiplicar este coste por el número de nodo no encontramos con que una emulación completa tiene complejidad

, donde es el número de tareas y el número de dependencias(V )O + E V E entre las tareas. A su vez, la complejidad en memoria también es .(V )O + E

30

El emulador de cluster también visualizaciones ricas en información sobre la política de planificación solapada al TDG (figura 8.2.1) y una visualización sobre cómo cada tarea es ejecutada en el cluster (figura 8.2.2). En estas visualizaciones el color representa el worker en el que fue ejecutado, también aparecen datos sobre el orden y el tiempo en que comienzan y finalizan las tareas dentro de la planificación.

Figura 8.2.1. Política solapada sobre una topología de cholesky

31

Figura 8.2.2. Visualización política en cluster sobre una topología de cholesky

Los números de cada bloque representan lo que dentro de la imagen anterior es la propiedad id definida dentro de cada tarea.

32

9 Políticas de planificación Todas las políticas de planificación hechas tendrán como mínimo una complejidad debido al coste de emular una tarea. Las políticas hechas (V )O + E en el trabajo se dividen en dos categorías, diagnósticas a la arquitectura y conscientes de la arquitectura del cluster. Las políticas agnósticas escogen el orden en que se debe ejecutar las tareas del grafo, pero no eligen en qué recurso del clúster se van a ejecutar. Para obtener la planificación hay que unir el orden con un algoritmo de selección de recursos para ejecutar la tarea que si dependa de la arquitectura del cluster. Para esta categoría se han desarrollado tres políticas: una política básica y dos política de prioridad. Las políticas conscientes de la arquitectura hacen uso de la mayor cantidad de información posible, información del grafo de tareas e información de la arquitectura del cluster. Para esta categoría se ha desarrollado una sola política: una política de búsqueda de mínimo global basado en A estrella. Este trabajo busca comparar resultados entre los algoritmos dentro de cada categoría y hacer una comparación global entre todas las políticas diseñadas. A lo largo del trabajo los resultados se analizarán sobre un cluster de cuatro nodos, un worker por nodo y tiempo de sincronización de 8 ms. El objetivo nos es buscar la política que da el mejor resultado, si no enfocarse en una comparación entre las políticas aportadas.

33

9.1 Políticas agnósticas a la arquitectura 9.1.1 Algoritmos de selección de recursos Como se comentaba anteriormente, los recursos del cluster son los workers dentro del cual se puede ejecutar en un dispositivo FPGA o SMP. Se han diseñado cuatro algoritmos selección para llevar a cabo esta tarea: azar, round robin, worker menos ocupado y afinidad. La selección al azar (random) tal y como su nombre lo indica consiste en elegir al azar en qué nodo se va a ejecutar la próxima tarea dada por el orden de ejecución de la política de planificación. El coste computacional y de memoria de este algoritmo es .(1)O La selección round robin selecciona los nodos por turnos, cada tarea se va ejecutando en el nodo siguiente que se ejecutó la anterior y si la tarea anterior fue ejecutada por el último worker se asigna la tarea actual al primer worker del cluster. Por ejemplo, si tenemos dos workers y una cola de tareas con el siguiente orden [tarea_a, tarea_b, tarea_c], tarea_a y tarea_c se ejecutarán en el primer worker y tarea_b se ejecutaría en el segundo worker. El coste computacional y de memoria de este algoritmo es .(1)O La selección del worker menos ocupado (least occupied worker) elige el worker cuya última tarea asignada tenga un tiempo de finalización menor que sea menor al tiempo de finalización de las últimas tareas asignadas en el resto de workers. Si tenemos dos workers, uno vacío y el otro con una tarea asignada, la próxima tarea se asignará al worker vacío. El coste computacional de este algoritmo es

y el coste en memoria es , donde representa el número de(ln(P ))O (P )O P workers. Como suele ser relativamente bajo se puede tomar como tiempo P constante. No es lineal porque necesita mantener en una cola de prioridad la ocupación de cada worker. La selección por afinidad (affinity) escoge el worker dependiendo del tamaño de las transferencias de datos, ahorrando potencialmente tiempo en transferencias. Este algoritmo tiende a sobrecargar algunos nodos más que otros, como medida preventiva a estas situaciones se ignora la afinidad cuando el nodo menos ocupado tiene un tiempo asignado menor a un porcentaje proporcionado del más ocupado. En caso de no activarse la medida preventiva una tarea se asignará al nodo donde se ahorre la transferencia de datos más grande.

34

El coste computacional de este algoritmo es y el coste en (P redecesores)O + P memoria es , donde representa el número de workers. Como suele (P )O P P ser relativamente bajo se puede tomar como tiempo constante.

35

9.1.2 Política básica La política básica desarrollada consiste en iterar sobre una cola de tareas que estén listas para ser ejecutadas, cada vez que una nueva tarea esté lista se añade al final de la cola. El algoritmo no hace uso de ninguna información en el grafo más allá de la necesaria para saber si una tarea se puede ejecutar. La complejidad computacional y de memoria de esta política es con (V )O + E una selección de nodo sencilla. Uniendola con una selección por afinidad o de worker menos ocupado nos encontramos con que el coste computacional de la política es y la complejidad en memoria es .(V )O * P + E (V )O + E + P 9.1.2.1 Resultados No importa la heurística de selección de nodos que se use el costo temporal de ejecutar el programa aumentará linealmente con respecto al número de tareas, inclusive con una heurística random. Se pueden El rendimiento general de esta política haciendo uso de distintas heurísticas de selección de nodos se puede observar en las Figuras 9.1.1, 9.1.2 y 9.1.3. Figura 9.1.1. Comparación entre selección de nodos usando la política básica sobre una topología de wavefront

36

Figura 9.1.2. Comparación entre selección de nodos usando la política básica sobre una topología de multiplicación de matrices

Figura 9.1.3. Comparación entre selección de nodos usando la política básica sobre una topología de cholesky

37

A priori se podría pensar que la elección de nodos tendría una alta influencia sobre el rendimiento de la ejecución. Sin embargo no es muy relevante, solamente tiene un efecto significativo en una factorización de cholesky cuando se aumenta el tamaño de los datos a transmitir sobre la red Figura 9.1.4. Figura 9.1.4. Comparación entre selección de nodos usando la política básica sobre una topología de cholesky aumentando el tamaño de los datos con 4961 tareas.

A lo largo de todas las ejecuciones se puede observar como factor común que la heurística de selección por afinidad es superior al resto en las topologías estudiadas, aunque sea en pocos casos comprobados.

38

9.1.3 Políticas de prioridad En las políticas de prioridad se hace un recorrido del grafo y a cada tarea se le asigna un número que represente su prioridad, mientra mayor el número mayor la prioridad. Esto se implementa con una cola de prioridad que ordene de menor a mayor, agregando cada tarea junto con su prioridad a la cola. 9.1.3.1 Prioridad por camino crítico El camino crítico de un grafo de tareas es el camino más largo desde los puntos iniciales del grafo a los puntos finales. Como estamos trabajando sobre un grafo acíclico dirigido, este problema se puede resolver con una variación de Depth-First-Search. Para obtener la prioridad se hace un recorrido que empieza por las tareas finales y se recorre el grafo con las aristas invertidas, el inverso de un grafo acíclico dirigido sigue siendo acíclico. A diferencia de un DFS no solo se ha de comprobar si una tarea se ha visitado sino también el número de veces que se ha hecho. Cada tarea empieza con una prioridad cero, y cada que es visitada se le pasa el camino crítico de la tarea anterior junto con el tiempo que esta tarda en ejecutarse. Cuando una tarea ha sido visitada por todos sus hijos (hay que recordad que el grafo está invertido) se guarda la prioridad máxima encontrada y se agregan las tareas padre a la cola del DFS. Técnicamente podríamos inventarnos un nombre como Depth-Last-Search, un nodo se da por visto únicamente cuando se ha visitado todas las veces posibles. La complejidad de este algoritmo es por las características del grafo, no funciona en (V )O + E grafos cíclicos o no dirigidos. Una vez que el orden ya está decidido la complejidad computacional es la misma que para las política básica pero con un coste añadido de ordenar las tareas. Si se usa una selección de nodos random o round robin y (V n(V ) )O * l + E complejidad en memoria . Si se usa una selección least occupied la (V )O + E complejidad es con complejidad en memoria (V n(V ) n(P ) )O * l + V * l + E

. Y si se usa una selección por afinidad la complejidad es(V )O + E + P con complejidad en memoria .(V n(V ) )O * l + V * P + E (V )O + E + P

39

9.1.3.2 Prioridad por trabajo restante Con trabajo restante se refiere al coste aproximado que se tiene que asumir antes de poder ejecutar una tarea. Si una tarea tiene varios predecesores, la heurística de camino crítico no toma en cuenta el coste total únicamente toma un solo camino, esto debe a que la heurística de camino crítico se comporta mejor a medida que Esto se resuelve con dos recorridos con un DFS modificado (o Depth-Last-Search), primero sobre el grafo original y luego sobre el grafo invertido. En el primer recorrido cada vez que una tarea es visitada, se le suma el coste del camino en tiempo para llegar hasta esa tarea, cuando se ha visitado tantas veces como predecesores tenga entonces se agregan los hijos a la pila. El recorrido termina con todas las tareas teniendo un valor aproximado de cuál es el coste que se tiene que asumir para poder ejecutar la tarea. El segundo recorrido es un recorrido inverso, tiene como finalidad hacer V tuplas de tamaño menor o igual a . Cada tupla se construye como la V concatenación de los costes de las tareas a lo largo del camino crítico, concatenado de la tarea final a la actual. Estas tuplas representan el orden de prioridad de las tareas, al añadirlas a una cola de prioridad se ordena las tareas según cuales tengan las tareas con más coste al final del camino. Si tenemos una tarea con prioridad y otra con , la 1000, 300, 200, 0)( 1000, 500, 200, 0)( segunda será ejecutada primero dado que 500 es mayor a 300. De esta forma se busca ejecutar que se ejecuten aquellas tareas que necesiten más trabajo previo para poder ejecutarse. La complejidad total de calcular esta heurística es de

debido a la creación de las tuplas, por lo mismo la(V n(V ) )O 2 + V * l + E complejidad en memoria es de .(V )O 2 Esta heurística tiene como defecto que suma trabajo de más, cuando si una tarea es predecesora de dos y esas dos son predecesores de una compartida entonces estamos contando el coste de ejecutar la primera tarea dos veces en la última tarea. En un caso más complejo se sumará más de dos veces la misma tarea.

40

9.1.3.3 Resultados Se puede observar que hay una gran diferencia de rendimiento entre las dos heurísticas desarrolladas. Como la selección de nodos random o por round robin son tan básicas y no aportan información nueva se dejan fuera de los resultados. Figura 9.1.5. Comparación entre selección de nodos usando políticas de prioridad sobre una topología de wavefront

Esa diferencia no se debe a que una sea mucho mejor que la otra sino que la heurística de trabajo restante no se comporta bien. Con 800 tareas, las políticas básicas se encuentran en el rango de los 25000 ms cuando la heurística de trabajo restante se encuentra en un rango entre 40000 ms y 70000 ms. La misma comparación en rendimiento de la heurística de trabajo restante se puede observar en las demás topologías.

41

Figura 9.1.6. Comparación entre selección de nodos usando políticas de prioridad sobre una topología de multiplicación de matrices

Figura 9.1.7. Comparación entre selección de nodos usando políticas de prioridad sobre una topología de factorización de cholesky

42

Lo que sí parece ser constante entre políticas es la ventaja de usar la heurística de afinidad con cualquier política de planificación. A medida que aumentan los datos con un número de tareas fijas se vuelve a repetir el resultado dado por la política básica. A medida que aumentan el tamaño de los datos no hay un aumento significativo de el tiempo de ejecución. Figura 9.1.8. Comparación entre selección de nodos usando políticas de prioridad sobre una topología de factorización de cholesky con aumento de datos con 4961 tareas

43

9.2 Políticas conscientes de la arquitectura Estas políticas toman en consideración el coste de hacer transferencias de datos entre workers con más detalle. 9.2.1 Política de búsqueda global Con la intención de probar una política de búsqueda global se ha desarrollado un algoritmo para generar una planificación por medio de A estrella. A estrella es un algoritmo de búsqueda de grafos que tiene como meta encontrar el camino mínimo entre dos puntos del grafo. Cada camino que se va expandiendo se coloca en una cola de prioridad y se va sacando de esta la que tiene menor costo. La función de costo se define como , f (n) (n) (n) = g + h′ donde representa el peso del camino desde el nodo inicial al nodo actual y (n)g

representa la función del costo estimado desde el nodo actual al nodo final.(n)h′ La función tiene que ser una estimación acotada inferiormente del valor (n)h′ actual, en caso contrario el algoritmo no encuentra un camino óptimo. Si = (n)h′ 0, el algoritmo pasa a ser un Dijkstra. En cambio, si fuese equivalente al (n)h′ costo real de llegar al nodo final el algoritmo convergerá a la solución directamente. La ventaja de usar A estrella en comparación a Dijkstra es que se exploran potencialmente menos estados. Mientras más precisa es la función de coste estimado más se pospondrá la exploración de caminos costosos. De esta (n)h′ forma el algoritmo puede buscar un camino con menos requerimientos de tiempo y memoria. Para encontrar una planificación con A estrella debemos definir un nuevo grafo. Si recorremos el grafo de tareas con A estrella obtendremos el menor camino de la tarea inicial a la final, pero eso no es lo que queremos.

44

Cada nodo del grafo es una planificación parcial, es decir, no tienen porque estar todas las tareas asignadas al cluster. El nodo inicial es el cluster vacío antes de que se le asigne una sola tarea y el nodo final es aquella planificación no parcial con coste mínimo. Cada nodo del grafo tiene los siguientes componentes:

● (n)f ● Suma total del tiempo de las tareas aún no asignadas ● El estado del modelo del cluster para el nodo actual ● Tareas que están listas para ser asignadas

Cada uno de los componentes es necesario para saber el estado, excepto el último. Las tareas que están listas para ser asignadas se pueden inferir del estado del modelo del cluster, sin embargo requiere un costo computacional extra que no merece la pena. Para explorar un nodo vecino en el grafo basta con asignar un tarea a un worker, recalcular , generar un nuevo modelo con la nueva tarea, actualizar las f (n) tareas listas y ponerlo en una cola de prioridad. Se puede observar que el número de nodos en el grafo es inmensamente grande y que tiene una cota inferior definida por la función , donde S es la (V , )S P función de los números de Sterling [26]. Como en el modelo usado los workers son indistinguibles los unos de los otros, al explorar el grafo se puede generar nodos repetidos que no vale la pena revisitar. Un ejemplo de esto sería tomar una planificación e intercambiar completamente las tareas asignadas entre dos workers, el costo temporal de la planificación sería el mismo solo que las tareas estarían en un worker distinto. Haciendo un cálculo combinatorio obtenemos que estaríamos por cada planificación parcial estaríamos explorando como mínimo P! planificaciones extra. Para evitar este problema tomamos la planificación parcial y ordenamos los workers de acuerdo a el id único de cada tarea y generamos un hash de esa representación, de esta forma no importa que intercambios totales de tareas entre workers se haga siempre tendrán el mismo hash. Como guardar estos tiene un coste adicional en memoria, estos hashes se borran de memoria apenas la planificación parcial es sacado de la cola de prioridad para ser explorado.

45

Para calcular la estimación , tomamos la suma total del tiempo de las tareas (n)h′ que faltan por asignar y las distribuimos desde el worker más vacío hasta el más lleno. Si no se puede llenar los workers hasta el nivel del más ocupado entonces

=0, en caso contrario si definimo como el tiempo restante luego de(n)h′ rT rellenar los workers hasta llegar al mismo nivel del nodo más ocupado y Nw como el número de workers tenemos que . La complejidad de (n) r wh′ = T ÷ N hacer esta estimación es .(P )O

Let s = priority_queue() workload_left = get_workload_left() # Sum of times of al unexecuted tasks

estimated_time_origin = h’(cluster_model, workload_left)

s.push((estimated_time_origin, workload_left, cluster_model, ready_tasks))

While not empty(s): (estimated_time_origin, workload_left,

cluster_model,

ready_tasks) = s.pop() If empty(ready_tasks):

return schedule(cluster_model) For worker in workers():

For task in ready_tasks:

new_ready_tasks = copy(ready_tasks).remove(task)

new_cluster_model = copy(cluster_model)

just_ready = execute(new_cluster_model, task, worker)

extend(new_ready_tasks, just_ready)

new_estimation = h’(new_cluster_model, workload_left)

new_workload_left = workload_left - time(task)

s.push((new_estimation,

new_workload_left,

new_cluster_model,

new_ready_tasks)) Output: the best schedule executed in the cluster model Versión simplificada del algoritmo, no se revisa la repetición de estados por permutación de intercambios completos de tareas entre workers. En el peor de los casos el algoritmo explorará todos los caminos posibles, en cuya situación lo más probable es que la memoria se acabe o se empiece a usar el disco duro como parte de la memoria RAM, lo cual no es muy deseable.

46

9.2.1.1 Resultados Ejecutar el algoritmo para grafos con más diez tareas no es viable, solo se ha comparado con la política de planificación heurística de camino crítico con selección de nodos por afinidad ya que ha sido la mejor encontrada hasta ahora. Ambas políticas dan resultados muy similares, aunque que sea a causa del tamaño del problema. Figura 9.2.1. Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella. Topología wavefront.

Lo que si mejora el algoritmo A estrella es el tiempo cuando los datos a transferir entre tareas aumentan. En las figura 9.2.2 y 9.2.3 se puede observa la diferencia entre las dos políticas cuando la proporción entre el tiempo de transferencia de datos y el coste de ejecutar una tarea se encuentra entre 0.5:1 a 1:1 (tiempo transferencia : coste ejecución tarea).

47

Figura 9.2.2. Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella cuando el tiempo de transferencia de datos aumenta. Topología wavefront 9 tareas.

Figura 9.2.3. Comparación heurística de camino crítico con elección por afinidad y política basada en A estrella cuando el tiempo de transferencia de datos aumenta. Topología cholesky 11 tareas.

48

10 Conclusiones La nueva versión de OmpSs@FPGA con Ompss@Cluster ha sido presentado en un proyecto europeo con éxito. Hacer uso de un modelo de cluster para emular una ejecución ha demostrado ser una buena herramienta para desarrollar buenas políticas. Acorta el ciclo de implementación de nuevas políticas y permite tener un mejor monitoreo con la desventaja de que siempre será un estimado. Sin poder emular el cluster, el desarrollo de políticas de planificación estáticas no sería posibles en primer lugar. Las políticas presentadas en el trabajo son muy simples como para obtener buenas soluciones. La política básica no hace uso suficiente de la información en el grafo, con la ayuda de una heurística selectora de nodo no demuestra ser mucho mejor que una heurística Round Robin exceptuando el caso de topologías más complejas y no simétricas como es el caso de una factorización de cholesky. La políticas basadas en heurísticas en el trabajo no mejoran mucho más sobre soluciones actuales, el camino crítico es un indicador conocido en la literatura para saber qué nodos hace falta ejecutar con mayor necesidad. El camino crítico es el camino con más peso desde el inicio del grafo hasta el final, por lo tanto el peso del camino es una cota inferior del tiempo total de ejecución. El problema de las heurísticas para este problema es que son cortas de vista y se suelen quedar en cerca de minimo locales difíciles de salir. El algoritmo de búsqueda global aportado ha demostrado no funcionar para grafos de más de 10 tareas, aún sin caer en la trampa de repetir estados por permutaciones de workers el costo es simplemente demasiado alto. Todo indica a que es mejor hacer uso de algoritmos de búsqueda local y aprovechar todas la información disponible, no tan robustas como A estrella pero tan poco con una complejidad computacional tan alta.

49

Como nota adicional, las asignaturas de la carrera que más me ayudaron a la realización del TFG fueron:

● EDA y A: Por los conocimiento de estructuras de datos, análisis de complejidad y algoritmos heurísticos.

● IDI y PROP: Estas asignaturas me ayudaron a desarrollar código de forma extensible con separación obligaciones entre clases y funciones, fue de especial ayuda al hacer el emulador de cluster. Y finalmente porque me ayudaron a hacer uso controladores de versiones para trabajar con más tranquilidad.

● IA: Me enseñó de algoritmos de búsqueda clásicos, los cuales son de especial relevancia en problemas reales.

● AC, PAR y CL: Sin estas asignaturas todo hubiese sido más difícil de entender dentro de OmpSs. Lo más probable es que me hubiese encontrado con muchos más problemas al integrar OmpSs@Cluster con OmpSs@FPGA.

50

11 Trabajo futuro

El trabajo logró el objetivo de integrar OmpSs@FPGA con OmpSs@Cluster; sin embargo, aún queda por mejorar las políticas de planificación con las que experimentar. Un lugar donde se podría expandir el trabajo es probando con otros modelos de cluster, no únicamente el de un solo worker. Una de las políticas a la que le falta refinamiento es a la heurística del trabajo restante. Una posible solución para evitar el problema de repetición en la suma de tareas es aplicando el algoritmo del ancestro común más bajo para identificar los casos en que dos tareas comparten un ascendiente y un descendiente. Habría que aumentar un poco el coste computacional del algoritmo pero no sería mucho más costoso. Otro sitio donde se podría mejorar es modificando el trabajo restante a medida que se van asignando tareas en el modelo del cluster. Los algoritmos de búsqueda local se ven como la opción más prometedora a seguir, si se puede aprovechar las ventajas de un algoritmo de búsqueda como A estrella pero con una cantidad de estados menor la solución podría aprovechar las transferencias de memoria y sin tener un coste de estimación exponencial. Especialmente seria interesante hacer un estudio de Simulated Annealing con una función de temperatura con un valor inicial que optimice la búsqueda de planificaciones. Otras políticas de planificación que sería interesante diseñar, son aquellas ligadas a una topología de grafos específica como es el caso de los grafos generados por un programa de cholesky o de multiplicación de matrices. Lo más probable es que sea posible diseñar políticas específicas de topología en tiempo lineal. Un desarrollador que escriba código en OmpSs luego podría especificar por medio de pragmas a que tipo de topología pertenecen las tareas generadas, o mejor aún se podría diseñar un algoritmo que lo haga automáticamente. Otros algoritmos que sería interesante probar en el futuro son aquellos basados en algoritmos genéticos. La mayor dificultad radica en cómo hacer un apareamiento entre estados, dado que es probable que cualquier intento de unir dos soluciones termine peor que ambas.

51

12 Referencias

[1] Corporation, A. (2007). White Paper Accelerating High-Performance

Computing With FPGAs. Cluster Computing, (October), 1–8. [2] Hedo, J. B. (2015). Run-time support for multi-level disjoint memory

address spaces. [3] Kindratenko, V., & Trancoso, P. (2011). Trends in high-performance Cloud

Computing. Computing in Science and Engineering, 13(3), 92–95. http://doi.org/10.1109/MCSE.2011.52

[4] Stephen Craven and Peter Athanas. “Examining the Viability of FPGA Supercomputing”. In: EURASIP J. Embedded Syst. 2007.1 (Jan. 2007), pp. 13–13. ISSN: 1687-3955. DOI: 10.1155/2007/93652. URL: http://dx.doi.org/10.1155/2007/93652.

[5] Silva, L., & Buyya, R. (1999). Parallel programming models and paradigms. High Performance Cluster Computing: Architectures …, 4–27. Retrieved from http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:Parallel+Programming+Models+and+Paradigms#0

[6] L. Dagum and R. Menon. “OpenMP: An industry standard API for shared-memory programming”. In: IEEE International Conference on Computational Science and Engineering. 1998.

[7] MPI Forum. MPI: A Message-Passing Interface Standard. Version 2.2. available at: http://www.mpi-forum.org. Sept. 2009

[8] UPC Consortium. UPC Specifications, v1.2. Tech. rep. Lawrence Berkeley National Lab Tech Report LBNL-59208, 2005

[9] N. Kapre and A. DeHon, “Performance comparison of single-precision SPICE model evaluation on FPGA, GPU, cell, and multi-core processors,” in FPL 09: 19th International Conference on Field Programmable Logic and Applications, 2009, pp. 65–72

[10] Cherkashin, A. (2015). Implementación de una infraestructura para ejecución heterogénea de aplicaciones (CPU + FPGA).

[11] I. Kuon, R. Tessier, and J. Rose, “FPGA Architecture: Survey and Challenges,” Foundations and Trends® in Electronic Design Automation, vol. 2, no. 2. pp. 135– 253, 2007.

[12] Baheti, R., & Gill, H. (2011). Cyber-physical Systems. The Impact of Control Technology, (1), 161--166. http://doi.org/10.1145/1795194.1795205

[13] Git. https://git-scm.com/. Accedido: 2017-09-26. [14] GitLab. https://about.gitlab.com/. Accedido: 2017-09-26. [15] AXIOM. http://www.axiom-project.eu/. Accedido: 2017-09-26 [16] David E. Culler et al. “Parallel Programming in Split-C”. In: Proceedings of

the Supercomputing ’93 Conference. Portland, OR, Nov. 1993, pp. 262–273. URL: http: //www.cs.cmu.edu/~seth/papers/culler-sc93.pdf.

52

[17] R Numwich and J Reid. Co-Array Fortran for parallel programming. Tech. rep. 1998.

[18] McClatchey, R., Anjum, A., Stockinger, H., Ali, A., Willers, I., & Thomas, M.

(2007). Data intensive and network aware (DIANA) grid scheduling. Journal of Grid Computing, 5(1), 43–64. http://doi.org/10.1007/s10723-006-9059-z

[19] DSMS. https://en.wikipedia.org/wiki/Distributed_shared_memory. Accedido: 2017-09-26.

[20] PGAS. https://en.wikipedia.org/wiki/Partitioned_global_address_space. Accedido: 2017-09-26.

[21] Vivado. https://git-scm.com/. Accedido: 2017-10-02. [22] GASNet. https://bitbucket.org/berkeleylab/gasnet. Accedido: 2017-10-02 [23] GCC. https://gcc.gnu.org/. Accedido: 2017-10-02 [24] MPICH. https://www.mpich.org/. Accedido: 2017-10-02 [25] free software. https://www.gnu.org/philosophy/free-sw.en.html. Accedido: 2017-10-07. [25] Fuertemente NP-Completo https://en.wikipedia.org/wiki/Weak_NP-completeness. Accedido: 2018-03-28. [26] Numeros de Sterling https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind. Accedido: 2018-04-10.

53