清華新聞網(wǎng)12月22日電 近日，清華大學(xué)交叉信息研究院高鳴宇研究組利用多種細(xì)粒度并行優(yōu)化，提出新型圖挖掘硬件加速芯片架構(gòu)。
圖挖掘（Graph Mining）算法在大規(guī)模（數(shù)百萬(wàn)節(jié)點(diǎn)及數(shù)千萬(wàn)邊）圖中匹配與指定圖案同構(gòu)的子圖。其在社會(huì)科學(xué)、生物信息學(xué)等領(lǐng)域有著廣泛的應(yīng)用。目前最先進(jìn)的普適圖挖掘算法將每個(gè)圖節(jié)點(diǎn)的鄰接節(jié)點(diǎn)表示為集合，將每個(gè)起始圖節(jié)點(diǎn)的匹配任務(wù)建模為一個(gè)搜索樹(shù)，在每一級(jí)中依次考慮圖案中各個(gè)節(jié)點(diǎn)，通過(guò)集合相交和相減進(jìn)行匹配。由于其巨大的計(jì)算復(fù)雜度，近年來(lái)圖挖掘算法開(kāi)始利用專(zhuān)用軟件系統(tǒng)和硬件加速芯片以?xún)?yōu)化性能和效率。
FINGERS采用的三種細(xì)粒度并行方式
為了進(jìn)一步提升圖挖掘算法的性能和效率，研究者提出了名為FINGERS的硬件加速芯片架構(gòu)。在利用不同搜索樹(shù)之間的粗粒度并行執(zhí)行的同時(shí)，該架構(gòu)提出并實(shí)現(xiàn)了三種不同的細(xì)粒度并行方式。片段層面并行：將兩個(gè)輸入集合分別拆分成片段并配對(duì)執(zhí)行集合相交和相減，利于并行處理和平衡工作量；集合層面并行：在提前計(jì)算未來(lái)結(jié)果的同時(shí)復(fù)用輸入數(shù)據(jù)；分支層面并行：提供更多可靈活選擇的子任務(wù)，最大化利用計(jì)算資源，并掩蓋訪(fǎng)存時(shí)間。在硬件設(shè)計(jì)上，論文采用資源分配、負(fù)載均衡、輕量計(jì)算單元間通信等創(chuàng)新設(shè)計(jì)，高效實(shí)現(xiàn)上述并行方式，在同等面積下相比當(dāng)前最佳架構(gòu)達(dá)到平均2.8倍、最高8.9倍的性能提升。
FINGERS整體硬件架構(gòu)
該研究成果被計(jì)算機(jī)體系結(jié)構(gòu)領(lǐng)域國(guó)際頂級(jí)會(huì)議編程語(yǔ)言和操作系統(tǒng)的體系結(jié)構(gòu)支持會(huì)議（ASPLOS 2022）接收。2019級(jí)姚班本科生陳啟航為論文第一作者，通訊作者為高鳴宇助理教授，其它作者包括交叉信息院2020級(jí)博士生田博宇。
此外，高鳴宇研究組與美國(guó)斯坦福大學(xué)師生關(guān)于云計(jì)算數(shù)據(jù)中心FPGA硬件上的可信執(zhí)行環(huán)境方面的合作成果亦被ASPLOS 2022接收。ASPLOS是國(guó)際計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的橫跨硬件、體系結(jié)構(gòu)、編譯器、編程語(yǔ)言、操作系統(tǒng)、網(wǎng)絡(luò)、應(yīng)用等多學(xué)科的國(guó)際會(huì)議，尤其關(guān)注這些學(xué)科間的交叉性研究課題。
供稿：交叉信息研究院
編輯：李華山
審核：呂婷
