In this paper we compare the optimum performance of the FFT on torus and hypercube multicomputers. The optimal number of floating point operations is architecturally invariant so the relative performance is determined by communication time. We compare the performance of known multiport communication algorithms that utilize the full bandwidth of the interconnection network on every cycle. Furthermore, data is routed unblocked over paths with minimum length. On the hypercube we observe the somewhat surprising result that, in the limit, communication can ultimately be negligible compared to computation.
Asymptotic efficiencies remain bounded away from zero even for fine-grain distributions.
While the opposite is true of the torus, it is nevertheless possible to obtain comparable performance over a broad range of processors and problem sizes. As computers are built with increasing numbers of processors, torus performance can still be made comparable to the hypercube by gradually increasing the dimension of the interconnect. Download a PostScript version of the original manuscript , 384K Download the PDF version , 189K Back to Publications Swarztrauber's Home Page Mail comments to Paul Swarztrauber .