Modelado del rendimiento de códigos irregulares paralelos en sistemas distribuidos

Abstract

La evolución de las tecnologías de la información nos permite abordar problemas en ciencia e ingeniería cada vez más grandes, complejos y con mejor resolución, obteniendo soluciones en un tiempo razonable. La necesidad, o posibilidad, de resolver estos problemas requieren, cada día más, el uso de las grandes infraestructuras computacionales disponibles en los centros de cálculo, o de los recursos distribuidos y coordinados a través de computación Grid sin necesidad de un control centralizado. Debido a esto, la programación en arquitecturas distribuidas es cada vez más popular, y, muchas veces, imprescindible, entre los miembros de la comunidad científica. Muchas veces se reciclan viejas técnicas para tratar con las nuevas arquitecturas. Así, los métodos de predicción de rendimiento, usados frecuentemente tanto por los arquitectos de computadores como por los creadores de compiladores, pueden ser adaptados para tener en cuenta las peculiaridades de estos nuevos sistemas distribuidos. Pero no todos los algoritmos pueden ser tratados de la misma forma. Hay una categoría especial de problemas, los llamados códigos irregulares, en los que cálculos, control de flujo, patrón de acceso a memoria y comunicaciones durante la ejecución dependen fuertemente de los datos de entrada, y no pueden ser caracterizados correctamente de forma estática. Estos problemas aparecen cada vez con mayor frecuencia en el software científico y de ingeniería. En este documento describimos una metodología que nos permite crear modelos de predicción de rendimiento de códigos irregulares para arquitecturas paralelas y distribuidas, metodología que se ha aplicado a un grupo escogido de algoritmos. Los algoritmos seleccionados corresponden todos a aplicaciones reales, que representan distintas categorías de códigos irregulares. Estos algoritmos cubren diferentes ámbitos de interés en ciencia y tecnología, incluyendo desde la resolución de sistemas de ecuaciones con matrices dispersas hasta métodos heurísticos de optimización. Sobre todos estos algoritmos se han llevado a cabo diferentes tipos de análisis para caracterizar su comportamiento ante diversas configuraciones de los sistemas computacionales y de los datos de entrada. El procesos ha supuesto distintas aproximaciones al problema de la modelización de códigos irregulares tanto en el aspectos de las computaciones como en el de las comunicaciones.