[發明專利]元組圖程序中子圖內優化的方法

有效

• 申請號: 201880038689.3
• 申請日: 2018-05-17
• 公開（公告）號: CN110998531B
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 戈塔姆·坦比多雷;馬休·羅森克蘭茲;桑杰·格瑪沃特;斯爾詹·彼得羅維奇;伊凡·普斯瓦
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 上海華誠知識產權代理有限公司 31300
• 代理人: 肖華

編程模型生成用于程序的圖形，所述圖形包括多個節點和邊，其中所述圖形的每個節點表示操作，并且所述節點之間的邊表示輸入到由所述節點表示的操作并從由所述節點表示的操作輸出的數據流。該模型確定分布式架構中執行由節點表示的操作的位置。這種確定可以包括確定哪些節點具有位置限制，基于該限制將位置分配給具有位置限制的每個節點，以及將該圖分區成多個子圖，該分區包括根據第一組約束將位置分配給沒有位置限制的節點，其中特定子圖內的每個節點被分配給相同的位置。每個子圖在其分配的位置在相應的單個線程中執行。

相關申請的交叉引用

本申請是2017年8月24日提交的美國專利申請No.15/685,055的繼續申請，其公開內容通過引用并入本文。

背景技術

云計算允許具有各種計算能力的用戶為了成本和計算效率而使用可配置資源的共享池來存儲和處理數據。用于云計算的當前編程模型包括MapReduce,Dryad和批量同步并行云處理。面向分布式計算的一個問題是性能。分布式計算中的性能與數據與計算單元的接近程度以及計算單元之間的數據傳輸成本有關。

發明內容

本公開描述了一種用于云計算的新的編程模型。新的編程模型可用于編寫分布式低延遲非批處理(non-batch)程序。應用在模型下構造程序，然后提交它以供執行。該程序由運算符的有向非循環圖組成。值的流沿著圖中的邊從一個運算符流到另一個運算符。通過流發送的每個值都是元組。相同程序中的不同運算符可以在不同的機器上運行。編程模型協調這些運算符在不同機器上的執行并將數據從一個運算符傳播到另一個運算符。

編程模型的一個方面提供了一種方法，包括：生成用于程序的圖，所述圖包括多個節點和邊，所述圖的每個節點表示操作，并且所述節點之間的邊表示輸入到所述節點所表示的所述操作并從所述節點所表示的所述操作輸出的數據流。該方法方法傲包括利用一個或多個處理器確定在分布式架構中執行由所述節點表示的所述操作的位置。該確定包括：確定哪些節點具有位置限制；基于所述限制，將位置分配給具有位置限制的每個節點；將所述圖分區成多個子圖，所述分區包括根據第一組約束將位置分配給沒有位置限制的節點，其中將特定子圖內的每個節點分配給相同的位置。確定哪些節點具有位置限制包括：識別由所述節點表示的所述操作的要求，并確定哪些位置能夠根據所述要求執行所述操作。在另一示例中，一些節點可以具有預定位置。分區可以包括減少具有分配給特定位置的操作的子圖的數目。可選地或附加地，分區可以包括檢測在子圖中創建循環的可能性，并通過進一步對所述子圖進行分區來消除所述循環。在相應的單個線程中在每個子圖被分配的位置處執行每個子圖。

另一方面提供了一種用于確定計算設備之間的操作的分布的方法，包括：利用一個或多個計算設備來確定哪些操作具有預定位置；以及創建一個或多個子圖，所述一個或多個子圖包括被識別為具有所分配的位置的每個操作。沒有分配位置的操作被合并到一個或多個子圖中。子圖在第一主階段被分區，其中每個所得到的子圖被分配給單獨的位置，并且每個所得到的子圖在第二本地階段被分區。第一主階段可以包括歸并分片的子圖，將相鄰的未分配節點添加到分片的子圖中，通過將位置從分配的節點復制到它們的相鄰節點，將位置分配給所有未分配的操作，以及將在相同位置運行的所有可能的未分片的子圖對歸并在一起。所述第二本地階段包括：識別需要拆分的子圖；準備識別出的子圖進行拆分；構建歸并圖，其中每個運算結束于單獨的子圖；重復地將所述單獨的子圖歸并在一起。