Paralelización de algoritmos de sort-merge sobre distintas arquitecturas

Abstract

Se presenta el desarrollo y análisis de performance de la paralelización de un algoritmo de ordenación de archivos basado en la técnica de Sort-Merge sobre distintas arquitecturas. Se estudian tres modelos de arquitectura: monoprocesador, red heterogénea con soporte PVM e hipercubo de transputers , trabajando en C y C paralelo. El algoritmo planteado consiste en una paralelización funcional y de datos del método de ordenación Merge-Sort, definiendo un conjunto de procesos encargados de la ordenación y mezcla de bloques de archivos, coordinados por un proceso maestro.

La metodología del trabajo consistió en las siguientes etapas: La implementación del algoritmo sobre una arquitectura de red con procesadores heterogéneos. Migración del algoritmo a una arquitectura paralela (hipercubo de transputers). Obtención de tiempos de ejecución, comunicación y sincronismo para su posterior comparación.

Por último, se analizan resultados y conclusiones obtenidas considerando factores de tiempo, performance, speed up y escalabilidad al aplicar el algoritmo en cada arquitectura.