CRPC-TR94485-S

Title:    A Linear-Time Algorithm for Computing the Memory
          Access Sequence in Data-Parallel Programs

Authors:  Ken Kennedy, Nenad Nedeljkovic, Ajay Sethi

Date:     October, 1994


Of the authors listed above, please indicate which are:

  Minority authors:

  Female authors:    

  Student authors:   Nenad Nedeljkovic, Ajay Sethi


Keywords (list up to 8):

  High Performance Fortran, Cyclic(k), Block-cyclic, Data parallelism

Abstract:

  Data-parallel languages, such as High Performance Fortran, are designed
  to facilitate writing of portable programs for distributed-memory machines.
  Novel features of these languages call for development of new techniques
  in both compilers and run-time support systems. We present an improved
  algorithm for finding the local memory access sequence in computations
  involving regular sections of arrays with cyclic(k) distribution. Using 
  the fact that regular section elements form an integer lattice we show how
  to find a lattice basis that allows for simple and fast enumeration of 
  memory accesses. The complexity of our algorithm is shown to be lower than
  that of the previous solution for the same problem. In addition, the 
  experimental results demonstrate the efficiency of our method in practice.

Publication History:

  Submitted to:	The 5th ACM SIGPLAN Symposium on Principles and Practice
                of Parallel Programming (PPoPP '95)