On Applying Or-Parallelism and Tabling to Logic Programs
Ricardo Rocha
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
Novembro de 2001
Resumo
Uma das vantagens do Prolog, como linguagem de Programação Lógica, é
possuir uma semântica que possibilita a exploração de paralelismo
implícito. Esta característica permite reduzir o tempo de execução de
um programa, sem que para isso sejam necessárias anotações adicionais
do programador. Para aplicações complexas, que demoram várias horas,
senão dias, a calcular uma solução, mesmo ganhos de velocidade
modestos em execução paralela, podem traduzir-se em significantes
ganhos de produtividade.
Apesar do poder, da flexibilidade e dos bons resultados que o Prolog
tem demonstrado desde o aparecimento da WAM, um amplo esforço tem
vindo a ser desenvolvido para aumentar o seu poder declarativo e
expressivo. A estratégia de resolução SLD, na qual o Prolog se baseia,
é limitadora do potencial inerente ao paradigma da Programação
Lógica. Uma das mais bem sucedidas técnicas para solucionar a
incapacidade da resolução SLD no que respeita a ciclos infinitos e
computações redundantes é a Tabulação.
Com este trabalho pretende-se demonstrar que a exploração implícita de
paralelismo-Ou em programas lógicos com tabulação pode ser tão eficaz
como o é em programas lógicos comuns. Para tal, propõem-se novos
modelos para integrar paralelismo-Ou com tabulação, desenvolve-se um
novo sistema, o OPTYap, e avalia-se o seu desempenho. Tanto quanto é
do nosso conhecimento, o OPTYap é o primeiro sistema a explorar
paralelismo em programas lógicos com tabulação. O OPTYap foi
desenvolvido tendo por base o sistema Yap, um dos mais rápidos
sistemas de execução sequencial de Prolog. O seu modelo de execução é
baseado na SLG-WAM, para tabulação, e em cópia de ambientes, para
paralelismo-Ou.
Os resultados mostram que os mecanismos para execução paralela de
programas lógicos podem generalizar-se para computações que usam
tabulação, e que os sistemas daí resultantes obtêm igualmente bons
desempenhos em máquinas paralelas de memória partilhada. Este trabalho
reforça a convicção de que paralelismo e tabulação podem contribuir
para expandir o leque de aplicações alvo da Programação Lógica.
