A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs
A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs
复制标题
DOI：
10.1016/j.cpc.2013.08.028
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
T. V. Duy;T. Ozaki
中科院分区：
文献类型：
--
作者：
T. V. Duy;T. Ozaki
快速傅立叶变换（FFT）无疑是一个基本的原始，已被应用于科学和工程的各个领域。在本文中，我们提出了一种分解方法的并行化的多维FFT与最小的通信量为所有范围内的进程数相比，以前提出的方法。这是通过两个显着的功能来实现的：自适应分解和转置顺序意识。在所提出的方法中，FFT数据被分解的基础上的一个逐行的基础上，映射的多维数据到一维数据，并将相应的坐标从多维转换为一维，使得一维数据可以被划分和分配均匀的过程使用块分布。因此，不同于以往的作品，有分解的维度预定义，我们的方法可以自适应分解的FFT数据的最低可能的维度取决于进程的数量。此外，这种逐行分解在数据转置方面提供了大量的替代方案，并且不同的转置顺序导致不同的通信量。通过分析所有可能的情况，我们确定了3-D，4-D和5-D FFT的最小通信量的最佳转置顺序。我们还开发了一个通用的并行软件包，最流行的三维FFT的基础上，我们的方法使用的2-D区域分解。数值结果表明，与其他并行软件包相比，我们的实现具有良好的性能和缩放特性。考虑到通信效率和可扩展性，我们的方法是有前途的高效并行包的FFT的发展。
The fast Fourier transform (FFT) is undoubtedly an essential primitive that has been applied in various fields of science and engineering. In this paper, we present a decomposition method for the parallelization of multi-dimensional FFTs with the smallest communication amounts for all ranges of the number of processes compared to previously proposed methods. This is achieved by two distinguishing features: adaptive decomposition and transpose order awareness. In the proposed method, the FFT data is decomposed based on a row-wise basis that maps the multi-dimensional data into one-dimensional data, and translates the corresponding coordinates from multi-dimensions into one dimension so that the one-dimensional data can be divided and allocated equally to the processes using a block distribution. As a result and different from previous works that have the dimensions of decomposition pre-defined, our method can adaptively decompose the FFT data on the lowest possible dimensions depending on the number of processes. In addition, this row-wise decomposition provides plenty of alternatives in data transpose, and different transpose order results in different amounts of communication. We identify the best transpose orders with the smallest communication amounts for the 3-D, 4-D, and 5-D FFTs by analyzing all possible cases. We also develop a general parallel software package for the most popular 3-D FFT based on our method using the 2-D domain decomposition. Numerical results show good performance and scaling properties of our implementation in comparison with other parallel packages. Given both communication efficiency and scalability, our method is promising in the development of highly efficient parallel packages for the FFT.