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

Communication Using Exact Data-Flow information

 A(N, N)
 do i = 1, U
   do j = 1, i - 1
     A(i, j) = A(j, i)
   enddo
 enddo

For the above code, which transposes an array, exact data-flow information is used to find communication. Exact data-flow information, which can be obtained using Last Write Trees, will provide producer-consumer relationships between read and write accesses. Instead of data decomposition as in the owner computes rule (see section Owner Computes Rule), computation distribution is supplied.

iter = [ 1 <= ir <= U 
         1 <= jr <= ir - 1 ]

decompr =  [ L*Pr <= ir < L*Pr + L ]
decompw =  [ L*Pw <= iw < L*Pw + L ]

lwt = [ iw = jr
        jw = ir ]

// Computation decomposition
#loop = { iter, decompr }
#loop = loop.order(U Pr ir jr)
#loop = loop.rename(U P i j)
loop.code(2)

// Communication 1
#comm1 = { iter, decompr, decompw, lwt 
           [ Pr > Pw ] }
#comm1 = comm1.order(U Pr ir jr Pw iw jw)
#comm1r = comm1.rename(U P i j Pw iw jw)
comm1r.code(2)
#comm1 = comm1.order(U Pw iw jw Pr ir jr)
#comm1w = comm1.rename(U P i j Pr ir jr)
comm1w.code(2)

// Communication 2
#comm2 = { iter, decompr, decompw, lwt
          [ Pr < Pw ] }
#comm2 = comm.order(U Pr ir jr Pw iw jw)
#comm2r = comm2.rename(U P i j Pw iw jw)
comm2r.code(2)
#comm2 = comm2.order(U Pw iw jw Pr ir jr)
#comm2w = comm2.rename(U P i j Pr ir jr)
comm2w.code(2)

end

The printout of the example session. Note that systems `comm2w' and `comm2r' are inconsistent since there is no communication when Pr < Pw.

csh> lic -c
Rapid Prototyping System for Code Generation
> < example6
iter = [ 1 <= ir <= U
         1 <= jr <= ir - 1 ]
-1+ir-jr >= 0
-1+jr >= 0
-ir+U >= 0
-1+ir >= 0

decompr =  [ L*Pr <= ir < L*Pr + L ]
-1+L+L*Pr-ir >= 0
-L*Pr+ir >= 0
decompw =  [ L*Pw <= iw < L*Pw + L ]
-1+L+L*Pw-iw >= 0
-L*Pw+iw >= 0

lwt = [ iw = jr
        jw = ir ]
jw-ir >= 0
-jw+ir >= 0
iw-jr >= 0
-iw+jr >= 0

// Computation decomposition
#loop = { iter, decompr }
#loop = loop.order(U Pr ir jr)
#loop = loop.rename(U P i j)
loop.code(2)
for(P = 2/L; P <= U/L; P++)
   for(i = max(2, L*P); i <= min(-1+L+L*P, U); i++)
      for(j = 1; j <= -1+i; j++)

// Communication 1
#comm1 = { iter, decompr, decompw, lwt
           [ Pr > Pw ] }
#comm1 = comm1.order(U Pr ir jr Pw iw jw)
#comm1r = comm1.rename(U P i j Pw iw jw)
comm1r.code(2)

for(P = (1+L)/L; P <= U/L; P++)
   for(i = L*P; i <= min(-1+L+L*P, U); i++)
      for(j = 1; j <= -1+L*P; j++)
         for(Pw = j/L; Pw <= j/L; Pw++) {
            iw = j;
            jw = i;
         }

#comm1 = comm1.order(U Pw iw jw Pr ir jr)
#comm1w = comm1.rename(U P i j Pr ir jr)
comm1w.code(2)

for(P = 1/L; P <= (-L+U)/L; P++)
   for(i = max(1, L*P); i <= -1+L+L*P; i++)
      for(j = L+L*P; j <= U; j++)
         for(Pr = max(j/L, (L+i)/L); Pr <= j/L; Pr++) {
            ir = j;
            jr = i;
         }

// Communication 2
#comm2 = { iter, decompr, decompw, lwt
          [ Pr < Pw ] }
#comm2 = comm.order(U Pr ir jr Pw iw jw)
#comm2r = comm2.rename(U P i j Pw iw jw)
comm2r.code(2)
Inconsistent inequalities
cannot find
#comm2 = comm2.order(U Pw iw jw Pr ir jr)
#comm2w = comm2.rename(U P i j Pr ir jr)
comm2w.code(2)
Inconsistent inequalities
cannot find

end
> quit
done(0)

csh>

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