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