Procesador paralelo de Prolog sobre una arquitectura de memoria distribuida

Resumen

En este trabajo se ha desarrollado un modelo de ejecución paralelo de los programas lógicos para sistemas distribuidos, su implementación y su evaluación. El modelo considera la explotación del paralelismo-y independiente y el paralelismo-o, así como la combinación de ambos. El sistema está soportado por una arquitectura distribuida con un alto número de procesadores que trabajan bajo un control jerárquico. El control se realiza en una serie de procesadores llamados controladores. El resto de los procesadores, procesadores básicos, están dedicados a la ejecución de programas prolog. El paralelismo-y se explota siguiendo un modelo de entornos cerrados (sin referencias a variables externas) en el que se forman tareas-y autónomas para la computación de cada objetivo independiente. La explotación del paralelismo-o se basa en la ejecución multisecuencial de las ramas del árbol de búsqueda. Cada tarea-o nueva que se crea para la exploración de una nueva rama reconstruye el entorno de la tarea padre recomputando el objetivo inicial pero siguiendo el camino de éxito (sin backtracking) recibido de la tarea padre. Cuando un programa presenta paralelismo o-bajo-y y es necesario combinar las distintas soluciones de los objetivos paralelos, se evita el almacenamiento de soluciones parciales y la sincronización de tareas produciendo la combinación de forma distribuida. La idea es crear una computación para cada combinación de soluciones, recomputando el camino de éxito que lleva del objetivo inicial a la llamada paralela considerada. De esta forma la explotación del paralelismo-y se realiza con el mecanismo del paralelismo-o, creando tareas autónomas que reducen considerablemente el trafico de mensajes. Se ha diseñado una maquina abstracta paralela que implementa el modelo de ejecución de los procesadores básicos del sistema. Esta maquina es una extensión de la wam y mantiene sus técnicas de ejecución en los segmentos secuenciales de programa conservando así las optimizaciones ya conseguidas en prolog secuencial. De la misma forma se ha tratado de mantener las técnicas de explotación de cada tipo de paralelismo con las menores modificaciones. El estudio de la planificación ha sido otro objetivo fundamental en el trabajo. Se han evaluando distintas políticas de reparto del trabajo pendiente entre los procesadores-desocupados. También se ha considerado la granularidad de los trabajos pendientes, diseñando distintos controles de granularidad. Finalmente se ha realizado una implementación sobre un sistema de transputers, haciendo un estudio de la red de interconexión que soporta al sistema. Se ha evaluado la explotación de cada tipo de paralelismo y su combinación.