Overheads in Or-Parallelism

Or-Parallelism has been implemented with quite limited overhead. The two major implementations proposed, Muse and Aurora, respectively report an average overhead over SICStus Prolog (on which both the implementations are based) of 8-22% (depending on the architecture considered) and 25%. These results are extremely encouraging.

The main advantage of or-parallelism (w.r.t. and-parallelism) is the fact that in or-parallelism it becomes quite natural to limit the overhead to the actual exploitation of parallelism. The compiler may detect (eventually through the help of user declarations) which are the choice points which may become parallel, and they will be appropriately marked (an almost zero-cost operation) when created. As long as parallelism is not exploited, choice points are treated normally, without any overhead.

Overheads generated in an or-parallel model depend on the specific model employed. Nevertheless, it is possible to make some general considerations. Gupta and Jayaraman [48] have observed that any or-parallel model implementing Prolog semantics is going to suffer a non-constant overhead in at least one of the following three phases:

1. Task Creation: which involves creating the global environment and goal-list for a new alternative taken from a choice-point;
2. Task Switching: which involves moving one agent from one node in the or-tree to another;
3. Variable Access: which involves reading and/or binding a variable.

Since the frequency of two of these operations, variable access and task creation, is outside the scope of control of the engine, it would be desirable to have models where the non-constant overhead is located exclusively in the task switching phase (whose frequency can be controlled by the scheduler). This observation is actually confirmed by the practical experience: the most effective implementations of or-parallelism available are exactly based on this principle (e.g., Muse and Aurora).

• Stack Copying:
• Binding Arrays: