CRPC-TR94484-S

Title:    Combining Dependence and Data-Flow Analyses to Optimize Communication

Authors:  Ken Kennedy, Nenad Nedeljkovic

Date:     September, 1994


Of the authors listed above, please indicate which are:

  Minority authors:

  Female authors:    

  Student authors:   Nenad Nedeljkovic


Keywords (list up to 8):

  Dependence analysis, Data-flow analysis, Communication,
  Fortran D, High Performance Fortran, Data parallelism

Abstract:

  Reducing communication overhead is crucial for improving the performance 
  of programs on distributed-memory machines. Compilers for data-parallel
  languages must perform communication optimizations in order to minimize
  this overhead. In this paper, we show how to combine dependence analysis,
  traditionally used to optimize regular communication, and a data-flow 
  analysis method originally developed to improve placement of irregular 
  communication. Our approach allows us to perform more extensive 
  optimizations --- message vectorization, elimination of redundant messages, 
  and overlapping communication with computation. We also present preliminary 
  experimental results that demonstrate the benefits of the proposed method.


Publication History:

  Will appear in the Proceedings of the 9th International 
                     Parallel Processing Symposium, IPPS '95