大规模集群上多维FFT算法的实现与优化研究

发布时间：2020-02-27 15:39

【摘要】：快速傅里叶变换(fast Fourier transform,FFT)是用于计算离散傅里叶变换(discrete Fourier transform,DFT)或其逆运算的快速算法,在工程、科学和数学领域的应用非常广泛,例如信号分解、数字滤波、图像处理等。因此,在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现,并提出了相关的优化策略。在此基础上,对多种FFT算法在不同平台上进行了性能评估,并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明,相关研究有助于对现有的FFT算法进行进一步的优化,以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。
【图文】：

ALL时每个接收者可接收来自别的发送者的数目不同的数据。例如，第m个进程发送的第n块数据将被第n个进程接收并存放在其接收消息缓冲区recv_buffer的第m块上。一维分解较为简单，然而采用该策略进行实现的库在可扩展性方面存在很大的不足，它要求P=n0，n0=max{n0,n1,n2}。当P>n0时，一维分解将不能被使用。另外当P>n1或P>n2时，数据分解所使用的进程数P将受限于n1或n2。数据转置之后，多余的进程数将会空闲得不到利用。因此，，对数据的划分需要采用更多维来进行计算[4]。图1为一维分解示意图。4.2.2二维分解二维分解[3]相较于一维分解很好地解决了可扩展性不足这一严重的弊端，故在大规模集群上也应用得比较普遍。图2即为二维分解的效果图。该分Fig.1One-dimensiondecompositionstrategy图1一维分解策略866

鍪

本文编号：2583320