next up previous contents
Next: An Example Up: Parallel Logic Programming Previous: Other Intermediate Languages

Classification of Parallelism

In the previous section we briefly introduced the basic forms of parallelism commonly identified in Logic Programming languages. In order to better understand the problems connected with the exploitation of parallelism in Logic Programming, it is important to introduce an additional level of classification. The parameter in this classification is simply represented by the level of interaction existing between parallel threads of computation [82]. This classification is independent from the specific form of parallelism exploited (i.e., either or- or and-parallelism). In order to make the description uniform, we generically talk about threads of computation to indicate potentially parallel pieces of computation (i.e., parallel subgoals in and-parallelism and alternatives from a parallel choice point in or-parallelism).

We will also use the generic term dependency between threads to indicate the potentialgif ability of one thread of affecting the execution of the other threads. For example, an unbound variable accessible by different threads may represent a dependency.

Using this parameter, we can develop the following classification of parallelism:

The classification above applies to both or- and and-parallel systems, and in the rest of this section we will see how the classes above instantiate in the two cases (for or- and and-parallelism) and for their combinations.


next up previous contents
Next: An Example Up: Parallel Logic Programming Previous: Other Intermediate Languages

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