Go to the first, previous, next, last section, table of contents.


Owner Computes Rule

 A(N,N), B(N,N)
 DISTRIBUTE (*,BLOCK) A, B
 do i = 2, N-1
   do j = i, N-1
     A(i, j) = A(i-1, j-1)
   enddo
 enddo

For the above loop nest, the computation distribution is found using the owner computes rule. The array `A' is distributed, thus the write access will determine the distribution of the loop nest. Since the block size used to distribute the array depends on number of processors, which is not known at compile time, a symbolic constant block size is used (`blk'). Since symbolic block size makes the system of inequalities non-linear, an extension to linear programming is used to solve this system (See the SUIFMATH Library Reference Manual).

iter = [2 <= i <= N - 1
        i <= j <= N - 1 ]

dist = [blk*p <= by < blk*p + blk ]

lhs = [bx = i
       by = j ]

res = { iter, dist, lhs }

#final = res.order(N p i j bx by)
final.code(2)

end

The printout of the example session:

csh> lic -c
Rapid Prototyping System for Code Generation
> < example3
iter = [2 <= i <= N - 1
        i <= j <= N - 1]
-1+N-j >= 0
j-i >= 0
-1+N-i >= 0
-2+i >= 0

dist = [blk*p <= by < blk*p + blk ]
-1+blk+blk*p-by >= 0
-blk*p+by >= 0

lhs = [bx = i
       by = j ]
by-j >= 0
-by+j >= 0
bx-i >= 0
-bx+i >= 0

res = { iter, dist, lhs }
-1+N-j >= 0
j-i >= 0
-1+N-i >= 0
-2+i >= 0
-1+blk+blk*p-by >= 0
-blk*p+by >= 0
-j+by >= 0
j-by >= 0
-i+bx >= 0
i-bx >= 0

#final = res.order(N p i j bx by)
final.code(2)

for(p = 2/blk; p <= (-1+N)/blk; p++)
   for(i = 2; i <= min(-1+N, -1+blk+blk*p); i++)
      for(j = max(blk*p, i); j <= min(-1+N, -1+blk+blk*p); j++) {
         bx = i;
         by = j;
      }
end
 > quit
done(0)

csh>


Go to the first, previous, next, last section, table of contents.