| | GSRC Student Profile:
Research Overview: Extracting Iteration Level Parallelism in the Presence of Inter-iteration Dependences
Automatic parallelization by compilers has a key role to play in utilizing the CMP architecture to improve single-threaded application performance. One of the most common compiler techniques to automatically parallelize loops is DOALL parallelization. While DOALL scales with the iteration count of the loop, its applicability is severely limited by the presence of inter-iteration or loop-carried dependences. My thesis proposes two new techniques to extract
iteration-level parallelism from loops with loop-carried dependences.
The first technique, known as Speculative Iteration Chunk Execution (Spice), uses value speculation to break loop-carried dependences,
enabling speculative execution of chunks of iterations in parallel. Unlike most value-speculation based parallelization techniques, Spice speculates only a few values to unlock parallelism using a software-based value predictor.
The second technique known as Parallel-Stage Decoupled Software Pipelining (PS-DSWP) extracts both pipelined parallelism and iteration-level parallelism from loops, thereby generalizing DOALL and DSWP. PS-DSWP partitions a loop into a sequence of pipeline stages that are executed concurrently by different threads, resulting in pipelined parallelism. Iteration-level parallelism is extracted by allowing those stages that do not have any loop-carried dependences, to be executed by multiple threads concurrently. The applicability and effectiveness of PS-DSWP is further enhanced by using speculation.
| |
