PDF de programación - Compiler Framework for the Automatic Detection of Loop-Level Parallelism

DEPARTMENT OF ELECTRONICS AND SYSTEMS

UNIVERSITY OF A CORU ÑA, SPAIN

PhD THESIS

Compiler Framework

for the Automatic Detection

of Loop-Level Parallelism

Author:
Manuel Arenaz Silva

PhD Advisors:
Dr. Juan Touriño Domínguez
Dr. Ramón Doallo Biempica

A Coruña, January 2003

Dr. Juan Touriño Domínguez
Profesor Titular de Universidad
Dpto. de Electrónica y Sistemas
Universidad de A Coruña

Dr. Ramón Doallo Biempica
Catedrático de Universidad
Dpto. de Electrónica y Sistemas
Universidad de A Coruña

CERTIFICAN

Que la memoria titulada “Compiler Framework for the Automatic Detection
of Loop-Level Parallelism” ha sido realizada por D. Manuel Carlos Arenaz
Silva bajo nuestra dirección en el Departamento de Electrónica y Sistemas de
la Universidad de A Coruña y concluye la Tesis Doctoral que presenta para
optar al grado de Doctor en Informática.

A Coruña, 3 de Enero de 2003

Fdo.: Juan Touriño Domínguez
Codirector de la Tesis Doctoral

Fdo.: Ramón Doallo Biempica
Codirector de la Tesis Doctoral

Fdo.: Ramón Doallo Biempica
Director del Dpto. de Electrónica y Sistemas

To my parents, for everything.

Acknowledgments

One does not realise the considerable effort required to write a PhD Thesis
until one has actually written it. It is at that moment, on looking back, that
the important and essential part played by the PhD advisors can be more
clearly appreciated.
It is for that reason that I want to thank Dr. Ramón
Doallo and Dr. Juan Touriño for directing me throughout this work.

I also want to acknowledge Rosa Vázquez for her patience and comprehen-

sion during the period of time that I have been writing this thesis.

I gratefully thank to the following institutions for funding this work: De-
partment of Electrónica y Sistemas of A Coruña for the human and mate-
rial support, University of A Coruña for financing my attendance at some
conferences, and Xunta de Galicia and Spanish Goverment for the projects
FEDER 1FD97-0118, PGIDT01-PXI10501PR and MCYT-FEDER TIC2001-
-3694-C02-02.

Manuel Arenaz

Resumen de la Tesis

Introducción

El desarrollo de aplicaciones eficientes para las máquinas paralelas disponibles
en la actualidad es una tarea complicada que exige un gran conocimiento de las
características de la máquina por parte del programador. Una aproximación
que permite simplificar esta tarea consiste en proporcionar al programador una
tecnología de compilación capaz de generar automáticamente código paralelo
a partir de un código fuente diseñado para ser ejecutado de manera secuencial
en un único procesador.

El proceso de paralelización automática de un código secuencial consta de
dos etapas bien diferenciadas: detección de las partes del código que se pueden
ejecutar en paralelo, y generación de código paralelo que no altere la semántica
del código secuencial. En esta tesis se aborda principalmente el problema de
detección en el ámbito de los códigos irregulares.

Las técnicas actuales de detección de paralelismo están basadas en el
análisis de las dependencias que existen entre las sentencias del programa.
Estas técnicas son efectivas en el ámbito de los códigos regulares debido a que,
en este tipo de códigos, las expresiones de los índices de las referencias a arrays
a menudo se pueden expresar como funciones lineales o afines de los índices de
los bucles en que aparecen. Sin embargo, los códigos irregulares son todavía
un reto debido a que dichas expresiones contienen referencias a arrays cuyo
valor, en general, no se puede determinar en tiempo de compilación. Esta
característica hace que el compilador no pueda obtener información precisa
acerca de las dependencias del programa.

Este trabajo de investigación ha dado lugar a varias publicaciones en el
campo de la detección automática de paralelismo [4, 7]. Los conocimientos que
han permitido llevarlo a cabo fueron adquiridos a través del estudio detallado

ix

x

del código fuente de un conjunto de aplicaciones irregulares. Como resultado
de estos estudios han surgido una serie de publicaciones en el ámbito de la
generación automática de código paralelo, siendo los más relevantes [5, 6, 8].

Metodología Utilizada

En esta tesis presentamos una técnica de detección de paralelismo a nivel
de bucle orientada, principalmente, al análisis de códigos irregulares. La
metodología utilizada consta de dos partes bien diferenciadas. La primera
parte consiste en la construcción de un entorno de compilación capaz de ex-
traer del código fuente la información relativa a los tipos de cálculos (en ade-
lante llamados kernels) que se realizan durante la ejecución de un bucle. En la
segunda parte se analiza la información recabada por el entorno de compilación
con el fin de identificar aquellos bucles que es posible ejecutar en paralelo. Los
detalles acerca de cada una de estas partes se describen a continuación.

La detección automática de paralelismo requiere tener un conocimiento
preciso acerca del flujo de valores que se producirá entre las variables de un
programa durante la ejecución del mismo. El entorno de compilación pro-
puesto está basado en la representación Gated Single Assignment (GSA) de
los programas, la cual permite analizar sintácticamente el flujo de valores. La
construcción del entorno consta de los siguientes pasos:

1. Traducción del código fuente del programa a la forma GSA.

2. Reconocimiento de los kernels básicos que se calculan durante la eje-

cución del bucle.
El objetivo que se persigue en esta fase es descomponer el cuerpo del bu-
cle en un conjunto de kernels más sencillos e identificar las dependencias
que existen entre ellos. El procedimiento empleado es el siguiente:

(a) Búsqueda de las componentes fuertemente conexas (SCCs) que con-

tiene el grafo de dependencias de la representación GSA.

(b) Reconocimiento del kernel básico asociado a cada SCC. Esta tarea
se lleva a cabo mediante un algoritmo de clasificación de SCCs que
analiza de forma exhaustiva todas las operaciones que se realizan en
las sentencias de la SCC. Este algoritmo permite reconocer una gran
variedad de kernels básicos, como por ejemplo, formas complejas

xi

de variables de inducción, operaciones de reducción con variables
escalares y array (incluidas operaciones de tipo mínimo/máximo),
asignaciones irregulares o reducciones irregulares.

(c) Clasificación de las dependencias entre SCCs. La búsqueda de las
dependencias se realiza durante la ejecución del algoritmo de clasi-
ficación de SCCs aprovechando el análisis exhaustivo de todas las
expresiones que componen el cuerpo del bucle. En esta fase se dis-
tinguen varios tipos de dependencias con el fin de identificar las más
relevantes desde el punto de vista del reconocimiento de kernels más
complejos que los representados mediante SCCs.

Toda la información obtenida durante la ejecución de las fases (b) y
(c) se representa en una estructura de datos que denominamos grafo de
SCCs, la cual se utilizará como soporte para las etapas posteriores de
construcción del entorno de compilación.

3. Reconocimiento del conjunto de kernels que se calculan en el bucle.

En general, los cálculos que se realizan en un bucle se pueden represen-
tar bien como kernels básicos bien como kernels más complejos que son
el resultado de combinar varios kernels básicos. Para la realización de
esta tarea hemos diseñado un algoritmo que está basado en el análisis
del grafo de SCCs. Algunos ejemplos de nuevos tipos de cálculos re-
conocidos mediante este algoritmo son mínimo/máximo con posición o
consecutively written array.

Una vez finalizada la construcción del entorno de compilación, el compi-
lador dispone de información acerca del conjunto de kernels que se calculan
durante la ejecución de un bucle. En la literatura se han propuesto una gran
variedad de métodos que permiten transformar el código secuencial de algunos
tipos de kernels irregulares en un código paralelo equivalente. La idea básica
de nuestra técnica de detección automática de paralelismo consiste en utilizar
la información proporcionada por el entorno para determinar cuales de dichas
transformaciones se pueden aplicar en cada caso. Nótese que con esta aproxi-
mación el compilador utiliza las transformaciones de código como soporte para
asegurar que, en tiempo de ejecución, las dependencias propias de cada kernel
se respetan y, de esta manera, se preserva la semántica del código secuencial.

xii

Conclusiones

En esta tesis se han abordado, principalmente, dos temas relacionados con el
análisis automático de los programas orientado a la extracción de paralelismo
del código fuente. Por una parte, hemos propuesto una técnica de compilación
que permite reconocer una gran variedad de kernels mediante el análisis de
anidamientos de bucles que contienen computación de tipo regular e irregu-
lar. Por otra parte, hemos descrito la manera de utilizar nuestro esquema de
reconocimiento como un entorno de compilación que hace posible la detección
automática de paralelismo en códigos irregulares.

Las principales aportaciones de la tesis se pueden resumir en los siguientes

puntos:

• Hemos propuesto un algoritmo de clasificación de SCCs basado en la
forma GSA de los programas que permite reconocer una gran variedad
de kernels básicos tanto de computación regular como irregular.
• Hemos propuesto un algoritmo de clasificación del grafo de SCCs de
un bucle. Este algoritmo está orientado al reconocimiento del conjunto
de kernels que se calculan durante la ejecución del bucle. Estos kernels
pueden consistir tanto en kernels básicos como en kernels más complejos.
• Hemos demostrado que los algoritmos descritos en los apartados ante-
riores pueden ser utilizados como potentes herramientas de recopilación
de información que proporcionan al compilador el soporte necesario para
la implementación de otras técnicas de compilació