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

有效

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

1.一種面向GPU的雙調歸并排序方法，其特征在于包括如下步驟：

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

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

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

2.如權利要求1所述的方法，其特征在于：

步驟（2）中多個線程并行執行歸并排序時，對于同一個工作組內的線程同步使用同步函數來完成，對于不同工作組內的線程間同步通過CPU完成。

3.如權利要求2所述的方法，其特征在于：

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

4.如權利要求1-3之一所述的方法，其特征在于：

由一個線程來模擬L×M個比較器，操作2×M個向量進行比較交換操作，每個線程內向量運算指令順序執行。

5.如權利要求4所述的方法，其特征在于：

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

6.如權利要求5所述的方法，其特征在于：

在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的后半部與該后半部分向量中的后半部交換位置后，再執行寫回共享內存的操作。

7.如權利要求5所述的方法，其特征在于：

在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的前半部與該后半部分向量中的前半部交換位置后，再執行寫回共享內存的操作。

8.一種面向GPU的雙調歸并排序系統，其特征在于包括如下模塊：

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

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

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

9.如權利要求8所述的系統，其特征在于：

多個線程并行執行歸并排序時，對于同一個工作組內的線程同步使用同步函數來完成，對于不同工作組內的線程間同步通過CPU完成。

10.如權利要求9所述的系統，其特征在于：

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

11.如權利要求8-10之一所述的系統，其特征在于：

由一個線程來模擬L×M個比較器，操作2×M個向量進行比較交換操作，每個線程內向量運算指令順序執行。

12.如權利要求11所述的系統，其特征在于：

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

13.如權利要求12所述的系統，其特征在于：

在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的后半部與該后半部分向量中的后半部交換位置后，再執行寫回共享內存的操作。

14.如權利要求12所述的系統，其特征在于：

在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的前半部與該后半部分向量中的前半部交換位置后，再執行寫回共享內存的操作。