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 language | English (US) |
|---|---|
| Pages (from-to) | 155-178 |
| Number of pages | 24 |
| Journal | The Journal of Logic Programming |
| Volume | 10 |
| Issue number | 2 |
| DOIs | |
| State | Published - Feb 1991 |
Bibliographical note
Funding Information:*This work was supported by Army Research Office grant DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the Computer Science Department at the University of Texas at Austin. *Y.-J. Lin is now with Bellcore, 445 South Street, MRE-2Q-277, Morfistown, NJ 07962-1910. E-mail: yowjian @thumper.bellcore.com *V. Kumar is now an Associate Professor with the Computer Science Department, University of Minnesota, Minneapolis, MN 55455. E-mail: kumar@cs.umn.edu Address correspondence to Yow-Jian Lin, Member of Technical Staff, Bellcore, 445 South Street, MRE-2Q-277, Morristown, NJ 07962-1910. Received May 1988; accepted March 1989.