Paralelización de Lu Utilizando Balanceo Dinámico en una Red de Estaciones de Trabajo Heterogéneas

Abstract

La contaminación ambiental es una de las grandes preocupaciones de la humanidad hoy en día. México y EE.UU. a través de SEDESOL y la agencia de protección ambiental (EPA) desarrollaron un plan ambiental para el área de la frontera México - Estados Unidos. Mejorar la comprensión de las condiciones ambientales de la frontera es uno de los mayores objetivos de este plan, en particular se pretende conocer la calidad del agua para consumo humano. El ITESM y SWRI tienen un proyecto conjunto para simular el transporte de sustancias peligrosas en el subsuelo de la zona fronteriza México - Estados unidos usando para tal propósito el modelo MÊLTIFLO desarrollado por SWRI[MUL96]. Dentro de los objetivos de este proyecto esta crear una meta-computadora regional para la paralelización eficiente de éste modelo. Uno de los algoritmos numéricos más importantes sobre los cuales está basado el modelo MÊLTIPLO es la descomposición de matrices mediante la técnica LU, que consiste en dividir la matriz A de entrada en dos matrices la triangula superior (Upper) y la triangular inferior (Lower). En este trabajo se realizó una investigación de las técnicas de balanceo de carga dinámica para ambientes heterogéneo y no heterogéneos de redes de estaciones de trabajo. La investigación de estas técnicas marcaron la pauta para paralelizar LU utilizando balanceo dinámico en un ambiente heterogéneo de redes de estaciones de trabajo, con el objeto de reducir el tiempo de ejecución del algoritmo LU. En este trabajo también se realizaron las implementaciones secuenciales y paralela de LU cuyos tiempos de ejecución sirvieron para analizar la versión paralela balanceada de LU. La experimentación demostró que el programa paralelo balanceado de LU es mejor que el programa paralelo para todos los ambientes de prueba. Se mostró que para matrices de 512 la mejora relativa de los tiempos de ejecución del programa paralelo balanceado con respecto del programa paralelo va desde 1.12 veces mejor hasta 1.78, para matrices de 1024 la mejora relativa va desde 1.06 veces mejor hasta 2.54 y que para matrices de 2048 la mejora relativa va desde 1.08 veces mejor hasta 2.93. Los valores del Speedup mantuvieron una tendencia incremental, que fueron del 1.31 al 2.32, al aumentar el tamaño de la matriz A y una tendencia decremental al aumentar los nodos en todos los ambientes de pruebas. La eficiencia también mantuvo una tendencia incremental relativa del programa balanceado, (Eb), con respecto del programa paralelo, (Ep), que va desde 12% hasta 114%, que, para matrices de 512, del 6% hasta el 154% para matrices de 1024 y por Último del 8% hasta el 193%, para matrices de 2048. Finalmente se afirma que el programa paralelo balanceado de LU es significativamente mejor que el programa paralelo, ya que obtuvo mejoras relativas de hasta el 193% en la eficiencia comparado con el programa paralelo para todos los ambientes de pruebas.