On Applying Or-Parallelism and Tabling to Logic Programs

Ricardo Rocha

November 2001

---

Abstract

Logic programming languages, such as Prolog, provide a high-level, declarative approach to programming. They offer a great potential for implicit parallelism and thus allow parallel systems to automatically reduce a program's execution time without any programmer intervention. For complex applications that take several hours, if not days, to return an answer, even modest parallel execution speedups can be directly translated to very significant productivity gains.
Despite the power, flexibility and good performance that Prolog has achieved, the past years have seen wide effort at increasing Prolog's declarativeness and expressiveness. Unfortunately, some deficiencies in Prolog's evaluation strategy - SLD resolution - limit the potential of the logic programming paradigm. Tabling has proved to be a viable technique to efficiently overcome SLD's susceptibility to infinite loops and redundant subcomputations.
With this research we aim at demonstrating that implicit or-parallelism is a natural fit for logic programs with tabling. To substantiate this belief, we propose novel computational models that integrate tabling with or-parallelism, we design and implement an or-parallel tabling engine - OPTYap - and we use a shared memory parallel machine to evaluate its performance. To the best of our knowledge, OPTYap is the first implementation of a parallel tabling engine for logic programming systems. OPTYap builds on Yap's efficient sequential Prolog engine. Its execution model is based on the SLG-WAM for tabling, and on the environment copying for or-parallelism.
The results in this thesis make it clear that the mechanisms proposed to parallelize search in the context of SLD resolution can indeed be effectively and naturally generalized to parallelize tabled computations, and that the resulting systems can achieve good performance on shared memory parallel machines. More importantly, it emphasizes our belief that through applying or-parallelism and tabling to logic programs we can contribute to increase the range of applications for Logic Programming.

Bibtex

@PhdThesis{rocha-phd,
  author =  {R. Rocha},
  title =   {{On Applying Or-Parallelism and Tabling to Logic Programs}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {November},
  year =    {2001},
  type =    {{PhD Thesis}},
}

Download Thesis

PDF file