Estudio, desarrollo e implementación de algoritmos para la paralelización de una biblioteca de cálculo científico basada en aritmética intervalar

Abstract

Cada día existen problemas de gran dificultad y que necesitan mayor poder de procesamiento para su resolución. Algunas áreas con fuerte demanda por la computación de alto desempeño son: química molecular (industria farmacéutica), astrofísica, biología genética, predicción del tiempo, computación gráfica, etc. (Rodríguez, 2004) La necesidad de determinar óptimos globales se presenta en numerosas disciplinas que modelan sistemas del mundo real, como la ingeniería, la química, sistemas financieros, medicina, física, tecnología. (Sahinidis, 2004) (Penot, 1989) (Campos y Valdés-González, 2006). Muchos problemas como los de matemática e ingeniería requieren una búsqueda completa. La optimización global trata de encontrar la mejor solución a un problema de optimización, realizando búsquedas completas sobre un conjunto de soluciones factibles, esto quiere decir que abarca todos los puntos existentes en la región de búsqueda dada. Encontrar un mínimo global es mucho más costoso que encontrar un mínimo local. Los problemas en donde se aplica la optimización global en general no pueden ser resueltos aplicando métodos de optimización local, ya que pueden haber muchos mínimos de la función dada en el dominio considerado. Bajo estas condiciones los mínimos globales solo pueden ser localizados con ayuda computacional. El rendimiento de algunos computadores determina el desempeño en la resolución de problemas, existen problemas tan complejos, que su solución podría tomar muchos años (Rodríguez, 2004). Para este tipo de problemas usamos paralelización, dado que la computación paralela es la forma más barata de mejorar el tiempo de respuesta para ciertos problemas puntuales. (Peña y Muñoz, 2007) Se entiende como computación paralela a una técnica de computación que descompone un gran problema en tareas menores, donde estás puedan ser computadas en diferentes máquinas o elementos de proceso al mismo tiempo. (Wilkinson, 2005). Se conoce como balanceo de carga a una técnica que acrecienta los recursos, explotando el paralelismo, y acortando el tiempo de respuesta mediante una distribución apropiada de la aplicación. (Bozyigita, 2000). La estrategia previamente implementada (Peña y Muñoz, 2007) se basa en la división y asignación de datos implementados de dos maneras: por división del espacio inicial de búsqueda, y por división de cajas resultado obtenidas mediante una optimización inicial. Se desarrollaron y testearon nuevas estrategias para implementar el algoritmo de optimización global, en donde se cree obtener mejores resultados. Se diseñaron e implementaron cuatro versiones paralelizadas, con y sin balanceo de carga, las cuales fueron sometidas a un sinnúmero de pruebas para evaluar su comportamiento a distintos problemas. Se utilizó como base al algoritmo de división de cajas resultado, se trabajó en una arquitectura multi-computador y en una red de interconexión de computadores (clúster). La comunicación se lleva a cabo por medio de la librería de programación paralela MPI, la cual gestiona la comunicación por medio de paso de mensajes entre los distintos procesadores. Los algoritmos fueron desarrollados bajo el lenguaje de programación C++. Se utilizaron herramientas bajo los preceptos del software libre, proporcionando mayor libertad a la comunidad interesada en este campo de investigación, contribuyendo así al desarrollo de la investigación científica en la comunidad universitaria, proporcionando una base para futuras investigaciones y desarrollo en un campo de interés creciente en el ámbito internacional.