Departamento de Computación

La programación paralela en general requiere que el programador realice el particionamiento del problema y asigne las partes entre los procesadores. Estas dos tareas se pueden complicar dependiendo del problema, y en el caso de usar un cluster como plataforma de ejecución pueden ser inadecuadas para un buen desempeño al existir factores ajenos al problema como: la multiprogramación y la heterogeneidad del hardware. Bajo estos factores el balance de carga (datos) es necesario para mejorar el desempeño. Para facilitar la programación paralela, esta tesis presenta un modelo de programación cuasi-secuencial en el que el particionamiento, la asignación y el balance de datos entre los procesadores se realiza de manera transparente al programador. Nuestro modelo, basado en listas de datos, sólo requiere que el programador proporcione sus datos organizados en una lista, los inicialice y realice llamados a funciones organizadas en una biblioteca. Los llamados incluyen funciones para la manipulación de las listas, como insertar y eliminar elementos, y funciones para soportar el paralelismo. Nuestro modelo facilita la programación y tiende a mejorar el rendimiento de los siguientes tipos de aplicaciones: 1) Aplicaciones con una cantidad fija de datos, con procesamiento constante o variable, es decir, misma o diferente carga computacional en el procesamiento de los datos; y 2) Aplicaciones con una cantidad variable de datos con procesamiento constante o variable. En nuestro modelo se hace un balance de datos entre los procesadores, basado en un algoritmo de subasta, de manera automática (transparente al programador) dentro de las funciones en nuestra biblioteca de manejo de listas. Nuestro enfoque lo hemos probado en un cluster con las siguientes aplicaciones: Ordenamiento paralelo (datos fijos, procesamiento fijo); algoritmos evolutivos (datos fijos, procesamiento variable), N-Reinas (datos variables, procesamiento variable) y Procesamiento digital de imágenes (datos fijos/variables, procesamiento variable). Los resultados obtenidos muestran que nuestro sistema mejora el desempeño de manera notable, cuando hay necesidad de balance de carga.