Loop parallelization

The second parallelization that was implemented identifies independent operations that take place in a loop, and move those instructions out into independent loops. Such an example can be seen in figure 4.4.

Figure 4.2: Serial and parallel version of the multiplication/division loop

Serial	Parallel
loop while $r_0$ $r_2 \gets r_2 \times r_1$ $r_2 \gets r_2 / r_0$ $r_0 \gets r_0 - 1$ $r_3 \gets r_3 \times r_1$ $r_3 \gets r_3 / r_0$ $r_0 \gets r_0 - 1$ end $r_2 \gets r_2 + r_3$	parallel block start task loop while $r_0 > 0$ $r_2 \gets r_2 \times r_1$ $r_2 \gets r_2 / r_0$ $r_0 \gets r_0 - 1$ $r_0 \gets r_0 - 1$ end end task loop while $r_0 > 0$ $r_0 \gets r_0 - 1$ $r_3 \gets r_3 \times r_1$ $r_3 \gets r_3 / r_0$ $r_0 \gets r_0 - 1$ end end end $r_2 \gets r_2 + r_3$

Clearly this way of parallelizing the loop is much faster than if we parallelized the independent operations inside the loop. That would require communication in every iteration thru the loop, and unless the independent operations where really computationally hard, we would end up doing a lot of communication and little real computation.

The parallelization of a loop is a step-wise process, where we gather more and more information, and continually decide whether it is possible to continue the loop parallelization. The steps are described in detail in the following.