Hierarchical transparent programming for heterogeneous computing

Resum

INTRODUCCIÓN: Resumen: La computación paralela y el desarrollo de programas paralelos intentan reducir el tiempo de ejecución de las aplicaciones. Durante años, las optimizaciones de códigos secuenciales fueron diseñadas sin tener en cuenta la paralelizacion de datos ni de las tareas. Actualmente, los dispositivos multi-core se han vuelto omnipresentes en nuestras máquinas de cómputo, haciendo que la paralelización tome un papel aún más importante. La computación paralela está estrechamente relacionada tanto con el hardware como con el software. El objetivo final de la computación paralela es mejorar, en la medida de lo posible, la capacidad computacional de las máquinas. El constante crecimiento en el rendimiento de las Unidades de Procesamiento Gráfico (GPUs), junto con recientes mejoras en su programabilidad, ha hecho que estos dispositivos sean una buena opción como aceleradores hardware en la Computación de Altas Prestaciones (HPC) para una variedad de aplicaciones. La noción de la computación heterogénea ha emergido hace muy pocos años. Este concepto se basa en explotar un sistema compuesto por dispositivos de naturaleza diferente. Los sistemas heterogéneos pueden estar formados por procesadores con múltiples núcleos, GPUs y procesadores reconfigurables entre otros. Aunque el uso de sistemas heterogéneos, para aprovechar al máximo toda la capacidad computacional, pueda resultar una idea interesante, su complejidad de programación se encuentra un paso por delante de la programación paralela. Los principales problemas que aparecen son los siguientes: el primer problema es la necesidad de escribir código propios tanto para los núcleos de la CPU como para la GPU y el segundo problema, es la distribución de carga de trabajo entre los diferentes dispositivos, ya que estos sistemas no comparten un espacio de direcciones común. Además, cada dispositivo presenta diferentes capacidades de cómputo, por lo que cada uno es capaz de trabajar a ritmo diferente. Durante la última década, se han propuesto diferentes modelos de programación con el objetivo de manejar la complejidad de las particiones y mapeo multinivel de datos. Estos modelos de programación pueden caer en dos categorías: aquellos que esconden las comunicaciones subyacentes y aquellos en donde las comunicaciones son impulsadas por las particiones creadas por el usuario. Estos modelos de programación paralela no ayudan al programador a expresar de forma explícita el modelo de comunicación que necesita el algoritmo independientemente de la partición de datos elegida. El Tiling es una técnica conocida que es usada para distribuir datos y tareas en programas paralelos y mejorar la localidad de bucles anidados en códigos secuenciales. El uso de estructuras de datos para soportar tiling, permite explotar eficientemente la jerarquía de memoria ya que a menudo los datos son reutilizados dentro del tile. Trasgo es un framework de programación que está siendo desarrollado por nuestro grupo de investigación de la Universidad de Valladolid. Trasgo se basa en especificaciones de alto nivel y paralelismo anidado, permitiendo expresar de forma sencilla varias combinaciones de paralelismo de tareas con un esquema común. El back-end de Trasgo es soportado por Hitmap, una biblioteca runtime para el tiling jerárquico y el mapeo de arrays. Hitmap implementa funciones para crear, manipular, mapear y comunicar tiling-arrays jerárquicos. En esta tesis doctoral estudiamos la posibilidad de desarrollar un sistema de programación portable y transparente que incorpore tiling jerárquico y políticas de scheduling con el objetivo de aprovechar las capacidades de la computación heterogénea. Para abordar nuestra propuesta de investigación hacemos uso de la biblioteca Hitmap como un framework prototipo. Este framework permite explotar sistemas de memoria distribuida. En este trabajo extendemos de forma conceptual y práctica este framework para aprovechar todos los recursos hardware (CPU-GPU) en entornos heterogéneos. Además, éste permite generar códigos abstractos que a su vez son transparentemente adaptados para sistemas con diferentes tipos de dispositivos. Para ello es necesario también un estudio de las arquitecturas GPU que ayude a determinar unos buenos valores de los parámetros de configuración GPU (la geometría/tamaño de los bloques de hilo o la configuración de la cache L1) que deberían ser escogidos de otra forma por el programador. El conocimiento obtenido de este estudio es usado para crear políticas de selección de dichos valores. Estas políticas son incluidas en la biblioteca Hitmap. Tras examinar y analizar los resultados experimentales concluimos que es factible la creación de un sistema de programación que incorpore técnicas de particionado de datos, herramientas de comunicación, y selección trasparente para el programador de buenos valores de los parámetros de configuración GPU para sistemas heterogéneos. Pregunta de investigación: ¿Es posible desarrollar un sistema de programación portable y transparente que incorpore tiling jerárquico y políticas de scheduling con el objetivo de aprovechar las capacidades de la computación heterogénea? Tareas: Con el objetivo de responder a la pregunta de investigación, hemos llevado a cabo las siguientes tareas: ¿ A partir de Hitmap, un framework que incorpora tiling y scheduling para sistemas de memoria distribuida, se han estudiado las modificaciones conceptuales y prácticas necesarias para dar soporte a Hitmap en entornos heterogéneos. ¿ Este estudio muestra la necesidad de nuevos niveles de particionado y sus políticas asociadas. Estas políticas incluyen mecanismos para: 1. Mover datos de forma transparente entre los diferentes dispositivos. 2. Realizar subdivisiones de tareas que encajen de forma adecuada en la memoria de cada dispositivo. 3. Seleccionar tamaños y geometrías para los conjuntos de hilos. Metodología de investigación: Con el fin de lograr los objetivos propuestos en este documento, seguiremos la metodología de investigación definida por un método de investigación para ingeniería. Este método establece cuatro fases diferentes que el proceso de investigación debe seguir. Cada fase puede repetirse de forma cíclica con el objetivo de redefinir las soluciones propuestas. ¿ Observar las soluciones existentes. Esta fase tiene el propósito de detectar problemas que serán alcanzados durante el proceso de investigación comenzando con la solución existente. Esto conlleva un completo estudio del estado del arte con el objetivo de encontrar trabajos relacionados con nuestro foco de investigación. Este estudio es presentado en este documento. ¿ Proponer mejores soluciones. En esta fase se propone una solución que aborde las limitaciones encontradas en la fase anterior. Como mostraremos a lo largo de este trabajo, existe una carencia de frameworks que encapsulen técnicas de particionado y mapeo de datos para entornos heterogéneos, que a su vez, exploten de forma automática y transparente los recursos hardware de los dispositivos GPU. Este trabajo está estrechamente relacionado con la arquitectura de las GPUs. Proponemos varias políticas para (a) seleccionar buenos valores para los parámetros de configuración GPU (tamaño/geometría de los bloques de hilos y la configuración de la cache L1 entre otros) para algunos tipos de aplicaciones y (b), explotar de forma eficiente un balanceo de carga sobre los sistemas heterogéneos. ¿ Construir o desarrollar la solución. La solución propuesta en la fase anterior es implementada en la fase actual. Hemos llevado a cabo un estudio sobre las arquitectura de la GPU y como ayudar al programador a determinar unos buenos valores de los parámetros de configuración. También hemos desarrollado un framework de programación para estudiar la factibilidad de las soluciones propuestas. ¿ Medir y analizar la nueva solución. Finalmente, este método ingenieril establece que la solución propuesta tiene que resolver los problemas descubiertos en la primera fase. Hemos evaluado el sistema usando tanto bancos de pruebas sintéticos como aplicaciones reales. CONTENIDO DE LA INVESTIGACIÓN: El capítulo 2 de esta Tesis doctoral muestra el estado del arte a través de las citas bibliográficas y discusiones. El capítulo 3 presenta la biblioteca Hitmap, cuya versión de memoria distribuida será usada para implementar nuevas abstracciones que soporten sistemas heterogéneos compuestos por CPUs-GPUs. En el capítulo 4 analizamos la posibilidad de crear un modelo de programación para encapsular la elección de unos buenos valores de los parámetros de configuración GPU, funciones de mapeo y balanceo de carga y sincronización/comunicación entre CPU-GPU. En el capítulo 5 realizamos un estudio de los parámetros de configuración GPU. El conocimiento de este estudio será usado en el capítulo 6 para integrarlo en nuestro framework, permitiendo de forma transparente elegir buenos valores de estos parámetros de configuración GPU. El capítulo 7 tiene como objetivo responder a la pregunta de investigación, resumiendo los resultados obtenidos. El apéndice A muestra los fundamentos del modelo de programación CUDA y el apéndice B contiene algunos de los algoritmos usados como benchmarks en nuestros experimentos. CONTRIBUCIONES y BIBLIOGRAFÍA: En este trabajo de Tesis se ha estudiado la viabilidad de desarrollar un sistema de programación portable y transparente que incorpore tiling jerárquico y políticas de scheduling con el objetivo de aprovechar las capacidades de la computación heterogénea. Para ello hemos presentado un prototipo de framework que encapsula la elección de (a) buenos valores de los parámetros de configuración para dispositivos heterogéneos, (b) estructuras de datos tile, funciones de mapeo y balanceo de carga y (c), funciones de sincronización/comunicación entre dispositivos heterogéneos CPU-GPU. Finalmente, se realiza una evaluación experimental del prototipo de framework con el objetivo de contestar la pregunta de investigación propuesta en esta Tesis. Primera: Hemos contribuido al desarrollado Hitmap. Se trata de una biblioteca software diseñada para desacoplar los patrones de comunicación del particionado de datos gracias al uso de expresiones abstractas de comunicación. Estas abstracciones son automáticamente adaptadas en tiempo de ejecución dependiendo de la partición. Podemos usar las abstracciones desarrolladas para Hitmap en sistemas homogéneos para implementar unas nuevas orientadas a entornos heterogéneos. 1. Arturo Gonzalez-Escribano, Yuri Torres, Javier Fresno, and Diego R. Llanos. An Extensible System for Multilevel Automatic Data Partition and Mapping. Parallel and Distributed Systems, IEEE Trans. on Parallel and Distributed Systems, PP(99):1¿1, 2013. Segunda: Hemos proporcionado nuevos conocimientos sobre la relación entre la ocupación, la geometría y el tamaño de bloque de hilos, la configuración de la jerarquía de la memoria cache (en la arquitectura Fermi), y el patrón de acceso a memoria global que presentan los hilos. 2. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Understanding the impact of CUDA tuning techniques for Fermi. High Performance Computing and Simulation (HPCS), 2011 International Conference on, pages 631-639, 2011. 3. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. CUDA Tuning and Configuration Parameters on FermiArchitectures. Advanced Computer Architecture and Compilation for High Performance and Embedded Systems (ACACES 2011), 2011. 4. Yuri Torres, Arturo Gonzalez -Escribano, and Diego R. Llanos. Uso del conocimiento de la arquitectura Fermi para mejorar el rendimiento en aplicaciones CUDA. Actas XXII Jornadas de Paralelismo, 2011. Tercera: Hemos introducido una suite de microbenchmarks (llamada uBench) para explorar el impacto sobre el rendimiento de (a) criterios de selección de la geometría y tamaño de los bloques de hilos y (b), las configuraciones y recursos hardware de la GPU. Esta suite de microbenchmarks cubre los detalles hardware de las arquitecturas Fermi y Kepler. 6. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Measuring the Impact of Configuration Parameters in CUDA Through Benchmarking. The 12th International Conference Computational and Mathematical Methods in Science and Engineering, CMMSE 2012, 2012. 7. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. uBench: Performance Impact of CUDA Block Geometry. Technical Report IT-DI-2012-0001, Depto. Informática, Universidad de Valladolid, Dec 2012. 8. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. uBench: exposing the impact of CUDA block geometry in terms of performance. The Journal of Supercomputing, 65(3):1150¿1163, 2013. Cuarta: Hemos desarrollado dos aplicaciones reales (el problema SSSP para encontrar el camino/ruta más corto desde un punto a todos los demás; el problema APSP para encontrar la ruta más corta entre cualquiera de los puntos al resto) con el objetivo de probar y verificar las conclusiones obtenidas en el puntos anteriores. 9. Hector Ortega-Arranz, Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. A New GPU-based Approach to the Shortest Path Problem. The 2013 International Conference on High Performance Computing & Simulation, (HPCS 2013), pages 505¿511, 2013. 10. Hector Ortega-Arranz, Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. A Tuned, Concurrent Multi-Kenel Approach to the APSP problem. The 13th International Conference Computational and Mathematical Methods in Science and Engineering, CMMSE 2013, 2013. Quinta Hemos presentado un framework de programación extendiendo la biblioteca Hitmap con el objetivo de analizar la posibilidad de (a) crear un modelo de programación y un framework que encapsulen la elección de unos buenos valores de los parámetros de configuración de GPU y las estructuras de datos, (b) funciones de mapeo y balanceo de carga, y (c), funcionalidades de comunicación/sincronización entre dispositivos heterogéneos CPU-GPU. 11. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Automatic Data Layout at Multiple Levels for CUDA. The 10th International Conference Computational and Mathematical Methods in Science and Engineering, CMMSE 2010, 2010. 12. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Data partition and syn- chronisation in heterogeneous systems. HPC-EUROPA2 project (project number: 228398) with the support of the European Commission Capacities Area - Research Infras- tructures, 2013. 13. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Encapsulated Synchronization and Load Balance in Heterogeneous Programming. Euro-Par 2012 Parallel Processing, volume 7484 of LNCS, pages 502¿513. Springer Berlin Heidelberg, 2012. 14. Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Automatic run-time mapping of polyhedral computations to heterogeneous devices with memory-size restrictions. In The 2013 International Conference on Parallel and Distributed Processing Techniques and Applications, 2013. CONCLUSIONES: Basado en la información, discusiones y resultados que se muestran a lo largo de este trabajo de Tesis, las principales conclusiones son las siguientes: ¿ El uso de Hitmap promueve programas más abstractos, fáciles de mantener y codificar, manteniendo un buen rendimiento. Esta biblioteca permite lograr rendimientos similares a implementaciones que han sido optimizadas manualmente para kernels y benchmarks conocidos en la comunidad científica. Hitmap reduce significativamente el esfuerzo de programación. ¿ La elección de los valores de los parámetros de configuración de una GPU está estrechamente relacionada con la implementación particular de la aplicación y la arquitectura del dispositivo. Un análisis combinado del conocimiento de la arquitectura GPU y las características del código implementado (tales como el tipo de patrón de acceso a memoria global, el flujo de carga total por hilo y el ratio de operaciones lectura-escritura sobre la memoria global) puede ayudar, de forma significativa, a seleccionar unos buenos valores para los parámetros de programación GPU. ¿ Es posible crear un entorno de programación que contenga técnicas de particionado automático, herramientas de comunicación, y seleccionar de forma transparente al usuario buenos valores de los parámetros de configuración GPU para sistemas heterogéneos. TRABAJO FUTURO: Existen varias cuestiones que nos gustaría abordar. Estos focos definen la orientación futura de este trabajo: ¿ Estamos planeando realizar un estudio sobre la influencia de los efectos hardware y los parámetros de configuración en otras arquitecturas de GPU, tales como AMD e Intel. ¿ Actualmente estamos trabajando sobre políticas de mapeo más sofisticadas que exploten de forma más eficiente los procesadores de la CPU y las arquitecturas GPU. Se desea probar y verificar la aplicabilidad de estas técnicas para un conjunto más amplio de problemas incluyendo otros benchmarks conocidos por la comunidad científica y aplicaciones reales. ¿ Personalmente, tengo curiosidad por estudiar los dispositivos FPGA (Field Programmable Gate Array) ya que su funcionalidad hardware puede ser reconfigu rada tantas veces como se dese. Me gustaría automatizar aquellas decisiones que cualquier programador debería de tomar antes de lanzar cualquier función sobre un dispositivo de estas características. Desearía dar soporte a dispositivos FPGAs en nuestro marco de programación.