Automatic Parallelization: An Overview of Fundamental Compiler Techniques

Preface......Page 11
Introduction and overview......Page 13
Parallel execution......Page 14
Shared and distributed memory parallelism......Page 15
Structures of parallel computation......Page 19
Compiler phases......Page 21
Intermediate representations......Page 23
Compiler support for parallel machines......Page 27
Dependence analysis, dependence graphs and alias analysis......Page 31
Constant propagation......Page 32
Alias analysis......Page 37
Abstract interpretation......Page 40
Data dependence analysis......Page 41
Determining references to test for dependence......Page 44
Testing for dependence......Page 46
Control dependence......Page 50
Use-def chains and dependence......Page 51
Dependence analysis in parallel programs......Page 54
Simple loop parallelization......Page 63
Parallelizing loops with acyclic and cyclic dependence graphs......Page 64
Targeting vector hardware......Page 67
Producer and consumer synchronization......Page 68
Optimizing producer/consumer synchronization......Page 72
Parallelizing recursive constructs......Page 74
Determining iterations to be executed by a thread......Page 76
Dealing with the effects of speculation......Page 78
Software pipelining for instruction level parallelism......Page 79
Loop peeling and splitting......Page 81
Loop skewing......Page 83
Forward substitution......Page 85
Scalar expansion and privatization......Page 87
Array privatization......Page 88
Node splitting......Page 90
Reduction recognition......Page 91
Which transformations are most important?......Page 93
Loop blocking or strip mining......Page 95
Loop fusion and fission......Page 96
Loop reversal......Page 98
Loop interchange......Page 99
Tiling......Page 101
Unimodular transformations......Page 105
Compiling for distributed memory machines......Page 107
Data distribution......Page 109
Cyclic distribution......Page 112
Block-cyclic distribution......Page 113
Computing the reference set......Page 114
Computation partitioning......Page 115
Bounds of block-cyclically distributed array dimensions......Page 116
Subscripts with multiple loop indices......Page 117
Generating loop bounds with multiple references......Page 118
The shift communication pattern......Page 119
Distributed memory programming languages......Page 120
High Performance Fortran (HPF)......Page 122
Co-Array Fortran......Page 126
Unified Parallel C (UPC)......Page 127
Solving single Diophantine equations......Page 131
Solving multiple Diophantine equations......Page 132
Extreme values of integer functions......Page 133
Dependence analysis, dependence graphs and alias analysis......Page 137
Program parallelization......Page 138
Tiling......Page 139
Compiling for distributed memory machines......Page 140
Current and future directions in parallelizing compilers......Page 141
Bibliography......Page 145
Author's Biography......Page 169