Implementation Techniques for Parallel Logic Programming: Systematic Development of Parallel Prolog Engines

逻辑编程语言(如PROLOG)的一个重要特性是，它们的声明性语义在很大程度上独立于程序中不同操作的执行顺序。不同的操作也可以并行执行。因此，可以利用为顺序机器编写的Prolog程序的实质并行性，而无需对其进行任何修改。PROLOG程序中存在各种形式的隐式并行度：或并行度、独立与并行度、从属与并行度、流与并行度、数据或并行度、数据与并行度。到目前为止，研究只集中于开发一种形式的并行性。这个项目的目标是并行实现技术，使人们能够扩展一个高性能的顺序Prolog系统，以同时开发各种形式的并行性。该项目的重点是自给自足的并行实现技术，这些技术很简单，将允许以系统和增量的方式将各种形式的并行添加到现有的顺序Prolog系统中。这里将要开发的技术将通过将它们整合到SICStus顺序PROLOG引擎中来测试和演示其有效性。还将开发用于编译时分析的相关工具。还将研究减少并行实现开销的通用运行时优化技术。***

An important property of logic programming languages, such as Prolog, is that their declarative semantics is largely independent of the order of execution of different operations in the program. The different operations can also be performed in parallel. As a result, it is possible to exploit substantial parallelism from Prolog programs, written for sequential machines, without making any modifications to them. There are various forms of implicit parallelism found in Prolog programs: or-parallelism, independent and-parallelism, dependent and-parallelism, stream and-parallelism, data or-parallelism, data and- parallelism. Research so far has only focused on exploiting a single form of parallelism. This project's objective is to parallel implementation techniques that will allow one to extend a high performance sequential Prolog system to exploit the various forms of parallelism simultaneously. The focus of this project is upon self-contained parallel implementation techniques that are simple and that will allow addition of the various forms of parallelism to an existing sequential Prolog system in a systematic and incremental way. The techniques to be developed here will be tested and demonstrated for efficacy by incorporating them in the SICStus sequential Prolog engine. Relevant tools for compile-time analysis will also be developed. General runtime optimization techniques for reducing the parallel implementation overhead will also be researched. ***