An execution model for exploiting and-or parallelism in logic programs (abstract)

摘要

Several models have been developed for parallel execution of logic programming languages. Most of them involve variations of two basic mechanisms: and parallelism and or parallelism.

Our work [1] is situated between the and/or process model of Conery [2] and the restricted and parallelism of DeGroot [3]. The model we have developped exploit both the and -and or- parallelism using a compile-time program-level and clause-level data dependence analysis to generate an execution graph that embodies the possible parallel executions. The execution graph is a directed acyclic graph, containing one node per atom of the clause body and two nodes for the head clause. Simple tests on the terms provided at run-time determine which of the different possible executions graph is to be used.

The purpose of the program-level data dependence analysis is to tag the variables of each atom in the clause, that is, to distinguish the variables which will be yield ground, non ground or the both case after the atom reduction. This tagging allows us to get rid of the eventualities that can never happen during the execution of the program. This improves the clause- level analysis and consequently generates a reduced graph.

The result of clause-level data dependence analysis is the execution graph. It is based on the last analysis and on the dependence of atoms in the clause. This is constructed in three phases.

The first phase, presents an algorithm which automatically extracts the maximum of parallelism from the body of the clause. It starts from the initial context, and by assuming that execution of an atom transforms the context by eliminating all the variables present in the atom, assuming they become ground. We get the maximum of parallelism by choosing to execute first the atom(or atoms) that allow to instantiate the maximum

* Permanent address: U.S.T.H.B, BP32 Bab Ezzouar Algiers ALGERIA number of variables in the clause using the tags and the weight of the atoms.

The second phase, enriches the graph by considering the possibility that an atom can produce after its execution independent non ground terms. In this case another ordering is deduced, consequently some edges are added to the graph.

The third phase deals with the possibility where the execution of the atom yields non ground but depended terms. In this case too, it means anticipating other ordering for the atoms, that is, we will consider that the atoms executed after an atom which supplies non ground dependent terms will be processed sequentially. In our approach, it is the only case where the degree of parallelism is less than that exploited in the dynamic approach of Conery.

Finally the graph is completed in the case where one or more nodes in the graph have no consumers (these are the nodes with no outcoming edge). We add edges which supply the logical values of the atom to the node representing the head of the clause.

The model support also the or-parallelism. The merge of the streams in the graph nodes is realized by a dynamic join algorithm that combines the multiple streams of partial solutions. We have adopted the algorithm proposed by Li and Martin in [4].

This model avoids the loss of parallelism due to the use of the static approach. The first improvement of this model, will be to limit the effect of the production of dependent terms to the atoms effectively affected. More details concerning this work can be found in [1].