[發明專利]分離可組合式架構下的圖計算工作集優化實現方法及系統

有效

• 申請號: 202110209494.4
• 申請日: 2021-02-24
• 公開（公告）號: CN112817767B
• 公開（公告）日: 2021-11-16
• 發明（設計）人: 李超;王靖;汪陶磊;朱浩瑾;過敏意
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/54
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王毓理;王錫麟

1.一種分離可組合式架構下的圖計算工作集優化實現方法，其特征在于，以數據段為單位，對待處理的圖計算任務進行數據段識別；將圖計算數據段按照四象限法劃分為四大集合，進而根據讀寫訪問熱度進一步將四個集合劃分為熱工作集，即不可遷移工作集和冷工作集，即可遷移工作集；自動化調節可遷移工作集的本地與遠程比例，根據圖計算遍歷過程中邊數據只讀不寫的特性，向遠程內存階段進行單邊遠內存訪問并讀回索引所對應的數據塊，實現優化協作；

所述的分離可組合式架構是指：數據中心中多臺服務器CPU與內存通過網絡連接的方式進行靈活的組合搭配的架構，其中：執行計算任務的服務器作為計算節點，執行內存訪問的服務器作為內存結點；

所述的識別是指：解析并得到圖計算任務中各項源圖數據、中間表述數據、結果保留數據運算過程中需要的圖數據段類別，具體包括：圖節點數據Vertex、節點標號V_id、屬性Attribute、圖計算專用中間變量節點集、中間變量、指針變量Pointer、迭代器Iterator、隊列Queue、邊的編號E_id、邊的偏移量Offset、邊的權重Weight、非活躍點集Inactive_v、文件讀取緩存Cache_fifo；

所述的自動化調節具體包括：

步驟1：將數據段集合的第一象限和第四象限的集合劃分為熱工作集，將數據段集合中的第二象限和第三象限的集合劃分為冷工作集；

步驟2：設置整體工作集大小為，熱工作集大小為，可遷移工作集為，當遠程內存區域RR大小為，則，本地內存區域LR大小為，通過調整的大小來實現本地和遠程數據分布比例的自動化調節；

步驟3：指按照已劃分的本地內存區域與遠程內存區域，在預處理階段將本地內存區域對應的數據段集合的數據留在本地DRAM中，將遠程內存區域對應的數據段集合的數據通過網絡傳輸到遠端內存節點以實現遠程數據讀寫；

步驟4：重復步驟1-3，直到所有需要傳到遠程的數據均傳遞完畢；

所述的單邊遠內存訪問，具體包括：

步驟i：計算節點在預處理過程中，按照已劃分的工作集將遠端數據集通過單邊寫入的形式，將數據連同對應的索引信息，輸出至遠端內存區域；

步驟ii：內存節點上的索引搜索模塊接收來自計算節點的帶索引的數據并保留在遠端內存區域中；

步驟iii：計算節點在執行過程中，不斷向內存節點發出包含索引的讀取遠端數據塊的請求；

步驟iv：內存節點根據收到的索引，將計算節點需要的對應的數據塊通過單邊讀取的形式返回到本地內存區域，供計算節點的本地執行程序使用；

步驟v：重復步驟iii和iv，直到計算節點上的應用結束。

2.根據權利要求1所述的分離可組合式架構下的圖計算工作集優化實現方法，其特征是，所述的四象限法劃分是指：根據識別得到的圖數據段的內存頁讀寫頻率，進行四象限法的工作集劃分，具體為：以橫坐標代表寫入頻率，縱坐標代表讀取頻率，以右上為正，第一象限包括讀多寫多集合，第二象限為讀多寫少集合，第三象限為讀少寫少集合，第四象限為讀少寫多集合；

所述的讀寫是指：任一數據段從內存中讀取和數據寫入到內存中的操作，該操作的總頻次和執行時的帶寬占用之乘積即內存成本，當若當前數據段比整體應用的所計算的內存成本平均值高，則視為多，否則為少。

3.根據權利要求1所述的分離可組合式架構下的圖計算工作集優化實現方法，其特征是，所述的自動化調節是指：通過分析圖數據訪存冪律性、讀取的數據量大而寫入的數據量小的特性，結合上述的四象限法集合劃分，將運行時數據段集合具體劃分到本地內存區域和遠程內存區域。