1984 Reports

LPS Algorithms: A Detailed Examination

Lowry, Andy; Taylor, Stephen; Stolfo, Salvatore

LPS is a Logic Programming System currently under development and specifically targeted for implementation on massively parallel architectures. We present a detailed explanation of algorithms under development for parallel execution of LPS programs. The explanation is significantly more detailed than those published previously. An abstract proof procedure is developed which encompasses these algorithms and several variants, as well as the standard sequential Prolog algorithm. This abstract procedure provides a conceptual basis for our discussion and. in a companion paper, for a critical analysis of various execution strategies. The algorithms have been successfully implemented and demonstrated in simulation on a number of small programs. Work is currently underway to transfer this implementation to a working prototype machine based on the DADO parallel architecture. Due to the depth of our treatment we assume that the reader has read previously published literature in the area.