Looking for Program Transformation Examples

Hello netters,


I am looking for example program kernels that can benefit from
the following compiler optimizations.


(1) Unimodular Loop Transformations


        Unimodular loop transformations use matrix calculations to guide
        some combination of loop interchange, skewing, and reversal to
        parallelize perfectly nested loops. A simple example
        is Successive-Over-Relaxation (SOR),


            do j = 2,N-1
                do i = 2,N-1
                    A(i,j) = F(...A(i-1,j),A(i,j-1),A(i+1,j),A(i,j+1)...)
                enddo
            enddo


        where loop skew and interchange can parallelize the inner loop:


            do i = 4,2*(N-1)
                doall j = max(2,i-N-1),min(N-1,i-2)
                    A(i-j,j) = F(...A(i-j-1,j),A(i-j,j-1),A(i-j+1,j),A(i-j,j+1)...)
                enddo
            enddo


        Another example comes from tridiagonal solves, where loop
        interchange can be used to move a parallel loop outwards.


            do j
                doall i
                    A(i,j) = F(...A(i,j-1)...)
                enddo
            enddo


        However, I can't seem to find much else. Are there common
        computations that can utilize unimodular loop transformations?




(2) Loop Distribution


        Loop distribution creates multiple loops from a single loop. It is
        pretty essential for vectorizing compilers. The most common use
        for loop distribution is to separate a sequential reduction from a
        parallel loop. For instance,


            do j
                A(j) = F(...)
                t = t + A(j)
            enddo


        can be distributed to yield the following loops:


            doall j
                A(j) = F(...)
            enddo
            do j
                t = t + A(j)
            enddo


        I'm having a difficult time discovering other cases where loop
        distribution can be used to increase parallelism.


I would appreciate pointers to computations that can benefit from
either of these techniques. I'll summarize responses, if I get any :-)


Thanks,


Chau-Wen Tseng
Grad Student
Rice University
--

Return to the comp.compilers page.
Search the comp.compilers archives again.