Departamento de Computación

En este documento se propone un mejor algoritmo para el problema de asignación de tareas a los procesadores en una malla de PC's no dedicados al procesamiento en paralelo bajo el modelo BSP. Dicho algoritmo se desarrolla en base al planteamiento de un campo de seudofuerzas --de aquí en adelante referido como fuerzas, con la aclaración de que no son fuerzas en el mismo sentido que las fuerzas físicas-- definido en torno a una malla de computadoras de escritorio. Mediante el análisis por simulación se comparan los resultados obtenidos del método de campo de fuerza con los algoritmos canónicos para la asignación de tareas en un ambiente paralelo. Se opta por la utilización del modelo BSP por el concepto de superpaso, un conjunto de tareas en paralelo entre barreras de sincronización. Este concepto permite analizar la manera en que podría trabajar un programa paralelo en un sistema con las características que presenta una malla de computadoras de escritorio. En consecuencia, para calificar el desempeño de un algoritmo de asignación de tareas, se mide qué tan cerca se encuentra la duración del superpaso al tiempo óptimo. Es decir, se busca la minimización del tiempo de vida del superpaso. Para ello se consideran características propias del conjunto de tareas, los procesadores y requerimientos de comunicación.
Se diseña y desarrolla un simulador para reproducir el comportamiento de una malla dinámica de computadoras. Con éste se efectúan las pruebas de rendimiento y comparación de los algoritmos de asignación de tareas. Se estudia el detalle de un problema abstracto y orto concreto. Este último compuesto por el análisis de la resolución en paralelo de la ecuación de onda para su aplicación a la tomografía sísmica de pozos. Adicionalmente, se desarrolla un método de diferencias finitas de mayor precisión y mayor demanda de recursos de cómputo que puede ser utilizado en la resolución en paralelo de la ecuación de onda para la tomografía sísmica.