基于多核多线程的FFT算法和堆排序算法的并行优化和实现

摘要

传统串行算法不能充分利用多个处理器，而多核多线程技术可以使程序的多线程实现同时运行，充分利用多个处理器内核。快速傅里叶变换(FFT)和堆排序算法都是常见的算法，它们在信号传输和科学计算等方面都有着广泛的应用。本文基于多核平台的多线程技术对FFT算法进行了两种并行化处理：一是根据FFT算法的特性，将数据集按序列顺序分为奇偶两部分，每部分创建一个线程，做并行运行。实验证明当数据量达到4194304时效率可提高39％左右，且随着数据量的增加，效率提升接近40％，且趋于平稳。二是为了充分说明并行化过程中需要注意的问题，又将其蝶形变换本身的内部循环分为两部分，每部分创建一个线程，做并行运行。实验证明这种做法随着数据量的增加，算法的运算效率变得更差，说明循环内部不适合创建多线程。
　　 本文对堆排序和归并排序进行并行处理，分别在单核，双核，三核处理器平台下运行单线程(串行)、双线程、四线程并行排序算法，对它们的运行结果进行分析和研究。实验结果表明，在堆排序算法中，当数据量达到25万时堆排序较串行堆排序在效率能提高42％左右，且随着数据量的增加效率的提高率接近50％，且趋于平稳；在归并排序算法中，线程内部需要创建临时的堆栈，这使得并行后的排序算法运行效率大幅度减低，说明程序并行优化时，应该避免在多线程内部临时创建堆栈。