Independent And-parallelism

this form of parallelism has been studied by various researchers and different implementations have been designed and developed. This wide interest in independent and-parallelism is mainly related to its apparent simplicity and the fact that many applications are naturally rich of independent and-parallelism (or they can be easily modified to expose it).

Independent and-parallelism is characterized by the fact that only subgoals which do not share any unbound variable at run-time are entitled to parallel execution. The condition guarantees that they will not affect each other's execution--removing the need of introducing any form of synchronization during parallel execution. The only synchronization activity required is a barrier placed at the end of the parallel part of the execution, needed to switch back to a sequential execution once all the parallel subgoals are completed.

Various steps are required in the exploitation of independent and-parallelism:

1. Detection of Independence: since only independent subgoals are allowed for and-parallel execution, some mechanisms are needed to allow detection of independence. Independency information may be either supplied by the user, detected through compile-time analysis, or detected at run-time.

   Granted that allowing the user to supply information about the subgoals can only improve the execution, the most attractive solution is based on a compromise between compile-time analysis and run-time analysis--compromise which is necessary, since

   • pure run-time analysis guarantees the best results but adds an unberable overhead to the execution;
   • pure compile-time analysis avoids run-time overhead but is forced to make very conservative assumptions (with consequent loss of parallelism).

   The solution, originally proposed by DeGroot [29] and successively elaborated by Hermenegildo and others [58, 94, 46], consists of generating at compile-time (through abstract interpretation techniques [79]) some conditional annotations (named Conditional Graph Expressions (CGE)), which identify potential independent subgoals and the conditions under which the independence is guaranteed. A CGE has the form ( conditions G & & G ), where are some simple tests on the instantiation status of some variables, and G , , G are the potentially independent subgoals. At run-time, whenever a CGE is encountered, the are evaluated and, if the evaluation is successful, the subgoals G , , G are executed in parallel. The symbol ``&'' is used to denote a parallel conjunction (i.e., the subgoals connected by & can be run in parallel), while ``,'' will be maintained to represent sequential conjunction.

2. Support for And-parallelism: once a set of independent subgoals has been identified, the subgoals need to be prepared for parallel execution and the and-agents should be notified of the availability of parallel work;
3. Distributed Backtracking: one of the biggest challenges in the development of any and-parallel system is the design of a sound, complete, and efficient backtracking mechanism. The main difficulty is represented by the arbitrary spreading of the computation between the different agents, with the possibility that more than one agent may be concurrently backtracking on the same part of computation. Different approaches to backtracking in this kind of framework have been proposed [58, 60, 95], although, to our knowledge, only one full-blown implementation has been realized, within the ACE project [46].

Systems exploiting independent and-parallelism have been successfully implemented; the most relevant proposals are &-Prolog [55], APEX [72], and &ACE [46].

Web Tour

• Laboratory for Logic and DBs
• CLIP Group