PDF de programación - Técnicas de compilación para la paralelización de códigos irregulares

UNIVERSIDAD DE SANTIAGO DE COMPOSTELA

FACULTAD DE FÍSICA

DEPARTAMENTO DE ELECTR ÓNICA Y COMPUTACI ÓN

TESIS DOCTORAL

Técnicas de compilación para la

paralelización de códigos irregulares

Presentada por:

David Expósito Singh

Octubre 2003

Dr. Francisco Fernández Rivera,
Profesor Titular de Arquitectura y
Tecnología de Computadores de la
Universidad de Santiago de Compos-
tela.

Dra. María Martín Santamaría,
Profesora Titular de Arquitectura y Tecno-
logía de Computadores de la Universidad
de A Coruña.

CERTIFICAN:
Que la memoria titulada “Técnicas de compilación para la paralelización
de códigos irregulares”, ha sido realizada por D. David Expósito Singh
bajo nuestra dirección en el Departamento de Electrónica y Computación de la
Universidad de Santiago de Compostela y concluye la Tesis que presenta para
optar al grado de Doctor en Ciencias Físicas.

Santiago, 16 de Octubre de 2003

Dr. Francisco Fernández Rivera
Codirector de la tesis

Dra. María Martín Santamaría
Codirectora de la tesis

Fdo. Dr. Diego Cabello Ferrer,
Director del Departamento de
Electrónica y Computación.

A mis padres
y a mis hermanos

Agradecimientos

Quiero dar mi más sincero agradecimiento a todas las personas que han contribuido a

la realización de esta tesis tanto en el ámbito académico como en el personal.

El primer lugar quiero dar las gracias a mis codirectores, los profesores D. Francisco
Fernández Rivera y Dña. María Martín Santamaría, por toda la ayuda que me han
prestado. Ellos me dieron la oportunidad de iniciar mis estudios de doctorado, y me han
ofrecido siempre todo su apoyo y colaboración. Quiero agradecerles muy especialmente
todo el tiempo y esfuerzo que me han dedicado, así como la confianza que han depositado
en mí.

También quiero expresar mis agradecimientos a todos los miembros del Departamento
de Electrónica y Computación, y en particular a aquellos que pertenecen, o han perte-
necido, al Grupo de Arquitectura de Computadores. Con ellos he compartido muchos
momentos “mágicos” que han hecho que esta etapa de mi vida haya sido tan gratificante.

Gracias especialmente a aquellos con los que en algún momento he compartido des-
pacho: Álvaro, Antonio, Dora, Inma, Juanjo, Marcos, Patricia, Pichel y Roberto. Todos
ellos me ofrecieron su amistad, y me ayudaron en los momentos más difíciles.

A Antonio le debo mi iniciación (o casi debería decir inicialización) en la gestión de
redes de computadores. Él fue la primera persona del grupo que conocí y la que despertó
en mí el interés por la programación de sistemas distribuidos. Roberto ha hecho que mi
vida fuera mucho más amena, y me ha dado ideas que resultaron de gran utilidad para mi
trabajo. A Juan le tengo que agradecer, ante todo, su compañía a lo largo de todos estos
años. Se puede decir que él estaba allí desde el primer momento, desde aquella tarde de
julio. Juntos hemos pasado muchas aventuras. Lo más sorprendente es que siempre me ha
sabido ayudar, independientemente del tipo de problema que hubiera tenido, y en parte,
gracias a su ayuda esta tesis ha podido finalizarse.

Quiero agradecer también al profesor Michael O’Boyle del Institute for Computing

Systems Architecture de la Universidad de Edimburgo, por su interés mostrado en mi tra-
bajo, así como por su asesoramiento en distintos tópicos relacionados con la paralelización
de códigos irregulares.

Quiero darles las gracias a todos mis amigos que me ofrecieron su compañía y me
prestaron su ayuda cuando más la necesitaba. En especial a Vladimir, por su colaboración
en el diseño gráfico de esta tesis. A Emilio, con quien compartí grandes momentos en
Escocia, y me ofreció la infraestructura necesaria para mantenerme comunicado y poder
realizar buena parte de mi trabajo de investigación. A Álvaro, por todos los grandes
momentos que hemos pasado juntos y por su carácter optimista que siempre ha sido una
fuente de motivación para mí. A Olalla, por su amistad, aprecio y simpatía durante todo
este tiempo. A Silvia, por su compañía a lo largo de estos años, y por todas las risas y
sustos que hemos compartido.

Quiero agradecer al EPCC (Edinburgh Parallel Computing Centre), al CSC (Centro de
Supercomputación Complutense) y al CESGA (Centro de Supercomputación de Galicia)
por darme acceso a sus recursos de computación distribuida.

A la Xunta de Galicia por la beca predoctoral que he disfrutado durante estos años.
Igualmente, al CICYT por el soporte económico dado por el proyecto TIC2001-3694-
C02, a la Secretaria Xeral de I+D de Galicia por la financiación del proyecto PGIDT99-
PXI20602B, al Fondo Europeo de Desarrollo Regional (FEDER) por el proyecto 1FD97-
0118-C02 y al TRACS European Community Access to Research Infrastructure por el
proyecto HPRI-CT-1999-00026.

A mi familia, por todo el apoyo que siempre me han dado. Ellos han tenido la paciencia
necesaria para que yo pudiera realizar mi trabajo de la forma más cómoda y despreocu-
pada.

Xa para rematar, debo engadir nestes agradecementos unhas verbas a Paula. A ela
débolle moitas cousas. A parte da sua amizade e compañía, ela foi e é pra min unha
referencia en canto a capacidade de traballo e esforzo persoal. Con ela compartín unha
infinidade de momentos únicos, e a sua vitalidade fixo que eu poidera acadar moitas das
metas propostas nesta tese.

“Y no dejamos de preguntarnos,
una y otra vez,
Hasta que un puñado de tierra
Nos calla la boca . . .
Pero ¿es eso una respuesta? ”

Heinrich Heine

Lazarus

Índice General

Notación

Prefacio

1 Introducción

1.1 Arquitecturas paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

3

5

7

1.2 Modelos de programación paralela . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Herramientas de paralelización automática . . . . . . . . . . . . . . . . . . . 12

1.4 Códigos irregulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Contribución y organización de esta tesis . . . . . . . . . . . . . . . . . . . . 18

2 Caracterización del patrón de acceso a memoria

25

2.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2 Trabajo previo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.1 Caracterización de los patrones de acceso . . . . . . . . . . . . . . . 30

2.2.2 Caracterización geométrica del patrón de acceso . . . . . . . . . . . 33

2.3 Clasificación de las entradas de una indirección . . . . . . . . . . . . . . . . 35

2.3.1 Algoritmo de clasificación por slices

. . . . . . . . . . . . . . . . . . 37

2.3.2 Algoritmo de clasificación por slices modificado . . . . . . . . . . . . 40

2.3.3 Resultados experimentales . . . . . . . . . . . . . . . . . . . . . . . . 41

i

2.4 Caracterización geométrica de la indirección . . . . . . . . . . . . . . . . . . 43

2.4.1 Algoritmo de caracterización geométrica . . . . . . . . . . . . . . . . 44

2.4.2 Evaluación del rendimiento . . . . . . . . . . . . . . . . . . . . . . . 63

2.5 Caracterización del patrón de acceso . . . . . . . . . . . . . . . . . . . . . . 71

2.5.1 Obtención de la representación IARD . . . . . . . . . . . . . . . . . . 71

2.5.2 Transformación de la representación IARD . . . . . . . . . . . . . . . 72

2.5.3 Evaluación del Rendimiento . . . . . . . . . . . . . . . . . . . . . . . 76

3 Detección de dependencias

81

3.1 Técnicas de detección de dependencias de datos . . . . . . . . . . . . . . . . 83

3.2 Región de solape entre dos representaciones IARD . . . . . . . . . . . . . . . 84

3.3 Algoritmo para la determinación de la región de solape . . . . . . . . . . . . 86

3.4 Consideraciones de eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4 Optimización de códigos irregulares con una indirección

95

4.1 Trabajo previo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.1.1 Librerías para la paralelización de códigos irregulares . . . . . . . . . 96

4.1.2 Técnicas de paralelización de códigos irregulares

. . . . . . . . . . . 99

4.2 Paralelización de lazos irregulares . . . . . . . . . . . . . . . . . . . . . . . . 108

4.2.1 Private Region Technique . . . . . . . . . . . . . . . . . . . . . . . . 110

4.2.2

Sorted Private Region Technique . . . . . . . . . . . . . . . . . . . . 129

4.3 Mejora en la localidad de códigos secuenciales . . . . . . . . . . . . . . . . . 157

4.3.1 Adaptación del algoritmo SPRT a códigos secuenciales

. . . . . . . . 157

4.3.2 Análisis de eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

4.4 Mejora del balanceo de la carga . . . . . . . . . . . . . . . . . . . . . . . . . 168

4.4.1 Balanceo de la carga en la regla del propietario . . . . . . . . . . . . 170

4.4.2 Balanceo de la carga en las estrategias PRT y SPRT . . . . . . . . . . 178

5 Optimización de códigos irregulares con varias indirecciones

183

5.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

5.2 Trabajo previo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

5.2.1 Ejecución especulativa . . . . . . . . . . . . . . . . . . . . . . . . . . 187

5.2.2 Estrategia Inspector-Ejecutor . . . . . . . . . . . . . . . . . . . . . . 188

5.3 Algoritmo CYT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

5.3.1 Fase de inspección del algoritmo CYT . . . . . . . . . . . . . . . . . . 190

5.3.2 Fase de ejecución del algoritmo CYT . . . . . . . . . . . . . . . . . . 192

5.3.3 Análisis de eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

5.4 Algoritmos LCYT y LO-LCYT . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

5.4.1 Fase de inspección del algoritmo LCYT . . . . . . . . . . . . . . . . . 195

5.4.2 Fase de inspección del algoritmo LO-LCYT . . . . . . . . . . . . . . . 197

5.4.3 Fase de ejecución