基于多核多線程的FFT算法和堆排序算法的并行優(yōu)化和實(shí)現(xiàn).pdf

1、傳統(tǒng)串行算法不能充分利用多個(gè)處理器，而多核多線程技術(shù)可以使程序的多線程實(shí)現(xiàn)同時(shí)運(yùn)行，充分利用多個(gè)處理器內(nèi)核。快速傅里葉變換(FFT)和堆排序算法都是常見(jiàn)的算法，它們?cè)谛盘?hào)傳輸和科學(xué)計(jì)算等方面都有著廣泛的應(yīng)用。本文基于多核平臺(tái)的多線程技術(shù)對(duì)FFT算法進(jìn)行了兩種并行化處理：一是根據(jù)FFT算法的特性，將數(shù)據(jù)集按序列順序分為奇偶兩部分，每部分創(chuàng)建一個(gè)線程，做并行運(yùn)行。實(shí)驗(yàn)證明當(dāng)數(shù)據(jù)量達(dá)到4194304時(shí)效率可提高39％左右，且隨著數(shù)據(jù)量的增加，

2、效率提升接近40％，且趨于平穩(wěn)。二是為了充分說(shuō)明并行化過(guò)程中需要注意的問(wèn)題，又將其蝶形變換本身的內(nèi)部循環(huán)分為兩部分，每部分創(chuàng)建一個(gè)線程，做并行運(yùn)行。實(shí)驗(yàn)證明這種做法隨著數(shù)據(jù)量的增加，算法的運(yùn)算效率變得更差，說(shuō)明循環(huán)內(nèi)部不適合創(chuàng)建多線程。
　　 本文對(duì)堆排序和歸并排序進(jìn)行并行處理，分別在單核，雙核，三核處理器平臺(tái)下運(yùn)行單線程(串行)、雙線程、四線程并行排序算法，對(duì)它們的運(yùn)行結(jié)果進(jìn)行分析和研究。實(shí)驗(yàn)結(jié)果表明，在堆排序算法中，當(dāng)數(shù)據(jù)量