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

Fast Fourier Transform Parallel Algorithm on Multi-core Computer

作　　者：王刚强[1] 钟诚[1] 柯琦[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机工程》2011年第16期57-59,共3页Computer Engineering

基　　金：广西高校优秀人才资助计划基金资助项目(RC2007004);广西高校人才小高地建设创新团队计划基金资助项目(桂教人[2007]71号);广西研究生教育创新计划基金资助项目

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

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

分 类 号：O246[理学—计算数学] TP312[理学—数学]