Latency and bandwidth requirements of massively parallel programs: FFT as a case study

In this paper we compare three routing algorithms for massively parallel architectures, each offering an increasing degree of adaptivity: a deterministic algorithm, a minimal adaptive based on Duato's methodology and a non-minimal adaptive, the Chaos routing. Rather than using a synthetic benchmark, the comparison is done with a real application, the transpose FFT algorithm. The simulation results collected on bi-dimensional tori with up to 256 processing nodes show that both adaptive algorithms suffer from post-saturation problems that degrade the network throughput.