A portable 3D FFT package for distributed-memory parallel architectures
Hong Ding, Robert D. Ferraro, Donald B. Gennery · 1995
A parallel algorithm for 3D FFTs is implemented as a series of local 1D FFTs combined with data transposes. This allows the use of vendor supplied (often fully optimized) sequential 1D FFTs. The FFTs are carried out in-place by using an inplace data transpose across the processors. 1 Introduction Multi-dimensional FFTs are used frequently in engineering and scientific calculations, especially in image processing. Parallel implementations of FFT generally follow two approaches. One is the binary-exchange approach[1,2], where data exchanges take place in all pairs of processors with processor numbers differing by one bit. Another one is the transpose approach[2] for multi-dimensional FFTs, where a 3D FFT is carried out in 3 successive 1D local sequential FFTs with data transposes occurring in between. Inter-processor communication only take place in these data transpose. One advantage of this approach is that we can use the vendor-supplied 1D FFTs, which are often fully optimized. Furth...