A decomposition method with minimal communication volume for parallelization of multi-dimensional FFTs
Truong Vinh Truong Duy, Taisuke Ozaki · 2013
We present a decomposition method for the parallelization of multi-dimensional FFTs with two distinguishing features: adaptive decomposition and transpose order awareness for achieving minimal communication volume. Based on a row-wise decomposition that translates the multi-dimensional data into one-dimensional data for equally allocating to the processes, our method can adaptively decompose the data in the lowest possible dimensions to reduce communication volume in the first place, differently from previous works that have pre-defined dimensions of decomposition. Also, this decomposition offers plenty of orders in data transpose, and different transpose orders result in different volumes of communication. By analyzing all the possible cases, we find out the best transpose orders with minimal communication volumes for 3-D, 4-D, and 5-D FFTs.