Lippert, T.FZJ* ; Schilling, K.Extern* ; Toschi, F. ; Trentmann, S. ; Tripiccione, R.

1998
Springer Berlin Heidelberg Berlin, Heidelberg
ISBN: 978-3-540-64443-9 (print), 978-3-540-69783-1 (electronic)

Abstract: We describe a novel practical parallel FFT scheme designed for SIMD systems and/or data parallel programming. A bit-exchange of elements between the processors is avoided by means of the ‘Transpose Algorithm’. Our transposition is based on the assignment of the data field onto a 1-dimensional ring of systolic cells which subsequently is mapped onto a ring of processors, realized as a subset of the system's connectivity. We have implemented and benchmarked a 2-dimensional parallel FFT code on the APE100/Quadrics parallel computer, where–due to a rigid next-neighbour connectivity and lack of local addressing–efficient FFT implementations could not be realized so far.