And-parallel execution of logic programs on a shared-memory multiprocessor

Yow Jian Lin, Vipin Kumar

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

This paper presents the implementation and performance results of anand-parallel execution model of logic programs on a shared-memory multiprocessor. The execution model is meant for logic programs with "don't-know nondeterminism", and handles binding conflicts by dynamically detecting dependencies among literals. The model also incorporates intelligent backtracking at the clause level. Our implementation of this model is based upon the Warren Abstract Machine (WAM); hence it retains most of the efficiency of the WAM for sequential segments of logic programs. Performance results on Sequent Balance 21000 show that on suitable programs, our parallel implementation can achieve linear speedup on dozens of processors. We also present an analysis of different overheads encountered in the implementation of the execution model.

Original languageEnglish (US)
Pages (from-to)155-178
Number of pages24
JournalThe Journal of Logic Programming
Volume10
Issue number2
DOIs
StatePublished - Feb 1991

Fingerprint Dive into the research topics of 'And-parallel execution of logic programs on a shared-memory multiprocessor'. Together they form a unique fingerprint.

Cite this