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. ***