本站小編為你精心準(zhǔn)備了并行排序算法的設(shè)計(jì)參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

《電腦與信息技術(shù)雜志》2014年第三期

1并行算法

1.1并行算法分類(lèi)并行算法的種類(lèi)非常多，分類(lèi)標(biāo)準(zhǔn)也均有所不同。按照基礎(chǔ)運(yùn)算對(duì)象進(jìn)行分類(lèi)，有數(shù)值和非數(shù)值兩周并行算法。按照并行運(yùn)算過(guò)程中，各進(jìn)程的執(zhí)行時(shí)間進(jìn)行分類(lèi)，有同步、異步和獨(dú)立三種不同的并行算法。按照進(jìn)程處理機(jī)中，它們各自承擔(dān)所要計(jì)算任務(wù)量進(jìn)行分類(lèi)，有大粒度、中粒度和小粒度三種并行算法。

1.2并行算法設(shè)計(jì)方法并行算法的設(shè)計(jì)需要參照系統(tǒng)類(lèi)型以及系統(tǒng)的特征，對(duì)某一問(wèn)題針對(duì)性在處理機(jī)上進(jìn)行并行解決。并行算法的設(shè)計(jì)一般有三種辦法：對(duì)已有的串行算法進(jìn)行檢查，對(duì)算法中的并行性進(jìn)行開(kāi)發(fā)，并加以?xún)?yōu)化；根據(jù)問(wèn)題本身的特征出發(fā)，設(shè)計(jì)一個(gè)完全不同的并行算法；在已有算法的基礎(chǔ)上，根據(jù)問(wèn)題的特征進(jìn)行修改，處理類(lèi)似的問(wèn)題；第一種設(shè)計(jì)方法中，如若該串行算法已經(jīng)有內(nèi)在相關(guān)順序性，就非常難做并行的優(yōu)化；第二種設(shè)計(jì)方法中，對(duì)現(xiàn)有算法進(jìn)行修改，則要熟知問(wèn)題的特殊性；第三種設(shè)計(jì)方法，憑空創(chuàng)新設(shè)計(jì)出一個(gè)算法，技巧性非常強(qiáng)，不但沒(méi)什么章法，而且技術(shù)水平達(dá)不到。針對(duì)并行算法的設(shè)計(jì)，目前最為普遍的設(shè)計(jì)方法有平衡樹(shù)技術(shù)、分治策略技術(shù)、流水線技術(shù)以及倍增技術(shù)等等。

1.3并行算法計(jì)算模型并行計(jì)算模型是指從所有并行機(jī)中，把共性存在的基本特征分離出來(lái)，最終形成一個(gè)抽象的并行計(jì)算處理機(jī)，且要在具體并行機(jī)至上。它與順序計(jì)算中的VonNeumann模型非常相似。根據(jù)普渡報(bào)告分析，并行計(jì)算模型，必須能夠保證并行計(jì)算處理機(jī)針對(duì)哪種計(jì)算，表現(xiàn)出超強(qiáng)的計(jì)算能力。并行計(jì)算的模型、算法設(shè)計(jì)以及并行機(jī)的相互關(guān)系，如圖1所示：并行計(jì)算模型在并行算法中，有著至關(guān)重要的作用。它作為一種常見(jiàn)物質(zhì)基礎(chǔ)提供給并行算法，進(jìn)行相關(guān)研究；它還可以拿出一個(gè)簡(jiǎn)單便利的框架結(jié)構(gòu)，用于并行算法的設(shè)計(jì)以及開(kāi)發(fā)分析；因其適用性較強(qiáng)，看適用在許多種類(lèi)的并行處理機(jī)上，使得新的并行算法充滿生命力。

2并行排序的基本思想

并行排序算法是參照快速排序算法的分治方法，首先在主進(jìn)程內(nèi)，把其宿主機(jī)上等待排序的某一數(shù)組分割為n塊，文件的大小決定n的值。然后再把n塊數(shù)據(jù)推送到對(duì)應(yīng)數(shù)量的從進(jìn)程中，從進(jìn)程對(duì)其已經(jīng)接受的數(shù)據(jù)在宿主機(jī)上進(jìn)行串行排序，最后所有從進(jìn)程將已排好序的數(shù)據(jù)回傳給主進(jìn)程，同時(shí)數(shù)據(jù)要放回到原數(shù)值的位置上，完成了并行排序。按照此思想進(jìn)行排序，缺點(diǎn)是不能確定算法的性能?？梢越梃b負(fù)載均衡的思想，對(duì)該算法做出一些改進(jìn)。從進(jìn)程接受到數(shù)據(jù)后，不再對(duì)數(shù)據(jù)進(jìn)行劃分，只需要將其分為相同大小的n塊，并將n塊推送到對(duì)應(yīng)的n個(gè)從進(jìn)程中，由從進(jìn)程來(lái)對(duì)分到的數(shù)據(jù)進(jìn)行排序操作，排序完成后將已排序的數(shù)據(jù)傳回給主進(jìn)程。最后主進(jìn)程只需要對(duì)接收到的n塊排序數(shù)據(jù)進(jìn)行歸并排序，至此就完成了數(shù)據(jù)的排序工作。

3算法設(shè)計(jì)

3.1算法基本思想本文并行排序的算法思想是，首先形成部分有序的數(shù)據(jù)庫(kù)，然后依次讀入將數(shù)據(jù)順序分成的數(shù)據(jù)塊，快的大小不能超出內(nèi)存的大小。最后再對(duì)每一個(gè)小塊進(jìn)行排序，排序的結(jié)果保存到臨時(shí)的文件中。

3.2算法設(shè)計(jì)假設(shè)需要排序的數(shù)據(jù)總量為N，分為n個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊的數(shù)據(jù)量為A，即N=nA，每一塊數(shù)據(jù)塊進(jìn)行排序的耗費(fèi)的時(shí)間為t(A)。設(shè)立三個(gè)A的函數(shù)，readblock()讀入數(shù)據(jù)塊、sortblock()數(shù)據(jù)塊的排序、writeblock()保存已排序的數(shù)據(jù)塊，分三個(gè)步驟完成數(shù)據(jù)排序。排序耗費(fèi)的總時(shí)間t(A)由三個(gè)函數(shù)執(zhí)行總時(shí)間的決定，分別記作tr(A)、ts(A)、tw(A)。完成所有數(shù)據(jù)排序的時(shí)間為：如果只需要某一個(gè)進(jìn)程對(duì)數(shù)據(jù)處理的話，即串行執(zhí)行上述三個(gè)步驟，如圖2所示：但是因?yàn)閞eadblock()、sortblock()、writeblock()三者在排序的時(shí)候所占用的系統(tǒng)資源均不相同。若如想要數(shù)據(jù)讀入readblock()和數(shù)據(jù)保存writeblock()二者同時(shí)進(jìn)行的話，就需要把排序前數(shù)據(jù)和已排序的數(shù)據(jù)分布安防在兩個(gè)不同的硬盤(pán)上，而且還不會(huì)爭(zhēng)奪I/0資源。另外，因?yàn)檫@兩個(gè)模塊占用的CPU資源特別少，數(shù)據(jù)排序sortblock()也可以并行運(yùn)行，互不影響。所以說(shuō)我們通過(guò)使用單機(jī)進(jìn)行數(shù)據(jù)的排序，提高了排序算法的效率。合理的并行算法運(yùn)行時(shí)，必須根據(jù)數(shù)據(jù)塊的特性制定。本文上述三個(gè)block相互排斥，在并行運(yùn)算時(shí)，必須遵循以下規(guī)則：第M個(gè)數(shù)據(jù)塊的readblock()、sortblock()、writeblock()結(jié)束之后，方能開(kāi)始第M+1個(gè)數(shù)據(jù)塊對(duì)應(yīng)的readblock()、sortblock()、writeblock()；第M個(gè)數(shù)據(jù)塊的readblock()結(jié)束之后方能開(kāi)始sortblock()；第M個(gè)數(shù)據(jù)塊的sortblock()結(jié)束之后，方能開(kāi)始write-block()?？傊?，要保證三個(gè)進(jìn)程并行運(yùn)行完成對(duì)數(shù)據(jù)的排序工作，如圖3所示：三個(gè)進(jìn)程并行運(yùn)行可以充分利用系統(tǒng)的CPU、I/0資源，當(dāng)開(kāi)始運(yùn)行后，任一時(shí)間都會(huì)有readblock()、sortblock()、writeblock()并行運(yùn)行。這樣保證了進(jìn)程運(yùn)行時(shí)不存在等待的情況，同時(shí)正好是重要路由算法得的最優(yōu)執(zhí)行方案。在調(diào)用三個(gè)進(jìn)程之前，必須要先創(chuàng)建進(jìn)程，應(yīng)用進(jìn)程創(chuàng)建函數(shù)。程序執(zhí)行時(shí)順序完成數(shù)據(jù)的讀入、數(shù)據(jù)排序和數(shù)據(jù)的保存。多次測(cè)量執(zhí)行時(shí)間后，取平均值，以此為依據(jù)啟動(dòng)三個(gè)進(jìn)程。最終，多進(jìn)程的并行排序得以實(shí)現(xiàn)。

4結(jié)束語(yǔ)

當(dāng)前數(shù)據(jù)信息量高速增長(zhǎng)，信息化建設(shè)也逐步推進(jìn)，人們對(duì)數(shù)據(jù)處理速度提出了更高的要求，計(jì)算機(jī)速度要求也越來(lái)越高，也成為許多學(xué)者和專(zhuān)家積極研究探索的重要課題。開(kāi)發(fā)人員也不再需要考慮進(jìn)程的通信和控制等問(wèn)題，僅需要編寫(xiě)正確的編譯指導(dǎo)語(yǔ)句實(shí)現(xiàn)數(shù)據(jù)的并行計(jì)算。并行計(jì)算中的算法設(shè)計(jì)和負(fù)載均衡等核心問(wèn)題，需要今后進(jìn)行進(jìn)一步的研究，從而提高并行處理的效率。

作者：覃賢立單位：云南師范大學(xué)信息學(xué)院廣西民族師范學(xué)院