Automatic parallelization

Automatic parallelization, also called auto-parallelization, is a compiler optimization in which a compiler or other tool transforms sequential program code so that some operations can run in parallel, on several cores, hardware threads or vector units. Its aim is to reduce how much explicit parallel programming a person must write. The compiler has to settle two questions: legality, meaning whether running operations concurrently preserves the behavior of the original program, and profitability, meaning whether the parallel version is likely to be faster once thread and synchronization overheads are counted. Loops are the traditional target, especially numerical code with regular array access, where a loop with no loop-carried dependence can run its iterations concurrently. The supporting analyses are dependence analysis, alias and pointer analysis and data-flow analysis, together with transformations that expose more parallelism. Early work includes the Parafrase system of David Kuck, Frances Allen and colleagues on PTRAN at IBM, and Ken Kennedy and collaborators on PFC at Rice University.