[發明專利]數據并行計算設備的排序

有效

• 申請號: 201780070349.4
• 申請日: 2017-11-14
• 公開（公告）號: CN109964203B
• 公開（公告）日: 2023-10-24
• 發明（設計）人: A.S.麥金農
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F7/24
• 分類號: G06F7/24;G06F7/36
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 金玉潔

本公開的各方面涉及響應于對信息的請求來確定相關內容。一個或多個計算設備(170)可以將數據元素加載到寄存器(385A?385B)中，其中每個寄存器與一組并行處理器(380A?380B)中的至少一個并行處理器相關聯。對于并行處理器中的每一個，加載到其相關聯的寄存器中的數據元素可以以降序并行排序。對于并行處理器中的每一個，排序的數據元素可以與該組中其它處理器的排序的數據元素合并。合并和排序的數據元素可以被轉置和存儲。

相關申請的交叉引用

本申請要求2016年11月14日提交的美國臨時專利申請第62/421，544號的申請日的權益，其公開內容通過引用結合于此。

背景技術

能夠快速有效地對數據進行排序對于計算設備的許多操作來說至關重要。例如，許多應用(諸如搜索、數據查詢處理、圖形、稀疏線性代數、機器學習等)要求基本上實時的數據排序。許多排序方法依賴于單線程CPU執行順序排序算法。這種排序方法非常耗時，并且要求大量的處理資源。

排序方法的最新改進包括由數據并行設備(data-parallel device)(諸如圖形處理單元(graphics processing unit，GPU))執行的半并行和并行算法。然而，這些半并行和并行算法存在許多不足，因為它們通常無法完全利用數據并行設備的計算能力并達到峰值吞吐量，直到要排序的值的數量變得非常大，從而填滿數據并行設備的帶寬。此外，這些半并行算法通常表現出顯著的分支差異，其中相鄰的處理元件不執行相同的指令，阻止數據并行設備變得完全達到計算約束。處理較小的數據元素集合同樣是低效的，因為數據并行設備可能在等待數據被加載或存儲時停頓。

發明內容

本公開內容內的實施例通常涉及在數據并行計算設備上并行排序數據。一個方面包括一種方法，該方法包括：由并行處理器的組將數據元素加載到寄存器中，其中每個寄存器與并行處理器的所述組中的至少一個并行處理器相關聯；對于并行處理器中的每一個，以降序對加載到其相關聯的寄存器中的數據元素進行并行排序；對于并行處理器中的每一個，將排序的數據元素與組中其它處理器的排序的數據元素合并；以及由并行處理器轉置和存儲合并和排序的數據元素。

在一些實施例中，將數據元素加載到寄存器中包括將數據元素同時加載到兩個或多個并行處理器的相關聯的寄存器中。在一些示例中，將數據元素加載到每個處理器的相應寄存器中包括以轉置的順序加載數據元素。在一些實施例中，對數據元素進行排序包括對與相應并行處理器相關聯的寄存器中的所有數據元素執行比較和交換操作。

在一些情況下，將排序的數據元素與該組中其它處理器的排序的數據元素合并包括將每個并行處理器與處理器的所述組中的另一并行處理器配對，以及將每個并行處理器的排序的數據元素與其相應配對處理器的排序的數據元素合并。

在一些示例中，合并排序的數據元素還包括將每對處理器的合并的數據元素與其它處理器對合并。在一些情況下，該組并行處理器包括兩組并行處理器。在一些示例中，將排序的數據元素與其它處理器的排序的數據元素合并包括將每個并行處理器與兩組處理器中的另一并行處理器配對；以及將每個并行處理器的排序的數據元素與兩組處理器中的每一組處理器內其相應配對處理器的排序的數據元素合并。在一些實施例中，合并兩組處理器的排序的數據元素。

本公開的另一方面包括一種用于并行排序數據的系統。該系統可以包括一個或多個計算設備和存儲指令的存儲器，該指令可由一個或多個計算設備執行。該指令可以包括將數據元素加載到寄存器中，其中每個寄存器與并行處理器的組中的至少一個并行處理器相關聯；對于并行處理器中的每一個，以降序對加載到其相關聯的寄存器中的數據元素進行并行排序；對于并行處理器中的每一個，將排序的數據元素與該組中其它處理器的排序的數據元素合并；以及由并行處理器轉置和存儲合并和排序的數據元素。