Communication efficient adaptive matrix transpose algorithm for FFT on symmetric multiprocessors

Computing fast Fourier transform (FFT) on parallel computers has the same communication requirement to transpose matrices one or more times. In this paper, we propose an efficient algorithm (the adaptive matrix-transpose algorithm) for transposing matrices, which is based on all-to-all communication. The adaptive matrix-transpose algorithm is efficient since it minimizes the overhead associated with transposing matrices by adaptively choosing the suitable radix based on data size, number of processors, start-up time, and the effective bandwidth. We study the effect of the adaptive matrix-transpose algorithm on the 6-step 1-D FFT using symmetric multiprocessors (SMP).