Digital Signal Processing Reference
In-Depth Information
If-Conversion is a useful optimization as it avoids pipeline stalls due to mis-
predicted branches. However, If-Conversion does not guarantee performance im-
provements in all cases. For large conditionally executed code blocks, for example,
conventional branches work better. In such cases many instructions need to be
fetched and decoded by the processor that turn out to be disabled and, thus, waste
valuable CPU time. In addition, deeply nested predicates quickly become imprac-
tical. For small, balanced branches, however, If-Conversion effectively increases
processor pipeline utilization through reduced number of stalls and higher flexibility
in instruction scheduling.
3.3
Loop Optimizations
Most execution time of DSP applications is spent on loops. Hence, effective
code optimization of loop structures promises significant overall performance
improvements. Unfortunately, the optimization of loops is a much “harder” problem
than optimizing straight-line code. This is because the individual iterations of a
loop may not be independent of each other, but data dependences might exist, i.e.
data generated in one iteration of the loop gets carried forward to another iteration
where it is consumed. Clearly, any loop restructuring transformation must obey
these dependences in order to preserve correctness.
In the following paragraphs we present a number of loop transformations that are
of particular importance to DSP kernels and applications. A more comprehensive
Within the compiler a suitable framework is used for representing and system-
atically manipulating loop structures. The two most popular frameworks for this
purpose are
unimodular transformations
and the
polyhedral model
. The approach
based on unimodular transformations represents statements of
n
-deep loop nests as
integer points in an
n
-dimensional space which can be captured in matrix notation
upon which transformations described by unimodular matrices can be applied.
These matrices can describe the
loop reversal
,
loop interchange
,and
loop skewing
transformations and combinations thereof. The polyhedral model goes beyond
this and describes the statements contained in a loop nest as unions of sets of
polytopes. The polytope model can represent imperfectly nested loops and affine
transformations. Data dependences and boundaries of the polytopes are expressed as
additional constraints. Both unimodular transformations and the polytope model are
excellent formalisms to capture loop transformations. Still, the key problem remains
to
identify
a suitable sequence of loop transformations to eventually improve the
