Um Sistema Prolog Paralelo-OU baseado na Cópia de Ambientes

Ricardo Jorge Rocha

Mestrado em Informática pela Universidade do Minho

Outubro 1996

---

Resumo

A implementação eficiente de Prolog bem como a adequação da linguagem para aplicações no domínio da Inteligência Artificial, são factores que muito contribuíram para a sua popularidade. Apesar do muito esforço no aumento de performance dos sistemas sequenciais de Prolog, surgiu a necessidade de novas propostas de implementação alicerçadas nas modernas arquitecturas paralelas, onde um vasto conjunto de unidades de processamento cooperam entre si para acelerar a execução de um programa. Através dessa aceleração, as implementações paralelas de Prolog podem aumentar a performance dos programas existentes e expandir a classe dos problemas que podem ser resolvidos nesta linguagem.

Nesta tese descreve-se o desenho e implementação do YapOr, um sistema paralelo de execução de Prolog, que explora paralelismo-Ou implícito a partir da plataforma Yap de execução sequencial. O YapOr utiliza o modelo de cópia de ambientes para exploração de paralelismo-Ou e implementa muitos dos conceitos introduzidos pelo sistema Muse.

No desenvolvimento deste sistema foi essencialmente importante desenhar as estruturas de dados de suporte a todo o processo paralelo, implementar o mecanismo de cópia incremental de ambientes, desenvolver uma organização de memória capaz de responder com elevada eficácia às necessidades do processo paralelo e em particular às do mecanismo de cópia incremental, implementar as estratégias de distribuição de trabalho, desenhar uma \emph{interface} entre o distribuidor de trabalho e o emulador de instruções do Yap, implementar eficientemente o conjunto de aspectos envolvidos no processo de partilha de trabalho, tratar o predicado de corte de alternativas e desenvolver um esquema de suporte às soluções que potencialmente podem corresponder a trabalho especulativo.

O YapOr suporta a execução paralela de uma ampla classe de programas escritos em Prolog, obteve elevados índices de performance na execução paralela de um largo conjunto de programas de teste, e mostrou um excelente comportamento quando comparado com o sistema Muse.