|
In nested loops, the dependence pattern is usually com-
plicated, especially in the case of coupled subscripts in mul-
tidimensional array references. When the dependences of nested
loops contain irregular dependence relations, it is very dif-
ficult to extract parallelism from the loops. In this thesis,
we present an improved scheme which is based on the static
strip scheduling scheme. Our scheme differs from the previous
scheme in that if we have known ma- ximal and minimal slopes of
all the possible dependence vec- tors, we directly select the
adequate synchronization vectors and strip direction of static
strip scheduling to exploit more parallelism. In our method,
when the strip direction is along the outer loop direction, we
can use the synchronization vectors (1,1) to replace the
synchronization vectors (1,0) in many cases. When the strip
direction is along the inner loop direction, we can also use
the synchronization vectors (1,1) to replace the
synchronization vectors (0,1) in many cases.If the slopes of
the dependence vectors are between 0 and 1 ,or between 0 and
-1, we can change the execution order in the inner loop from
bottom-up to top-down ,or from top-down to bottom-up respec-
tively. Because the longer dependence distance between a source
and a sink reduces the busy-wait time required the sink . It
will make the probability of the synchronization being wait-
free higher.
|