[發明專利]并行處理設備和進行并行多值歸約的方法

有效

• 申請號: 201880034679.2
• 申請日: 2018-12-06
• 公開（公告）號: CN111448545B
• 公開（公告）日: 2021-10-15
• 發明（設計）人: 埃里希·康拉德·埃爾森;桑德·艾蒂安·利亞·迪勒曼
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F9/30
• 分類號: G06F9/30
• 代理公司: 上海華誠知識產權代理有限公司 31300
• 代理人: 肖華

1.一種包括多個并行處理單元的并行處理設備，其特征在于，所述并行處理設備被配置為執行使所述并行處理設備進行操作的指令，所述操作包括：

接收進行多值歸約的請求，以從存儲在所述多個并行處理單元的M個初始寄存器空間中的初始值計算M個最終歸約值，其中，所述M個初始寄存器空間中的每一個都存儲有N個初始值，所述N個初始值要歸約成所述M個最終歸約值的相應最終歸約值；

由所述并行處理單元串行地進行多個初始部分歸約，每個初始部分歸約對所述M個初始寄存器空間中的不同的相應寄存器空間中的數據進行操作，其中，每個初始部分歸約將存儲有助于所述M個最終歸約值的數據的寄存器的數量減半，并且在進行多個初始部分歸約之后，存儲有助于所述M個最終歸約值的數據的寄存器的當前數量j小于或等于由所述并行處理單元并行執行的線程的數量N；

一個或多個并行處理單元中的每一個將由一個或多個初始部分歸約計算出的相應值從一個寄存器移動到另一個寄存器，以便將從所述多個初始部分歸約計算出的有助于所述M個最終歸約值的所有值存儲在相同第一寄存器空間中；以及

由所述并行處理單元對存儲在所述第一寄存器空間中的值并行進行多個后續歸約，以計算所述M個最終歸約值，其中所述M個最終歸約值中的每一個都是對存儲在所述M個初始寄存器空間中的相應數據的相應歸約，

串行地進行所述多個初始部分歸約包括：由每個并行處理單元進行向下洗牌操作，之后進行向上洗牌操作，反之亦然。

2.如權利要求1所述的并行處理設備，其特征在于，所述并行處理設備為圖形處理單元。

3.如權利要求1所述的并行處理設備，其特征在于，這些操作還包括將所述M個最終歸約值中的一個或多個移動到相同并行處理單元的相應寄存器中。

4.如權利要求1所述的并行處理設備，其特征在于，每個初始部分歸約包括一個或多個迭代，并且所述一個或多個迭代中的每個迭代將存儲有助于所述M個最終歸約值之一的數據的寄存器的數量減半。

5.如權利要求1所述的并行處理設備，其特征在于，移動由一個或多個初始部分歸約計算的值包括將由每個相應的初始部分歸約計算的有助于所述M個最終歸約值之一的值移動到相同寄存器空間中的不同的相應寄存器分區中。

6.如權利要求5所述的并行處理設備，其特征在于，每個寄存器分區是相同寄存器空間中的寄存器的互斥子集。

7.一種由并行處理設備的多個并行處理單元進行并行M值歸約的方法，其特征在于，所述方法包括：

接收進行多值歸約的請求，以從存儲在所述多個并行處理單元的M個初始寄存器空間中的初始值計算M個最終歸約值，其中，所述M個初始寄存器空間中的每一個都存儲有N個初始值，所述N個初始值要歸約成所述M個最終歸約值的相應最終歸約值；

由所述并行處理單元串行地進行多個初始部分歸約，每個初始部分歸約對所述M個初始寄存器空間中的不同的相應寄存器空間中的數據進行操作，其中，每個初始部分歸約將存儲有助于所述M個最終歸約值的數據的寄存器的數量減半，并且在進行多個初始部分歸約之后，存儲有助于所述M個最終歸約值的數據的寄存器的當前數量j小于或等于由所述并行處理單元并行執行的線程的數量N；

一個或多個并行處理單元中的每一個將由一個或多個初始部分歸約計算出的相應值從一個寄存器移動到另一個寄存器，以便將從所述多個初始部分歸約計算出的有助于所述M個最終歸約值的所有值存儲在相同第一寄存器空間中；以及

由所述并行處理單元對存儲在所述第一寄存器空間中的值并行進行多個后續歸約，以計算所述M個最終歸約值，其中所述M個最終歸約值中的每一個都是對存儲在所述M個初始寄存器空間中的相應數據的相應歸約，

串行地進行所述多個初始部分歸約包括：由每個并行處理單元進行向下洗牌操作，之后進行向上洗牌操作，反之亦然。

8.如權利要求7所述的方法，其特征在于，所述并行處理設備為圖形處理單元。