The reduce-or process model for parallel execution of logic programs

Research output: Contribution to journalArticlepeer-review

Abstract

A method for parallel execution of logic programs is presented. It uses REDUCE-OR trees instead of AND-OR or SLD trees. The REDUCE-OR trees represent logic-program computations in a manner suitable for parallel interpretation. The REDUCE-OR process model is derived from the tree representation by providing a process interpretation of tree development, and devising efficient bookkeeping mechanisms and algorithms. The process model is complete-it produces any particular solution eventually-and extracts full OR parallelism. This is in contrast to most other schemes that extract AND parallelism. It does this by solving the problem of interaction between AND and OR parallelism effectively. An important optimization that effectively controls the apparent overhead in the process model is given. Techniques that trade parallelism for reducing overhead are also described.

Original languageEnglish (US)
Pages (from-to)55-84
Number of pages30
JournalThe Journal of Logic Programming
Volume11
Issue number1
DOIs
StatePublished - Jul 1991
Externally publishedYes

ASJC Scopus subject areas

  • Logic

Fingerprint

Dive into the research topics of 'The reduce-or process model for parallel execution of logic programs'. Together they form a unique fingerprint.

Cite this