并行歸并排序算法及其在PC集群中的實(shí)現(xiàn).pdf

1、現(xiàn)代許多領(lǐng)域中具有挑戰(zhàn)性的大規(guī)模計(jì)算課題需要高性能并行處理機(jī),而硬件技術(shù)的迅速發(fā)展已使建造并行處理機(jī)的新一代計(jì)算機(jī)的經(jīng)濟(jì)可行性顯著增加,但是阻礙并行處理機(jī)進(jìn)入主流技術(shù)的主要問題還是在軟件和應(yīng)用方面.但是并行算法設(shè)計(jì)有著特殊的困難.以前我們考慮問題是按時(shí)間的順序來考慮,而現(xiàn)在我們卻要把整個(gè)問題看作由多個(gè)可并行的子問題組成.大型計(jì)算中心,排序被認(rèn)為占用了大量的計(jì)算時(shí)間.隨著并行處理技術(shù)的發(fā)展,并行排序已經(jīng)成為并行算法中的一個(gè)重要的研究領(lǐng)域.

2、該文提出了并詳細(xì)描述了一種新的并行歸并排序算法,算法充分利用了各個(gè)處理器排序后序列長度相等的特點(diǎn),計(jì)算出歸并段對中的一個(gè)元素和最后一個(gè)元素的位置,然后從相應(yīng)的位置進(jìn)行歸并排序.該算法達(dá)到了較高的負(fù)載平衡性、可擴(kuò)展性和排序穩(wěn)定性,而且排序后,數(shù)據(jù)分布完全平衡.現(xiàn)在PC機(jī)的性能不斷的提高,價(jià)格下降,很好的性能價(jià)格比使很多單位普遍使用PC集群.因此,研究PC機(jī)組成的網(wǎng)絡(luò)并行計(jì)算平臺,并在其上進(jìn)行并行計(jì)算,可以大大提高現(xiàn)有設(shè)備解決實(shí)際問題的能力

3、且為并行算法的研究提供一個(gè)試驗(yàn)環(huán)境.Linux是UNIX在PC機(jī)上的實(shí)現(xiàn),它是一種開放源代碼的分時(shí)操作系統(tǒng).它已被廣泛用于并行計(jì)算平臺.MPI消息傳遞方式是被廣泛應(yīng)用并行機(jī)的一種模式,特別適用于那些分布存儲的并行機(jī).十多年來,這種模式在重要的計(jì)算應(yīng)用中已取得了實(shí)質(zhì)進(jìn)步.MPI標(biāo)準(zhǔn)已定義了與C語言、C++和Fortran的綁定.MPICH是MPI的一種穩(wěn)定的實(shí)現(xiàn),它可以建立與C語言、C++、Fortran 77、Fortran 90、Ja