Optimized and Compiled Parallel Execution of Logic Programs

本研究旨在寻求逻辑程序的高效并行执行 通过REDUCE或process模型。 该模型旨在利用 大规模并行处理器 通过设计，它适合于共享 存储器以及消息传递机器。 它试图提取 通过处理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.