Automatic parallelization

Automatic parallelization, also auto parallelization, or autoparallelization refers to converting sequential code into multi-threaded and/or vectorized code in order to use multiple processors simultaneously in a shared-memory multiprocessor (SMP) machine.^[1] Fully automatic parallelization of sequential programs is a challenge because it requires complex program analysis and the best approach may depend upon parameter values that are not known at compilation time.^[2]

The programming control structures on which autoparallelization places the most focus are loops, because, in general, most of the execution time of a program takes place inside some form of loop. There are two main approaches to parallelization of loops: pipelined multi-threading and cyclic multi-threading.^[3] For example, consider a loop that on each iteration applies a hundred operations, and runs for a thousand iterations. This can be thought of as a grid of 100 columns by 1000 rows, a total of 100,000 operations. Cyclic multi-threading assigns each row to a different thread. Pipelined multi-threading assigns each column to a different thread.

Automatic parallelization technique

Parse

This is the first stage where the scanner will read the input source files to identify all static and extern usages. Each line in the file will be checked against pre-defined patterns to segregate into tokens. These tokens will be stored in a file which will be used later by the grammar engine. The grammar engine will check patterns of tokens that match with pre-defined rules to identify variables, loops, control statements, functions etc. in the code.

Analyze

The analyzer is used to identify sections of code that can be executed concurrently. The analyzer uses the static data information provided by the scanner-parser. The analyzer will first find all the totally independent functions and mark them as individual tasks. The analyzer then finds which tasks have dependencies.

Schedule

The scheduler will list all the tasks and their dependencies on each other in terms of execution and start times. The scheduler will produce the optimal schedule in terms of number of processors to be used or the total execution time for the application.

Code Generation

The scheduler will generate a list of all the tasks and the details of the cores on which they will execute along with the time that they will execute for. The code Generator will insert special constructs in the code that will be read during execution by the scheduler. These constructs will instruct the scheduler on which core a particular task will execute along with the start and end times.

Cyclic multi-threading

A cyclic multi-threading parallelizing compiler tries to split up a loop so that each iteration can be executed on a separate processor concurrently.

Compiler parallelization analysis

The compiler usually conducts two passes of analysis before actual parallelization in order to determine the following:

Is it safe to parallelize the loop? Answering this question needs accurate dependence analysis and alias analysis
Is it worthwhile to parallelize it? This answer requires a reliable estimation (modeling) of the program workload and the capacity of the parallel system.

The first pass of the compiler performs a data dependence analysis of the loop to determine whether each iteration of the loop can be executed independently of the others. Data dependence can sometimes be dealt with, but it may incur additional overhead in the form of message passing, synchronization of shared memory, or some other method of processor communication.

The second pass attempts to justify the parallelization effort by comparing the theoretical execution time of the code after parallelization to the code's sequential execution time. Somewhat counterintuitively, code does not always benefit from parallel execution. The extra overhead that can be associated with using multiple processors can eat into the potential speedup of parallelized code.

Example

A loop is called DOALL if all of its iterations, in any given invocation, can be executed concurrently.

The Fortran code below is DOALL, and can be auto-parallelized by a compiler because each iteration is independent of the others, and the final result of array z will be correct regardless of the execution order of the other iterations.

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

There are many pleasingly parallel problems that have such DOALL loops. For example, when rendering a ray-traced movie, each frame of the movie can be independently rendered, and each pixel of a single frame may be independently rendered.

On the other hand, the following code cannot be auto-parallelized, because the value of z(i) depends on the result of the previous iteration, z(i - 1).

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

This does not mean that the code cannot be parallelized. Indeed, it is equivalent to the DOALL loop

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

However, current parallelizing compilers are not usually capable of bringing out these parallelisms automatically, and it is questionable whether this code would benefit from parallelization in the first place.

Pipelined multi-threading

A pipelined multi-threading parallelizing compiler tries to break up the sequence of operations inside a loop into a series of code blocks, such that each code block can be executed on separate processors concurrently.

There are many pleasingly parallel problems that have such relatively independent code blocks, in particular systems using pipes and filters.

For example, when producing live broadcast television, the following tasks must be performed many times a second:

Read a frame of raw pixel data from the image sensor,
Do MPEG motion compensation on the raw data,
Entropy compress the motion vectors and other data,
Break up the compressed data into packets,
Add the appropriate error correction and do a FFT to convert the data packets into COFDM signals, and
Send the COFDM signals out the TV antenna.

A pipelined multi-threading parallelizing compiler could assign each of these six operations to a different processor, perhaps arranged in a systolic array, inserting the appropriate code to forward the output of one processor to the next processor.

Recent research focuses on using the power of GPU's^[4] and multicore systems^[5] to compute such independent code blocks( or simply independent iterations of a loop) at runtime. The memory accessed (whether direct or indirect) can be simply marked for different iterations of a loop and can be compared for dependency detection. Using this information, the iterations are grouped into levels such that iterations belonging to the same level are independent of each other, and can be executed in parallel.

Difficulties

Automatic parallelization by compilers or tools is very difficult due to the following reasons:^[6]

dependence analysis is hard for code that uses indirect addressing, pointers, recursion, or indirect function calls because it is difficult to detect such dependencies at compile time;
loops have an unknown number of iterations;
accesses to global resources are difficult to coordinate in terms of memory allocation, I/O, and shared variables;
irregular algorithms that use input-dependent indirection interfere with compile-time analysis and optimization.^[7]

Workaround

Due to the inherent difficulties in full automatic parallelization, several easier approaches exist to get a parallel program in higher quality. One of these is to allow programmers to add "hints" to their programs to guide compiler parallelization, such as HPF for distributed memory systems and OpenMP or OpenHMPP for shared memory systems. Another approach is to build an interactive system between programmers and parallelizing tools/compilers. Notable examples are Vector Fabrics' Pareon, SUIF Explorer (The Stanford University Intermediate Format compiler), the Polaris compiler, and ParaWise (formally CAPTools). Finally, another approach is hardware-supported speculative multithreading.

Parallelizing compilers and tools

Most research compilers for automatic parallelization consider Fortran programs,^{[citation needed]} because Fortran makes stronger guarantees about aliasing than languages such as C. Typical examples are:

Recently, Aubert, Rubiano, Rusch, and Seiller^[8] used a dependency analysis technique ^[9] to automatically parallelise loops in C code.

References

^ Yehezkael, Rafael (2000). "Experiments in Separating Computational Algorithm from Program Distribution and Communication" (PDF). Applied Parallel Computing. New Paradigms for HPC in Industry and Academia. Lecture Notes in Computer Science. Vol. 1947. Springer Verlag. pp. 268–278. doi:10.1007/3-540-70734-4_32. ISBN 978-3-540-41729-3.
^ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. pp. 575, 593. ISBN 978-1-55860-253-3.
^ Campanoni, Simone; Jones, Timothy; Holloway, Glenn; Wei, Gu-Yeon; Brooks, David (2012). The HELIX Project: Overview and Directions.
^ Anantpur, J.; Govindarajan, R. "Runtime dependence computation and execution of loops on heterogeneous systems" (PDF). Archived from the original (PDF) on 6 October 2015. Retrieved 5 October 2015.
^ Zhuang, X.; Eichenberger, A. E.; Luo, Y.; O'Brien, Kathryn Kevin, Exploiting Parallelism with Dependence-Aware Scheduling
^ "Automatic parallelism and data dependency". Archived from the original on 14 July 2014.
^ Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". Parallel Algorithms and Cluster Computing. Lecture Notes in Computational Science and Engineering. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN 978-3-540-33539-9.
^ Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2023). "Distributing and Parallelizing Non-canonical Loops". Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science. Vol. 13881. pp. 91–108. doi:10.1007/978-3-031-24950-1_1.
^ Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Loop Quasi-Invariant Chunk Detection". Automated Technology for Verification and Analysis. Lecture Notes in Computer Science. Vol. 10482. pp. 91–108. doi:10.1007/978-3-319-68167-2_7. ISBN 978-3-319-68166-5.

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Automatic parallelization