基於動態差異化策略的高效大規模圖計算系統研究

《基於動態差異化策略的高效大規模圖計算系統研究》是依託上海交通大學，由陳榕擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於動態差異化策略的高效大規模圖計算系統研究
• 項目類別：青年科學基金項目
• 項目負責人：陳榕
• 依託單位：上海交通大學

項目摘要

許多大數據套用如社交計算、模式識別、推薦系統和自然語言處理等均可以通過大規模基於圖數據結構的計算進行處理，這也對如何構建大規模的圖計算系統從劃分算法、編程模型和計算引擎等方面的設計與實現提出了全新的挑戰。然而，現有圖計算系統大多採用單一性策略，缺乏對圖計算中數據、算法和負載的多樣性的支持，因而對目前具有種類多和變化快等特徵的圖數據未能充分挖掘系統效能。本項目將研究基於動態差異化策略的高效圖計算系統，擬結合離線剖視和在線上抽樣等手段，以及神經網路和效能建模等技術，研究高效的動態特徵感知方法；同時針對不同特徵的圖數據、套用和負載，設計並融合不同劃分算法、編程模型和計算引擎的策略，充分挖掘圖計算過程中的數據局部性和計算並行性，併兼容於現有面向單一策略的最佳化方法。項目的研究成果將為構建高效的大規模圖計算系統提供有力支持，對大數據時代的複雜關聯數據的分析研究起到積極的推動作用。

結題摘要

許多大數據套用如社交計算、模式識別、推薦系統和自然語言處理等均可以通過大規模基於圖數據結構的計算進行處理，這也對如何構建大規模的圖計算系統從劃分算法、編程模型和計算引擎等方面的設計與實現提出了全新的挑戰。然而，現有圖計算系統大多採用單一性策略，缺乏對圖計算中數據、算法和負載的多樣性的支持，因而對目前具有種類多和變化快等特徵的圖數據未能充分挖掘系統效能。本項目的研究目標是構建基於動態差異化策略的高效圖計算系統。 具體包含以下主要研究工作： 首先，我們發現現有圖計算系統通常採用“一刀切”的設計來處理數據分布不均勻的圖，從而導致了負載不均、數據競爭、頻繁通信和高記憶體開銷等一系列性能問題。本項目提出了一種基於差異化思想的混合圖計算系統，能夠動態的為圖數據中具有不同特徵的頂點選擇最適合的計算模型和劃分算法。使用典型圖計算套用和機器學習套用的詳細測試表明，差異化策略能夠帶來高達5.5倍的性能提升和更少的記憶體占用。 其次，圖算法本身的疊代和收斂特徵導致現有圖計算系統存在兩種不同的計算模式：即同步和異步。然而當前尚缺少對於不同執行模式特點的深入研究，導致程式設計師必須手動選擇適合的執行模式或者忍受性能損失。本項目給出了對兩種圖計算執行模式的首個詳細評測和分析，並在此基礎上提出了一種混合圖計算執行模式，通過線上取樣和離線剖視技術能夠在兩種模式間實現動態自主切換。該方法相比最優的單一執行模式（同步或異步）能夠獲得7%至73%的性能提升。 最後，本項目還進一步的挖掘高性能硬體特性（如，NUMA、HTM和RDMA等）對線上記憶體計算系統進行了大量最佳化探索，並獲得了一個數量級以上的性能提升，其中包括面向NUMA架構的圖計算系統、分散式事務處理系統和並發圖查詢系統等。 項目的研究成果將為構建高效的大規模圖計算系統提供有力支持，對大數據時代的複雜關聯數據的分析研究起到積極的推動作用。