Supporting general data structures and execution models in runtime environments

Résumé

----------------- Introducción ----------------- Durante las últimas décadas, los sistemas paralelos se han vuelto cada vez más populares tanto en el ámbito de la computación de altas prestaciones como en el de la computación convencional. Esto se debe a un enorme incremento en las capacidades de las plataformas paralelas. Esto ha sido registrado por el proyecto Top500 que clasifica los 500 sistemas de mayor potencia del mundo [1]. Para aprovechar las ventajas de estas plataformas, se necesitan nuevas herramientas de programación. En primer lugar, se necesitan modelos de programación con abstracciones de alto nivel para poder representar apropiadamente los algoritmos paralelos. Además, los entornos paralelos que implementan dichos modelos requieren sistemas en tiempo de ejecución completos que ofrezcan diferentes paradigmas de computación a los programadores. De este modo es posible construir programas que puedan ser ejecutados eficientemente en diferentes plataformas. ----------------------------------------- Contenido de la investigación ----------------------------------------- Existen diferentes áreas a estudiar con el fin de construir un sistema en tiempo de ejecución completo para un entorno paralelo. Esta Tesis aborda dos problemas comunes: el soporte unificado de datos densos y dispersos, y la integración de paralelismo orientado a mapeo de datos y paralelismo orientado a flujo de datos. En primer lugar, un entorno paralelo genérico requiere integrar manejo para datos densos y dispersos usando un interfaz común siempre que sea posible. La mayoría de los lenguajes de programación paralelos actuales, como HPF [2] o UPC [3], solo tienen soporte nativo para arrays densos. Para utilizar estructuras dispersas, los programadores deben recurrir a herramientas externas como por ejemplo Metis [4], una biblioteca de partición de grafos. Nosotros proponemos una solución que desacopla la representación, partición y reparto de datos, del algoritmo y de la estrategia de diseño paralelo. En segundo lugar, un entorno paralelo de estás características debe permitir programar aplicaciones dinámicas y de flujo de datos, las cuales son difíciles de realizar con las herramientas actualmente disponibles. Los lenguajes y bibliotecas de flujo de datos, tales como FastFlow [5], OpenStream [6] o S-Net [7], son una aproximación prometedora porque ofrecen modelos de alto nivel que permiten definir los elementos computacionales y sus dependencias de forma separada. De esta forma, los programadores pueden dedicarse a definir la solución de los problemas, dejando la responsabilidad de la ejecución a los runtimes. Sin embargo, estos modelos no tienen un sistema genérico para definir canales MPMC (Multiple-Producer/Multiple-Consumer) o no tienen mecanismos para definir afinidades de tareas. En esta Tesis, introducimos un nuevo modelo de programación basado en el paradigma de flujo de datos, donde diferentes actividades pueden ser arbitrariamente enlazadas para formar redes genéricas pero estructuradas que representan el cómputo global. La biblioteca Hitmap [8] ha sido usada en esta Tesis como base para crear un sistema en tiempo de ejecución para un entorno de programación genérico. Respecto al soporte de estructuras de datos dispersos, hemos ampliado la metodología de programación de Hitmap para integrar conceptualmente dominios densos y dispersos. Además, hemos desarrollado una nueva versión de la biblioteca siguiendo la metodología propuesta. La nueva implementación permite utilizar varias estructuras para grafos y matrices dispersas con las mismas abstracciones. Respecto a la integración de modelos de flujo de datos, hemos estudiado las redes de Petri [9] y las redes de Petri coloreadas [10] como lenguajes de modelado para la descripción de sistemas paralelos. Usando estos lenguajes como base, hemos desarrollado un modelo teórico de flujo de datos. Hemos ampliado Hitmap para soportar el modelo propuesto. Esta versión de Hitmap nos permite describir programas como redes reconfigurables de actividades y contenedores de datos arbitrariamente interconectados. Se han implementado diferentes programas de prueba usando la versión extendida de Hitmap y se ha llevado a cabo trabajo experimental para validar la solución en términos de rendimiento y de facilidad de programación. Todos los experimentos muestran que Hitmap simplifica la tarea de programación y obtiene tiempos de ejecución similares a otras soluciones. ---------------- Conclusión ---------------- El trabajo presentado en esta tesis nos permite concluir que es posible crear un sistema en tiempo de ejecución para un lenguaje de programación que ofrezca abstracciones comunes para manejo de datos densos y dispersos, y soporte para paralelismo orientado a mapeo y flujo de datos para entornos híbridos de memoria compartida y distribuida. La biblioteca Hitmap carecía de soporte para datos dispersos y para estructuras dinámicas basadas en flujo de datos. Con el trabajo de investigación realizado en esta Tesis, hemos sido capaces de extender la biblioteca para eliminar estas limitaciones. Las contribuciones realizadas en esta Tesis han sido presentadas en diferentes publicaciones científicas, siendo las más relevantes [11-14]. ----------------- Bibliografía ----------------- [1] Erich Strohmaier, Erich Dongarra, Horst Simon and Martin Meuer. Top500 Supercomputer site. url: http://www.top500.org (visited on 04/02/2015). [2] Ken Kennedy, Charles Koelbel and Hans Zima. 'The rise and fall of High Performance Fortran'. In: Proceedings of the thrid ACM SIGPLAN conference on History of programming languages (HOPL III). Vol. 54. 11. New York, NY, USA: ACM Press, 2007, pp. 7.1¿7.22. doi: 10.1145/1238844.1238851. [3] William W. Carlson, Jesse M. Draper, David E. Culler, Katherine A. Yelick, Eugene Brooks and Karen Warren. Introduction to UPC and Language Specification. Tech. rep. CCS-TR-99-157. 1999. url: www.gwu.edu/~upc/publications/upctr.pdf. [4] George Karypis and Vipin Kumar. MeTiS¿A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices¿Version 4.0. Tech. rep. 1998. url: http://glaros.dtc.umn.edu/gkhome/views/metis. [5] Marco Aldinucci, Marco Danelutto, Peter Kilpatrick and Massimo Torquati. 'FastFlow: high-level and efficient streaming on multi-core'. In: Programming Multi-core and Many-core Computing Systems. Ed. by Sabri Pllana and Fatos Xhafa. 1st. Parallel and Distributed Computing. Wiley, 2014. isbn: 0470936908. [6] Antoniu Pop and Albert Cohen. 'A OpenStream: Expressiveness and Data-Flow Compilation of OpenMP Streaming Programs'. In: ACM Transactions on Architecture and Code Optimization (TACO), vol. 9, no. 4, 2013, 53:1¿53:25. 2013. doi: 10.1145/2400682.2400712. [7] Clemens Grelck, Sven-Bodo Scholz and Alex Shafarenko. 'A Gentle Introduction to S-Net: Typed Stream Processing and Declarative Coordination of Asynchronous Components'. In: Parallel Processing Letters, vol. 18, no. 2, 2008, pp. 221¿237. 2008. [8] Arturo Gonzalez-Escribano, Yuri Torres, Javier Fresno and Diego R. Llanos. 'An Extensible System for Multilevel Automatic Data Partition and Mapping'. In: IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 5, May 2014, pp. 1145¿1154. May 2014. issn: 1045-9219. doi: 10.1109/TPDS.2013.83. [9] Tadao Murata. 'Petri nets: Properties, analysis and applications'. In: Proceedings of the IEEE, vol. 77, no. 4, 1989, pp. 541¿580. 1989. doi: 10.1109/5.24143. [10] Kurt Jensen and Lars M. Kristensen. 'Coloured Petri nets: modelling and validation of concurrent systems'. Springer, 2009. isbn: 978-3-642-00283-0. [11] Javier Fresno, Arturo Gonzalez-Escribano and Diego R. Llanos. 'Automatic Data Partitioning Applied to Multigrid PDE Solvers'. In: Proceedings of the 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP). February 9-11, Ayia Napa, Cyprus: IEEE, Feb. 2011, pp. 239¿246. isbn: 978-1-4244-9682-2. doi: 10.1109/PDP.2011.38 [12] Javier Fresno, Arturo Gonzalez-Escribano and Diego R. Llanos. 'Extending a hierarchical tiling arrays library to support sparse data partitioning' In: The Journal of Supercomputing, vol. 64, no. 1, 2013, pp. 59¿68. Springer US, 2013. issn: 0920-8542. doi: 10.1007/s11227-012-0757-y [13] Javier Fresno, Arturo Gonzalez-Escribano and Diego R. Llanos. 'Blending Extensibility and Performance in Dense and Sparse Parallel Data Management'. In: IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 10, 2014, pp. 2509¿2519. IEEE, 2014. doi: 10.1109/TPDS.2013.248 [14] Javier Fresno, Arturo Gonzalez-Escribano and Diego R. Llanos. 'Runtime Support for Dynamic Skeletons Implementation'. In: Proceedings of the 19th International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). July 22-25, Las Vegas, NV, USA., 2013, pp. 320¿326