Re: tiling irregular array accesses

shrey wrote:


> I am wondering if any tiling technique exists which can tile a
> perfectly nested loop with both regular and indexed array expressions.
> I understand perfectly how the tiling example works for simple matrix
> multiplication or how it is done (bucket tiling etc) for an statement
> with indexed array accesses on the LHS (Sum += A[x[i]]).But how do u
> go abt finding commmon tile sizes satisfying two statements one with
> regular access and the other with indexed array access.




I have done some work in this area and so has Craig Douglas
(http://www.mgnet.org/~douglas/).


The following papers are posted on my publications page
(http://www-unix.mcs.anl.gov/~mstrout/papers.html).




This paper describes full sparse tiling and how it compares to cache
blocking developed by Craig Douglas and others.


    Sparse Tiling for Stationary Iterative Methods
          Michelle Mills Strout, Larry Carter, Jeanne Ferrante, and
Barbara Kreaseck
          International Journal of High Performance Computing
Applications, 18(1):95-114, February 2004.




This paper describes using full sparse tiling for shared memory
parallelism.


    Combining Performance Aspects of Irregular Gauss-Seidel via Sparse
Tiling
          Michelle Mills Strout, Larry Carter, Jeanne Ferrante, Jonathan
Freeman, and Barbara Kreaseck
          The 15th Workshop on Languages and Compilers for Parallel
Computing (LCPC), College Park, Maryland, July 25-27, 2002.


This paper presents a compile-time framework for composing all run-
time reordering transformations including full sparse tiling.


    Compile-time Composition of Run-time Data and Iteration Reorderings
          Michelle Mills Strout, Larry Carter, and Jeanne Ferrante.
          In the proceedings of Programming Language Design and
Implementation (PLDI), June 2003.


There is plenty of work still to be done. I am starting to look at
ways to handle distributed parallelism with full sparse tiling and
ways to automate the generation of inspectors and executors based on
the framework.


-Michelle






=======================================
    Michelle Mills Strout
    Assistant Professor


    Colorado State University
    Computer Science Department
    1873 Campus Delivery
    Fort Collins, CO 80523-1873


    (970) 491-7026
    mstrout@cs.colostate.edu
=======================================

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