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

  1. AMOR LOPEZ, MARGARITA
Dirixida por:
  1. Francisco Argüello Pedreira Director
  2. Juan López Gómez Director

Universidade de defensa: Universidade de Santiago de Compostela

Ano de defensa: 1998

Tribunal:
  1. Emilio López Zapata Presidente/a
  2. Javier Díaz Bruguera Secretario/a
  3. José Duato Marín Vogal
  4. María Inmaculada García Fernández Vogal
  5. Ramón Doallo Vogal
Departamento:
  1. Departamento de Electrónica e Computación

Tipo: Tese

Teseo: 64061 DIALNET

Resumo

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.