[發明專利]一種面向GPU的雙調歸并排序方法

有效

• 申請號: 201210187386.2
• 申請日: 2012-06-07
• 公開（公告）號: CN102750131A
• 公開（公告）日: 2012-10-24
• 發明（設計）人: 遲學斌;王玨;闞圣哲;聶寧明;郎顯宇
• 申請（專利權）人: 中國科學院計算機網絡信息中心
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F9/50
• 代理公司: 北京億騰知識產權代理事務所 11309
• 代理人: 陳霽

本發明涉及一種數據排序方法，特別是一種面向GPU的基于OpenCL規范的雙調歸并排序方法。

背景技術

排序是計算機應用中最常見的操作之一，隨著并行處理技術的進一步發展，并行排序已經成為一個非常重要的研究領域。通常將并行排序分為兩類：一類是直接排序，能夠直接實現序列的排序；另一類是歸并排序，即可以將多個有序列快速合并為一個有序列。

在現有技術中，大部分的排序方法都需要開辟新的內存空間來存儲排序中間步驟的結果，例如常見的快速排序、基數排序和并行排序算法中的桶排序等。雙調歸并排序方法能夠直接在待排序列的存儲空間進行數據交換，有效節省了內存開銷。

目前AMD的OpenCL軟件開發套件（SDK）中包含了OpenCL版本的雙調排序方法在GPU上的實現。其雙調排序程序能夠充分利用GPU的流處理器，但是排序中的同步工作完全由CPU部分完成，工作組間的線程同步需要進行上下文的切換，從而影響計算效率。

因此，在節省存儲空間的基礎上，如何有效減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率等是本發明要解決的技術問題。

發明內容

本發明的目的是為了有效減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率。

為了實現上述目的，本發明提供了一種面向GPU的雙調歸并排序方法，包括如下步驟：

（1）將共享內存中的待排序列數據拷貝到GPU設備局部內存中；

（2）判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程并行執行歸并排序；

（3）將排序結果由GPU設備局部內存拷貝到共享內存中。

本發明還提供了一種面向GPU的雙調歸并排序系統，包括如下模塊：

用于將共享內存中的待排序列數據拷貝到GPU設備局部內存中的模塊；

用于判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程并行執行歸并排序的模塊；

用于將排序結果由GPU設備局部內存拷貝到共享內存中的模塊。

本發明的一種優選方案為：多個線程并行執行歸并排序時，對于同一個工作組內的線程同步使用同步函數來完成，對于不同工作組內的線程間同步通過CPU完成。

本發明的另一優選方案為：當一個工作組內的比較器本次和下次操作數都存在于該工作組的局部內存時，使用同步函數同步工作組內線程；當一個工作組內的比較器本次和下次操作數存放在不同的工作組局部內存時，由CPU參與線程的同步。

本發明的另一優選方案為：由一個線程來模擬L×M個比較器，操作2×M個向量進行比較交換操作，每個線程內向量運算指令順序執行。

本發明的另一優選方案為：在排序過程中，改變比較器操作數的寫回地址，以使局部內存讀操作的地址連續，同時為防止線程間數據讀寫沖突，設置每個線程將需要操作的數據讀入寄存器再進行比較交換操作。

本發明的另一優選方案為：在排序一組向量時，若該組向量的前半部分向量不連續，則將該前半部分向量中的后半部與該后半部分向量中的后半部交換位置后，再執行寫回共享內存的操作。

本發明的另一優選方案為：在排序一組向量時，若該組向量的前半部分向量不連續，后半部分向量連續，則將該前半部分向量中的前半部與該后半部分向量中的前半部交換位置后，再執行寫回共享內存的操作。

附圖說明

圖1為雙調歸并排序網絡的原理圖；

圖2為本發明的由CPU端執行的主機程序流程；

圖3為本發明的GPU雙調歸并排序方法執行過程。

具體實施方式

下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。

本發明主要通過以下幾種方式，對現有技術中GPU雙調歸并排序方法做出改進：

一、使用向量模擬多個比較器

在傳統的GPU雙調歸并排序方法中，一條線程作為一個比較器(compare?and?conditionally?interchange)，待排序列長度為比較器數的2倍。可以將比較器第一次分組，通過組號即可確定所排列的數據段是按升序還是降序排列，同時可以將比較器二次分組，通過組號能夠得到該比較器操作的序列元素的位置，圖1是擁有4個比較器的雙調歸并排序網絡的簡單原理示意。