CRPC-TR1234567

Title:    Loop Distribution with Arbitrary Control Flow

Authors:  Ken Kennedy, Kathryn S. McKinley

Date:     August 1990


Of the authors listed above, please indicate which are:

  Minority authors:

  Female authors:    Kathryn S. McKinley

  Student authors:   Kathryn S. McKinley


Keywords (list up to 8):

  Parallelization, Vectorization, Transformation, Control dependence,
  Data dependence, Loop distribution

Abstract:

  Loop distribution is an integral part of transforming a sequential
  program into a parallel one.  It is used extensively in
  parallelization, vectorization, and memory management.  For loops with
  control flow, previous methods for loop distribution have significant
  drawbacks.  We present a new algorithm for loop distribution in the
  presence of control flow modeled by a control dependence graph.  This
  algorithm is shown optimal in that it generates the minimum number of
  new arrays and tests possible.  We also present a code generation
  algorithm that produces code for the resulting program without
  replicating statements or conditions.  Although these algorithms are
  being developed for use in an interactive parallel programming
  environment for Fortran, they are very general and can be used in
  automatic parallelization and vectorization systems.


Publication History:

  Submitted to:

  Published in:  Proceedings of SUPERCOMPUTING '90