OR-parallel Prolog made efficient on shared memory multiprocessors
Number of Authors: 3
1987 (English)Report (Refereed)
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.
Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 1987, 1. , 44 p.
SICS Research Report, ISSN 0283-3638 ; R87:06
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22214OAI: oai:DiVA.org:ri-22214DiVA: diva2:1041758
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.2016-10-312016-10-31Bibliographically approved