HPJava Programming for Irregular Problems

Bryan Carpenter

February 13, 1998

Example from the CHAOS manual:

C  Outer loop L1
L1 do i = 1, n_step
     ...
C    Sweep over edges: Inner Loop L2
L2   do i = 1, nedge
       n1 = edge1(i)
       n2 = edge2(i)
       y(n1) = y(n1) + f(x(n1), x(n2))
       y(n2) = y(n2) + g(x(n1), x(n2))
     end do
     ...
   end do

This could be expressed in HPJava using the HPF-like gather/scatter operations in Adlib. That would already allow some optimization and reuse of communication schedules, but it involves copying whole arrays of temporaries, and doesn’t directly allow for irregular repartition of the original data array to reduce the absolute volume of traffic.

Chaos allows various kinds of preprocessing before executing the outer loop

1. Repartitioning of the main data to minimize off processor references

2. Repartitioning the indirection vectors, to optimize placement of iterations.

3. Translation of values in the indirection vectors to local subscripts, and generation of the communication schedule (“inspector” phase).

To enable this preprocessing…