Performance of an OR-parallel logic programming system

The research focus in parallel logic programming is shifting rapidly from theoretical considerations and simulation on uniprocessors to implementation on true multiprocessors. This report presents performance figures from such a system,Boplog, for OR-parallel Horn clause logic programs on the BBN Butterfly Parallel Processor. Boplog is designed expressly for a large scale shared memory multiprocessor with an Omega interconnect. The target machine and underlying execution model are described briefly. The primary focus of the paper is on detailed statistics taken from the execution of benchmark programs to assess the performance of the model and clarify the impact of design and architecture decisions. They show that while speedup of this implementation on highly OR-parallel problems is very good, overall performance is poor. Despite its speed drawback, many aspcts of the implementation and its performance can prove useful in designing future systems for similar machines. A binding model that prohibits constant time access to bindings, and the inability of the machine to support an ambitious use of machine memory appear to be most damaging factors.This work was carried out at the University of Utah, Salt Lake City, Utah. It was supported by a University of Utah Graduate Research Fellowship, the National Science Foundation under Grant DCR-856000, and by an unrestricted gift from L. M. Ericsson Telefon AB, Stockholm, Sweden, Production of the document was supported by the Rockwell International Science Center.