Tesis doctoral de Margarita Amor Lopez
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.
Datos académicos de la tesis doctoral «Algoritmos divide-y-venceras en mallas de procesadores.«
- Título de la tesis: Algoritmos divide-y-venceras en mallas de procesadores.
- Autor: Margarita Amor Lopez
- Universidad: Santiago de compostela
- Fecha de lectura de la tesis: 01/01/1998
Dirección y tribunal
- Director de la tesis
- Francisco Arguello Pedreira
- Tribunal
- Presidente del tribunal: Emilio Lopez Zapata
- José Duato Marin (vocal)
- Inmaculada Garcia Fernandez (vocal)
- Ramon Doallo Biempica (vocal)