摘要: 针对现有多核结构上快速傅里叶变换(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
中图分类号:
王刚强, 钟诚, 柯琦. 多核计算机上的快速傅里叶变换并行算法[J]. 计算机工程, 2011, 37(16): 57-59.
WANG Gang-Jiang, ZHONG Cheng, KE Qi. Fast Fourier Transform Parallel Algorithm on Multi-core Computer[J]. Computer Engineering, 2011, 37(16): 57-59.