Abhijit Sahay

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-722
January 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-722.pdf

This paper presents a novel computation schedule for FFT-type computations on a bandwidth-limited parallel computer. Using P processors, we are able to process an n-input FFT graph in the optimal time of n log n / P by carefully interleaving interprocessor communication steps with local computation. Our algorithm is suitable for both shared-memory and distributed memory machines and is analyzed in a simplification of the LogP model suitable for studying bandwidth-limited parallel machines. Our parallel FFT algorithm incorporates several techniques that have long been used by parallel programmers to reduce communication costs and our analysis provides theoretical justification for the success of these techniques in the context of highly structured computations like FFTs. At another level, our algorithm can be viewed as an optimal simulation of large butterfly networks on arbitrary machines (as modeled under LogP). Thus, we argue that computations thought to be inherently suited to butterfly networks can be executed with no loss in efficiency on arbitrary bandwidth-limited networks, given sufficient slack.

BibTeX citation:

@techreport{Sahay:CSD-92-722,
    Author = {Sahay, Abhijit},
    Title = {Hiding Communication Costs in Bandwidth-Limited Parallel FFT Computation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6033.html},
    Number = {UCB/CSD-92-722},
    Abstract = {This paper presents a novel computation schedule for FFT-type computations on a bandwidth-limited parallel computer. Using <i>P</i> processors, we are able to process an <i>n</i>-input FFT graph in the optimal time of <i>n</i> log <i>n</i> / <i>P</i> by carefully interleaving interprocessor communication steps with local computation. Our algorithm is suitable for both shared-memory and distributed memory machines and is analyzed in a simplification of the LogP model suitable for studying bandwidth-limited parallel machines. Our parallel FFT algorithm incorporates several techniques that have long been used by parallel programmers to reduce communication costs and our analysis provides theoretical justification for the success of these techniques in the context of highly structured computations like FFTs. At another level, our algorithm can be viewed as an optimal simulation of large butterfly networks on arbitrary machines (as modeled under LogP). Thus, we argue that computations thought to be inherently suited to butterfly networks can be executed with no loss in efficiency on arbitrary bandwidth-limited networks, given sufficient slack.}
}

EndNote citation:

%0 Report
%A Sahay, Abhijit
%T Hiding Communication Costs in Bandwidth-Limited Parallel FFT Computation
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-92-722
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6033.html
%F Sahay:CSD-92-722