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

在審

• 申請(qǐng)?zhí)枺?/td>: 202110142908.6
• 申請(qǐng)日: 2021-02-02
• 公開（公告）號(hào): CN112799845A
• 公開（公告）日: 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
• 代理人: 齊文劍

1.一種基于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é)果。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述獲取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值的步驟，包括：

依據(jù)所述CPU個(gè)數(shù)k確認(rèn)所述目標(biāo)模型的工作節(jié)點(diǎn)個(gè)數(shù)n；其中，所述目標(biāo)模型包括一個(gè)所述主節(jié)點(diǎn)和若干個(gè)所述工作節(jié)點(diǎn)，若干個(gè)所述工作節(jié)點(diǎn)包括P₁至P_n；

依據(jù)所述輸入內(nèi)存單元的大小l確認(rèn)目標(biāo)輸入內(nèi)存單元的大小；

依據(jù)所述額外內(nèi)存單元的大小q確認(rèn)目標(biāo)額外內(nèi)存單元的大小；

依據(jù)所述工作節(jié)點(diǎn)個(gè)數(shù)n確認(rèn)每個(gè)工作節(jié)點(diǎn)用于傳遞信息的頂點(diǎn)個(gè)數(shù)為所述工作節(jié)點(diǎn)個(gè)數(shù)n的兩倍，具體地，工作節(jié)點(diǎn)P_i通過(guò)頂點(diǎn)w_i,1至w_i,n向其他工作節(jié)點(diǎn)傳遞信息，通過(guò)頂點(diǎn)w_1,i至w_n,i接收其他工作節(jié)點(diǎn)傳遞信息；

依據(jù)所述工作節(jié)點(diǎn)個(gè)數(shù)、所述目標(biāo)輸入內(nèi)存單元的大小、所述目標(biāo)額外內(nèi)存單元的大小和所述每個(gè)工作節(jié)點(diǎn)用于傳遞信息的頂點(diǎn)個(gè)數(shù)生成所述目標(biāo)模型。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述獲取輸入數(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ù)的步驟，包括：

獲取所述輸入數(shù)據(jù)，并調(diào)用所述目標(biāo)模型內(nèi)的目標(biāo)工作節(jié)點(diǎn)以及所述索引數(shù)組對(duì)所述輸入數(shù)據(jù)進(jìn)行部分計(jì)算，生成所述初始ID元組和所述內(nèi)存訪問(wèn)元組。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述獲取所述輸入數(shù)據(jù)，并調(diào)用所述目標(biāo)模型內(nèi)的目標(biāo)工作節(jié)點(diǎn)以及所述索引數(shù)組對(duì)所述輸入數(shù)據(jù)進(jìn)行部分計(jì)算，生成所述初始ID元組和所述內(nèi)存訪問(wèn)元組的步驟，包括：

調(diào)用所述目標(biāo)模型內(nèi)的所述目標(biāo)工作節(jié)點(diǎn)根據(jù)所述輸入數(shù)據(jù)在所述索引數(shù)組中查詢生成數(shù)組元素；

依據(jù)所述數(shù)組元素確定對(duì)應(yīng)所述目標(biāo)工作節(jié)點(diǎn)的編號(hào)；

依據(jù)所述目標(biāo)工作節(jié)點(diǎn)的編號(hào)生成對(duì)應(yīng)于所述目標(biāo)工作節(jié)點(diǎn)的所述初始ID元組；

依據(jù)輸入數(shù)據(jù)生成所述訪問(wèn)內(nèi)存元組。