Automatic parallelization

History

Research on automatic parallelization developed alongside work on optimizing compilers, vector processors and parallel computer architectures. One motivation was the existence of sequential scientific programs, particularly in Fortran, that researchers sought to execute efficiently on machines capable of performing multiple operations concurrently.

During the 1970s, David Kuck and colleagues at the University of Illinois Urbana-Champaign developed the Parafrase compiler system. Parafrase was used to investigate automatic vectorization, dependence-based program restructuring and transformations for parallel execution. Work on Parafrase influenced subsequent restructuring-compiler research at other institutions, including work associated with Ken Kennedy at Rice University and parallelizing-compiler research at IBM.

At IBM, Frances Allen and colleagues developed PTRAN (Parallel TRANslator), a system for automatically restructuring sequential Fortran programs for execution on parallel architectures. PTRAN's analysis incorporated interprocedural information into dependence analysis. Allen's work on compiler optimization, interprocedural analysis and parallelization later formed part of the work for which she received the 2006 Turing Award; she was the first woman to receive the award.

At Rice University, Kennedy and collaborators developed compiler analyses and restructuring techniques for vector and parallel execution. Work there included the PFC (Parallel Fortran Converter) and research on practical dependence testing.

By 1993, Utpal Banerjee, Rudolf Eigenmann, Alexandru Nicolau and David Padua published a survey of automatic program parallelization in the Proceedings of the IEEE. It covered dependence analysis, program transformations, loop parallelization, recursive routines and experimental evaluations of parallelizing compilers. Research subsequently continued into techniques including polyhedral compilation, runtime dependence analysis, automatic vectorization and parallelization for multicore processors.

Compiler techniques

Automatic parallelization generally combines several forms of program analysis and transformation rather than following a single fixed compiler pipeline.

Dependence analysis

A central problem is determining whether operations can interfere with one another. A data dependence exists when the required ordering of operations is constrained because they access the same data and at least one operation modifies it.

For loops, a compiler is particularly concerned with loop-carried dependences, in which an operation in one iteration depends on an operation in another. Loops without relevant loop-carried dependences are candidates for executing multiple iterations concurrently.

Dependence analysis can involve reasoning about array subscripts, induction variables, loop bounds and relationships between memory accesses. Tests for array dependences have therefore been an important area of parallelizing-compiler research.

Alias and pointer analysis

Dependence analysis becomes more difficult when different expressions may refer to the same memory location. In languages with pointers or references, a compiler may require alias analysis or points-to analysis to determine whether apparently distinct accesses can interfere.

If a compiler cannot establish that memory references are independent, it may need to preserve their sequential ordering even when the references would not overlap during a particular execution. Regular array-access patterns can make these relationships easier to analyze than indirect or input-dependent memory accesses.

Program transformations

Code that cannot immediately be parallelized can sometimes be transformed into an equivalent form that exposes parallelism. Parallelizing compilers have used transformations including loop interchange, loop distribution, loop fusion and fission, scalar expansion, privatization and transformations that modify or eliminate dependences.

Transformations may interact with other optimization goals such as cache locality and vectorization, so increasing the amount of exposed parallelism does not by itself guarantee improved execution time.

Profitability analysis

After determining that parallel execution is legal, a compiler can estimate whether it is worthwhile. Relevant factors include the amount of computation, the number of available processors, synchronization and scheduling costs, memory behavior and the expected number of loop iterations.

A compiler may therefore choose not to parallelize code even when it can establish that doing so would preserve program behavior.

Code generation and runtime techniques

After identifying parallel work, a compiler must map it to mechanisms supported by the target system. Depending on the compiler and target, this can involve generating multiple threads, calls to a parallel runtime, vector operations, or another parallel execution model.

Some approaches defer part of the dependence decision until runtime. Runtime checks can establish properties such as non-overlapping memory regions for a particular execution when static analysis alone cannot prove them.

Forms of parallelism

Loop and data parallelism

Loop parallelization distributes independent loop iterations among multiple execution resources. It has been extensively studied for numerical computations with regular array accesses.

Closely related automatic vectorization transforms operations so that one instruction operates on multiple data elements using SIMD hardware. Vectorization and thread-level loop parallelization are distinct transformations, but they can rely on related dependence analyses and loop transformations.

Task parallelism

Parallelism can also occur between larger regions of computation rather than individual loop iterations. Analysis can identify statements, functions, tasks or regions whose dependences permit concurrent execution.

Extracting such parallelism becomes more difficult when control flow and data access patterns depend strongly on runtime information.

Pipelined parallelism

Some computations consist of a sequence of stages in which the output of one stage becomes the input of another. Different data items can occupy different stages simultaneously, producing pipeline parallelism.

Compiler techniques such as software pipelining similarly reorganize operations from different loop iterations so that multiple stages of computation overlap in execution.

Challenges and limitations

Fully automatic parallelization is limited by the need to establish that transformations preserve program behavior and by the cost of parallel execution.

Common obstacles include:

• Uncertain memory dependences. Pointers, aliases, indirect array accesses and dynamically allocated data structures can make it difficult to determine whether operations access the same memory.
• Irregular control flow. Branches, recursion, indirect function calls and input-dependent execution can make parallel structure harder to determine statically.
• Unknown workloads. Loop iteration counts and the amount of work performed by individual iterations may depend on runtime input.
• Side effects and external state. Input/output, shared variables and other externally visible operations can impose ordering constraints.
• Synchronization and communication costs. Coordinating parallel work can offset the execution time saved by running computations concurrently.
• Memory-system limitations. Parallel code can be limited by memory bandwidth, cache behavior or contention rather than processor execution capacity.
• Conservative static analysis. When a compiler cannot establish that a transformation is safe, it generally must retain an ordering that preserves the sequential program's behavior.

These issues help explain why automatic parallelization has been studied particularly extensively for regular numerical programs, where iteration spaces and memory-access relationships can often be analyzed statically.

Programmer-assisted parallelization

Because a compiler cannot always infer enough information to parallelize a program automatically, parallel programming systems can instead allow the programmer to explicitly identify parallel work or provide information to the compiler.

OpenMP is a widely implemented example of this programmer-directed approach. It provides compiler directives, library routines and environment variables for expressing parallel regions, work distribution, tasks, synchronization and data-sharing behavior in C, C++ and Fortran. The OpenMP specification explicitly distinguishes this model from compiler-generated automatic parallelization: OpenMP requires the programmer to specify the actions used to execute the program in parallel and does not require the implementation to discover data dependences automatically.

Historically, systems such as High Performance Fortran similarly provided language-level information for data-parallel execution. Programmer annotations and directives can supply information that would otherwise be difficult for static compiler analysis to infer.

Interactive parallelization systems have also been investigated, in which compiler analysis identifies potential parallelism or obstacles and the programmer participates in selecting transformations or supplying additional information.

Implementations and research systems

Automatic parallelization has been implemented in research systems and in production compiler infrastructure. The following are representative examples rather than a comprehensive list.

GCC's -ftree-parallelize-loops optimization provides a production example of loop autoparallelization. GCC documents the transformation as splitting a loop's iteration space among multiple threads and limits it to loops whose iterations are independent and