動態圖計算系統設計與性能最佳化研究

《動態圖計算系統設計與性能最佳化研究》是依託清華大學，由章明星擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：動態圖計算系統設計與性能最佳化研究
• 依託單位：清華大學
• 項目負責人：章明星
• 項目類別：青年科學基金項目

項目摘要

由於具有良好的表達能力，圖數據結構被廣泛用於對元素間具有複雜聯繫的數據進行建模，如社交網路、知識圖譜等。為了應對大規模圖數據帶來的挑戰，當前主要的圖計算系統通過分散式集群或者外存設備極大地提升了其能夠處理的圖數據容量。然而，在實際生產生活中產生的圖數據往往是處於不斷地動態變化的狀態下的。傳統的大規模圖計算系統由於並未考慮到這一需求，往往並不提供對圖結構進行變更的接口。即便是提供了相關接口的系統（如 Giraph），也僅僅是提供了簡單地支持，效率並不高。. 針對這一問題，本項目擬進行三方面的研究：（1）研究新型的圖數據組織方式，使得其在支持輕量級的圖數據修改的同時保持很好的數據局部性；（2）研究支持增量和並發計算的動態圖計算框架，使得對原圖小規模的修改可以不至於完全重置之前的計算結果;（3）增加時間戳的概念設計新型的編程模型，從而支持用戶對時序要求的表達。

結題摘要

由於具有良好的表達能力，圖數據結構被廣泛用於對元素間具有複雜聯繫的數據進行建模，如社交網路、知識圖譜等。為了應對大規模圖數據帶來的挑戰，當前主要的圖計算系統通過分散式集群或者外存設備極大地提升了其能夠處理的圖數據容量。然而，在實際生產生活中產生的圖數據往往是處於不斷地動態變化的狀態下的。傳統的大規模圖計算系統由於並未考慮到這一需求，往往並不提供對圖結構進行變更的接口。即便是提供了相關接口的系統（如 Giraph），也僅僅是提供了簡單地支持，效率並不高。本研究主要針對基於日誌信息建模生成的時序圖數據的高效分析進行研究。主要完成內容包括一套對時序圖進行高效匹配分析的系統，一套對圖上進行隨機遊走類算法進行最佳化的算法，以及一套針對現代新型硬體最佳化上層套用執行性能的框架。發表在 SOSP 2019，ASPLOS 2020 上的高水平論文 3 篇。相關受資助人參與發表在 TPDS 上高水平期刊論文 2 篇。其中針對日誌圖查詢 CPU 資源浪費過多、中間結果龐大的問題，提出了時序 視窗匹配模型，將匹配的搜尋空間限制到視窗內部。極大的降低了匹配的空間以 及中間狀態數量，從而顯著的提升了計算的性能。實驗結果顯示，在記憶體模式下， 比現有算法快出 1-2 個數量級;在外存模式下比現有算法快出 2 個數量級以上。同時進一步探索了在圖上進行隨機遊走類分析的性能提升工作，通過提出一套統一的轉移機率定義公式，提出了一套通用的計算方法，在極大的減少了計算量的同時，保證計算結果與原算法等效。同時，我們還提出了針對該方法的一些最佳化策略，進一步降低了計算開銷。