Sequence parallelization

The most basic parallelization that happens is that sequences of instructions are parallelized, when possible. An example of such a parallelization could be the Fibonacci calculator. The serial and parallel pseudo-code is shown in figure 4.3.

Figure 4.1: Serial and parallel version of the Fibonacci calculator

Serial	Parallel
if $r_0>2$ then $r_1 \gets a_0$ $r_1 \gets r_1-1$ $r_2 \gets \mathrm{fib}(r_1)$ $r_1 \gets r_1-1$ $r_3 \gets \mathrm{fib}(r_1)$ $r_2 \gets r_2 + r_3$ return $r_2$ else return $a_0$	if $r_0>2$ then $r_1 \gets a_0$ $r_1 \gets r_1-1$ parallel block start task $r_2 \gets \mathrm{fib}(r_1)$ end task $r_1 \gets r_1-1$ $r_3 \gets \mathrm{fib}(r_1)$ end end $r_2 \gets r_2 + r_3$ return $r_2$ else return $a_0$

The strategy behind the sequence parallelizer is actually quite simple. We have our sequential code as input, and we have another code sequence where we put our instructions as we finish treating them. Furthermore we have some temporary buffers where we hold the instructions as we try to arrange them in parallel tasks.

Our temporary buffers are: main which hold a number of instructions that are currently not parallel, but may have the potential to become a task that can run concurrently with other tasks. And we have the tasks array (it is a vector of instruction sequences), which is in use only when we are actually adding instructions to a set of concurrent tasks. The tasks structure will then hold an instruction sequence per active task.

We look at an instruction too see what data it depends upon (uses) and what data it modifies (touches). The current instruction is called C (for Current). We will search for the most recent instruction that touches any of the data the current instruction uses, and call this instruction T (for Toucher). If the instruction cannot be found, we assume that the data was touched somewhere outside the block of code we are currently looking at, and therefore we ``fake'' the toucher by setting it to be the first instruction in the main sequence.

Several cases can now arise, also depending on our current parallelizer state (whether we have parallel tasks already or not):