王雪巖 陳序航 賈小濤 楊建磊 屈 鋼 趙巍勝*

①(北京航空航天大學(xué)集成電路科學(xué)與工程學(xué)院 北京 100191)

②(北京航空航天大學(xué)計(jì)算機(jī)學(xué)院 北京 100191)

③(馬里蘭大學(xué)帕克分校電子與計(jì)算機(jī)工程系 馬里蘭州 20742)

1 引言

萬物皆關(guān)聯(lián)，用于表達(dá)和處理關(guān)聯(lián)關(guān)系的圖和圖計(jì)算廣泛應(yīng)用于網(wǎng)絡(luò)安全、社交媒體、推薦系統(tǒng)等關(guān)鍵領(lǐng)域，成為學(xué)術(shù)界和產(chǎn)業(yè)界的關(guān)注重點(diǎn)與研究熱點(diǎn)。隨著大數(shù)據(jù)產(chǎn)業(yè)的深入發(fā)展，圖數(shù)據(jù)規(guī)模正在爆炸式增長(zhǎng)，圖計(jì)算系統(tǒng)性能面臨前所未有的挑戰(zhàn)。傳統(tǒng)的圖計(jì)算系統(tǒng)基于馮諾依曼架構(gòu)，該架構(gòu)下數(shù)據(jù)存儲(chǔ)與計(jì)算分離，數(shù)據(jù)需要在內(nèi)存與中央處理器(CPU)之間通過數(shù)據(jù)總線進(jìn)行傳輸。進(jìn)入后摩爾時(shí)代，內(nèi)存訪問和 CPU 計(jì)算的速度不匹配嚴(yán)重制約了計(jì)算效率，更為嚴(yán)重的是，大規(guī)模圖計(jì)算問題具有高訪存/計(jì)算比、訪存局部性差、非結(jié)構(gòu)化等特點(diǎn)，導(dǎo)致馮諾依曼瓶頸在大規(guī)模圖計(jì)算系統(tǒng)中更為凸顯[1,2]。據(jù)統(tǒng)計(jì)，圖計(jì)算過程中存儲(chǔ)系統(tǒng)消耗能量占系統(tǒng)整體的 90% 以上[3]，訪存帶寬問題成為大規(guī)模圖計(jì)算系統(tǒng)高效計(jì)算的關(guān)鍵瓶頸。當(dāng)前已有多種圖計(jì)算的軟件框架來提高分布式計(jì)算系統(tǒng)與單節(jié)點(diǎn)計(jì)算系統(tǒng)[4]中圖算法大規(guī)模處理的效率，以及定制圖加速器[5]、近存圖處理方案[6]也被提出，然而這些基于馮諾依曼計(jì)算架構(gòu)或近存的框架難以從根本上解決圖計(jì)算的訪存瓶頸[7,8]。

存內(nèi)計(jì)算技術(shù)為解決這一問題提供了可能，通過將數(shù)據(jù)存儲(chǔ)單元和計(jì)算單元融合為一體，可大幅減少甚至消除數(shù)據(jù)搬運(yùn)。然而，傳統(tǒng)易失性的內(nèi)存技術(shù)面臨功耗大、設(shè)計(jì)成本高等問題，近年來，新型非易失性存儲(chǔ)器，尤其是自旋磁存儲(chǔ)器(Magnetoresistive Random Access Memory, MRAM)的快速發(fā)展，為存內(nèi)計(jì)算的高效實(shí)施帶來了曙光[9]?；谧孕鎯?nèi)計(jì)算架構(gòu)的大規(guī)模圖計(jì)算技術(shù)有望解決當(dāng)前大規(guī)模圖計(jì)算系統(tǒng)面臨的馮諾依曼瓶頸，大幅提高大規(guī)模圖計(jì)算效率[9–11]。

在自旋存內(nèi)計(jì)算架構(gòu)下，存算一體陣列中的存儲(chǔ)單元塊同時(shí)是存內(nèi)處理核，只需與CPU之間傳輸少量的控制指令或地址信息。然而，相比于傳統(tǒng)馮諾依曼計(jì)算架構(gòu)下中央處理器具備非常強(qiáng)大的復(fù)雜計(jì)算能力和控制能力，自旋存內(nèi)計(jì)算架構(gòu)中相對(duì)分散的存內(nèi)處理核更適合處理計(jì)算類型相對(duì)單一、控制邏輯相對(duì)簡(jiǎn)單的任務(wù)[12]。由于存內(nèi)計(jì)算架構(gòu)的上述數(shù)據(jù)傳輸模式和計(jì)算特點(diǎn)，傳統(tǒng)圖算法往往不能很好地直接應(yīng)用于存內(nèi)計(jì)算。此外，圖算法種類很多，不同的圖算法的計(jì)算類型差別比較大。因此，如何匹配圖計(jì)算和存內(nèi)計(jì)算架構(gòu)的特點(diǎn)，實(shí)現(xiàn)圖在存內(nèi)計(jì)算架構(gòu)下的高效存儲(chǔ)和計(jì)算，是大規(guī)模圖計(jì)算存內(nèi)加速的關(guān)鍵挑戰(zhàn)。本文針對(duì)該問題開展了深入研究，首先以多種圖算法為實(shí)例進(jìn)行優(yōu)化設(shè)計(jì)，進(jìn)一步探索面向自旋存內(nèi)計(jì)算架構(gòu)的圖算法的優(yōu)化設(shè)計(jì)方法學(xué)，提出圖算法面向存內(nèi)計(jì)算架構(gòu)的優(yōu)化模型。

2 相關(guān)背景

2.1 圖與圖計(jì)算

圖(Graph)是計(jì)算機(jī)領(lǐng)域用于表示對(duì)象之間關(guān)聯(lián)關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)，包含頂點(diǎn)(Vertex)和邊(Edge)，頂點(diǎn)和邊分別表示對(duì)象以及對(duì)象之間的關(guān)系，對(duì)現(xiàn)實(shí)世界有著強(qiáng)大的表征能力。圖計(jì)算便是以圖作為數(shù)據(jù)模型來表達(dá)問題并予以解決的這一過程，通過對(duì)大型圖數(shù)據(jù)的迭代處理，獲得圖數(shù)據(jù)中隱藏的重要信息。圖計(jì)算已被廣泛應(yīng)用于醫(yī)療、教育、軍事、金融等多個(gè)領(lǐng)域，成為全球科技競(jìng)爭(zhēng)新的戰(zhàn)略制高點(diǎn)。

圖計(jì)算具有高訪存計(jì)算比和不規(guī)則訪存的特點(diǎn)，馮諾依曼架構(gòu)下的訪存開銷是大規(guī)模圖計(jì)算的關(guān)鍵瓶頸。傳統(tǒng)優(yōu)化方法通過用對(duì)暫存器內(nèi)存優(yōu)化和流水線的順序訪問減少內(nèi)存訪問延遲等策略只能從一定程度上緩解，難以從根本上解決訪存瓶頸問題。2016年，通用的存內(nèi)計(jì)算架構(gòu)Pinatubo被提出[13]，在存儲(chǔ)陣列中實(shí)現(xiàn) AND/OR/XOR/INV 等布爾邏輯，并基于該架構(gòu)進(jìn)行圖計(jì)算加速的評(píng)估。此后的一系列研究工作在存算一體陣列中實(shí)現(xiàn)了更多的邏輯計(jì)算功能，如ADD等，并利用這些邏輯功能實(shí)現(xiàn)了更多的圖算法類型，對(duì)圖計(jì)算存內(nèi)處理的可行性也進(jìn)行了分析和驗(yàn)證[11,14]。前期工作也針對(duì)特定圖算法，如三角形計(jì)數(shù)算法等進(jìn)行了優(yōu)化設(shè)計(jì)，以更好地在存內(nèi)計(jì)算架構(gòu)中執(zhí)行[12]。然而，面向存內(nèi)計(jì)算架構(gòu)的更廣泛的圖算法優(yōu)化模型有待進(jìn)一步深入研究。

2.2 自旋存內(nèi)計(jì)算模型

自旋磁存儲(chǔ)器利用電子的自旋屬性實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，具有非易失、耐擦寫、高速度和低功耗等優(yōu)點(diǎn)，被認(rèn)為是下一代最具潛力的非易失性工作內(nèi)存技術(shù)之一[8]。更為關(guān)鍵的是，MRAM 使用器件的電阻信息存儲(chǔ)數(shù)據(jù)，通過電流的累加可以自然地實(shí)現(xiàn)邏輯運(yùn)算，尤其是在耐擦寫方面具有很大優(yōu)勢(shì)，已被證明是最適合的存算介質(zhì)之一[9,10]。一個(gè)典型的自旋轉(zhuǎn)移矩磁存儲(chǔ)器(Spin-Transfer Torque MRAM,STT-MRAM) 單元由1個(gè)接入晶體管和1個(gè)磁性隧道結(jié)(Magnetic Tunnel Junction, MTJ)組成，MTJ由固定磁取向的固定層和可切換磁取向的自由層組成。磁性層被一種隧道氧化物隔開。自由層與固定層的相對(duì)磁性取向決定了MTJ所提供的電阻。平行阻態(tài)RP對(duì)應(yīng)了低阻態(tài)，而反平行阻態(tài)RAP對(duì)應(yīng)了高阻態(tài)。讀操作是通過啟用字線并在位線與源線之間施加一個(gè)偏置電壓，比較通過MTJ時(shí)的總電流與提供的參考閾值來讀出存儲(chǔ)在MTJ中的數(shù)據(jù)。寫操作是通過啟用字線并在位線與源線上施加適當(dāng)?shù)碾妷?，使得流?jīng)MTJ的電流大于MTJ臨界開關(guān)電流來完成。寫入的邏輯值取決于寫入電流的方向。利用STT-MRAM實(shí)現(xiàn)存內(nèi)計(jì)算是在一個(gè)STT-MRAM的陣列中同時(shí)啟用多個(gè)字線(WLi和WLj)，并且在字線上施加一個(gè)偏置電壓Vread，流過源線的總電流(ISL)是流過每個(gè)比特單元的電流的總和。通過設(shè)置不同的參考閾值可以實(shí)現(xiàn)相應(yīng)不同的邏輯功能。

2.3 自旋存內(nèi)圖加速架構(gòu)

自旋存內(nèi)計(jì)算芯片電路模塊主要包括存儲(chǔ)陣列、行列譯碼器、讀寫電路、輸入輸出 (I/O) 模塊、控制器等，其中存儲(chǔ)陣列、輸入輸出模塊與常規(guī)自旋磁存儲(chǔ)器芯片類似。通過對(duì)行列譯碼器和讀寫電路做修改可支持圖計(jì)算涉及的邏輯運(yùn)算功能。圖計(jì)算存內(nèi)加速架構(gòu)主要由4個(gè)部分組成：控制器、數(shù)據(jù)緩沖器、MRAM存算單元、特殊功能單元(Special Function Unit, SFU)(見圖1(a))[12,15]。首先將圖數(shù)據(jù)存儲(chǔ)在存算一體陣列，通過控制器控制在存算一體陣列中執(zhí)行相對(duì)應(yīng)的邏輯操作，若圖算法需要比較、乘法等復(fù)雜的運(yùn)算操作，則將需要進(jìn)行運(yùn)算的數(shù)據(jù)轉(zhuǎn)到SFU中進(jìn)行特殊運(yùn)算。計(jì)算陣列的內(nèi)部結(jié)構(gòu)如圖1(b)所示，每個(gè)芯片由若干Bank組成，每個(gè)Bank由若干子陣列構(gòu)成，它們連接到全局行解碼器和全局?jǐn)?shù)據(jù)寄存器上。子陣列由多個(gè)Mat構(gòu)成，每個(gè)Mat中由行驅(qū)動(dòng)和列驅(qū)動(dòng)對(duì)陣列的計(jì)算形式進(jìn)行控制。

圖1 基于MRAM的圖計(jì)算存內(nèi)加速架構(gòu)

3 面向存內(nèi)計(jì)算架構(gòu)的圖算法優(yōu)化

利用圖和矩陣在數(shù)學(xué)上的等價(jià)關(guān)系，圖算法通?？梢酝ㄟ^矩陣運(yùn)算在存內(nèi)計(jì)算架構(gòu)中實(shí)現(xiàn)。然而，一些復(fù)雜的矩陣運(yùn)算(例如矩陣乘法)普遍存在于圖算法的矩陣實(shí)現(xiàn)中，且在存算一體陣列中實(shí)現(xiàn)這些復(fù)雜運(yùn)算面臨很大的開銷。通過分析矩陣運(yùn)算對(duì)應(yīng)圖計(jì)算的物理意義，可以避免矩陣乘法等復(fù)雜的運(yùn)算，僅利用“與”邏輯運(yùn)算等簡(jiǎn)單位運(yùn)算即可完成特定圖算法，從而能夠高效地在自旋存內(nèi)處理核中實(shí)現(xiàn)[15]。本部分進(jìn)一步探索了單源最短路徑、K-core、鏈路預(yù)測(cè)等圖算法的優(yōu)化實(shí)現(xiàn)，并以此提出基于位運(yùn)算等簡(jiǎn)單運(yùn)算的圖算法優(yōu)化設(shè)計(jì)模型。

3.1 單源最短路徑算法優(yōu)化設(shè)計(jì)

單源最短路徑算法廣泛應(yīng)用于路線圖、超大規(guī)模集成電路設(shè)計(jì)等領(lǐng)域。單源最短路徑算法計(jì)算一個(gè)初始頂點(diǎn)到其他頂點(diǎn)的最短距離。傳統(tǒng)的計(jì)算單源最短路徑的算法涉及大量的循環(huán)遞歸操作，難以在存內(nèi)計(jì)算架構(gòu)高效實(shí)現(xiàn)。因此，亟需對(duì)單源最短路徑算法進(jìn)行優(yōu)化設(shè)計(jì)。

本文提出基于原位計(jì)算的單源最短路徑計(jì)算方法。如圖2所示，首先，設(shè)置一個(gè)序列標(biāo)記未被處理的頂點(diǎn)(Tag序列)，除源頂點(diǎn)V0外均初始化為1，將源頂點(diǎn)V0對(duì)應(yīng)位置設(shè)置為0；一個(gè)序列標(biāo)明源頂點(diǎn)與各目標(biāo)頂點(diǎn)的初始連接關(guān)系(Connected序列)，即為圖的鄰接矩陣中源頂點(diǎn)對(duì)應(yīng)行；一個(gè)結(jié)果序列用于存儲(chǔ)源頂點(diǎn)到圖中其他所有頂點(diǎn)的最短路徑(Distance序列)，初始化為圖的鄰接矩陣中源頂點(diǎn)對(duì)應(yīng)行，元素0表示當(dāng)前源頂點(diǎn)不可到達(dá)該目標(biāo)頂點(diǎn)。然后，將Tag序列與Connected序列進(jìn)行AND邏輯操作，找到未被處理且存在路徑從V0可達(dá)的頂點(diǎn)Vi(AND運(yùn)算為“1”)。最后，在鄰接矩陣中定位第i行，定位該行中第1個(gè)不為0的頂點(diǎn)Vj，將源頂點(diǎn)到頂點(diǎn)Vi的路徑長(zhǎng)度S(V0,Vi)與頂點(diǎn)Vi到頂點(diǎn)Vj路徑長(zhǎng)度S(Vi,Vj)相加，并將其與目前源頂點(diǎn)到頂點(diǎn)Vj的路徑長(zhǎng)度S(V0,Vj)進(jìn)行比較，較小的即為當(dāng)前源頂點(diǎn)到頂點(diǎn)Vj的最短路徑。注意需區(qū)分當(dāng)前源頂點(diǎn)與目標(biāo)頂點(diǎn)的路徑狀態(tài)是否為不可達(dá)的狀態(tài)，如果連接序列相應(yīng)值為0表示不可達(dá)，此時(shí)應(yīng)輸出較大值作為當(dāng)前路徑長(zhǎng)度，圖2中使用比較單元(CoMPare unit, CMP)和多路選擇器實(shí)現(xiàn)該邏輯。之后，重復(fù)上述操作，不斷更新源頂點(diǎn)到各目標(biāo)頂點(diǎn)更短的路徑距離，直到得到源頂點(diǎn)到所有頂點(diǎn)的最短路徑。

圖2 基于位邏輯運(yùn)算優(yōu)化實(shí)現(xiàn)單源最短路徑

3.2 K-core算法優(yōu)化設(shè)計(jì)

K-core算法在圖中找出符合指定核心度的緊密關(guān)聯(lián)的子圖結(jié)構(gòu)，其中每個(gè)頂點(diǎn)至少具有K的度數(shù)，且所有頂點(diǎn)都至少與該子圖中的K個(gè)其他頂點(diǎn)相連。K-core算法在金融風(fēng)控、社交網(wǎng)路和生物信息等領(lǐng)域廣泛應(yīng)用。本文首先計(jì)算圖中每一個(gè)頂點(diǎn)的度數(shù)，即計(jì)算圖的鄰接矩陣中每一行非0元素的個(gè)數(shù)，這一過程可以用比特計(jì)數(shù)器完成。將比特計(jì)數(shù)器返回的結(jié)果發(fā)送到比較器，與預(yù)定的K值進(jìn)行比較，如果計(jì)算后的結(jié)果大于K值，則不做處理，否則將該頂點(diǎn)在矩陣中所在的行與列做清零處理，相當(dāng)于在圖中刪除了該頂點(diǎn)。重復(fù)上述過程直到?jīng)]有新的頂點(diǎn)被刪除，返回當(dāng)前K-core子圖。

3.3 鏈路預(yù)測(cè)算法優(yōu)化設(shè)計(jì)

鏈路預(yù)測(cè)是圖計(jì)算中的一個(gè)經(jīng)典問題，即通過已知的網(wǎng)絡(luò)節(jié)點(diǎn)以及網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性。例如，集成數(shù)據(jù)庫系統(tǒng)(DataBase systems and Logic Programming, DBLP)網(wǎng)站集成了計(jì)算機(jī)科學(xué)領(lǐng)域的綜合研究論文列表。 可以從 DBLP 中的論文構(gòu)建共同作者關(guān)系圖，其中作者是節(jié)點(diǎn)，如果作者共同撰寫了至少1篇 DBLP 中記錄的論文，則可以認(rèn)為他們是有聯(lián)系的，預(yù)測(cè)以前從未合作過的作者之間的新合作是一個(gè)有趣的鏈路預(yù)測(cè)問題。局部重疊度量是非常有效的鏈路預(yù)測(cè)的啟發(fā)式方法，即基于鄰域重疊度來處理關(guān)系預(yù)測(cè)任務(wù)，鄰域重疊度定義為兩個(gè)頂點(diǎn)共同鄰居節(jié)點(diǎn)和總鄰居節(jié)點(diǎn)數(shù)量的比值，然后設(shè)置一個(gè)閾值來確定何時(shí)預(yù)測(cè)邊的存在。該方法適用于資源受限的邊緣側(cè)計(jì)算場(chǎng)景，且即使與更先進(jìn)復(fù)雜的深度學(xué)習(xí)方法相比，也常常能獲得有競(jìng)爭(zhēng)力的性能[16]。

圖3展示了一個(gè)在存內(nèi)優(yōu)化實(shí)現(xiàn)圖的鏈路預(yù)測(cè)的例子。假設(shè)要預(yù)測(cè)頂點(diǎn)V2與頂點(diǎn)V4之間是否有一條邊相連，首先找到頂點(diǎn)V2和V4在圖的鄰接矩陣中所對(duì)應(yīng)的行，分別為R2和R4，對(duì)R2和R4兩行間進(jìn)行AND邏輯運(yùn)算，并用比特計(jì)數(shù)器統(tǒng)計(jì)非零元素的個(gè)數(shù)，即為兩個(gè)頂點(diǎn)間共同鄰居頂點(diǎn)的個(gè)數(shù)。之后，再對(duì)R2和R4兩行之間進(jìn)行OR邏輯運(yùn)算，并用比特計(jì)數(shù)器統(tǒng)計(jì)非零元素的個(gè)數(shù)，即為兩個(gè)頂點(diǎn)間總的頂點(diǎn)的個(gè)數(shù)。最后，將進(jìn)行AND邏輯運(yùn)算與進(jìn)行OR邏輯運(yùn)算后的結(jié)果發(fā)送到特殊功能單元(Special Function Unit, SFU)中進(jìn)行除法運(yùn)算操作，再與我們?cè)O(shè)定的預(yù)測(cè)閾值進(jìn)行比較，從而確定頂點(diǎn)V2與頂點(diǎn)V4之間存在邊的可能性。

圖3 基于位邏輯運(yùn)算優(yōu)化實(shí)現(xiàn)鏈路預(yù)測(cè)算法

3.4 圖優(yōu)化設(shè)計(jì)模型

面向存內(nèi)計(jì)算架構(gòu)優(yōu)化的圖算法計(jì)算過程主要分為4個(gè)主要的步驟：(1)初始化；(2)目標(biāo)定位：尋找頂點(diǎn)的鄰居頂點(diǎn)；(3)屬性匯聚：將頂點(diǎn)與其鄰居頂點(diǎn)聚合；(4)計(jì)算更新：更新頂點(diǎn)聚合后的屬性。具體而言，在初始化階段，將給定圖算法的計(jì)算參數(shù)和與數(shù)據(jù)存儲(chǔ)在圖數(shù)據(jù)緩沖區(qū)中。如表1所示，在目標(biāo)定位階段，定位滿足特定條件的頂點(diǎn)，其中不同圖算法具有不同的條件，例如連通分量計(jì)算算法和單源最短路徑算法根據(jù)AND運(yùn)算結(jié)果進(jìn)行篩選；在屬性匯聚階段，通過邏輯運(yùn)算將目標(biāo)頂點(diǎn)的相關(guān)頂點(diǎn)信息匯聚，如AND/OR/Bitcount等計(jì)算；在計(jì)算更新階段，通過位計(jì)數(shù)器或者特殊功能單元(包括加法、除法、比較操作等)來更新圖的相關(guān)屬性值。反復(fù)迭代該過程，直到滿足算法的終止條件，得到最終的結(jié)果。本文提出的面向存內(nèi)計(jì)算架構(gòu)的圖算法優(yōu)化模型可以為其他圖算法設(shè)計(jì)提供思路框架。

表1 圖算法存內(nèi)計(jì)算優(yōu)化模型

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

為了驗(yàn)證本文所提方法的有效性，我們進(jìn)行了自旋存內(nèi)圖計(jì)算系統(tǒng)的器件 電路 架構(gòu)跨層次協(xié)同仿真。具體而言，在器件級(jí)，使用 Brinkman 模型和 Landau Lifshitz Gilbert(LLG)方程表征自旋電子器件(參數(shù)設(shè)置見表2)；在電路級(jí)，設(shè)計(jì)自旋電子器件的Verilog A模型，使用 45 nm的FreePDK庫對(duì)電路進(jìn)行表征，獲取器件單元的讀寫時(shí)延和能耗；進(jìn)一步地，基于Verilog設(shè)計(jì)外圍控制電路等模塊，實(shí)現(xiàn)圖算法需要的基本邏輯運(yùn)算類型，并使用 Synopsis Tool 進(jìn)行綜合后仿真，得到邏輯運(yùn)算的性能參數(shù)；在架構(gòu)級(jí)，基于開源的模擬器NVSim獲得在自旋存算一體陣列(16 MB STT-MRAM)中進(jìn)行邏輯運(yùn)算的性能；最后，基于SNAP圖數(shù)據(jù)集[17]進(jìn)行整體性能評(píng)估。在CPU(Intel(R)Core(TM)i7-7700HQ, 2.8 GHz, 8核)計(jì)算平臺(tái)上調(diào)用GraphX計(jì)算框架作為計(jì)算速度與能耗的比較基準(zhǔn)。

表2 MTJ關(guān)鍵參數(shù)

4.2 性能與能耗比較

表3展示了本文所提單源最短路徑算法、K-core算法和鏈路預(yù)測(cè)算法在圖的存內(nèi)加速架構(gòu)上的性能與現(xiàn)有的CPU計(jì)算框架GraphX的實(shí)現(xiàn)對(duì)比。在單源最短路徑算法、K-core算法、鏈路預(yù)測(cè)算法上，相比于CPU實(shí)現(xiàn)，本文所提方案均可以實(shí)現(xiàn)平均一個(gè)數(shù)量級(jí)以上的加速。

表3 圖計(jì)算存內(nèi)加速架構(gòu)實(shí)現(xiàn)與CPU實(shí)現(xiàn)速度對(duì)比(s)

圖4展示了在單源最短路徑算法、K-core算法和鏈路預(yù)測(cè)算法上的能耗情況與現(xiàn)有的CPU上的計(jì)算框架GraphX上的比較。與現(xiàn)有的CPU計(jì)算框架相比，本文提出的方案在單源最短路徑算法、K-core算法和鏈路預(yù)測(cè)算法上平均節(jié)省30倍以上的能耗。

圖4 圖計(jì)算存內(nèi)加速架構(gòu)實(shí)現(xiàn)與CPU實(shí)現(xiàn)的能耗標(biāo)準(zhǔn)化結(jié)果對(duì)比

5 結(jié)論

傳統(tǒng)的大規(guī)模圖計(jì)算系統(tǒng)面臨馮諾依曼架構(gòu)下的訪存瓶頸，基于新型自旋磁存儲(chǔ)器的存內(nèi)計(jì)算架構(gòu)加速大規(guī)模圖計(jì)算成為研究熱點(diǎn)。本文探索了單源最短路徑、K-core、鏈路預(yù)測(cè)等圖算法的優(yōu)化實(shí)現(xiàn)，并以此提出了基于位運(yùn)算等簡(jiǎn)單運(yùn)算的圖算法優(yōu)化設(shè)計(jì)模型，對(duì)于突破大規(guī)模圖計(jì)算所面臨的馮諾依曼瓶頸具有關(guān)鍵意義。