Overheads in And/Or-Parallelism

And/or-parallel system clearly suffer of the overheads coming from both and- and or-parallelism. Unfortunately, these overheads may get worse due the combination of the two forms of parallelism.

Adopting a model for exploitation of and/or-parallelism based on the layering approach, we can observe the following effects:

• and-parallelism is locally exploited within a team--and will not suffer of any additional overhead since its execution model is unchanged;
• or-parallelism becomes considerably more complex. The computation developed by an or-agent is not anymore nicely stored on a single stack, but it is spread across the stacks of the various and-agents belonging to the corresponding team. This makes the management of or-parallelism more complex.

  If stack-copying is the technique adopted to support or-parallelism, then the distributed nature of the computation makes very complicate to detect the areas that need to be transferred, making incremental copying very hard. Furthermore, and-parallelism can produce arbitrary intermixing of subgoals on the stacks, leaving trapped subgoals and empty gaps; during the copying operation, this will cause the transfer of areas which are not needed (and that will need to be properly marked as garbage).

  On the other hand, if binding arrays are used to support or-parallelism, various issues related on how binding arrays are to be managed emerges and will often translates to additional overhead. If a technique like Paged Binding Arrays is used, then there will be the additional cost for managing pages and for supporting an extra level of indirection during variable access.

• scheduling becomes, in general, considerably more complex. Scheduling or-parallelism is complicated by the fact that the computation along each branch is spread between different processors and keeping track of the choice points created becomes a challenging task.

  Furthermore, the presence of both and- and or-parallelism requires an additional scheduling step, in order to decide which form of parallelism to exploit next.

  All these additional scheduling requirements can be achieved only through the use of additional data structures which collect the information required by the scheduler.