Extracting Coarse-grained Parallelism with the Affine Transformation Framework and its Limitations

摘要

Coarse-grained parallelization consists of partitioning sequential code into multiple threads. Each thread may include a large number of dependent statements and it is executed at a different processor (locus) of computation, with occasional synchronizations. The affine transformation framework is the most powerful technique available today to extract coarse-grained parallelism from program loops. However, this paper shows that even the best algorithms defined within this framework may not extract coarse-grained parallelism for the general case of non-uniform loops, as well as for some cases of uniform loops. This motivates further research of advanced techniques allowing the extraction of more coarse-grained parallelism. Some ideas are presented to derive more powerful approaches.