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

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

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

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

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

撰文 | 徐丹、吳昕

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三 原創(chuàng)GraphABCD框架

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

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

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

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

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

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

圖3:三種類型的頂點(diǎn)運(yùn)算符的PageRank示例

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

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

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

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

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

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

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