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

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

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

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