一种基于二叉胖树模型的并行FFT算法
魏文红 高大利
华南理工大学 泉州师范学院
Parallel fast Fourier transform algorithm based on binary fat tree network
摘要 二叉胖树网络结构是一种易于实现蝶式计算的网络拓扑结构，基于这一特点，首先构造了一种二叉胖树的逻辑模型，并提出了一种基于该模型的并行快速傅立叶变换算法。该算法使得进程间有良好的负载平衡，相对于串行算法来说，大大降低了时间复杂度。在集群系统和MPI环境下，给出了该算法的实现及实验数据分析。
关键词 ：
二叉胖树 ,
蝶式计算 ,
快速傅立叶变换 ,
并行计算
Abstract ：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.
Key words ：
binary fat tree
butterfly computing
Fast Fourier Transform (FFT)
parallel computing
收稿日期: 2006-10-12
通讯作者:
魏文红
E-mail: hquwwh@tom.com
[1]
王玉着, 刘修国, 张唯. 统一设备计算架构下的栅格河网提取并行算法
[2]
刘晓红, 曲志坚, 曹雁锋, 张先伟, 冯刚. 基于自适应机制的多宇宙并行量子衍生进化算法
[3]
余晓山 吴扬扬. 基于MapReduce的文本层次聚类并行化
[4]
林勤 薛云. 双聚类算法在电信高价值客户细分的应用
[5]
熊焕亮 曾国荪 吴沧海 匡桂娟 何火娇. 延迟可扩展性与并行执行时间的关系
[6]
贺章擎 黄威 戴葵 郑朝霞. 图像Laplace变换在异构多核工程科学计算加速协处理器上的实现
[7]
陈劲源 李建华 郭卫斌. 改进的硅各向异性腐蚀GPU并行模拟
[8]
孙远帅 陈垚 官新均 林琛. 基于Hadoop的大矩阵乘法处理方法
[9]
杨玉星 王世英. k元n立方网络的k圈排除问题的递归算法
[10]
魏浩洋 曾国荪 丁春玲. 层流扩散燃烧在GPU上的并行计算和数值分析
[11]
李斌 谭光华 高春鸣. 改进基本矩阵计算和优化的多摄像机并行标定算法
[12]
王喆 高三红 郑慧英 李立春. 月面地形重构系统中的并行Delaunay算法设计
[13]
张雪萍 龚康莉 赵广才. 基于MapReduce的K-Medoids并行算法
[14]
李太全 肖柏勋. 求解三对角线性方程组的迭代对角占优算法
[15]
贺毅辉 叶晨 刘志忠 彭伟. 基于CUDA的大规模群体行为实时仿真并行实现及优化
