Automatic parallelization
Automatic parallelization, also auto-parallelization or autoparallelization, is a compiler optimization in which a compiler or other software tool transforms sequential program code so that some of its operations can execute in parallel. The generated program may use multiple processor cores or hardware threads, vector instructions, or other forms of parallel execution.[1]
Automatic parallelization attempts to reduce the amount of explicit parallel programming required of the programmer. To do so, a compiler must determine whether operations can execute concurrently without changing the behavior of the program and whether executing them in parallel is likely to improve performance. This involves analyses such as dependence analysis, alias analysis and data-flow analysis, together with program transformations that expose or increase usable parallelism.[2][1]
Loops have historically been an important target for automatic parallelization, particularly in numerical programs with regular array accesses.[1] Automatic parallelization is therefore closely related to automatic vectorization, loop transformation, and other compiler techniques for exploiting parallel hardware.
Overview
[edit]Consider a sequential loop in which corresponding elements of two arrays are added:
do i = 1, n
z(i) = x(i) + y(i)
enddo
Each iteration writes to a different element of z and, assuming the arrays do not overlap in a way that introduces a dependence, does not require the result of another iteration. The iterations can therefore potentially execute concurrently. A loop for which all iterations of a given invocation can execute concurrently is commonly called a DOALL loop.[2]
By contrast:
do i = 2, n
z(i) = z(i - 1) * 2
enddo
contains a loop-carried dependence: iteration i reads a value produced by iteration i - 1. Executing the iterations simultaneously without an additional transformation would therefore change the program's behavior.[1]
A parallelizing compiler consequently has to address two distinct questions:
- Legality: can a transformation execute computations in parallel while preserving the semantics of the original program?
- Profitability: if the transformation is legal, is parallel execution expected to improve performance?
The distinction is important because parallel execution has overhead. Work may need to be divided among threads, processors may need to synchronize or communicate, and memory-system effects can reduce the speedup obtained from concurrent execution. A transformation can therefore be legal without being profitable.[1]
Some dependences can be modified or eliminated by program transformations. Automatic parallelization can therefore involve both detecting parallelism already present in a program and restructuring computations to expose additional parallelism.[2][1]
History
[edit]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.[2]
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.[3] 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.[3]
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.[4] 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.[5]
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.[6]
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.[2] Research subsequently continued into techniques including polyhedral compilation, runtime dependence analysis, automatic vectorization and parallelization for multicore processors.[1]
Compiler techniques
[edit]Automatic parallelization generally combines several forms of program analysis and transformation rather than following a single fixed compiler pipeline.[1]
Dependence analysis
[edit]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.[2]
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.[6]
Alias and pointer analysis
[edit]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.[1]
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.[1]
Program transformations
[edit]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.[2][1]
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.[1]
Profitability analysis
[edit]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.[1]
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
[edit]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.[1]
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.[1]
Forms of parallelism
[edit]Loop and data parallelism
[edit]Loop parallelization distributes independent loop iterations among multiple execution resources. It has been extensively studied for numerical computations with regular array accesses.[2][1]
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.[1]
Task parallelism
[edit]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.[2]
Extracting such parallelism becomes more difficult when control flow and data access patterns depend strongly on runtime information.
Pipelined parallelism
[edit]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.[2]
Challenges and limitations
[edit]Fully automatic parallelization is limited by the need to establish that transformations preserve program behavior and by the cost of parallel execution.[1]
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.[1]
- Irregular control flow. Branches, recursion, indirect function calls and input-dependent execution can make parallel structure harder to determine statically.[2]
- 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.[1]
- 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.[1]
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.[1]
Programmer-assisted parallelization
[edit]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.[7] 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.[7]
Historically, systems such as High Performance Fortran similarly provided language-level information for data-parallel execution.[1] 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.[2]
Implementations and research systems
[edit]Automatic parallelization has been implemented in research systems and in production compiler infrastructure. The following are representative examples rather than a comprehensive list.
| System | Role |
|---|---|
| Parafrase | University of Illinois restructuring compiler used to investigate vectorization, dependence analysis and transformations for parallel execution.[3] |
| IBM PTRAN | Research system for automatically restructuring sequential Fortran programs for parallel architectures.[4] |
| PFC | Rice University work on converting Fortran programs into forms suitable for vector and parallel execution.[6] |
| Polaris | Research parallelizing compiler developed to investigate program analysis and transformations for scientific programs.[2] |
| GCC | Production compiler with an option for parallelizing suitable loops across multiple threads.[8] |
| LLVM Polly | Polyhedral optimization infrastructure developed for LLVM; research on Polly has included detection of parallel loops and generation of OpenMP or SIMD code from polyhedral representations.[9] |
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
References
[edit]- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Midkiff, Samuel P. (2022). Automatic Parallelization: An Overview of Fundamental Compiler Techniques. Springer. doi:10.1007/978-3-031-01736-0. ISBN 978-3-031-00608-1.
- 1 2 3 4 5 6 7 8 9 10 11 12 13 Banerjee, Utpal; Eigenmann, Rudolf; Nicolau, Alexandru; Padua, David A. (1993). "Automatic Program Parallelization". Proceedings of the IEEE. 81 (2): 211–243. doi:10.1109/5.214548.
- 1 2 3 "David J. Kuck". Engineering and Technology History Wiki. IEEE. Retrieved 20 August 2026.
- 1 2 Allen, Frances; Burke, Michael; Charles, Philippe; Cytron, Ron; Ferrante, Jeanne (1988). "An overview of the PTRAN analysis system for multiprocessing". Journal of Parallel and Distributed Computing. 5 (5): 617–640. doi:10.1016/0743-7315(88)90015-9.
- ↑ "Frances Allen". IBM History. IBM. Retrieved 20 August 2026.
- 1 2 3 Goff, Gina; Kennedy, Ken; Tseng, Chau-Wen (1991). "Practical dependence testing". ACM SIGPLAN Notices. 26 (6): 15–29. doi:10.1145/113446.113448.
- 1 2 "OpenMP Application Programming Interface Specification". OpenMP. OpenMP Architecture Review Board. Retrieved 20 August 2026.
- ↑ "Optimize Options". Using the GNU Compiler Collection. Free Software Foundation. Retrieved 20 August 2026.
- ↑ Grosser, Tobias (2011). Enabling Polyhedral Optimizations in LLVM (PDF) (Thesis).