Communication-Efficient Implementation of Block Recursive Algorithms on Distributed-Memory Machines

Sandeep K. S. Gupta, Chua-Huang Huang, Rodney W. Johnson, P. SadayappanICPADS 1994 · OpenReview

Abstract

This paper presents a design methodology for developing efficient distributed-memory parallel programs for block-recursive algorithms such as the fast Fourier transform and bitonic sort. This design methodology is specifically suited for most modern supercomputers having a distributed-memory architecture with circuit-switched or wormhole routed mesh or hypercube interconnection network. A mathematical framework based on the tenser product and other matrix operations is used for representing algorithms. Communication-efficient implementations with effectively overlapped computation and communication are achieved by manipulating the mathematical representation using the tenser algebra. Performance results for FFT programs on the Intel iPSC/860 and Intel Paragon are presented.
BibTeX
@inproceedings{gupta1994communication,
  author = {Sandeep K. S. Gupta and Chua-Huang Huang and Rodney W. Johnson and P. Sadayappan},
  title = {{Communication-Efficient Implementation of Block Recursive Algorithms on Distributed-Memory Machines}},
  booktitle = {ICPADS},
  year = {1994},
  url = {https://openreview.net/forum?id=SPS4zgBBOp},
}

Loading related content...

Figure