Hiding Communication Costs in Bandwidth-Limited Parallel FFT
Abhijit Sahay · 1992
We consider FFT computations on parallel machines in which communication speed is limited by network bandwidth rather than by message overhead. Such machines are modeled well by a special case of the LogP model of Culler et al. We show how commonly used parallel programming techniques such as intelligent data placement, careful co-ordination of computation and communication, and pipelining long streams of messages, can yield 100% efficiency (in speedup) even in the presence of substantial message traffic. At a different level, our parallel algorithm can be viewed as an efficient simulation of a butterfly network on the LogP model in the presence of reasonable slack.