OR-parallel Prolog made efficient on shared memory multiprocessors

Hausman, Bogumil and Ciepielewski, Andrzej and Haridi, Seif (1987) OR-parallel Prolog made efficient on shared memory multiprocessors. [SICS Report]



With the arrival of commercially available shared-memory multiprocessors, Prolog implementation efforts begin to shift from single processor architectures to the new ones. Among the main problems are efficient implementation of operations on variables and of task switching. Most of the solutions proposed so far suffer from expensive, non-constant time implementation of operations on variables. We propose a model (Versions-Vector Model) in which operations on all variables are constant time operations. The price we pay is a non-constant time of a task switch. As a remedy we propose two ways of decreasing that price. The first is promotion of variables on a task switch, from versions-vectors to the stack or heap, making subsequent task switches cheaper. The second is delayed installation of variables in versions-vectors, decreasing the cost of short branches. We believe that the increased memory consumption induced by our model can be accepted as it is traded for speed.

Item Type:SICS Report
Additional Information:Original report number R87006. Also published in Proceedings of the 1987 Symposium on Logic Programming, August 31-September 4, 1987, San Francisco, California, pp. 69-79, IEEE Computer Society Press.
ID Code:2553
Deposited By:Vicki Carleson
Deposited On:17 Sep 2009
Last Modified:18 Nov 2009 16:11

Repository Staff Only: item control page