《基於GPU的並行排序算法設計與最佳化》是依託清華大學，由都志輝擔任項目負責人的面上項目。
基本介紹
- 中文名：基於GPU的並行排序算法設計與最佳化
- 依託單位：清華大學
- 項目負責人：都志輝
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
利用GPU來加速科學問題的求解已成為高性能計算的一個重要研究方向，而排序算法是一個非常基礎的算法，設計基於GPU的並行排序算法可以直接支持一大類科學計算套用。基於對GPU內部層次化記憶體模型和流處理單元的抽象與分析，設計實現層次化確定性採樣排序算法，該算法與同類型的並行排序算法相比，能夠更加有效的利用GPU的高並行性和層次化記憶體模型。同時，本研究深入對比GPU和CPU特點，設計並實現基於CPU-GPU協同工作的快速排序算法。不僅對這些算法進行理論分析，本研究還設計開發原型系統進行實驗驗證，將理論和實驗結果進行對比分析，進一步對本研究提出的最佳化方法、算法以及相應的程式實現進行改進和提高，並結合MapReduce並行計算框架對本研究成果進行實際套用。本研究提供的基礎性理論與方法一方面可充分挖掘GPU計算潛力，另一方面對廣泛的套用問題和領域在新型加速器增強型體構上提供高效支持。
結題摘要
利用GPU來加速科學問題的求解已成為高性能計算的一個重要研究方向，而排序算法是一個非常基礎的算法，設計基於GPU的並行排序算法可以直接支持一大類科學計算套用。在充分了解GPU硬體體系結構與已有的各種排序算法性能特點的基礎上，本研究提出並實現了一種集成最佳化的GPU排序方法，將桶排序、快速排序、歸併排序等在不同的階段有效集成起來，結合雙緩衝等最佳化手段，可以有效均衡負載並大幅提高算法的整體性能。此外，通過對比GPU和CPU特點，設計並實現基於CPU-GPU協同工作的排序算法；在已知數據集特點的情況下，設計實現了更為有效的定製排序算法。通過設計開發原型系統對各種算法進行了實驗驗證，測試結果表明本研究提出的方法可以高效處理不同規模、不同數據分布特點的數據集。我們還進一步將本研究得到的經驗與成果套用到一些大型實用程式的數據處理（性能提高50倍）與模擬分析（性能提高10倍）中，這些工作充分展示了本研究不僅在基礎性算法設計、最佳化與分析方面，而且在對這些基礎性成果的套用方面，都取得了顯著的成果。
