Algoritmos divide-y-vencerás en mallas de procesadores

Zusammenfassung

En esta tesis se propone una metodología general para particionar y proyectar algoritmos divide y vencerás sobre computadores paralelos de topología malla y memoria distribuida. El trabajo parte de la obsrvación de que durante la evaluación de un algoritmo sobre un multicomputador es necesario redistribuir los datos entre los procesadores en una gran variedad de formas, tanto regulares como irregulares. En general, esto implica complejos movimientos de datos, cuya visualización puede ser bastante difícil. La metodología desarrollada se basa en una combinación de dos técnicas: la proyección vector y las permutaciones índice-dígito. Esta técnicas nos permiten formular de forma precisa el flujo de datos de los algoritmos y, en muchos casos, realizar importantes simplificaciones. Este punto de vista se aplica a la paralelización de las versiones más utilizadas de la transformada rápida de fourier, a los más significativos algoritmos de resolución de sistemas tridiagonales y a algoritmos irregulares como el algoritmo Barnes-Hut del problema de los N cuerpos. Adicionalmente, también se aborda un problema de gran interés tanto para la programación paralela como para la implementación VLSI: la proyección de árboles r-arios completos sobre las topologías array lineal y malla. Presentamos una nueva metodología para realizar esta proyección que puede ser una alternativa a las técnicas usuales, basadas en árbol en "H" o en baldosas. En todos los casos, la distribución de los nodos del árbol entre los procesadores es balanceda y las comunicaciones son sólo entre procesadores vecinos.