RIS ID
30258
Abstract
OR parallelism can be exploited when a relationship is defined by more than a clause and a calling subgoal may be unified by more than a procedure header. In such a case, the bodies of the clauses involved may be executed in parallel, giving raise to an OR parallel execution. So OR parallelism becomes an efficient method for exploiting alternative solutions in parallel. In section 1 we concentrated the main problems and limitations which appear in OR parallelism implementation, presenting also the most important result (due to Gupta and Jayaraman) obtained until now with respect to this aspect: the impossibility of simultaneously fulfilling the three criteria which define the implementation of an ideal OR parallel system. In section 2 we presented the main memory management mechanisms involved in a classical sequential implementation of the Prolog language. The analysis and characterization of the OR parallel execution models from section 3 are mainly performed relatively to the types of binding environments (centralized or distributed). We present and analyze also models based on multiagents systems and methods based on stack operations. Section 4 represents the main original contribution of this paper, building a formal model for OR parallelism implementation and making an analysis of its complexity. The results obtained here formally validate the limitation reported by Gupta and Jayaraman, being also of a significant practical utility regarding possible improvements for OR parallel implementations. In section 5 we present a classification based on the three criteria, characterizing a set of implementations proposed in the literature or being in use at this time.
Publication Details
Mocean, L., Ciaca, M. & Khelalfa, H. 2009, 'A formal model for implementation of OR parallelism', Economic Computation and Economic Cybernetics Studies and Research, vol. 43, no. 2, pp. 173-184.