Successive Over Relaxation Example

Successive Over Relaxation (or Red-Black Relaxation) is a common technique in HPF kernels. BLOCK distribution is perfect as most calculations will involve all local calculations. It is only the calculation of the border elements that require elements from other processors.

 DO j = 2,n-1
   DO i = 2,n-1
      a(i,j)=(omega/4)*(a(i,j-1)+a(i,j+1)+ &
              a(i-1,j)+a(i+1,j))+(1-omega)*a(i,j)
   END DO
 END DO

The calculation of a(i,j) uses its 4 neighbours (see Figure 38).

  
Figure 38: Access Patterns in Nearest Neighbour Calculations

Since one element accesses its four closest neighbours when being updated BLOCK distribution in both dimensions can be seen to be the most effective distribution.

Now try this question

Return to corresponding overview page