[發(fā)明專利]數(shù)據(jù)并行計算設(shè)備的排序

有效

• 申請?zhí)枺?/td>: 201780070349.4
• 申請日: 2017-11-14
• 公開（公告）號: CN109964203B
• 公開（公告）日: 2023-10-24
• 發(fā)明（設(shè)計）人: A.S.麥金農(nóng)
• 申請（專利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類號: G06F7/24
• 分類號: G06F7/24;G06F7/36
• 代理公司: 北京市柳沈律師事務(wù)所 11105
• 代理人: 金玉潔

1.一種用于在數(shù)據(jù)并行計算設(shè)備上并行排序數(shù)據(jù)的方法，包括：

由一組并行處理器將數(shù)據(jù)元素加載到寄存器中，其中每個寄存器與并行處理器的組中的至少一個并行處理器相關(guān)聯(lián)；

對于并行處理器中的每一個，以降序?qū)虞d到其相關(guān)聯(lián)的寄存器中的數(shù)據(jù)元素進(jìn)行并行排序；

對于并行處理器中的每一個，將排序的數(shù)據(jù)元素與所述組中其它處理器的排序的數(shù)據(jù)元素合并；以及

由所述并行處理器轉(zhuǎn)置和存儲合并和排序的數(shù)據(jù)元素。

2.根據(jù)權(quán)利要求1所述的方法，其中將所述數(shù)據(jù)元素加載到寄存器中包括，將所述數(shù)據(jù)元素同時加載到兩個或多個并行處理器的相關(guān)聯(lián)的寄存器中。

3.根據(jù)權(quán)利要求1所述的方法，其中將所述數(shù)據(jù)元素加載到每個處理器的相應(yīng)寄存器中包括，以轉(zhuǎn)置的順序加載所述數(shù)據(jù)元素。

4.根據(jù)權(quán)利要求1所述的方法，其中對所述數(shù)據(jù)元素進(jìn)行排序包括，對與相應(yīng)并行處理器相關(guān)聯(lián)的寄存器中的所有數(shù)據(jù)元素執(zhí)行比較和交換操作。

5.根據(jù)權(quán)利要求1所述的方法，其中將所述排序的數(shù)據(jù)元素與所述組中其它處理器的排序的數(shù)據(jù)元素合并包括，將每個并行處理器與一組處理器中的另一并行處理器配對；以及

將每個并行處理器的排序的數(shù)據(jù)元素與其相應(yīng)配對處理器的排序的數(shù)據(jù)元素合并。

6.根據(jù)權(quán)利要求5所述的方法，其中合并排序的數(shù)據(jù)元素還包括，將每對處理器的合并的數(shù)據(jù)元素與其它處理器對合并。

7.根據(jù)權(quán)利要求1所述的方法，其中并行處理器的所述組包括兩個并行處理器的組。

8.根據(jù)權(quán)利要求7所述的方法，其中將排序的數(shù)據(jù)元素與其它處理器的排序的數(shù)據(jù)元素合并包括，將每個并行處理器與兩組處理器中的另一并行處理器配對；以及

將每個并行處理器的排序的數(shù)據(jù)元素與兩個處理器的組中每一組處理器內(nèi)其相應(yīng)配對處理器的排序的數(shù)據(jù)元素合并。

9.根據(jù)權(quán)利要求8所述的方法，還包括合并兩個處理器的組的排序的數(shù)據(jù)元素。

10.一種用于并行排序數(shù)據(jù)的系統(tǒng)，包括：

一個或多個計算設(shè)備；和

存儲指令的存儲器，所述指令可由一個或多個計算設(shè)備執(zhí)行；

其中指令包括：

將數(shù)據(jù)元素加載到寄存器中，其中每個寄存器與并行處理器的組中的至少一個并行處理器相關(guān)聯(lián)；

對于并行處理器中的每一個，以降序?qū)虞d到其相關(guān)聯(lián)的寄存器中的數(shù)據(jù)元素進(jìn)行并行排序；

對于并行處理器中的每一個，將排序的數(shù)據(jù)元素與所述組中其它處理器的排序的數(shù)據(jù)元素合并；以及

由所述并行處理器轉(zhuǎn)置和存儲合并和排序的數(shù)據(jù)元素。

11.根據(jù)權(quán)利要求10所述的系統(tǒng)，其中將所述數(shù)據(jù)元素加載到寄存器中包括，將所述數(shù)據(jù)元素同時加載到兩個或多個并行處理器的相關(guān)聯(lián)的寄存器中。

12.根據(jù)權(quán)利要求10所述的系統(tǒng)，其中將所述數(shù)據(jù)元素加載到每個處理器的相應(yīng)寄存器中包括，以轉(zhuǎn)置的順序加載所述數(shù)據(jù)元素。

13.根據(jù)權(quán)利要求10所述的系統(tǒng)，其中對所述數(shù)據(jù)元素進(jìn)行排序包括，對與相應(yīng)并行處理器相關(guān)聯(lián)的寄存器中的所有數(shù)據(jù)元素執(zhí)行比較和交換操作。

14.根據(jù)權(quán)利要求10所述的系統(tǒng)，其中將所述排序的數(shù)據(jù)元素與所述組中其它處理器的排序的數(shù)據(jù)元素合并包括，將每個并行處理器與一組處理器中的另一并行處理器配對；以及

將每個并行處理器的排序的數(shù)據(jù)元素與其相應(yīng)配對處理器的排序的數(shù)據(jù)元素合并。

15.根據(jù)權(quán)利要求14所述的系統(tǒng)，其中合并排序的數(shù)據(jù)元素還包括，將每對處理器的合并的數(shù)據(jù)元素與其它處理器對合并。