El modelo de computación colectiva: una metodología eficiente para la ampliación del modelo de libreria de paso de mensajes con paralelismo de datos anidados

Abstract

Se propone el Modelo de Computación Colectiva para la traslación eficiente de algoritmos con paralelismo de datos anidados sobre arquitecturas paralelas reales. El modelo viene caracterizado por una tripleta (M. Div. Col) donde M representa la plataforma paralela, Div es el conjunto de funciones de división y Col el conjunto de funciones colectivas. Una función se dice colectiva cuando es realizada por todos los procesadores del conjunto actual. Los conjuntos de procesadores pueden ser divididos utilizando las funciones de Div. Se hace una propuesta para una implementación eficiente de los procesos de división con la idea subyacente a de que cada uno de los procesadores de uno de los conjuntos producto de la escisión mantiene una relación con uno (o más) de los procesadores en los otros subconjuntos. Esta relación determina las comunicaciones de los resultados producto de la tarea realizada por el conjunto al que el procesador pertenece. Esta estructura de división da lugar a patrones de comunicaciones que se asemejan a los de un hipercubo. La dimensión viene determinada por el número de divisiones demandadas mientras que la aricidad en cada dimensión es igual al número de subconjuntos solicitados. A semejanza de lo que ocurre en un hipercubo k-ario convencional, una dimensión divide al conjunto en k subconjuntos comunicados a través de la dimensión. Sin embargo, los subconjuntos opuestos según una dimensión no tienen porqué tener el mismo cardinal. A estas estructuras resultantes se las ha denominado Hipercubos Dinámicos. Se presenta una clasificación de problemas paralelos en función de las características de los datos de entrada y de salida de los mismos con respecto a la visión que de ellos tienen los procesadores de la máquina. La nomenclatura introducida se utiliza pra caracterizar los problemas que se pesentan en la memoria. Se aportan ejemplos de algoritmos tanto del tipo de los que se han denominado de Computación Colectiva como de Computación Colectiva Común. Este último tipo de algoritmos resuelven un tipo concreto de problemas según la clasificación introducida. Para ambos tipos de algoritmos se estudian diferentes formas de introducir equilibrado de la carga de trabajo y los resultados que produce cada una de ellas. Se presenta también una herramienta, La Laguna C, que representa una implementación concreta de las ideas subyacentes al Modelo de Computación Colectiva y se exponen los resultados computacionales obtenidos para varios algoritmos en diferentes arquitecturas