Content deleted Content added
Simetrical (talk | contribs) m Disambiguate Loop to Control flow#Loops using popups |
No edit summary |
||
Line 1:
'''Automatic parallelization''' (also known as '''auto parallelization''' or '''Autoparallelization'''), refers to the use of a modern optimizing parallelizing [[compiler]] to convert sequential [[source code|code]] into [[multi-threaded]] or vectorized (or even both) code in order to utilize multiple processors simultaneously in a shared-memory [[multiprocessor]] (SMP) machine. The goal of automatic parallelization is to relieve programers from the tedious and error-prone manual parallelization process. Though highly improved since several decades, full automatic parallelization of sequential programs by compilers remains a grand challenge due to the complex [[program analysis]] needed and the unknown factors (such as input data range) during compilation.
The programming control structures on which auto parallelization places the most focus are [[Control flow#Loops|loop]]s, because, in general, most of the [[execution time]] of a program takes place inside some form of loop. An auto parallelization compiler tries to split up a loop so that its [[iterations]] can be executed on separate [[processors]] concurrently.
Line 5:
==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? Reliable estimation of workload of programs and capacity of parallel systems is required.
The first pass of the compiler performs a [[dependence analysis|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.
Line 30:
This does not mean that the code cannot be parallelized. However, current parallelizing compilers are not capable of bringing out these parallelisms automatically, and it is very questionable as to whether this code would benefit from parallelization in the first place.
==Workaround ==
Due to the inherent difficulties in full automatic parallelization, several easier approaches exist to get a parallel program in higher quality. They are:
* let programmers to add "hints" into programs to guide compiler parallelization, such as [[HPF]] for [[distributed memory system]]s and [[OpenMP]] for [[shared memory system]]s.
* build an interactive system between programmers and parallelizing tools/compilers. Notable examples are [[SUIF]] explorer, [[Polaris compiler]], and [[CAPTOOLS]](now [[Parawise]]).
* hardware-supported speculative threading
[[Category:Compiler optimizations]]
| |||