We have developed a new method of executing Horn Clause programs with low overhead on multiple processors. This method does not involve the sharing of memory or the copying of computation state between processors. Under certain conditions, the method has the remarkable property of executing a given program in the minimum time theoretically required. Such optimal operation is not always possible, but performance of the implemented system is such as to render it of practical use. Because there is no contention for shared memory or variable bindings, performance is monotonic in the number of processors, that is, performance does not degrade as more processors are available beyond the contention limit. This is illustrated by the following graph showing execution time for the 8-queens problem:
The current implementation runs on a network of 40 DECstation-3000's in the Computer Laboratory.
W.F. Clocksin and H. Alshawi, 1986. A method for efficiently executing Horn Clause programs using multiple processors. Technical Report CCSC-3, SRI International (Cambridge Computer Science Centre).
W.F. Clocksin, 1987. Principles of the DelPhi parallel inference machine. Computer Journal 30(5), 386-391.
W.F. Clocksin and H. Alshawi, 1988. A method for efficiently executing Horn Clause programs using multiple processors. New Generation Computing 5, 361-376.
H. Alshawi and D.B. Moran, 1989. The Delphi model and some preliminary experiments. Proc 5th Conf Symp Log Prog (ed Kowalski and Bowen), MIT Press, 1578-1589.
K.L. Wrench, 1990. A distributed and-or parallel prolog network. PhD dissertation. Available in summary form as Technical Report 212, Computer Laboratory, University of Cambridge.
C.S. Klein, 1991. Exploiting or-parallelism in Prolog using multiple sequential machines. PhD dissertation. Reprinted as Technical Report 216, Computer Laboratory, University of Cambridge.
W.F. Clocksin, 1993. The DelPhi multiprocessor inference computer. in 4th UK Conference on Logic Programming (K. Boda, ed), Springer Verlag.