[發(fā)明專利]一種基于GRAPE框架的圖算法并行加速方法和裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202110142908.6
• 申請(qǐng)日: 2021-02-02
• 公開(kāi)（公告）號(hào): CN112799845A
• 公開(kāi)（公告）日: 2021-05-14
• 發(fā)明（設(shè)計(jì)）人: 樊文飛;何昆;李乾;王越
• 申請(qǐng)（專利權(quán)）人: 深圳計(jì)算科學(xué)研究院
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06F9/48;G06F16/901;G06F16/903
• 代理公司: 深圳市智勝聯(lián)合知識(shí)產(chǎn)權(quán)代理有限公司 44368
• 代理人: 齊文劍

本申請(qǐng)?zhí)峁┝艘环N基于GRAPE框架的圖算法并行加速方法和裝置，所述方法包括：獲取PRAM模型的參數(shù)信息，并根據(jù)所述PRAM模型的參數(shù)信息構(gòu)建生成目標(biāo)模型；獲取輸入數(shù)據(jù)，并依據(jù)所述目標(biāo)模型中的所述索引數(shù)組對(duì)所述輸入數(shù)據(jù)進(jìn)行運(yùn)算，確定初始ID元組和內(nèi)存訪問(wèn)元組；依據(jù)所述初始ID元組和所述輸入數(shù)據(jù)進(jìn)行增量運(yùn)算，迭代運(yùn)算直至所有工作節(jié)點(diǎn)均不再接收來(lái)自其他工作節(jié)點(diǎn)的參數(shù)信息時(shí)生成最終計(jì)算結(jié)果；獲取所述最終計(jì)算結(jié)果內(nèi)所有工作節(jié)點(diǎn)的計(jì)算結(jié)果，并依據(jù)所述所有工作節(jié)點(diǎn)的計(jì)算結(jié)果匯總生成所述運(yùn)算結(jié)果；可以把串行的圖算法遷移到GRAPE框架，并保證遷移后的算法加速比足夠高。

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

本申請(qǐng)涉及數(shù)據(jù)處理領(lǐng)域，特別是一種基于GRAPE框架的圖算法并行加速方法和裝置。

背景技術(shù)

分布式計(jì)算是一種重要的算法加速技術(shù)。分布式計(jì)算將該應(yīng)用分解成許多小的部分，分配給多臺(tái)計(jì)算機(jī)進(jìn)行處理，不同的計(jì)算機(jī)之間通過(guò)信道傳遞信息。這樣可以節(jié)約整體計(jì)算時(shí)間，大大提高計(jì)算效率。目前已經(jīng)有很多成熟的用于大規(guī)模數(shù)據(jù)集的分布式計(jì)算的編程框架，如MapReduce、Hadoop、Spark、GRAPE等等。其中，GRAPE框架是一種新的專門針對(duì)圖數(shù)據(jù)的分布式計(jì)算框架。該計(jì)算框架由數(shù)據(jù)庫(kù)領(lǐng)域著名科學(xué)家、英國(guó)皇家科學(xué)院院士樊文飛提出，相關(guān)工作獲得了2016年數(shù)據(jù)庫(kù)領(lǐng)域頂會(huì)SIGMOD的最佳論文獎(jiǎng)，在國(guó)際上擁有巨大的影響力。

GRAPE框架是針對(duì)圖數(shù)據(jù)的分布式計(jì)算框架。令Q為查詢的集合，給定圖G和某個(gè)查詢Q∈Q，GRAPE框架計(jì)算結(jié)果為Q(G)。每個(gè)GRAPE框架所使用的節(jié)點(diǎn)包含兩類，一個(gè)主節(jié)點(diǎn)P₀和若干個(gè)工作節(jié)點(diǎn)P₁,Λ,P_n。初始時(shí)，輸入的圖G被劃分成n個(gè)部分，這n個(gè)部分分別存儲(chǔ)在P₁,Λ,P_n上。在分布式計(jì)算中，往往假設(shè)這n個(gè)部分大小相似。

目前沒(méi)有基于GRAPE框架的串行算法并行加速方案；雖然很多重要的圖算法都存在著PRAM并行算法，但沒(méi)有一種通用的方案，將PRAM算法遷移到GRAPE框架上。

發(fā)明內(nèi)容

鑒于所述問(wèn)題，提出了本申請(qǐng)以便提供克服所述問(wèn)題或者至少部分地解決所述問(wèn)題的一種基于GRAPE框架的圖算法并行加速方法和一種基于GRAPE框架的圖算法并行加速裝置，所述方法包括：

獲取PRAM模型的參數(shù)信息，并根據(jù)所述PRAM模型的參數(shù)信息構(gòu)建生成目標(biāo)模型，其中，所述目標(biāo)模型包括索引數(shù)組、一個(gè)主節(jié)點(diǎn)和若干個(gè)工作節(jié)點(diǎn)，且工作節(jié)點(diǎn)數(shù)量小于或等于所述PRAM模型中的CPU的數(shù)量；具體地，所述參數(shù)信息至少包括CPU個(gè)數(shù)k、輸入內(nèi)存單元的大小l、額外內(nèi)存單元的大小q、數(shù)據(jù)ID信息和PRAM模型執(zhí)行信息；所述數(shù)據(jù)ID信息用于獲取數(shù)據(jù)集內(nèi)的數(shù)據(jù)對(duì)應(yīng)的ID值；

獲取輸入數(shù)據(jù)，并依據(jù)所述目標(biāo)模型中的所述索引數(shù)組對(duì)所述輸入數(shù)據(jù)進(jìn)行運(yùn)算，確定初始ID元組和內(nèi)存訪問(wèn)元組；其中，ID元組形式為步數(shù)編號(hào)，階段，工作節(jié)點(diǎn)編號(hào)；內(nèi)存訪問(wèn)元組形式為操作-段，地址，數(shù)據(jù)；

依據(jù)所述初始ID元組和所述輸入數(shù)據(jù)進(jìn)行增量運(yùn)算，迭代運(yùn)算直至所有工作節(jié)點(diǎn)均不再接收來(lái)自其他工作節(jié)點(diǎn)的參數(shù)信息時(shí)生成最終計(jì)算結(jié)果；具體地，依據(jù)所述初始ID元組的所述步數(shù)編號(hào)、所述階段和所述工作節(jié)點(diǎn)編號(hào)在每一次增量運(yùn)算時(shí)生成用于下一次增量運(yùn)算的更新ID元組；

獲取所述最終計(jì)算結(jié)果內(nèi)所有工作節(jié)點(diǎn)的計(jì)算結(jié)果，并依據(jù)所述所有工作節(jié)點(diǎn)的計(jì)算結(jié)果匯總生成所述運(yùn)算結(jié)果。

進(jìn)一步地，所述獲取PRAM模型的參數(shù)信息，并根據(jù)所述PRAM模型的參數(shù)信息構(gòu)建生成目標(biāo)模型，其中，所述目標(biāo)模型包括索引數(shù)組、一個(gè)主節(jié)點(diǎn)和若干個(gè)工作節(jié)點(diǎn)，且工作節(jié)點(diǎn)數(shù)量小于或等于所述PRAM模型中的CPU的數(shù)量；具體地，所述參數(shù)信息至少包括CPU個(gè)數(shù)k、輸入內(nèi)存單元的大小l、額外內(nèi)存單元的大小q、數(shù)據(jù)ID信息和PRAM模型執(zhí)行信息；所述數(shù)據(jù)ID信息用于獲取數(shù)據(jù)集內(nèi)的數(shù)據(jù)對(duì)應(yīng)的ID值的步驟，包括：