[發(fā)明專利]基于FPGA的異構(gòu)可重構(gòu)圖計算加速器系統(tǒng)的設(shè)計方法

有效

• 申請?zhí)枺?/td>: 201810011291.2
• 申請日: 2018-01-05
• 公開（公告）號: CN108563808B
• 公開（公告）日: 2020-12-04
• 發(fā)明（設(shè)計）人: 周學(xué)海;李曦;王超;陳香蘭
• 申請（專利權(quán)）人: 中國科學(xué)技術(shù)大學(xué)
• 主分類號: G06F30/34
• 分類號: G06F30/34;G06F117/08
• 代理公司: 蘇州創(chuàng)元專利商標(biāo)事務(wù)所有限公司 32103
• 代理人: 范晴

本發(fā)明公開了一種基于FPGA的異構(gòu)可重構(gòu)圖計算加速器系統(tǒng)的設(shè)計方法，整個加速器系統(tǒng)包括PC和FPGA兩大異構(gòu)模塊，具體步驟：首先加載啟動FPGA所需要的驅(qū)動模塊，將FPGA的PCIe DMA等設(shè)備打開；根據(jù)所需要處理的圖數(shù)據(jù)的頂點數(shù)和邊數(shù)進(jìn)行圖計算加速器引擎的選擇；在選擇好加速器引擎之后對圖數(shù)據(jù)進(jìn)行預(yù)處理；將預(yù)處理好的圖數(shù)據(jù)通過PCIe DMA傳輸給FPGA開發(fā)板的板載DDR；啟動加速器從板載DDR指定的地址開始讀取圖數(shù)據(jù)；控制器將圖數(shù)據(jù)分配給不同的處理單元進(jìn)行處理和計算；在各個處理單元計算和處理完數(shù)據(jù)之后，將結(jié)果發(fā)送給計算結(jié)果收集模塊；收集模塊將結(jié)果寫回板載DDR，在整個圖數(shù)據(jù)處理完之后，PC將結(jié)果從板載DDR中讀取出。本發(fā)明具有高性能、高能效、低功耗等特點。

技術(shù)領(lǐng)域

本發(fā)明涉及計算機(jī)硬件加速領(lǐng)域，具體地涉及一種基于FPGA的圖計算加速器系統(tǒng)設(shè)計方法。

背景技術(shù)

現(xiàn)實世界中，圖可以用來表征不同實體間的關(guān)系，它是實體之間關(guān)系模型的抽象，許多的信息可以存儲在圖結(jié)構(gòu)中，因而其在實際中有著很廣泛的應(yīng)用，例如：社交網(wǎng)絡(luò)分析、網(wǎng)頁圖搜索、商品推薦系統(tǒng)建立、交通網(wǎng)絡(luò)分析以及生物醫(yī)學(xué)信息分析等等。在現(xiàn)今大數(shù)據(jù)時代，圖的規(guī)模變得越來越大，例如：Facebook在2014年7月的用戶數(shù)達(dá)到22億，用戶之間的關(guān)系數(shù)量達(dá)到幾百甚至上千億，如果這些用戶的關(guān)系以圖的邊的形式進(jìn)行存儲，存儲量將達(dá)到幾百GB甚至TB級。因此如何來對大規(guī)模圖在可接受的時間內(nèi)進(jìn)行有效的分析、搜索和計算成為當(dāng)前研究的一大難點，也是當(dāng)前研究的一大熱點。

從計算的角度來看，圖計算系統(tǒng)常常被分成vertex-centric(以頂點為中心)和edge-centric(以邊為中心)的計算模型。前者將所有的計算迭代在頂點上，每個頂點從起in-neighbors獲取相應(yīng)的數(shù)據(jù)，然后再執(zhí)行user-defined函數(shù)，更新自身的狀態(tài)或者屬性值，最后每個頂點將自身更新好的狀態(tài)或者屬性值分發(fā)其out-neighbors，直到圖算法收斂或者達(dá)到預(yù)先設(shè)置的迭代次數(shù)。后者將所有的計算迭代在邊上，依次遍歷圖中所有的邊，將source vertices產(chǎn)生的更新值通過邊傳遞給每條邊的destination vertices，然后遍歷destination vertices，將更新值更新到destination vertices上，直到圖算法收斂或者達(dá)到預(yù)先設(shè)置的迭代次數(shù)。兩種計算模型存在著明顯的不同之處：前者順序的訪問頂點，導(dǎo)致對邊的隨機(jī)訪問；后者順序的訪問邊，導(dǎo)致對頂點的隨機(jī)訪問。

通常來說，對于大規(guī)模的數(shù)據(jù)的計算會采用分布式計算的思想，圖計算也不例外。隨著圖數(shù)據(jù)規(guī)模的不斷增長，國內(nèi)外研究者們設(shè)計并實現(xiàn)了很多分布式圖計算系統(tǒng)，例如：Pregel、GraphLab、PowerGraph、GraphX、Giraph。這些分布式圖計算系統(tǒng)大多數(shù)采用的是vertex-centric的計算模型，而PowerGraph采取的是edge-centric的計算模型。直觀的來說，分布式圖計算系統(tǒng)隨著圖數(shù)據(jù)規(guī)模的增大表現(xiàn)出良好的可擴(kuò)展性，但是在其他方面面臨著很多的挑戰(zhàn)，概括的說有以下幾點：(1)圖劃分：要使得分布式系統(tǒng)能夠很好的處理大規(guī)模圖，首先就需要將圖進(jìn)行劃分，但是在劃分的時候需要考慮負(fù)載均衡的問題，使得分布式集群中各節(jié)點間的通信量最少，而這是一個NP-hard的問題；(2)網(wǎng)絡(luò)依賴：分布式圖計算中，集群中的各個節(jié)點間的通信依賴于當(dāng)前處于的網(wǎng)絡(luò)環(huán)境，網(wǎng)絡(luò)環(huán)境有可能成為整個系統(tǒng)的延遲瓶頸；(3)容錯：在分布式圖計算系統(tǒng)中，不能因為某個節(jié)點的故障而導(dǎo)致整個系統(tǒng)的崩潰，因而，分布式圖計算系統(tǒng)中需要設(shè)計容錯機(jī)制；(4)編程、維護(hù)困難：分布式系統(tǒng)的程序設(shè)計、優(yōu)化需要具有專業(yè)人員進(jìn)行開發(fā)與實現(xiàn)，而且維護(hù)起來較為困難。