Optimized and Compiled Parallel Execution of Logic Programs

本研究通过归约OR过程模型寻求逻辑程序的高效并行执行。该模型旨在开发大规模并行处理器。通过设计，它既适用于共享内存，也适用于消息传递机器。它试图通过处理AND和OR并行性并有效地处理它们之间的交互来从逻辑程序中提取最大的并行性。开发了一个运行在Intel Hypercube、Encore MultiMax、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.