[發(fā)明專利]一種面向GPU的雙調(diào)歸并排序方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210187386.2
• 申請(qǐng)日: 2012-06-07
• 公開（公告）號(hào): CN102750131A
• 公開（公告）日: 2012-10-24
• 發(fā)明（設(shè)計(jì)）人: 遲學(xué)斌;王玨;闞圣哲;聶寧明;郎顯宇
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06F9/50
• 代理公司: 北京億騰知識(shí)產(chǎn)權(quán)代理事務(wù)所 11309
• 代理人: 陳霽

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

（1）將共享內(nèi)存中的待排序列數(shù)據(jù)拷貝到GPU設(shè)備局部?jī)?nèi)存中；

（2）判斷是否需要進(jìn)行向量?jī)?nèi)排序，若需要?jiǎng)t由一個(gè)線程操作向量模擬L個(gè)比較器，多個(gè)線程并行執(zhí)行歸并排序；

（3）將排序結(jié)果由GPU設(shè)備局部?jī)?nèi)存拷貝到共享內(nèi)存中。

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

步驟（2）中多個(gè)線程并行執(zhí)行歸并排序時(shí)，對(duì)于同一個(gè)工作組內(nèi)的線程同步使用同步函數(shù)來完成，對(duì)于不同工作組內(nèi)的線程間同步通過CPU完成。

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

當(dāng)一個(gè)工作組內(nèi)的比較器本次和下次操作數(shù)都存在于該工作組的局部?jī)?nèi)存時(shí)，使用同步函數(shù)同步工作組內(nèi)線程；當(dāng)一個(gè)工作組內(nèi)的比較器本次和下次操作數(shù)存放在不同的工作組局部?jī)?nèi)存時(shí)，由CPU參與線程的同步。

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

由一個(gè)線程來模擬L×M個(gè)比較器，操作2×M個(gè)向量進(jìn)行比較交換操作，每個(gè)線程內(nèi)向量運(yùn)算指令順序執(zhí)行。

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

在排序過程中，改變比較器操作數(shù)的寫回地址，以使局部?jī)?nèi)存讀操作的地址連續(xù)，同時(shí)為防止線程間數(shù)據(jù)讀寫沖突，設(shè)置每個(gè)線程將需要操作的數(shù)據(jù)讀入寄存器再進(jìn)行比較交換操作。

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

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

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

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

8.一種面向GPU的雙調(diào)歸并排序系統(tǒng)，其特征在于包括如下模塊：

用于將共享內(nèi)存中的待排序列數(shù)據(jù)拷貝到GPU設(shè)備局部?jī)?nèi)存中的模塊；

用于判斷是否需要進(jìn)行向量?jī)?nèi)排序，若需要?jiǎng)t由一個(gè)線程操作向量模擬L個(gè)比較器，多個(gè)線程并行執(zhí)行歸并排序的模塊；

用于將排序結(jié)果由GPU設(shè)備局部?jī)?nèi)存拷貝到共享內(nèi)存中的模塊。

9.如權(quán)利要求8所述的系統(tǒng)，其特征在于：

多個(gè)線程并行執(zhí)行歸并排序時(shí)，對(duì)于同一個(gè)工作組內(nèi)的線程同步使用同步函數(shù)來完成，對(duì)于不同工作組內(nèi)的線程間同步通過CPU完成。

10.如權(quán)利要求9所述的系統(tǒng)，其特征在于：

當(dāng)一個(gè)工作組內(nèi)的比較器本次和下次操作數(shù)都存在于該工作組的局部?jī)?nèi)存時(shí)，使用同步函數(shù)同步工作組內(nèi)線程；當(dāng)一個(gè)工作組內(nèi)的比較器本次和下次操作數(shù)存放在不同的工作組局部?jī)?nèi)存時(shí)，由CPU參與線程的同步。

11.如權(quán)利要求8-10之一所述的系統(tǒng)，其特征在于：

由一個(gè)線程來模擬L×M個(gè)比較器，操作2×M個(gè)向量進(jìn)行比較交換操作，每個(gè)線程內(nèi)向量運(yùn)算指令順序執(zhí)行。

12.如權(quán)利要求11所述的系統(tǒng)，其特征在于：

在排序過程中，改變比較器操作數(shù)的寫回地址，以使局部?jī)?nèi)存讀操作的地址連續(xù)，同時(shí)為防止線程間數(shù)據(jù)讀寫沖突，設(shè)置每個(gè)線程將需要操作的數(shù)據(jù)讀入寄存器再進(jìn)行比較交換操作。

13.如權(quán)利要求12所述的系統(tǒng)，其特征在于：

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

14.如權(quán)利要求12所述的系統(tǒng)，其特征在于：

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