面向自旋存內(nèi)計算架構(gòu)的圖算法優(yōu)化設(shè)計

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

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

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

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

1 引言

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

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

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

2 相關(guān)背景

2.1 圖與圖計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果

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

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

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

4.2 性能與能耗比較

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

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

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

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

5 結(jié)論

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