對於許多數據密集型的應用分析而言，高效求解的大規模圖計算算法是至關重要的。因此，人們提出了大量的圖分析框架來對多種圖計算算法進行性能優化，其應用從CPU拓展到GPU、FPGA和ASIC。
然而，多樣性的計算平臺也給圖分析帶來了異質性，大量的協調和同步工作使得圖分析框架很難從單一平臺擴展到異構平臺。
此外，現有框架在優化迭代算法時僅關注單次迭代的執行時間，很少對算法收斂所需迭代次數進行探討，因此，算法性能的整體優化遇到了顯著瓶頸。
從工作方法上說，以往的工作大多依靠經驗實現優化收斂速度，缺乏系統的收斂速度分析和優化方法來迭代圖算法。
這些瓶頸若不能突破，必將嚴重製約圖計算框架的完善，也會極大限制大數據分析等領域的進一步發展。
撰文 | 徐丹、吳昕
上周，第47屆國際計算機體系結構大會（ISCA）通過線上形式進行。清華大學魏少軍、劉雷波教授團隊發表了題為《GraphABCD：通過分塊坐標下降擴展圖分析》（GraphABCD: Scaling Out Graph Analytics with Asynchronous Block Coordinate Descent ）的學術報告。
該報告介紹了一種在可重構架構下（FPGA平臺）將圖計算問題轉化為最優化問題，利用 分塊坐標下降（Block Coordinate Descent ，簡稱BCD) 執行模型，可以同時優化圖計算算法的迭代次數和單次迭代時間。
該方法充分利用了可重構陣列的空間並行性，給出了一個優化圖計算框架性能的全新視角，相比傳統方法具有顯著優勢。
實驗結果表明，在單源最短路徑、PageRank、協同濾波等重要圖算法上，新型計算框架GraphABCD 相比現行主流圖計算框架GraphMat，收斂速度提高了4.8倍，執行時間提升了2倍。
論文主要由清華大學魏少軍、劉雷波團隊完成，在過去十餘年中，他們在動態可重構晶片領域取得了多項重要技術突破，關鍵技術在多項國家重大工程中得到批量應用。
論文第一作者楊軼凡目前正在麻省理工學院攻讀博士學位。這篇文章是他在清華攻讀學士學位時完成的。論文通訊作者是劉雷波教授，主要合作者還有李兆石、劉志偉、尹首一、鄧仰東等。
一 可重構晶片的想像力
該篇論文的核心就是提出了面向可重構晶片的圖計算加速技術。
可重構晶片是一種軟硬體可編程的晶片，相比於普通晶片，可重構晶片有諸多卓越性，包括軟硬體可編程、硬體架構的動態可變性及高效的架構變換能力、兼具高計算效率和高能量效率、不需要晶片設計能力的應用簡便性和軟體定義晶片能力等。
可重構晶片一個明顯的優勢是可復用性。半導體製程的演進帶來了高成本問題。僅研發一款14nm製程的晶片綜合成本高達1.5-2億美元，銷售3000萬顆以上才能把研發成本攤銷到每顆晶片上。
這時復用晶片就會成為一個不錯的選擇。相同的晶片，功能可通過軟體改變，不同的軟體寫入就變成了「專用」晶片。目前，國內大多AI晶片的設計思路正是基於此。
魏少軍教授被選為2020年度IEEE產業先驅獎（Industry Pioneer Award）獲獎人，圖片來源清華大學微電子所。
論文的主要作者，魏少軍、劉雷波團隊是國內可重構晶片的領軍人物。魏少軍是清華大學微納電子學系主任、微電子學研究所所長，曾帶領團隊登上世界頂級高性能晶片頂級會議Hot Chips，先後獲得國家知識產權局和世界智慧財產權組織中國專利金獎、國際半導體產業協會(SEMI)突出貢獻獎、第五屆世界網際網路大會全球領先科技成果等，並在2019年當選IEEE會士。
二 將圖計算問題轉化為最優化問題
針對圖計算技術瓶頸，魏少軍團隊的研究集中成果在兩個方面。
首先是將圖計算問題轉化為最優化問題，將最優化分析的分塊坐標下降方法（Block Coordinate Descent ，簡稱BCD)創新性地引入到圖計算框架中。
圖1:將分塊坐標下降算法應用於圖形域模型
現有圖計算框架局限性的癥結在於，採用整體同步並行執行模型，即圖計算每次迭代都利用屏障進行全局同步。整體同步並行模型不僅限制了框架的可擴展性，而且無法在算法執行過程中動態優化算法收斂所需的迭代次數。
在分塊坐標下降方法執行模型下，圖算法的迭代過程不再依賴全局同步，而是在每次迭代中選擇一個或多個由子圖構成的數據塊，按照坐標下降的方法進行更新，直至算法收斂。
該研究通過分析數據塊的大小、選擇順序和更新方法這三個變量來辨別塊坐標下降模型參數對收斂速度的影響，能夠系統地優化算法收斂所需迭代次數。
實驗結果證明，更大的塊大小意味著更慢的收斂，但有更明確的並行性和位置記憶，適合解決衝突或隨機內存訪問中開銷較大的系統。
優先級調度由於包含了高階全局信息，收斂速度更快。然而，該方案需要更多的工人之間的全局協調來提取信息，這可能會在高度異構的分布式系統中造成嚴重的延遲。
同時，由於多個數據塊之間無須同步，塊坐標下降可實現異步並發執行。
三 原創GraphABCD框架
研究的第二個成果是根據塊坐標下降視圖方法設計並實現了GraphABCD框架異構系統。
系統中包含一個CPU和硬體加速器，通過減少迭代次數大大提高迭代圖算法點收斂速度，可以以異步執行的方式擴展到可重構晶片上。
圖2:GraphABCD系統的架構、執行示例和內存布局示例
GraphABCD框架異構系統包括如下個關鍵設計：
實現快速收斂。GraphABCD的目標是在異構平臺上同步實現輕量級的快速收斂，所以它同時支持優先級調度和簡單循環塊選擇方法。支持優先級塊選擇方法是由於其快速收斂點特性，然而運行時較大的開銷可能會抵消改進的收斂速度，因此也支持簡單循環塊選擇方法。
實現更好的內存位置和寬帶利用率。圖計算算法的不規則性很大程度上來自於大量的數據隨機訪問。GraphABCD選擇「pull-push」作為頂點操作符和邊緣圖格式，結合在異構系統上的任務分配，能夠確保所有的加速器內存訪問都是有順序的。
圖3:三種類型的頂點運算符的PageRank示例
支持異步執行。如果部署同步執行模型，系統中異構組建之間的高同步開銷會嚴重降低性能。在異步BCD保證了異步收斂性的情況下，GraphABCD通過，基於狀態更新信息、解耦的CPU加速執行和不連續的塊內存布局實現了以最小的協調開銷設計異步執行。
CPU-FPGA混合執行優化。GraphABCD會將計算分配給加速器和可用的CPU，以有效地利用異構系統。為此，團隊構造了一個CPU版本的收集-應用函數，並在運行時檢測到CPU充分利用它。
最後，團隊在FPGA上實現了硬體加速器的原型，並將整個GraphABCD系統部署在現有的CPU-FPGA異構系統Intel HARPv2 CPU-FPGA系統上，證實了該框架的可用性。
在GraphABCD中，簡單的定製硬體模塊(GATHER, APPLY)和軟體功能(SCATTER)作為API暴露給最終用戶。這些模塊和功能可以修改，使框架適應不同算法。硬體方面，GraphABCD為定製邏輯提供了一個直接的數據流接口。定製組件可以由高級合成工具或通過集成現有ip生成。
實驗結果環節，團隊將GraphABCD與三種迭代圖算法，PageRank (PR)、單源最短路徑(SSSP)和協同過濾(CF)在7個真實圖上(以edgelist格式)運行。每一種算法運行到收斂9次，並報告執行時間。
圖4:GraphABCD、GraphMat和ASIC (Graphicionado)的執行時間和吞吐量
實驗結果表明，在單源最短路徑、PageRank、協同濾波等重要圖算法上，新型計算框架GraphABCD 相比現行主流圖計算框架GraphMat，收斂速度提高了4.8倍，執行時間提升了2倍。