An execution model for exploiting AND-parallelism in logic programs

Yow Jian Lin, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

This paper presents a parallel execution model for exploiting AND-parallelism in Horn Clause logic programs. The model is based upon the generator-consumer approach, and can be implemented efficiently with small run-time overhead. Other related models that have been proposed to minimize the run-time overhead are unable to exploit the full parallelism inherent in the generator-consumer approach. Furthermore, our model performs backtracking more intelligently than these models. We also present two implementation schemes to realize our model: one has a coordinator to control the activities of processes solving different literals in the same clause; and the other achieves synchronization by letting processes pass messages to each other in a distributed fashion. Trade-offs between these two schemes are then discussed.

Original languageEnglish (US)
Pages (from-to)393-425
Number of pages33
JournalNew Generation Computing
Volume5
Issue number4
DOIs
StatePublished - Mar 1 1988

Keywords

  • AND-Parallelism
  • AND/OR Process Model
  • Intelligent Backtracking
  • Logic Programs

Fingerprint Dive into the research topics of 'An execution model for exploiting AND-parallelism in logic programs'. Together they form a unique fingerprint.

Cite this