[發(fā)明專利]元組圖程序中子圖內(nèi)優(yōu)化的方法

有效

• 申請?zhí)枺?/td>: 201880038689.3
• 申請日: 2018-05-17
• 公開（公告）號: CN110998531B
• 公開（公告）日: 2021-09-17
• 發(fā)明（設(shè)計）人: 戈塔姆·坦比多雷;馬休·羅森克蘭茲;桑杰·格瑪沃特;斯?fàn)栒病け说昧_維奇;伊凡·普斯瓦
• 申請（專利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 上海華誠知識產(chǎn)權(quán)代理有限公司 31300
• 代理人: 肖華

1.一種方法，其特征在于，所述方法包括：

生成用于程序的圖，所述圖包括多個節(jié)點和邊，所述圖的每個節(jié)點表示操作，并且所述節(jié)點之間的邊表示輸入到所述節(jié)點所表示的所述操作并從所述節(jié)點所表示的所述操作輸出的數(shù)據(jù)流；

利用一個或多個處理器確定在分布式架構(gòu)中執(zhí)行由所述節(jié)點表示的所述操作的位置，所述確定包括：

確定哪些節(jié)點具有位置限制；

基于所述限制，將位置分配給具有位置限制的每個節(jié)點；

將所述圖分區(qū)成多個子圖，所述分區(qū)包括根據(jù)第一組約束將位置分配給沒有位置限制的節(jié)點，其中特定子圖內(nèi)的每個節(jié)點被分配了相同的位置；以及

根據(jù)第二組約束對所述多個子圖中的每個子圖進行本地分區(qū)，其中，所述第二組約束與所述第一組約束不同。

2.如權(quán)利要求1所述的方法，其特征在于，確定哪些節(jié)點具有位置限制包括：識別由所述節(jié)點表示的所述操作的要求，并確定哪些位置能夠根據(jù)所述要求執(zhí)行所述操作。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，確定哪些節(jié)點具有位置限制包括：確定哪些節(jié)點具有預(yù)定位置。

4.如權(quán)利要求1所述的方法，其特征在于，所述分區(qū)包括減少具有分配給特定位置的操作的子圖的數(shù)目。

5.如權(quán)利要求1所述的方法，其特征在于，所述分區(qū)包括檢測在子圖中創(chuàng)建循環(huán)的可能性，并通過進一步對所述子圖進行分區(qū)來消除所述循環(huán)。

6.如權(quán)利要求1所述的方法，其特征在于，還包括在所述子圖中的每一個子圖被分配的位置處執(zhí)行所述子圖中的每一個子圖，其中在相應(yīng)的單個線程中執(zhí)行每個子圖。

7.一種用于確定計算設(shè)備中的操作分布的方法，其特征在于，所述方法包括：

利用一個或多個計算設(shè)備確定哪些操作具有預(yù)定位置；

創(chuàng)建一個或多個子圖，所述一個或多個子圖包括被識別為具有分配位置的每個操作；

將沒有分配位置的操作合并到所述一個或多個子圖中；

在第一主階段中，根據(jù)第一組約束對所述子圖進行分區(qū)，其中將每個所得到的子圖分配給單獨的位置；和

在第二本地階段中，根據(jù)第二組約束對每個所得到的子圖進行分區(qū)，其中，所述第二組約束與所述第一組約束不同。

8.如權(quán)利要求7所述的方法，其特征在于，所述第一主階段包括：

歸并分片的子圖；

將相鄰的未分配節(jié)點添加到分片的子圖中；

通過將位置從分配的節(jié)點復(fù)制到它們的相鄰節(jié)點，將位置分配給所有未分配的操作；

將在相同位置運行的所有未分片的子圖對歸并在一起。

9.如權(quán)利要求7所述的方法，其特征在于，所述第二本地階段包括：

識別需要拆分的子圖；

準(zhǔn)備識別出的子圖進行拆分；

構(gòu)建歸并圖，其中每個運算結(jié)束于單獨的子圖；

重復(fù)地將所述單獨的子圖歸并在一起。

10.一種用于確定計算設(shè)備中的操作分布的方法，其特征在于，所述方法包括：

創(chuàng)建有向圖，其中每個節(jié)點表示程序的操作，并且每個邊表示在由相應(yīng)節(jié)點表示的操作之間的數(shù)據(jù)通信流；

利用一個或多個計算設(shè)備來確定哪些操作具有預(yù)定位置；

創(chuàng)建一個或多個子圖，所述一個或多個子圖包括被識別為具有分配位置的每個操作；由所述一個或多個計算設(shè)備自動地將沒有分配位置的操作合并到所述一個或多個子圖中，所述合并包括：

歸并分片的子圖；

將相鄰的未分配節(jié)點添加到分片的子圖中；

通過將位置從分配的節(jié)點復(fù)制到它們的相鄰節(jié)點，將位置分配給所有未分配的操作；和

將在相同位置運行的所有未分片的子圖對歸并在一起。