Red-Black Relaxation

Jacobi relaxation is not normally used in practise. It is more common to use the variant know as red-black relaxation. In this scheme alternate iterations update only odd sites and only even sites of the array.

This scheme is very easy to implement in HPJava. The only new language feature it introduces is the option of specifying a stride as well as an upper and lower bound in the limits of the overall construct. The program becomes:

  Procs2 p = new Procs2() ;
  on(p) {
    Range x = new ExtBlockRange(N, p.dim(0)) ;
    Range y = new ExtBlockRange(N, p.dim(1)) ;

    double [[-,-]] a = new double [[x, y]] ;

    // Initialize `a' - set boundary values.

    ... Identical to previous example ... 
    
    // Main loop.

    double [[-,-]] r = new double [[x, y]] ;

    int iter = 0 ;

    do {
      Adlib.writeHalo(a) ;

      overall(i = x for 1 : N - 2)
        overall(j = y for 1 + (i` + iter) % 2 : N - 2 : 2) {

          double newA = 0.25 * (a [i - 1, j] + a [i + 1, j] +
                                a [i, j - 1] + a [i, j + 1]) ;

          r [i, j] = Math.abs(newA - a [i, j]) ;

          a [i, j] = newA ;
        }

      iter++ ;

    } while(Adlib.maxval(r) > EPS) ;
  }

The most significant change is in the bounds of the inner overall construct. The rather complex lower bound expression

1 + (i` +
iter) % 2

takes the value 1 or 2. In any case the step associated with j is 2. If iter is even, the lower bound is 1 if i` is even and 2 if i` is odd. So the nested overall constructs enumerate all non-boundary elements for which i` + j` is odd. Conversely if iter is odd the nested overalls enumerate all elements for which i` + j` is even.

Note we no longer need the intermediate array b, although we did store the new array element in the local scalar variable newA, just so we could compute the residual before overwriting the old value of the array element. As emphasized earlier declaring a local variable inside an overall construct is perfectly acceptable. It is no different to declaring a local variable inside the body of a for construct in Java.

Next: Array Sections

Bryan Carpenter, (dbc@ecs.soton.ac.uk). Last updated May 2007.