Problems in Combining And- and Or-Parallelism

Considering that parallel systems exploiting a single form of parallelism have been studied and efficiently implemented, it may seem that the task of combining the two forms of parallelism in a unique framework can be reduced to a simple engineering problem. This in consideration of the apparent orthogonal nature of the two forms of parallelism.

A more careful observation shows that this is not the case: combining different forms of parallelism introduces new complex issues to be solved, mainly related to environment representation and memory management. This can be illustrated quite easily. As we have shown in the previous sections, the different forms of parallelism impose specific constraints on the way in which environments and data areas are managed:

• in and-parallelism, the different and-agents are computing different parts of the same solution to the original query--i.e., the different agents are working on the same branch of the or-tree. This leads to the need of allowing different agents to freely access each others' memory areas, in order to allow an efficient combination of the partial solutions computed by each agent. That is, the different and-agents should share their environments and data areas.
• in or-parallelism, the different or-agents are working on different solutions of the original query--i.e., they are working on different branches of the or-tree. As pointed out in a previous section, each agent's environments should be kept strictly separated from those of the other agents.

As a consequence, the requirements imposed by or- and and-parallelism are antithetical.

 

Furthermore, in order to guarantee a proper response to unbalanced distribution of or- and and-parallelism in the computation tree, the structure of the teams need to be dynamic, i.e., agents should be allowed to move from one team to another, or to create new teams in case of necessity. This requires the presence in the system of a top-level scheduler, whose task is to select the best teams configuration.

This layered approach to and/or-parallelism has been adopted in the most recent proposals related to and/or-parallelism, like Andorra-I [21, 85], ACE [47, 46], and SPBA [43, 42].