Next: Overheads in Or-Parallelism Up: Adventures in Parallel Logic Previous: New Models

Parallelism Efficiency

The issue of efficiency is becoming of major importance in the area of parallel implementation of logic programming. It is relatively straightforward to produce a naive parallel models, eventually based on intuitive views of the execution model. This is the case, for example, of the process view adopted in some of the seminal works on parallel Prolog [119, 17, 18], in which each subgoal was treated as a separate process, and the shared variables used as communication channels--a useful view to understand the model, but a very inefficient approach if directly used as design principle.

As already mentioned in a previous section, one of the objectives of an efficient parallel implementation is its sequential efficiency, i.e. its ability to maintain during sequential execution a speed comparable to that of the state-of-the-art sequential implementations. Achieving this target is far from being easy, and very few systems can actually claim of being able to obtain similar results.

Supporting parallelism imposes various costs, which translates on overhead w.r.t. the standard sequential behaviour. Furthermore, due to the inability of the engine of realizing whether parallelism will be actually exploited or not, part of this overhead will be paid even if the actual execution is carried on by a single agent. Merit of a good parallel model is to force most of the necessary overhead to occur at the moment in which the actual parallelism is exploited--avoiding it in case of sequential execution.

Parallel execution in a logic programming system can be viewed as the parallel traversal of an and-or tree. An and-or tree has or-nodes and and-nodes. Or-nodes are created when there are multiple ways to solve a goal. An and-node is created when a goal invokes several conjunctive subgoals. The or- and and-nodes represent sources of parallelism, i.e. points of the execution where it is possible to fork parallel computations. Figure 11 illustrates an and-or tree for a logic program.

Parallelism allows overlapping of exploration of different parts of the and-or tree (which are instead sequentialized in sequential computation). Nevertheless, as mentioned earlier, this does not always translate to an improvement in performance. This happens mainly because:

• the tree structure developed during the parallel computation needs to be explicitly maintained, in order to allow for proper management of nondeterminism and backtracking--this requires the use of additional data structures, not needed in sequential execution. Allocation and management of these data structures represent an overhead during parallel computation w.r.t. the sequential one.
• the tree structure of the computation needs to be repeatedly traversed in order to search for multiple alternatives and/or cure eventual failure of goals, and such traversal often requires synchronization between the computing agents. These traversal and synchronization activities are absent from a sequential computation (in which the management of nondeterminism is reduced to a linear and fast scan of the branches, following a predetermined order).

So far we have intuitively identified the main sources of overhead in a parallel computation--the management of additional data structures, and the need to traverse a complex tree structure.

Overheads in the traversal of the tree can be tackled by simplifying as much as possible the structure of the computation (e.g. reducing the level of nesting of parallelism), and by collecting information that may guide the traversal (and prune useless parts of the tree). Management of the data structures can be made more effective by reusing data structures whenever possible and avoiding allocation of new structure until they are strictly necessary.

These observations can be actually concretized into various optimizations (some have been illustrated in various works [83, 86, 23]), allowing improvements in performance and reductions in parallel overhead.

In the rest of this section we will present a more specific discussion on overheads emerging in the different forms of parallelism.

Next: Overheads in Or-Parallelism Up: Adventures in Parallel Logic Previous: New Models

'Enrico
Tue Mar 19 14:37:09 MST 1996