Efficient parallel execution of prolog programs
Enrico Pontelli, Gopal Gupta · 1997
The problem tackled in this dissertation is the design and development of efficient execution mechanisms to support parallel logic programming. Through a rational analysis of the various forms of parallelism present in logic programming, we achieve a clear understanding of the issues involved in supporting automatic exploitation of parallelism. This in turn allows us to (i) classify and compare existing proposals in this area; and (ii) propose new models, arguably superior than the existing ones. In this dissertation we propose (i) a novel execution model for independent and-parallelism, capable of supporting efficient memory usage and complete backtracking; (ii) a complete system to support dependent and-parallelism, from automatic compile-time detection of parallelism to its actual run-time exploitation; (iii) an execution model for combined and/or-parallelism; (iv) a set of optimization principles for non-deterministic parallel systems; (v) theoretical results on the complexity of the various forms of parallelism. Each of the models presented has been implemented and successfully tested on a variety of real-life benchmarks.