Re: tiling irregular array accesses

Michelle Strout <mstrout@CS.ColoState.EDU>
14 Oct 2005 17:22:28 -0400

          From comp.compilers

Related articles
tiling irregular array accesses (shrey) (2005-10-08)
Re: tiling irregular array accesses (Jeff Kenton) (2005-10-13)
Re: tiling irregular array accesses mstrout@CS.ColoState.EDU (Michelle Strout) (2005-10-14)
| List of all articles for this month |

From: Michelle Strout <mstrout@CS.ColoState.EDU>
Newsgroups: comp.compilers
Date: 14 Oct 2005 17:22:28 -0400
Organization: Compilers Central
References: 05-10-067
Keywords: storage, parallel
Posted-Date: 14 Oct 2005 17:22:28 EDT

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

The following papers are posted on my publications page

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

    Combining Performance Aspects of Irregular Gauss-Seidel via Sparse
          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 Mills Strout
    Assistant Professor

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

    (970) 491-7026

Post a followup to this message

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