對于許多數(shù)據(jù)密集型的應(yīng)用分析而言，高效求解的大規(guī)模圖計算算法是至關(guān)重要的。因此，人們提出了大量的圖分析框架來對多種圖計算算法進行性能優(yōu)化，其應(yīng)用從CPU拓展到GPU、FPGA和ASIC。

然而，多樣性的計算平臺也給圖分析帶來了異質(zhì)性，大量的協(xié)調(diào)和同步工作使得圖分析框架很難從單一平臺擴展到異構(gòu)平臺。

此外，現(xiàn)有框架在優(yōu)化迭代算法時僅關(guān)注單次迭代的執(zhí)行時間，很少對算法收斂所需迭代次數(shù)進行探討，因此，算法性能的整體優(yōu)化遇到了顯著瓶頸。

從工作方法上說，以往的工作大多依靠經(jīng)驗實現(xiàn)優(yōu)化收斂速度，缺乏系統(tǒng)的收斂速度分析和優(yōu)化方法來迭代圖算法。

這些瓶頸若不能突破，必將嚴重制約圖計算框架的完善，也會極大限制大數(shù)據(jù)分析等領(lǐng)域的進一步發(fā)展。

撰文 | 徐丹、吳昕

上周，第47屆國際計算機體系結(jié)構(gòu)大會（ISCA）通過線上形式進行。清華大學(xué)魏少軍、劉雷波教授團隊發(fā)表了題為《GraphABCD：通過分塊坐標下降擴展圖分析》（GraphABCD: Scaling Out Graph Analytics with Asynchronous Block Coordinate Descent ）的學(xué)術(shù)報告。

該報告介紹了一種在可重構(gòu)架構(gòu)下（FPGA平臺）將圖計算問題轉(zhuǎn)化為最優(yōu)化問題，利用 分塊坐標下降（Block Coordinate Descent ，簡稱BCD) 執(zhí)行模型，可以同時優(yōu)化圖計算算法的迭代次數(shù)和單次迭代時間。

該方法充分利用了可重構(gòu)陣列的空間并行性，給出了一個優(yōu)化圖計算框架性能的全新視角，相比傳統(tǒng)方法具有顯著優(yōu)勢。

實驗結(jié)果表明，在單源最短路徑、PageRank、協(xié)同濾波等重要圖算法上，新型計算框架GraphABCD 相比現(xiàn)行主流圖計算框架GraphMat，收斂速度提高了4.8倍，執(zhí)行時間提升了2倍。

論文主要由清華大學(xué)魏少軍、劉雷波團隊完成，在過去十余年中，他們在動態(tài)可重構(gòu)芯片領(lǐng)域取得了多項重要技術(shù)突破，關(guān)鍵技術(shù)在多項國家重大工程中得到批量應(yīng)用。

論文第一作者楊軼凡目前正在麻省理工學(xué)院攻讀博士學(xué)位。這篇文章是他在清華攻讀學(xué)士學(xué)位時完成的。論文通訊作者是劉雷波教授，主要合作者還有李兆石、劉志偉、尹首一、鄧仰東等。

一 可重構(gòu)芯片的想象力

該篇論文的核心就是提出了面向可重構(gòu)芯片的圖計算加速技術(shù)。

可重構(gòu)芯片是一種軟硬件可編程的芯片，相比于普通芯片，可重構(gòu)芯片有諸多卓越性，包括軟硬件可編程、硬件架構(gòu)的動態(tài)可變性及高效的架構(gòu)變換能力、兼具高計算效率和高能量效率、不需要芯片設(shè)計能力的應(yīng)用簡便性和軟件定義芯片能力等。

可重構(gòu)芯片一個明顯的優(yōu)勢是可復(fù)用性。半導(dǎo)體制程的演進帶來了高成本問題。僅研發(fā)一款14nm制程的芯片綜合成本高達1.5-2億美元，銷售3000萬顆以上才能把研發(fā)成本攤銷到每顆芯片上。

這時復(fù)用芯片就會成為一個不錯的選擇。相同的芯片，功能可通過軟件改變，不同的軟件寫入就變成了「專用」芯片。目前，國內(nèi)大多AI芯片的設(shè)計思路正是基于此。

魏少軍教授被選為2020年度IEEE產(chǎn)業(yè)先驅(qū)獎（Industry Pioneer Award）獲獎人，圖片來源清華大學(xué)微電子所。

論文的主要作者，魏少軍、劉雷波團隊是國內(nèi)可重構(gòu)芯片的領(lǐng)軍人物。魏少軍是清華大學(xué)微納電子學(xué)系主任、微電子學(xué)研究所所長，曾帶領(lǐng)團隊登上世界頂級高性能芯片頂級會議Hot Chips，先后獲得國家知識產(chǎn)權(quán)局和世界知識產(chǎn)權(quán)組織中國專利金獎、國際半導(dǎo)體產(chǎn)業(yè)協(xié)會(SEMI)突出貢獻獎、第五屆世界互聯(lián)網(wǎng)大會全球領(lǐng)先科技成果等，并在2019年當(dāng)選IEEE會士。

二 將圖計算問題轉(zhuǎn)化為最優(yōu)化問題

針對圖計算技術(shù)瓶頸，魏少軍團隊的研究集中成果在兩個方面。

首先是將圖計算問題轉(zhuǎn)化為最優(yōu)化問題，將最優(yōu)化分析的分塊坐標下降方法（Block Coordinate Descent ，簡稱BCD)創(chuàng)新性地引入到圖計算框架中。

圖1:將分塊坐標下降算法應(yīng)用于圖形域模型

現(xiàn)有圖計算框架局限性的癥結(jié)在于，采用整體同步并行執(zhí)行模型，即圖計算每次迭代都利用屏障進行全局同步。整體同步并行模型不僅限制了框架的可擴展性，而且無法在算法執(zhí)行過程中動態(tài)優(yōu)化算法收斂所需的迭代次數(shù)。

在分塊坐標下降方法執(zhí)行模型下，圖算法的迭代過程不再依賴全局同步，而是在每次迭代中選擇一個或多個由子圖構(gòu)成的數(shù)據(jù)塊，按照坐標下降的方法進行更新，直至算法收斂。

該研究通過分析數(shù)據(jù)塊的大小、選擇順序和更新方法這三個變量來辨別塊坐標下降模型參數(shù)對收斂速度的影響，能夠系統(tǒng)地優(yōu)化算法收斂所需迭代次數(shù)。

實驗結(jié)果證明，更大的塊大小意味著更慢的收斂，但有更明確的并行性和位置記憶，適合解決沖突或隨機內(nèi)存訪問中開銷較大的系統(tǒng)。

優(yōu)先級調(diào)度由于包含了高階全局信息，收斂速度更快。然而，該方案需要更多的工人之間的全局協(xié)調(diào)來提取信息，這可能會在高度異構(gòu)的分布式系統(tǒng)中造成嚴重的延遲。

同時，由于多個數(shù)據(jù)塊之間無須同步，塊坐標下降可實現(xiàn)異步并發(fā)執(zhí)行。

三 原創(chuàng)GraphABCD框架

研究的第二個成果是根據(jù)塊坐標下降視圖方法設(shè)計并實現(xiàn)了GraphABCD框架異構(gòu)系統(tǒng)。

系統(tǒng)中包含一個CPU和硬件加速器，通過減少迭代次數(shù)大大提高迭代圖算法點收斂速度，可以以異步執(zhí)行的方式擴展到可重構(gòu)芯片上。

圖2:GraphABCD系統(tǒng)的架構(gòu)、執(zhí)行示例和內(nèi)存布局示例

GraphABCD框架異構(gòu)系統(tǒng)包括如下個關(guān)鍵設(shè)計：

實現(xiàn)快速收斂。GraphABCD的目標是在異構(gòu)平臺上同步實現(xiàn)輕量級的快速收斂，所以它同時支持優(yōu)先級調(diào)度和簡單循環(huán)塊選擇方法。支持優(yōu)先級塊選擇方法是由于其快速收斂點特性，然而運行時較大的開銷可能會抵消改進的收斂速度，因此也支持簡單循環(huán)塊選擇方法。

實現(xiàn)更好的內(nèi)存位置和寬帶利用率。圖計算算法的不規(guī)則性很大程度上來自于大量的數(shù)據(jù)隨機訪問。GraphABCD選擇「pull-push」作為頂點操作符和邊緣圖格式，結(jié)合在異構(gòu)系統(tǒng)上的任務(wù)分配，能夠確保所有的加速器內(nèi)存訪問都是有順序的。

圖3:三種類型的頂點運算符的PageRank示例

支持異步執(zhí)行。如果部署同步執(zhí)行模型，系統(tǒng)中異構(gòu)組建之間的高同步開銷會嚴重降低性能。在異步BCD保證了異步收斂性的情況下，GraphABCD通過，基于狀態(tài)更新信息、解耦的CPU加速執(zhí)行和不連續(xù)的塊內(nèi)存布局實現(xiàn)了以最小的協(xié)調(diào)開銷設(shè)計異步執(zhí)行。

CPU-FPGA混合執(zhí)行優(yōu)化。GraphABCD會將計算分配給加速器和可用的CPU，以有效地利用異構(gòu)系統(tǒng)。為此，團隊構(gòu)造了一個CPU版本的收集-應(yīng)用函數(shù)，并在運行時檢測到CPU充分利用它。

最后，團隊在FPGA上實現(xiàn)了硬件加速器的原型，并將整個GraphABCD系統(tǒng)部署在現(xiàn)有的CPU-FPGA異構(gòu)系統(tǒng)Intel HARPv2 CPU-FPGA系統(tǒng)上，證實了該框架的可用性。

在GraphABCD中，簡單的定制硬件模塊(GATHER, APPLY)和軟件功能(SCATTER)作為API暴露給最終用戶。這些模塊和功能可以修改，使框架適應(yīng)不同算法。硬件方面，GraphABCD為定制邏輯提供了一個直接的數(shù)據(jù)流接口。定制組件可以由高級合成工具或通過集成現(xiàn)有ip生成。

實驗結(jié)果環(huán)節(jié)，團隊將GraphABCD與三種迭代圖算法，PageRank (PR)、單源最短路徑(SSSP)和協(xié)同過濾(CF)在7個真實圖上(以edgelist格式)運行。每一種算法運行到收斂9次，并報告執(zhí)行時間。

圖4:GraphABCD、GraphMat和ASIC (Graphicionado)的執(zhí)行時間和吞吐量

實驗結(jié)果表明，在單源最短路徑、PageRank、協(xié)同濾波等重要圖算法上，新型計算框架GraphABCD 相比現(xiàn)行主流圖計算框架GraphMat，收斂速度提高了4.8倍，執(zhí)行時間提升了2倍。