Un Software Paralelo para el Cálculo de Integrales con Reglas Adaptivas

Abstract

Las reglas adaptivas resultan un interesante recurso para realizar el cálculo numérico de integrales, cuando el integrando presenta grandes variaciones funcionales. Estas reglas permiten administrar de manera flexible el tamaño del paso a costas de incrementar el número de cómputos de manera considerable, razón por la cual se pensó en la paralelización de dichas reglas.
Nuestra propuesta consistió en desarrollar un algoritmo que busca mejorar el tiempo de cómputo, evitando que un procesador se mantenga ocioso cuando finalizó todas sus tareas, mientras otro está trabajando y aún con tareas pendientes de realizar. Además, con este algoritmo se elimina la recursividad de las reglas adaptivas, con la ventaja de poder distribuir el cálculo sin esperar la terminación de etapas intermedias.
En la implementación se incorporó una variación del método de paralelización “bolsa de trabajo”, que consiste en distribuir dicha bolsa en cada proceso y mantener un estado global de cada proceso, para realizar el balanceo de carga cuando corresponda.
Hay que destacar que cada proceso accede a su propio grupo de variables, son todas variables locales, no hay memoria compartida y por lo tanto no hay posibilidad de una race-condition. Cada lista (“bolsa de trabajo”) es local y las variables que se usan para describir el estado de cada proceso, sólo son modificadas por el propio proceso cuando recibe mensajes específicos que así lo indiquen.
Se propone un “schedulling” que realiza una distribución uniforme de carga y de tiempo entre todos los procesadores. Las estructuras principales utilizadas son: listas simples para implementar cada bolsa de trabajo y una cola circular entre todos los procesos, implementada mediante un arreglo, donde cada procesador registra su carga de trabajo actual. Al quedar un procesador libre, utiliza esta estructura para solicitar, mediante un mensaje, al procesador más ocupado subintervalos para continuar con el cálculo.
Para la implementación se utiliza MPI en razón de contar con un cluster de 20 PC estándar.
En razón de encontrarnos actualmente en la etapa de depuración del programa, no podemos establecer en forma precisa tiempos de procesamiento para poder realizar análisis respecto de la performance.