Restricted And-parallelism:

restricted and-parallelism emerges from allowing and-parallel execution of subgoals which share unbound variables, as long as there is guarantee that no solvable conflicts can emerge on binding such shared variables. Two main approaches have been proposed in this area:

Non-strict Independence:

proposed by Hermenegildo [75], consists of allowing parallel execution of subgoals sharing variables, as long as the different computations do not ``compete'' for their bindings (e.g., at most one computation will attempt to bind each of these variables).

This approach has the advantage of not requiring any additional run-time mechanism (only compile-time analysis needs to be improved to detect these cases). On the other hand it is still an open question whether this generalization does really improve the applicability of and-parallelism.

Basic Andorra Model:

developed by D.H.D. Warren [114] and integrated in the Andorra-I system [21], this model allows exploitation of and-parallelism between subgoals which are determinate, i.e., subgoals that will produce at most one solution. The different subgoals may have any kind of dependency but, being determinate, no solvable conflict may occur--if a conflict on binding a variable occurs, then we are guaranteed that the execution does not have any solution. Results for the Andorra-I system have been proposed and they show considerable speed-ups. On the other hand various issues need to be carefully tackled, like detection of determinacy and management of subgoals. In particular, the approach taken by Andorra-I, where parallel execution may actually change the order in which subgoals are explored (determinate subgoals may be executed ahead of time, independently from their position in the query), requires very complex run-time mechanisms (backtrackable goal chains), and their management seems to have a noticeable negative effect on the overall performance.

Web Tour

• Andorra-I
• Vitor Santos Costa
• Manuel Hermenegildo
• Reform Prolog