C^3模型上FFT算法的设计与分析  

DESIGN AND ANALYSIS OF A PARALLEL FFT ALGORITHM ON THE C 3 MODEL

作　　者：许锦波[1] 顾乃杰[1] 陈国良[1] 

机构地区：[1]中国科学技术大学计算机系

出　　处：《计算机研究与发展》1997年第S1期66-70,共5页Journal of Computer Research and Development

基　　金：国家教委博士点基金

摘　　要：文中给出了Ｃ３模型［１，２］上并行ＦＦＴ算法的设计方案，算法的时间复杂度为Ｏｎｌｏｇｎｐ＋ｎ（ｈ＋ｐ／ｂ）ｐｌ，采用Ｋｕｍａｒ等提出的等效率（ｉｓｏ－ｅｆｉｃｉｅｎｃｙ）分析法［３］对算法进行可扩放性（ｓｃａｌａｂｉｌｉｔｙ）分析．通过Ｔｒａｎｓｐｕｔｅｒ系统上的几组实验对理论结果给予了验证．最后讨论了Ｃ３模型作为算法开发平台的优缺点．The design and analysis of a parallel FFT algorithm on the C 3 model are presented. The cost time of this algorithm is On log np+n(h+p/b)pl. After serveral sets of experiments on the transputer array, it is found that the speedup of this algorithm is good, but the scalability is dependent of the computer architecture. Finally, the reasons for the results are discussed and the drawbacks of the C 3 model are analyzed.

关 键 词：C^3模型 FFT算法 可扩放性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]