Or-Parallel Prolog Execution on Multicores Based on Stack Splitting

Rui Vieira, Ricardo Rocha and Fernando Silva

January 2012

---

Abstract

Many or-parallel Prolog computational models exploiting implicit parallelism have been proposed in the past. The Muse and YapOr systems are arguably two of the most efficient systems exploiting or-parallelism on shared memory architectures, both based on the environment copying model. Stack splitting emerged as an alternative model specially geared to distributed memory architectures as it basically splits the computation in such a way that no further, or just minimal, synchronization is required.
With the new multicore architectures, it just makes sense to recover the body of knowledge there is in this area and reengineer prior computational models to evaluate their performance on newer architectures. In this paper, we focus on the design and implementation of stack splitting in the YapOr system. Our aim is to take advantage of its robustness to efficiently implement stack splitting support using shared memory, and then be able to directly compare the original YapOr with the YapOr using stack splitting. We consider two splitting models, vertical splitting and half splitting, and have adapted data structures, scheduling and incremental copy procedures in YapOr to cope with the new models. Experimental results, on a multicore machine with 24 cores, show that YapOr using stack splitting is, in general, comparable to the original YapOr, obtaining in some cases better performance than with only environment copying.

Bibtex

@InProceedings{vieira-damp12,
  author =    {R. Vieira and R. Rocha and F. Silva},
  title =     {{Or-Parallel Prolog Execution on Multicores Based on Stack Splitting}},
  booktitle = {Proceedings of the 7th International Workshop on Declarative Aspects 
               and Applications of Multicore Programming (DAMP 2012)},
  pages =     {1--9},
  publisher = {ACM},
  editor =    {V. Santos Costa},
  month =     {January},
  year =      {2012},
  address =   {Philadelphia, Pennsylvania, USA},
}

Download Paper

PDF file
ACM Digital Library

Download Slides

PDF file