next up previous contents
Next: And-parallelism: Up: Compile-time Analysis for Parallelism Previous: Compile-time Analysis for Parallelism

Or-parallelism:

compile-time analysis have been scarcely used in the context of or-parallelism. Nevertheless there are considerable advantages that could be obtained by having static knowledge of various properties of the program:
  1. or-parallelism is exploited by exploring in parallel different alternatives emanating from a given choice point. Abstract interpretation may be able to supply information regarding the probability of success of certain alternatives. An alternative that would surely fail with a certain arguments pattern may be avoided. In the same way knowledge regarding the determinacy of certain choice points may allow the scheduler to have a better view of the distribution of the work in the or-tree, allowing better scheduling choices.
  2. as we have described earlier, independent or-parallelism is considerably easier to implement. Abstract interpretation could be used to detect occurrences of this form of parallelism, by guaranteeing that the subgoal to which the choice point is associated does not access any conditional variable (e.g., the subgoal has only ground arguments). Related to the point above, knowledge regarding which variables are accessed along every path of the computation may allow the scheduler to assign to the same or-agent all the alternatives which may access the same conditional variables.
  3. in various models implementing or-parallelism, whenever an or-agent steals some work from another agent, a phase is required to remove/reinstall bindings in order to reconstruct the agent's state for the new computation. Various information extracted through compile-time analysis may help in this phase (e.g., allowing to skip this phase). As an example, knowledge of the modes of the arguments may allow to detect the freeness status of a variable, removing the need of performing trailing and untrailing, and leading to avoidance of the bindings removal phase.
  4. in the stack-copying approach to or-parallelism, compile-time analysis may allow to reduce the amount of information copied. Freeness and aliasing information may, as already observed, remove the need of dealing with binding de-installation and, partially, with binding installation.


next up previous contents
Next: And-parallelism: Up: Compile-time Analysis for Parallelism Previous: Compile-time Analysis for Parallelism

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