OR-Parallel Execution of Prolog on a Multi-Sequential Machine

Ali, Khayri Mohammed (1986) OR-Parallel Execution of Prolog on a Multi-Sequential Machine. [SICS Report]



Based on extending the sequential execution model of Prolog to include parallel execution, we present a method for OR-parallel execution of Prolog on a multiprocessor system. The method reduces the overhead incurred by parallel processing. It allows many processing elements (PEs) to process simultaneously a common branch of a search tree, and each of these PEs creates its local environment and selects a subtree for processing without communication. The run-time overhead is small: simple and efficient operations for selecting the proper subtree. Communication is necessary only when some PEs have exhausted their search spaces and there are others still searching for solutions. The method is able to utilize most of the technology devised for sequential implementation of Prolog. It is optimized for an architecture which supports broadcast copying.

Item Type:SICS Report
Additional Information:Original report number R86006B. (Revised version of R86006). (Also located in the International Journal of Parallel Programming. Vol. 15, No. 3, June 1986, pp. 189-214.)
ID Code:2008
Deposited By:Vicki Carleson
Deposited On:15 Sep 2009
Last Modified:18 Nov 2009 15:59

Repository Staff Only: item control page