Optimized and Compiled Parallel Execution of Logic Programs

本研究通过REDUCE OR进程模型寻求逻辑程序的高效并行执行。该模型旨在开发大规模并行处理器。通过设计，它适用于共享内存和消息传递机器。它试图通过处理与或并行性和有效地处理它们的交互，从逻辑程序中提取最大的并行性。开发了在Intel Hypercube、Encore multiax、Sequent、ALLIANT上运行的C语言解释器和仿真系统。设计并实现了绑定方案和运行时系统，并进行了关键优化。挑战在于控制模型中的开销，使其超过使用几个处理器编译的顺序Prolog，并证明它是一种编程大型并行机器的有用方法。这将通过使用静态分析、注释、优化算法和流线型运行时系统的优化编译器来实现。识别特定子句中“嵌入式”变量的缺失和确定性将允许生成接近顺序编译器生成的代码。粒度控制将减少系统开销的比例。其他问题涉及有效依赖图的生成和各种控制策略。

This research seeks the efficient parallel execution of Logic Programs via the REDUCE OR process model. The model is aimed at exploiting large-scale parallel processors. By design, it is suitable for shared memory as well as message passing machines. It attempts to extract maximum parallelism from logic programs by dealing with AND and OR parallelism and handling their interaction effectively. An interpreter in C that runs on Intel Hypercube, Encore MultiMax, Sequent, ALLIANT and a simulation system has been developed. A binding scheme and runtime system were designed and implemented and key optimizations developed. The challenge is to control the overhead in the model so that it surpasses compiled sequential Prolog with a few processors, and to demonstrate that it is a useful way of programming large parallel machines. This will be achieved with an optimizing compiler, using static analysis, annotations, optimized algorithms and a streamlined runtime system. Identifying absence of "embedded" variables and determinacy in specific clauses will allow generation of code close to that produced by sequential compilers. Grain-size control will reduce the proportion of system overhead. Other issues involve generation of effective dependence graphs, and various control strategies.