Optimization Under the Perspective of Soundness, Completeness, and Reusability - Correct System Design: Recent Insights and Advances - page 297

a) b)

h := a+b

ParBegin

ParBegin

y := a+b

x := a+b y := a+b

x := a+b

a := ...

a := ... a := ...

a := ...

y := a+b

x := a+b y := a+b

x := a+b

ParEnd

ParEnd

z := a+b

z := h

Up-safe Points
Down-safe Points

Fig. 7. Violation of soundness by the as-early-as-possible placing strategy.

and interference. Intuitively, this is because up-safety and down-safety reflect
properties of interleaving sequences, which cannot adequately be made use of in
a parallel program, which can be considered a \compact" nite representation of
all interleaving sequences. As a consequence, the insertion at the program's entry
can never be used, though it is down-safe. On the other hand, a computation
of at the use site of the temporary h will (usually) yield a dierent value

than the one which is stored in this temporary because of the assignments to
h executed in the parallel statement. A reinitialization, however, is suppressed,
since

a + b

is up-safe, i.e., available, after leaving the parallel statement. In the
sequential setting, this guarantees that the temporary stores the desired value,
and hence, suppressing the reinitialization is correct. In the parallel setting, this
does not hold (cf. [27]). We will discuss the reason of this failure in more detail
in Section 7.
Besides the loss of soundness of the PSE-transformation, a second new phe-
nomenon shows up in the parallel setting. Dening completeness of a PRE-
transformation in terms of computational optimality is by no means adequate
at all. This is demonstrated in the example of Figure 8. For this example, the
PSE-transformation is sound, i.e., it preserves the semantics of the original pro-
gram. Figure 8(b) shows the result of the PSE-transformation for the program of
Figure 8(a). Note that both programs are computationally optimal, however, the
performance of the program of Figure 8(b) will be worse than that of the pro-
gram of Figure 8(c). The point here is that the relation \computationally better"
is based on a simple count of the occurrences of computations on (sequential-
ized) program paths, i.e., on a pure interleaving view. It does not distinguish
between computations in sequential and parallel program parts. The execution

a + b