Automatic parallelization

Automatic parallelization, also auto parallelization or Autoparallelization, refers to use a modern optimizing compiler(paralleling compiler) to compile sequential code to multi-threaded or vectorized (or even both) one in order to utilize a number of processors simultaneously in a shared-memory multiprocessor (SMP) machine. It aims to relief programers from tedious and error-prone manual parallelization process.

The major focus in auto parallelization is the loops in codes, because loops take the most part of the execution time in general. A auto parallelization compiler tries to splits a loop up so that a number of iterations of the loop can be executed on separate processors concurrently.

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

• Is it safe to parallelize the loop?
• Is it worthwile to parallize it?

The first phase largely involves the data dependence of the loop to decide that each iteration of the loop can be executed independently to other iterations. The seconde phase tries to justify the parallization effort by comparing final outcome of the parallelized code to the execution time of theoriginal sequential code because parallization introduces extra overheads.

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.

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

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

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