Compile-time support for thread-level speculation

Resumo

----------------- Introducción ----------------- Una de las principales preocupaciones de las ciencias de la computación es el estudio de las capacidades paralelas tanto de programas como de los procesadores que los ejecutan. Existen varias razones que hacen muy deseable el desarrollo de técnicas que paralelicen automáticamente el código. Entre ellas se encuentran el inmenso número de programas secuenciales existentes ya escritos, la complejidad de los lenguajes de programación paralelos, y los conocimientos que se requieren para paralelizar un código. Sin embargo, los actuales mecanismos de paralelización automática implementados en los compiladores comerciales no son capaces de paralelizar la mayoría de los bucles en un código [1], debido a la dependencias de datos que existen entre ellos [2]. Por lo tanto, se hace necesaria la búsqueda de nuevas técnicas, como la paralelización especulativa [3-5], que saquen beneficio de las potenciales capacidades paralelas del hardware y arquitecturas multiprocesador actuales. Sin embargo, ésta y otras técnicas requieren la intervención manual de programadores experimentados. ----------------------------------------- Contenido de la investigación ----------------------------------------- Antes de ofrecer soluciones alternativas, se han evaluado las capacidades de paralelización de los compiladores comerciales, exponiendo las limitaciones de los mecanismos de paralelización automática que implementan. El estudio revela que estos mecanismos de paralelización automática sólo alcanzan un 19% de speedup en promedio para los benchmarks del SPEC CPU2006 [6], siendo este un resultado significativamente inferior al obtenido por técnicas de paralelización especulativa [7]. Sin embargo, la paralelización especulativa requiere una extensa modificación manual del código por parte de programadores. Esta Tesis aborda este problema definiendo una nueva cláusula OpenMP [8], llamada ¿speculative¿, que permite señalar qué variables pueden llevar a una violación de dependencia. Además, esta Tesis también propone un sistema en tiempo de compilación que, usando la información sobre los accesos a las variables que proporcionan las cláusulas OpenMP, añade automáticamente todo el código necesario para gestionar la ejecución especulativa de un programa. Esto libera al programador de modificar el código manualmente, evitando posibles errores y una tediosa tarea. El código generado por nuestro sistema enlaza con la librería de ejecución especulativamente paralela desarrollada por Estebanez, García-Yagüez, Llanos y Gonzalez-Escribano [9,10]. Antes de instrumentar un bucle con directivas y cláusulas OpenMP, incluyendo nuestra propuesta de cláusula ¿speculative¿, los programadores deben extraer cierta información sobre el código fuente que quieren paralelizar [11]. Esto incluye el uso de las variables dentro de cada bucle; funciones de entrada y salida que puedan complicar o incluso impedir la paralelización; y aún más importante, determinar si merece la pena paralelizar un bucle [12], o si la sobrecarga necesaria para gestionar los diferentes hilos será mayor que el beneficio obtenido de la paralelización. Sin herramientas automáticas, los programadores tienen que extraer manualmente esta información. Por tanto, esta Tesis aborda también el problema de la caracterización automática de bucles secuenciales con el objetivo de encontrar nichos de paralelización en benchmarks conocidos que puedan beneficiarse de la paralelización especulativa basada en software. Para hacer esto, proponemos un sistema que aprovecha una representación intermedia XML para realizar un análisis estático del código fuente y lo combina con la información de su perfil de ejecución, obteniendo la caracterización del código. Finalmente, esta Tesis propone un sistema que aprovecha esta información, sintetizando y generando automáticamente las directivas y cláusulas OpenMP necesarias para paralelizar un código especulativamente. ---------------- Conclusión ---------------- Esta Tesis da respuesta a varios de los problemas asociados con la paralelización especulativa. Uno de los problemas es la detección de nichos donde aplicar este paralelismo, y cuánto representan esos nichos en términos de tiempo de ejecución. Para realizar estas tareas, se ha propuesto un sistema que se ha evaluado con los benchmarks del SPEC CPU2006 para obtener que el 38% de los bucles son únicamente paralelizables mediante técnicas de paralelización especulativa, representando un 28% del tiempo de ejecución total. La obtención de estas cifras es una tarea inabordable si quiere realizar manualmente, y esta Tesis propone una solución automática para la realización de la misma. Por otro lado, el principal problema de los esquemas de paralelización especulativa basada en software es la necesidad de enriquecer y modificar el código con todo lo necesario para gestionar su ejecución especulativa. Para solucionar este problema, esta Tesis propone un sistema en tiempo de compilación que permite la paralelización automática del código. Esta paralelización es activada mediante el uso de una nueva cláusula OpenMP, con lo que este estándar es mejorado también con capacidades especulativas. Finalmente, para evitar la también tediosa tarea, predispuesta a errores, de clasificar manualmente las variables del código a paralelizar, esta Tesis propone un sistema automático de clasificación de variables, así como la anotación automática del código a paralelizar con directivas OpenMP, incluyendo el uso de la cláusula propuesta. De esta manera hemos conseguido la completa generación de código paralelo, partiendo de un código secuencial. La incorporación de nuestra cláusula ¿speculative¿ en la implementación de OpenMP de un compilador tan extendido como GCC [13], junto con la automatización de todo el proceso de paralelización, ayudará a que la paralelización especulativa basada en software esté lo suficientemente madura como para ser utilizada en producción. ----------------- Bibliografía ----------------- [1] Sergio Aldea, Diego R. Llanos, and Arturo Gonzalez-Escribano. Using SPEC CPU2006 to evaluate the sequential and parallel code generated by commercial and open-source compilers. The Journal of Supercomputing, 59:486¿498, June 2012. [2] Arthur J. Bernstein. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers, EC-15(5):757¿763, 1966. [3] Manish Gupta and Rahul Nim. Techniques for speculative run-time parallelization of loops. In Proceedings of the 1998 ACM/IEEE Conference on Supercomputing, SC¿98, pages 1¿12, 1998. [4] Francis Dang, Hao Yu, and Lawrence Rauchwerger. The R-LRPD test: speculative parallelization of partially parallel loops. In Proceedings of the 16th IEEE International Parallel and Distributed Processing Symposium, IPDPS¿02, pages 20¿29, 2002 [5] Marcelo Cintra and Diego R. Llanos. Toward efficient and robust software speculative parallelization on multiprocessors. In Proceedings of the Ninth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP¿03, pages 13¿24, 2003. [6] John L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Computer Architecture News, 34(4):1¿17, September 2006. [7] Venkatesan Packirisamy, Antonia Zhai, Wei-Chung Hsu, Pen-Chung Yew, and Tin-Fook Ngai. Exploring speculative parallelism in SPEC2006. In Proceedings of the 2009 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS¿09, pages 77¿88, April 2009. [8] OpenMP Architecture Review Board. The OpenMP application program interface specification, version 3.1. http://openmp.org, July 2011. [9] Alvaro Estebanez, Diego R. Llanos, and Arturo Gonzalez-Escribano. New data structures to handle speculative parallelization at runtime. In Proceedings of the 7th International Symposium on High-level Parallel Programming and Applications, HLPP ¿14, 2014. [10] Álvaro García-Yágüez, Diego R. Llanos, and Arturo Gonzalez-Escribano. Robust thread-level speculation. In Proceedings of the 18th International Conference on High Performance Computing, HIPC¿11, pages 1¿11, 2011. [11] Bradford L. Chamberlain, David Callahan, and Hans P. Zima. Parallel programmability and the Chapel language. International Journal of High Performance Computing Applications, 21(3):291¿312, 2007. [12] Shengyue Wang, Xiaoru Dai, Kiran S. Yellajyosula, Antonia Zhai, and Pen-Chung Yew. Loop selection for thread-level speculation. In Proceedings of the 18th International Conference on Languages and Compilers for Parallel Computing, LCPC¿05, pages 289¿303, 2006. [13] GNU Project. GCC, the GNU Compiler Collection. http://gcc.gnu.org/.