Control de granularidad en la ejecución paralela de programas lógicas mediante técnicas de análisis y transformación

Resumen

Los lenguajes de programación lógica ofrecen un excelente marco para la aplicación de técnicas de paralelización automática. Existen resultados teóricos que pueden asegurar cuando los programas paralelizados son correctos, es decir, obtienen los mismos resultados que los correspondientes secuenciales y cuando la ejecución de los primeros no tarda más tiempo que la de los segundos. Sin embargo dichos resultados suponen un entorno ideal de ejecución paralela y no tienen en cuenta que en la práctica existen una serie de costes asociados con la ejecución paralela de tareas, como por ejemplo creación y gestión de tareas, posible migración de tareas a procesadores remotos, costes de comunicación, etc. Dichos costes pueden dar lugar a que la ejecución de los programas paralelos sea más lenta que la de los secuenciales o al menos limitar la ganancia debida al paralelismo introducido. En esta tesis hemos desarrollado completamente e integrado en un sistema avanzado de manipulación de programas que realiza análisis y optimización de los mismos un sistema automático de control de granularidad para programas lógicos que estima eficientemente la granularidad de las tareas (e.d., el trabajo necesario para su ejecución completa) y la usa para limitar el paralelismo de forma que se controla el efecto de los costes mencionados anteriormente. El sistema está basado en un esquema de análisis y transformación de programas, en el cual se realiza tanto trabajo como sea posible en tiempo de compilación para evitar añadir nuevos costes a la ejecución de los programas. En la realización de la transformación de programas se persigue el objetivo de minimizar el trabajo adicional hecho en tiempo de ejecución, para lo que hemos propuesto una serie de técnicas mientras que en el análisis el objetivo es obtener la información necesaria para esta fase de transformación, lo que nos ha llevado a desarrollar varios tipos de análisis capaces de inferir informaciones tales como cotas del coste de procedimientos qué llamadas a procedimientos no fallarán, etc. El coste adicional en tiempo de ejecución asociado con la técnica que proponemos es usualmente bastante pequeño. Además realizamos un análisis estático del coste asociado con el proceso de control de granularidad, de forma que se pueda, decidir su conveniencia. Es interesante resaltar que muchas de las técnicas que hemos desarrollado tienen otras aplicaciones importantes, además del mencionado control de granularidad entre otras: eliminación de paralelismo especulativo, detección de errores de programación, varias aplicaciones relacionadas con la transformación de programas, por ejemplo, reordenación de objetivos o ayuda a los sistemas de transformación de programas a elegir las transformaciones óptimas, eliminación de recursividad, selección de diferentes algoritmos o reglas de control cuya eficiencia puede depender de los tamaños de los datos de entrada, depuración de eficiencia (optimización) de programas y la optimización de consultas a bases de datos deductivas. Finalmente, los resultados experimentales realizados con un prototipo del sistema, han mostrado que el control de granularidad puede contribuir sustancialmente a la optimización de la ejecución en paralelo de programas, especialmente en sistemas distribuidos y que parece bastante factible un enfoque automático del mismo.