在分布式存储器上实现多维快速傅里叶变换的方法和系统

摘要

本发明的目的在于一种用于实现一个多维数组的多维快速傅里叶变换(FFT)的方法、系统和程序存储设备，其中该多维数组包含多个元素，所述多个元素最初分布在一个多节点计算机系统中，所述多节点计算机系统包含多个经由一个网络进行通信的节点，其包含：经由该网络跨越该计算机系统的多个节点分布在第一维度上分布该数组的多个元素，以便于进行第一一维FFT；在第一维度上对分布在每个节点处的数组元素上执行第一一维FFT；通过经由网络跨越该计算机系统的其它节点的、以随机次序进行的“所有-到-所有”分布，在第二维度上在每个节点处重新分布经过一维FFT-转换的元素；以及在第二维度上对在每个节点处重新分布的数组元素执行第二一维FFT，其中随机次序便于网络的有效利用，由此实现多维FFT。该“所有-到-所有”重新分布或者数组元素在除了在分布存储器、并行巨型计算机上的多维FFT之外的应用中被进一步更高效地实现。