作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (16): 57-59. doi: 10.3969/j.issn.1000-3428.2011.16.019

• 软件技术与数据库 • 上一篇    下一篇

多核计算机上的快速傅里叶变换并行算法

王刚强,钟 诚,柯 琦   

  1. (广西大学计算机与电子信息学院,南宁 530004)
  • 收稿日期:2011-01-07 出版日期:2011-08-20 发布日期:2011-08-20
  • 作者简介:王刚强(1983-),男,硕士研究生,主研方向:高性能计算,FFT并行算法;钟 诚,教授、博士、博士生导师;柯 琦,硕士研究生
  • 基金资助:
    广西高校优秀人才资助计划基金资助项目(RC2007004);广西高校人才小高地建设创新团队计划基金资助项目(桂教人[2007]71号);广西研究生教育创新计划基金资助项目

Fast Fourier Transform Parallel Algorithm on Multi-core Computer

WANG Gang-qiang, ZHONG Cheng, KE Qi   

  1. (School of Computer and Electronics Information, Guangxi University, Nanning 530004, China)
  • Received:2011-01-07 Online:2011-08-20 Published:2011-08-20

摘要: 针对现有多核结构上快速傅里叶变换(FFT)并行算法没有利用多级缓存和线程级并行等多核特性问题,通过运用多核多级存储特性合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,给出一个N点、一维、有序和基数为2的多核多线程并行计算FFT非递归算法。理论分析和实验结果表明,该算法实用、高效,能获得较好的加速比和可扩展性。

关键词: 快速傅里叶变换, 多核计算机, 线程级并行, 多级缓存, 非递归

Abstract: Aiming at the problem of Fast Fourier Transform(FFT) parallel algorithm on current multi-core architecture not fully use of multi-level caches and thread-level parallelism, by distributing data into multi-level caches and combining computation of subsequence FFT with parallel computing FFT one by one pair, a thread-level parallel and non-recursive FFT algorithm for a N-point, one-dimension, ordered and 2-radix is presented on multi-core computer. Theoretical analysis and experimental results show that the presented algorithm is pragmatic and efficient, and it can obtain very good speed-up ratio and scalability.

Key words: Fast Fourier Transform(FFT), multi-core computer, thread-level parallelism, multi-level caches, non-recursion

中图分类号: