On a Tabling Engine That Can Exploit Or-Parallelism

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2001

Autores

Rocha, R (Autor) FCUP; Silva, F (Autor) FCUP; Costa, VS (Autor) FCUP

Ata de Conferência Internacional

Título: Logic Programming, 17th International Conference, ICLP 2001, Paphos, Cyprus, November 26 - December 1, 2001, Proceedings

Páginas: 43-58

Indexação

ISI Web of Knowledge

Scopus - 19 Citações

Outras Informações

ID Authenticus: P-008-KJG

DOI: 10.1007/3-540-45635-X_11

Abstract (EN): Tabling is an implementation technique that improves the declarativeness and expressiveness of Prolog by reusing solutions to goals. Quite a few interesting applications of tabling have been developed in the last few years, and several are by nature non-deterministic. This raises the question of whether parallel search techniques can be used to improve the performance of tabled applications. In this work we demonstrate that the mechanisms proposed to parallelize search in the context of SLD resolution naturally generalize to parallel tabled computations, and that resulting systems can achieve good performance on multi-processors. To do so, we present the OPT Yap parallel engine. In our system individual SLG engines communicate data through stack copying. Completion is detected through a novel parallel completion algorithm that builds upon the data structures proposed for or-parallelism. Scheduling is simplified by building on previous research on or-parallelism. We show initial performance results for our implementation. Our best result is for an actual application, model checking, where we obtain linear speedups. © Springer-Verlag Berlin Heidelberg 2001.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16