面向自旋存內計算架構的圖算法優化設計

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

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

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

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

1 引言

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

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

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

2 相關背景

2.1 圖與圖計算

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

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

2.2 自旋存內計算模型

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

2.3 自旋存內圖加速架構

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

圖1 基于MRAM的圖計算存內加速架構

3 面向存內計算架構的圖算法優化

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

3.1 單源最短路徑算法優化設計

單源最短路徑算法廣泛應用于路線圖、超大規模集成電路設計等領域。單源最短路徑算法計算一個初始頂點到其他頂點的最短距離。傳統的計算單源最短路徑的算法涉及大量的循環遞歸操作，難以在存內計算架構高效實現。因此，亟需對單源最短路徑算法進行優化設計。

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

圖2 基于位邏輯運算優化實現單源最短路徑

3.2 K-core算法優化設計

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

3.3 鏈路預測算法優化設計

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

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

圖3 基于位邏輯運算優化實現鏈路預測算法

3.4 圖優化設計模型

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

表1 圖算法存內計算優化模型

4 實驗結果

4.1 實驗環境設置

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

表2 MTJ關鍵參數

4.2 性能與能耗比較

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

表3 圖計算存內加速架構實現與CPU實現速度對比(s)

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

圖4 圖計算存內加速架構實現與CPU實現的能耗標準化結果對比

5 結論

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