Thread-level Speculative Parallelization

The basic idea under speculative parallelization (also called thread-level spec-ulation) [2, 6, 7] is to assign the execution of dierent blocks of consecutive iterations to dierent threads, running each one on its own processor. While execution proceeds, a software monitor ensures that no thread consumes an in-correct version of a value that should be calculated by a predecessor, therefore violating sequential semantics. If such a dependence violation occur, the monitor stops the parallel execution of the oending threads, discards iterations incor-rectly calculated, and restart their execution using the correct values. Figure 1 shows an example of speculative parallel execution of a loop with dependences. The detection of dependence violations can be done either by hardware or software. Hardware solutions [4, 5] rely on additional hardware modules to detect dependences, while software methods [2, 6, 7] augment the original loop with new instructions that check for violations during the parallel execution. The author's visits to EPCC thanks to the TRACS and HPC-Europa pro-grammes led to a successful collaboration with Dr. Marcelo Cintra, of th