Source: http://www.ac.uma.es/~asenjo/PAGES/phd/memoria/memoria.html
Timestamp: 2018-01-22 18:15:56+00:00

Document:
TESIS DOCTORAL Rafael Asenjo Plaza
Factorización LU de matrices dispersas en multiprocesadores
Málaga, 15 de Diciembre de 1997
Muchos años después, [...] Aureliano Buendía había de recordar aquella tarde remota en que su padre lo llevó a conocer el hielo.
``Cualquier tecnología suficientemente avanzada es indistinguible de la magia.''
Fichero PostScript de la memoria:UMA-DAC-97-32.ps.gz 1.6Mbytes (10Mbytes descomprimido)
Director: Emilio López Zapata
Presidente: Francisco Tirado Fernández Arquitectura de Computadores y Automática. Complutense de Madrid.
Vocal: Eduard Ayguade Parra Arquitectura de Computadores. Politecnica de Cataluña.
Vocal: Emilio Luque Fadón Arquitectura de Computadores y Sistemas Operativos. Autónoma de Barcelona
Vocal: Inmaculada García Fernández Arquitectura de Computadores y Electrónica. Univ. Almería
Secretario: Jose María Troya Linero Lenguajes y Ciencias de la Computación. Univ. Málaga
Indice; indpref.ps.gz (94K)
Parte I Algoritmos paralelos de factorización LU dispersa 1
1 Factorización LU dispersa (pp. 1-34) cap1.ps.gz (1257K -debido a figuras con patrones de matrices-)
2 Arquitecturas y programación paralela (pp. 35-50) cap2.ps.gz (109K)
3 Paralelización de métodos directos (pp. 51-90) cap3.ps.gz (222K)
Parte II Compilación
4 Soporte HPF-2 para códigos dispersos (pp. 91-122) cap4.ps.gz (146K)
5 Paralelización automática de códigos dispersos (pp. 123-150) cap5.ps.gz (131K)
Conclusiones; concl.ps.gz (84K)
Apéndice A. Factorización por bloques (pp. 155-156) apendA.ps.gz (81K)
Referencias (pp. 157-168) ref.ps.gz (98K)
Referencias de otras publicaciones del autor relacionadas con la tesis
Muchas veces me he planteado la opción de comenzar y acabar esta sección únicamente con la palabra ``Gracias.''... y nada más. Sencillamente por evitar el resumir en una sola página la mención de tantas personas a las que debo mucho:
A mi director de Tesis, Emilio L. Zapata, fuente de motivación y al que considero mi maestro y ejemplo de dedicación. Muchas gracias por, como tú dices, ``enseñarnos a pescar''.
A David Padua por la atención, dedicación en largas horas de reuniones, y su espléndida hospitalidad. También a Iain Duff por sus consejos y supervisión. A Juan Touriño, Oscar Plata, Eladio Gutiérrez, Guillermo Pérez, Gerardo Bandera y Manuel Ujaldón, les debo su productiva colaboración.
A mis padres, siempre preocupados por mi felicidad, alentadores y reconfortantes en los momentos bajos y a los que es imposible pagar su cariño como se merecen, también debo este trabajo. A mi hermana, cómplice y amiga, tanto en la infancia como en la madurez.
A la memoria de Gabriel y Adelaida, y a María Teresa, que gracias a su esfuerzo y lucha son, seguramente en un mayor porcentaje de lo que incluso yo creo, responsables de la gran cantidad de oportunidades que he tenido.
A los amigos y compañeros de departamento, Nico, Mario, Juan, Oswaldo, Manuel, Julio, Felipe, Pablo, Julián, Andrés, Francisco, Mª Antonia, Patricia, Ezequiel y Mª Carmen, maestros del trabajo bien hecho y a todos los que mantienen día a día el departamento como un lugar de camaradería, alegre, distendido y bullicioso de trabajo.
A Nacho, Javi, Pedro, Juan, Miguel, Jesús, José, Pepe y Ester, y demás amigos pese a la distancia y los años.
A los miembros del departamento de Computer Science de la Univ. de Illinois, especialmente a Yuan Lin, Bill Pottenger y Sheila Clark. También a Jacko Koster y los demás compañeros del Parallel Algorithm Team de CERFACS (Francia).
A K.I.M. McKinnon y su grupo del Depto. de Matemáticas de la Univ. de Edimburgo, así como a los miembros del EPCC de la misma universidad, por su soporte e introducción en la programación paralela del Cray T3D.
También agradecemos al CIEMAT (Madrid), CINECA (Italia), EPFL (Suiza) y Cray Research Inc. (Minnesota, USA), por habernos brindado acceso a sus plataformas Cray T3D y T3E.
Agradecemos el soporte y la financiación de este trabajo y de las estancias realizadas en el extranjero a los proyectos TIC96-1125-C03 de la CICYT, BRITE-EURAM III BE95-1564 de la Unión Europea, ERB4050P1921660 del programa de Movilidad y Capital Humano y al programa TRACS (Training and Research on Advanced Computing Systems) del Centro de Computación Paralela de Edimburgo (EPCC).
Aunque en último lugar, con mayor énfasis quiero agradecer a Mª Ángeles todo el cariño, apoyo incondicional, alegrías, colaboración y comprensión que ella me da, y con la cual vivo cada día con una sonrisa en la cara.
Amenudo nos encontramos frente a compromisos del tipo prestaciones/coste. Esta dualidad que se manifiesta en todos los ámbitos, aparece, como no, en muchos de los párrafos de esta memoria. Ya en la propia tarea de realizar una tesis, aflora un primer compromiso: ante un problema, bien definido por el director de tesis, al estudiante se le presentan diversos caminos sin explorar. Cuando compensa seguir por un camino sin saber lo que hay al final, o volver a atrás para tomar otra dirección es una cuestión de intuición y presenta un ineludible compromiso. Con ingenio y perseverancia se pueden encontrar distintas soluciones al final de sus correspondientes caminos. Si se ha explorado una buena parte del mapa y se han topografiado las regiones hasta entonces vírgenes, el relato del viaje y la descripción de las soluciones, constituyen una metodología apropiada para realizar la tesis. Es claramente una tarea de investigación, pero no podemos negar que en el proceso también hay una gran componente de ingeniería, donde aparece el compromiso entre el tiempo invertido y el número de caminos explorados.
En la presente tesis, el problema estaba bien definido: encontrar soluciones paralelas eficientes para algoritmos de factorización dispersa LU y aplicar las técnicas encontradas en el camino a otros problemas irregulares. Nosotros hemos explorado tres rutas: paralelización manual, semi-automática y por último, automática. En este punto, aparece de nuevo el compromiso entre las prestaciones del código generado y el coste en términos de tiempo de desarrollo. Es decir, la paralelización manual consigue las mejores prestaciones a cambio de un gran esfuerzo en el desarrollo y depuración de los códigos. La situación al paralelizar usando herramientas automáticas es recíproca, situándose la paralelización semi-automática en un punto intermedio entre los otros dos paradigmas.
La motivación que soporta el esfuerzo que realizamos en resolver problemas irregulares es definitiva: se estima que al menos el cincuenta por ciento de todos los programas científicos son irregulares y que más del cincuenta por ciento de todos los ciclos de reloj consumidos en supercomputadores son consumidos por este tipo de códigos.
Dentro de los problemas irregulares hemos elegido como caso de estudio la resolución de sistemas de ecuaciones dispersos. Esta elección se justifica en que este problema abarca varios de los paradigmas presentes en otros códigos irregulares. De esta forma, las técnicas encontradas son útiles a otros problemas con similares características al primero: principalmente algoritmos que presentan llenado o movimiento de datos dentro de una estructura irregular.
De cualquier modo, la resolución paralela de sistemas de ecuaciones dispersos es un problema relevante por sí sólo. Así como es una realidad que los grandes problemas necesitan grandes computadores para ser resueltos, es igualmente cierto que en el corazón de la mayoría de los problemas computacionales a gran escala está la solución de grandes sistemas de ecuaciones dispersos.
Sin embargo, durante la realización de esta tesis, hemos querido ir más lejos, dirigiendo nuestra búsqueda con el objetivo de encontrar soluciones generales para la paralelización de códigos irregulares, y no el de resolver únicamente el problema particular de la factorización de matrices dispersas. En este punto es donde entran en juego las técnicas de compilación ya sean automáticas o semi-automáticas.
De este modo, la memoria se organiza en dos partes bien diferenciadas: la primera aborda directamente el problema de la paralelización manual de códigos dispersos de resolución de ecuaciones; la segunda parte trata de aplicar los conocimientos adquiridos en la primera, para extraer técnicas genéricas que puedan ser aplicadas automática o semi-automáticamente mediante un compilador.
La primera parte tiene tres capítulos. En el primero, formulamos el problema a resolver, enunciamos las distintas alternativas para abordarlo y profundizamos en una de ellas. Además describimos las características relevantes y las estructuras de datos apropiadas al trabajar con matrices dispersas. En el capítulo 2 introducimos los conceptos básicos de paralelismo (arquitecturas y programación paralela) utilizados a lo largo de esta memoria de forma que podamos seguir sin problemas su lectura. Finalmente en el capítulo 3 desarrollamos un eficiente programa paralelo para la resolución de sistemas de ecuaciones dispersos. Este algoritmo es evaluado experimentalmente y comparado con un algoritmo estándar de resolución, comprobándose las buenas prestaciones que proporciona tanto en secuencial como en paralelo. Además de este resultado, el manejo con este algoritmo nos ha permitido familiriazarnos con el problema, adquiriendo una visión global que nos facilita ahora abordar la segunda parte de la tesis. En esta primera parte nos ha sido de gran ayuda la colaboración con Iain Duff durante nuestra estancia en CERFACS, así como el entrenamiento en la programación del Cray T3D que nos brindaron en el EPCC de la Universidad de Edimburgo. Los trabajos publicados de esta primera parte de la tesis se encuentran en [4, 8].
La segunda parte la organizamos en dos capítulos. Abordamos primero la paralelización semi-automática de códigos dispersos en el capítulo 4. Aquí se determinan las limitaciones de los compiladores actuales de paralelismo de datos al intentar expresar códigos dispersos de factorización. Para salvar esas limitaciones proponemos una extensión sencilla y eficiente al lenguaje HPF-2 que resulta válida para otros problemas dispersos o irregulares. En el capítulo 5 se da un paso más en complejidad, tratando de delegar completamente el problema de la paralelización en el compilador. La tecnología actual de compiladores paralelos no es capaz de manejar eficientemente problemas irregulares, por lo que presentamos en este capítulo algunas técnicas que permiten solventar este inconveniente. Para ello hemos partido de un algoritmo secuencial de factorización dispersa, identificando las técnicas necesarias para su paralelización automática. Para justificar la implementación de estas técnicas en un compilador paralelo hemos comprobado que también son aplicables a una gran variedad de códigos numéricos dispersos. En esta segunda parte hemos contado con el apoyo de David Padua durante nuestras estancias en la Universidad de Illinois. En [6, 5, 1, 9, 2, 3] encontramos más detalladamente la evolución del trabajo desarrollado en esta línea.
Finalmente, en el capítulo de conclusiones, sintetizamos las principales aportaciones de esta tesis, así como enumeramos las principales líneas en las que seguiremos trabajando en el futuro.
Recientemente celebraron en la Universidad de Illinois el nacimiento simbólico de HAL 9000, que en la novela de Arthur C. Clarke ``2001: A Space Odyssey'' despierta en Enero de 1997 en el Digital Computer Laboratory de la misma Universidad. Es cierto que aún no existe ninguna máquina tan inteligente ni versátil como HAL, pero siempre he sido optimista al imaginarme el futuro y la evolución de la ciencia... Como dijo David J. Kuck con motivo de esta celebración: ``La computación paralela práctica es algo escurridizo por el momento. HAL tendría que ser una máquina paralela, y hasta que el problema del paralelismo práctico sea resuelto, no seremos capaces de construir HAL''.
Sabedores de la importancia de la computación dispersa e irregular, hemos profundizado en esta tesis en la paralelización de este tipo de problemas. Hemos elegido la resolución de ecuaciones dispersas como caso de estudio por constituir un problema con muchos de los paradigmas representativos de la computación irregular. En resumen, en nuestra búsqueda hemos programado en C, F90 y F77, para plataformas como el CRAY T3D, T3E y el SGI Power Challenge, hemos utilizado librerías de comunicación PVM, MPI y SHMEM, los entornos de paralelismo de datos CRAFT y HPF-2, hemos extendido la librería DDLY y usado la herramienta Cocktail en el desarrollo del compilador, hemos comparado con CHAOS, y finalmente hemos identificado algunas limitaciones de los paralelizadores PFA y Polaris, proponiendo soluciones.
Las principales aportaciones y las líneas de investigación que pretendemos seguir en el futuro se discuten a continuación.
Volviendo a la analogía, comentada en el prefacio, entre la investigación y la búsqueda del camino apropiado en una región desconocida, en esta tesis hemos topografiado tres rutas para alcanzar soluciones al problema de la resolución paralela de sistemas de ecuaciones dispersos: la paralelización manual, semi-automática y automática.
Paralelización manual
Hemos desarrollado un algoritmo secuencial, SpLU, para resolver sistemas de ecuaciones dispersos, que incluye las etapas de análisis-factorización y resolución triangular. El algoritmo secuencial conduce en muchos casos a un error de factorización y a un llenado menor que el que consigue la rutina estándar MA48. En general, en los experimentos realizados nuestro algoritmo SpLU ha resultado ser más estable que la rutina MA48. Adicionalmente el tiempo de factorización puede llegar a ser bastante menor que el de la MA48.
Hemos comprobado que la rutina MA48 no puede ser paralelizada eficientemente debido a su organización left-looking. Sin embargo nuestro algoritmo exhibe un alto grado de paralelismo, no sólo por basarse en una aproximación right-looking, sino también por explotar la dispersión de la matriz agrupando un cierto número de pivots compatibles. El algoritmo paralelo presenta una eficiencia muy alta, superior a las que proporcionan otros trabajos previos en la misma línea.
Paralelización semi-automática
Hemos identificado las limitaciones de los compiladores de paralelismo de datos CRAFT y HPF a la hora de expresar códigos dispersos. Básicamente estas limitaciones se derivan de la imposibilidad de estas herramientas para manejar estructuras de datos dinámicas o comprimidas. Esto impide la paralelización eficiente de algoritmos dispersos dado que se apoyan en las mencionadas estructuras de datos. Nuestra aportación ha consistido en extender la capacidad de HPF-2, mediante la inclusión de una directiva (SPARSE) y la extensión semantica de otras ya existentes. De esta forma, permitimos al programador escribir códigos en F90 basados en estructuras de datos con listas enlazadas o vectores comprimidos, delegando en el compilador la tarea de generar la versión paralela. La idea más importante de nuestra extensión es permitir al programador especificar mediante directivas, no sólo la distribución de los datos, sino también la estructura de estos datos en memoria. Las extensiones son mínimas y simples pero al mismo tiempo suficientes para proporcionar una gran flexibilidad al programador.
Adicionalmente, hemos desarrollado parte del módulo de compilación que completa el compilador de HPF-2 para soportar las nuevas extensiones propuestas. Más precisamente, disponemos del analizador léxico y sintáctico para reconocer la directiva añadida, junto con las rutinas en tiempo de ejecución encargadas de la distribución de datos y comunicaciones. Para construir los analizadores hemos hecho uso de la herramienta Cocktail para diseño de compiladores, mientras que las rutinas en tiempo de ejecución se han construido siguiendo la filosofía de las DDLY.
Hemos simulado la salida paralela generada por nuestro compilador, partiendo de un algoritmo secuencial en F90 anotado con las nuevas directivas, comparable en prestaciones a la rutina MA48. La salida paralela ha resultado ser bastante eficiente, presentando el mismo error de factorización y llenado que la versión secuencial. También hemos comparado nuestra aproximación con la técnica Inspector-Executor implementada en la librería CHAOS para la paralelización de códigos irregulares, resultando esta última claramente insuficiente.
Hemos analizado la salida de dos paralelizadores automáticos, PFA y Polaris, cuando la entrada es un código de factorización dispersa en F77. Ninguno de los dos obtiene buenos resultados debido a ciertas limitaciones en las técnicas de detección y paralelización de ambos compiladores. Para resolverlo hemos introducido cuatro técnicas para la detección de dependencias y paralelización automática de códigos dispersos: monotonía en los arrays que acotan bucles, no solapamiento de variables de inducción, detección de vectores de permutación, y extensión de las técnicas de privatización.
Hemos aplicado estas técnicas a nuestro algoritmo de factorización en F77 obteniendo eficiencias muy altas en la SGI Power Challenge de memoria compartida. Adicionalmente estas técnicas se han mostrado válidas en otros códigos irregulares dispersos, justificándose así su necesaria implementación en los paralelizadores automáticos.
Nuestro algoritmo SpLU para la resolución paralela de sistemas de ecuaciones dispersos puede ser mejorado en dos puntos principales. El primero está orientado a reducir el coste de las comunicaciones aplicando una distribución cíclica por bloques en lugar de una cíclica pura. El segundo se centra en reducir el movimiento de datos y facilitar el insertado de entradas utilizando una estructura de listas enlazadas desordenadas tanto por filas como por columnas. Estos dos aspectos unidos a un mayor cuidado en el aprovechamiento de la cache pueden resultar en mejores prestaciones.
Sin embargo, más que optimizar un problema particular, nos parece más interesante simplificar las técnicas de programación paralela ya sea de forma semi-automática o automática. Nosotros hemos abordado la construcción de un módulo de compilación que procesa sólo la directiva SPARSE introducida, pero también es necesario contemplar extesiones para problemas no estructurados. En cuanto a la aproximación automática, las técnicas propuestas para poder paralelizar códigos basados en estructuras de datos comprimidas, ya están siendo implementadas en Polaris en colaboración con el grupo de investigación dirigido por el profesor David Padua en Illinois.
En la misma línea de la paralelización automática, aparte de las estructuras de datos comprimidas, es necesario trabajar en otras situaciones con estructuras de datos dinámicas basadas en punteros, como las listas, árboles, etc. La detección automática de paralelismo de este tipo de problemas presenta un gran desafío al que nos queremos enfrentar. Por ejemplo, los códigos de factorización LU basados en listas enlazadas en C o en F90 no pueden ser paralelizados automáticamente con la tecnología actual.
Dando un paso más en complejidad y en aras de facilitar la tarea al programador, no descartamos la idea de dedicar algunos esfuerzos al campo de los reestructuradores de códigos densos secuenciales en dispersos y paralelos. Bik y Pingali presentan algunas soluciones para generar un código disperso secuencial a partir del código denso asociado, pero por el momento, sus resultados aún dejan un amplio margen para la investigación en este campo. La ventaja que presenta abordar la paralelización automática de un código disperso partiendo de la versión densa, estriba principalmente en la mayor cantidad de información que puede obtener el compilador. Más precisamente, el análisis de dependencias de algoritmos numéricos dispersos se simplifica si partimos de la versión densa.
Tue Nov 25 12:42:14 MET 1997

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución