對於許多數據密集型的應用分析而言，高效求解的大規模圖計算算法是至關重要的。因此，人們提出了大量的圖分析框架來對多種圖計算算法進行性能優化，其應用從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框架異構系統包括如下個關鍵設計：
圖3:三種類型的頂點運算符的PageRank示例
最後，團隊在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倍。