基于多核多线程的FFT算法和堆排序算法的并行优化和实现-计算机应用技术专业论文.docxVIP

摘要摘要 摘要 摘要 传统串行算法不能充分利用多个处理器，而多核多线程技术可以使程序的 多线程实现同时运行，充分利用多个处理器内核。快速傅里叶变换(FFT)和堆 排序算法都是常见的算法，它们在信号传输和科学计算等方面都有着广泛的应 用。 本文基于多核平台的多线程技术对FFT算法进行了两种并行化处理：一是 根据FFT算法的特性，将数据集按序列顺序分为奇偶两部分，每部分创建一个 线程，做并行运行。实验证明当数据量达到4194304时效率可提高39％左右， 且随着数据量的增加，效率提升接近40％，且趋于平稳。二是为了充分说明并 行化过程中需要注意的问题，又将其蝶形变换本身的内部循环分为两部分，每 部分创建一个线程，做并行运行。实验证明这种做法随着数据量的增加，算法 的运算效率变得更差，说明循环内部不适合创建多线程。 本文对堆排序和归并排序进行并行处理，分别在单核，双核，三核处理器 平台下运行单线程(串行)、双线程、四线程并行排序算法，对它们的运行结果 进行分析和研究。实验结果表明，在堆排序算法中，当数据量达到25万时堆排 序较串行堆排序在效率能提高42％左右，且随着数据量的增加效率的提高率接 近50％，且趋于平稳；在归并排序算法中，线程内部需要创建临时的堆栈，这 使得并行后的排序算法运行效率大幅度减低，说明程序并行优化时，应该避免 在多线程内部临时创建堆栈。 关键词：多线程，多核，排序，并行优化，FFT AbstractAbstract Abstract Abstract The traditional serial algorithms cannot take full advantage of multiple processors；the development of multi-core processor technology provides a real important platform for parallel computing．Fast Fourier Transform(FFT)and Heap Sort algorithm FFT algorithm are very common,they are widely applied in signal transmission range and scientific calculation．The combination of Multi—core multi-threading technology and FFT algorithm is a hot spot for the application of FFT algorithm． Based on the multi-threaded technology in the multi-core platform，this paper， we make two parallel processing ways for FFT algorithm．Firstly，according tO the characteristics of FFT algorithm，parity of the data set is divided into two parts． Create threads for each section and do run in parallel．Experiments show that when the data reaches 4，1 94，304，39％efficiency call be improved，and晰th the increase in the amount of data,efficiency close to nearly 40％and leveled．Secondly，for fully illustrating the problems that need attention in optimization project,this paper divided the butterfly transformation its internal cycle into two parts，each part creates a thread and run in parallel way．Experiments show that this method is not feasible、衙吐1 the data set increasing．So we need avoided create threads inside the loop． This paper implem