Automatic parallelization: Difference between revisions

Revision as of 04:26, 14 October 2005

Revision as of 22:36, 29 October 2005

Line 1:

Automatic parallelization, also auto parallelization or Autoparallelization, refers to the use of a modern optimizing [[compiler]](a parallelizing compiler) to compileconvert sequential code tointo multi-threaded or vectorized (or even both) onecode in order to utilize a number ofmultiple processors simultaneously in a [[shared-memory multiprocessor]] (SMP) machine. ItThe aimsgoal of automatic parallelization is to reliefrelieve programers from the tedious and error-prone manual parallelization process.

The majorprogramming focuscontrol instructures on which auto parallelization isplaces the most focus are [[loop]]s in codes, because, loopsin take thegeneral, most part of the execution time inof generala program takes place inside some form of loop. An auto parallelization compiler tries to splitssplit up a loop up so that theits iterations of the loop can be executed on separate processors concurrently.

== Compiler Analysis==

The compiler usually conducts two passes of analysis before actual parallelization:

----

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

* Is it safe to parallelize the loop?

* Is it worthwile to parallize it?

The first phasepass largely involvesof the compiler performs a [[data dependence analysis]] of the loop to decidedetermine that ifwhether each iteration of the loop can be executed independently toof the others. The secondeData phasedependence triescan tosometimes justifybe thedealt parallizationwith, effortbut byit comparingmay finalincur outcomeadditional ofoverhead in the parallelizedform codeof tomessage thepassing, execution timesynchronization of theshared originalmemory, sequentialor codesome becauseother parallizationmethod introducesof extraprocessor overheadscommunication.

The second pass attempts to justify the parallization 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 parallized code.

For example, code 1 can be auto-parallelized by a compiler because each iteration is independent to others and the final result of array z is always correct for any execution order of the iterations.

== A Brief Example of Auto-Parallelization==

----

ForCode example,1 code 1below can be auto-parallelized by a compiler because each iteration is independent toof the others, and the final result of array z is alwayswill be correct forregardless anyof the execution order of the other iterations.

<pre>

!code 1

Line 17 ⟶ 23:

</pre>

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

<pre>

!code 2

Line 25 ⟶ 31:

</pre>

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.