Automatic parallelization: Difference between revisions

Revision as of 10:30, 12 October 2008

Revision as of 16:25, 13 March 2009

Line 15:

==Example==

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

<source lang="fortran">

<pre>

do i=1, n

z(i) = x(i) + y(i)

enddo

</presource>

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

<source lang="fortran">

<pre>

do i=2, n

z(i) = z(i-1)*2

enddo

</presource>

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

<source lang="fortran">

<pre>

do i=2, n

z(i) = z(1)*2**(i-1)

enddo

</presource><!-- Yes, it would be more efficient to use bit-shifting, but let's keep it simple. -->

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. <!-- Really? That seems doubtful. Maybe we should have an example of tricky-to-parallelize code like this, and an example of something actually impossible to parallelize? -->