Compiler framework for the automatic detection of loop-level parallelism

Abstract

En esta tesis se presenta un entorno de compilación para la detección de paralelismo de grano grueso en bucles que contienen computaciones complejas, tales como indirecciones y sentencias condicionales que introducen flujos de control complejos. El mecanismo de detección se lleva a cabo sobre la representación GSA (Gated Single Assignment) del código fuente en dos fases. En primer lugar, se analizan las cadenas de uso-definición (USE-DEF CHAINS) entre las sentencias que forman cada una de las componentes fuertemente conexas (Strongly Connected Components, SCCS) del grafo GSA. De esta manera, se detecta el Kernel básico computado en cada SCC. En segundo lugar, con el fin de detectar los Kernels computacionales más complejos (y potencialmente paralelos) ejecutados en el Bucle, se realiza un análisis de las cadenas de uso-definición entre sentencias pertenecientes a distintas SCCS. Este entorno proporciona un soporte de información para la aplicación de técnicas de optimización y paralelización para la aplicación de técnicas de optimización y paralelización de código. En concreto, en esta tesis se muestra su aplicación para la generación automática de código paralelo eficiente. Finalmente, se ha desarrollado un prototipo de la técnicas de detección y se ha verificado experimentalmente su efectividad sobre códigos reales mediante una comparativa exhaustiva con el copiladorparalelizador polaris