Nuevos modelos de predicción en computación paralela

Zusammenfassung

En este trabajo se estudian los modelos de computación paralela más importantes de los últimos años: el modelo LogP, el modelo C3 y el modelo BSP, Todos ellos presentan contribuciones importantes pero también inconvenientes que los limitan como modelos de carácter general. Se introducen dos nuevas propuestas: el modelo de Patrones y el modelo BSP Sin Barreras (BSPWB). El modelo de Patrones ofrece un conjunto empírico de conductas de los algoritmos que utilizan funciones de comunicaciones colectivas. Cabe destacar el estudio realizado sobre los patrones inyectivos y los patrones tipo "uno a muchos", tanto para multicomputadoras de memoria distribuida como para redes de área local. El modelo BSP Sin Barreras es un modelo de computación asíncrona basado en la utilización de librerías estándar tipo PVM o MPI. Se presenta una metodología para obtener los valores de los parámetros del modelo BSP. Sin Barreras en las librerías MPI y PVM, y sobre diferentes arquitecturas paralelas y redes de estaciones de trabajo. Esta metodología permite observar el grado de cumplimiento de la hipótesis de la h-relación sobre las diferentes máquinas. Las predicciones del modelo BSPWB se muestran con ejemplos que hacen uso de diferentes patrones de comunicaciones y diferentes tamaños de mensajes. En el caso de la Paralelización de la Transformada Rápida de Fourier se utilizan tamaños grandes de mensajes y el patrón de comunicaciones PingPong. Para la ordenación paralela Quicksort, se utiliza el patrón Exchange. El algoritmo de programación dinámica de la asignación de un único recurso utiliza gran cantidad de mensajes de tamaño pequeño. Y el algoritmo de ordenación paralela por muestreo regular utiliza diferentes patrones: OnetoAll, AlltoOne, AlltoAll y diferentes tamaños de mensajes: grandes y pequeños. Los resultados computacionales muestran como el BSPWB permite predecir las comunicaciones con un margen