本站小編為你精心準備了并行排序算法的設計參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

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

1并行算法

1.1并行算法分類并行算法的種類非常多，分類標準也均有所不同。按照基礎運算對象進行分類，有數值和非數值兩周并行算法。按照并行運算過程中，各進程的執行時間進行分類，有同步、異步和獨立三種不同的并行算法。按照進程處理機中，它們各自承擔所要計算任務量進行分類，有大粒度、中粒度和小粒度三種并行算法。

1.2并行算法設計方法并行算法的設計需要參照系統類型以及系統的特征，對某一問題針對性在處理機上進行并行解決。并行算法的設計一般有三種辦法：對已有的串行算法進行檢查，對算法中的并行性進行開發，并加以優化；根據問題本身的特征出發，設計一個完全不同的并行算法；在已有算法的基礎上，根據問題的特征進行修改，處理類似的問題；第一種設計方法中，如若該串行算法已經有內在相關順序性，就非常難做并行的優化；第二種設計方法中，對現有算法進行修改，則要熟知問題的特殊性；第三種設計方法，憑空創新設計出一個算法，技巧性非常強，不但沒什么章法，而且技術水平達不到。針對并行算法的設計，目前最為普遍的設計方法有平衡樹技術、分治策略技術、流水線技術以及倍增技術等等。

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

2并行排序的基本思想

并行排序算法是參照快速排序算法的分治方法，首先在主進程內，把其宿主機上等待排序的某一數組分割為n塊，文件的大小決定n的值。然后再把n塊數據推送到對應數量的從進程中，從進程對其已經接受的數據在宿主機上進行串行排序，最后所有從進程將已排好序的數據回傳給主進程，同時數據要放回到原數值的位置上，完成了并行排序。按照此思想進行排序，缺點是不能確定算法的性能。可以借鑒負載均衡的思想，對該算法做出一些改進。從進程接受到數據后，不再對數據進行劃分，只需要將其分為相同大小的n塊，并將n塊推送到對應的n個從進程中，由從進程來對分到的數據進行排序操作，排序完成后將已排序的數據傳回給主進程。最后主進程只需要對接收到的n塊排序數據進行歸并排序，至此就完成了數據的排序工作。

3算法設計

3.1算法基本思想本文并行排序的算法思想是，首先形成部分有序的數據庫，然后依次讀入將數據順序分成的數據塊，快的大小不能超出內存的大小。最后再對每一個小塊進行排序，排序的結果保存到臨時的文件中。

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

4結束語

當前數據信息量高速增長，信息化建設也逐步推進，人們對數據處理速度提出了更高的要求，計算機速度要求也越來越高，也成為許多學者和專家積極研究探索的重要課題。開發人員也不再需要考慮進程的通信和控制等問題，僅需要編寫正確的編譯指導語句實現數據的并行計算。并行計算中的算法設計和負載均衡等核心問題，需要今后進行進一步的研究，從而提高并行處理的效率。

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