[發(fā)明專利]矩陣求和運算的分布式物理處理

在審

• 申請?zhí)枺?/td>: 202010781703.8
• 申請日: 2020-08-06
• 公開（公告）號: CN112346852A
• 公開（公告）日: 2021-02-09
• 發(fā)明（設(shè)計）人: 馬丁·沙茨;阿敏·費魯沙希安
• 申請（專利權(quán)）人: 臉譜公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F17/16
• 代理公司: 北京安信方達知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 周靖;楊明釗

1.一種方法，包括：

接收執(zhí)行矩陣的指定部分的一個或更多個逐元素求和的運算的規(guī)范；

分析所述運算的規(guī)范以選擇要應(yīng)用的處理負載劃分的類型；

基于所選擇的要應(yīng)用的處理負載劃分的類型，對在多個物理處理元件上并行執(zhí)行所述運算所需的處理進行劃分；和

將經(jīng)劃分的處理分配給所述物理處理元件，以并行執(zhí)行所述矩陣的指定部分的逐元素求和。

2.根據(jù)權(quán)利要求1所述的方法，還包括產(chǎn)生與所述運算相關(guān)聯(lián)的一個或更多個輸出元素。

3.根據(jù)權(quán)利要求1所述的方法，其中，所述規(guī)范包括指示將被包括在所述運算中的所述矩陣的索引的第一向量。

4.根據(jù)權(quán)利要求3所述的方法，其中，所述規(guī)范還包括指示所述第一向量的索引分組的第二向量。

5.根據(jù)權(quán)利要求1所述的方法，其中，分析所述規(guī)范以選擇要應(yīng)用的處理負載劃分的類型包括確定計算度量值是否滿足指定閾值。

6.根據(jù)權(quán)利要求5所述的方法，其中，所述計算度量值至少部分基于所述運算的每個輸出元素的計算工作量。

7.根據(jù)權(quán)利要求6所述的方法，其中，響應(yīng)于確定所述計算度量值不滿足所述指定閾值，所選擇的要應(yīng)用的處理負載劃分的類型與以下操作相關(guān)聯(lián)：將所述物理處理元件的指定部分分配給與關(guān)聯(lián)于所述運算的長度向量中的條目相關(guān)聯(lián)的每組索引。

8.根據(jù)權(quán)利要求6所述的方法，其中，響應(yīng)于確定所述計算度量值滿足所述指定閾值，所選擇的要應(yīng)用的處理負載劃分的類型與以下操作相關(guān)聯(lián)：將所述運算的所有輸出元素分配給所述物理處理元件中的每一個以及向所述物理處理元件中的每一個分派計算對于與所述運算的輸出元素相關(guān)聯(lián)的最終結(jié)果的部分貢獻的任務(wù)。

9.根據(jù)權(quán)利要求1所述的方法，其中，所述物理處理元件包括以下項中的一個：專用數(shù)字邏輯電路、現(xiàn)場可編程門陣列、專用集成電路或中央處理單元。

10.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理包括：在所述物理處理元件的至少一部分之間均衡所述運算的輸出元素的集合的計算工作負載。

11.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理包括：與關(guān)聯(lián)于每個輸出元素的長度向量值成比例地將所述物理處理元件的一部分分配給所述運算的每個輸出元素。

12.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理包括：對所述運算的輸出元素的不同集合進行分組，使得所述不同集合需要基本相似量的計算資源。

13.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理利用以下劃分算法中的至少一種：擴展貪婪算法、貪婪啟發(fā)式算法或Karmarkar-Karp啟發(fā)式算法。

14.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理包括：分配所述物理處理元件中的每一個以計算與所述運算的每個輸出元素相關(guān)聯(lián)的部分貢獻，并累積每個輸出元素的部分貢獻。

15.根據(jù)權(quán)利要求1所述的方法，其中，將經(jīng)劃分的處理分配給所述物理處理元件包括使用網(wǎng)絡(luò)來訪問所述物理處理元件。

16.根據(jù)權(quán)利要求1所述的方法，其中，執(zhí)行所述運算所需的處理包括：使用一個或更多個工作隊列來分配所述運算的輸出元素。

17.根據(jù)權(quán)利要求16所述的方法，其中，所述工作隊列由所述物理處理元件內(nèi)的一個或更多個主處理元件協(xié)調(diào)。