一种基于二叉胖树模型的并行FFT算法  

Parallel fast Fourier transform algorithm based on binary fat tree network

作　　者：魏文红[1] 高大利[2] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510640 [2]泉州师范学院计算机系,福建泉州362000

出　　处：《计算机应用》2007年第4期795-797,共3页journal of Computer Applications

摘　　要：二叉胖树网络结构是一种易于实现蝶式计算的网络拓扑结构,基于这一特点,首先构造了一种二叉胖树的逻辑模型,并提出了一种基于该模型的并行快速傅立叶变换算法。该算法使得进程间有良好的负载平衡,相对于串行算法来说,大大降低了时间复杂度。在集群系统和MPI环境下,给出了该算法的实现及实验数据分析。The binary fat tree is a network topology which is prone to accomplish butterfly computing. According to this feature, a logical model for binary fat tree was constructed at first, and then a parallel Fast Fourier Transform algorithm based on it was developed. In this algorithm, balance of load was achieved in the process, and time complexity was reduced compared with serial algorithm. At last the algorithm was implemented in cluster and MPI, and experimental data was analyzed.

关 键 词：二叉胖树 蝶式计算 快速傅立叶变换 并行计算 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]