Information Technology Reference
In-Depth Information
formation resulting from this adaptation guarantees admissibility, i.e., soundness
(in the strong sense), and executional improvement, i.e.,
relative
completeness.
Actually, this is the best we can hope for, since executional optimality is out of
the scope of any static approach because the property of being the bottleneck
component of a parallel statement is highgradely run-time dependent.
Reuse on the Analysis and Transformation Level.
Reusability has a
slightly dierent flavour on the analysis and transformation level. On the trans-
formation level reusability amounts essentially to the robustness of a specic
optimization strategy with respect to setting and paradigm changes, on the anal-
ysis level it amounts essentially to the uniformity of the specication of a DFA
problem which can possibly be fed into a generic paradigm-dependent algorithm
producing the concrete algorithm for solving the corresponding DFA problem.
On the analysis level, reusability in the sense of uniformity has been achieved
to quite a large extent. In fact, the DFA approaches of the various settings
considered can be condensed to the abstract version shown in Figure 10 (cf. [15]).
Though the specics of the various paradigms and settings are dierent, from the
point of view of a DFA designer, the specication interfaces and proof obligations
to guarantee soundness and completeness are almost the same. In particular, this
allows us the construction of DFA generators in the fashion of [11] and [15]. On
the analysis level of optimization, this is an important contribution to enhance
reusability
and
portability
of know-how and of techniques based thereon.
Similarly, this also holds on the transformation level of optimization even
though reuse on this level, i.e., of specic optimization strategies, demands usu-
ally for setting and paradigm-dependent adaptations in order to accommodate
the specics of a new setting as we demonstrated here by means of PRE. Gen-
erally, however, this is worth the eort. In fact, often an optimization turns out
to be much more powerful in a setting dierent from the one it was designed for.
A striking example was the extension of
partial dead-code elimination
[22] and
partial redundant-assigment elimination
[23] and their combination for
distribu-
tion assignment placement
(
DAP
) [18,19] in
High Performance Fortran
(
HPF
),
a data-parallel language. Though the completeness or optimality results apply-
ing to the individual transformations in the basic intraprocedural setting do not
carry over to the data-parallel setting of HPF, DAP proved to be most powerful
in practical experiments, which have been performed by means of the Vienna
Fortran Compilation System [2,45]. Often, improvements of several hundred per
cent could be observed, which are rather unlikely of being ever observed for in-
traprocedural sequential programs. In HPF programs they are rendered possible
by the specics of distribution statements causing (costly!) communication.
8 Conclusions
In this article, we reconsidered optimization under the perspective of soundness,
completeness, and, additionally, reusability. While the choice of soundness and
completeness aimed at highlighting an analogy between program optimization
and program verication, which are usually considered independent or at most
Search WWH ::
Custom Search