金 洲，段懿洳，伊恩鑫，戢昊男，劉偉峰

(中國石油大學(北京) 信息科學與工程學院， 北京 102249)

規(guī)約和掃描是并行計算中的兩個核心原語，對諸多并行計算的性能有著顯著影響。并行規(guī)約是并行點積、并行矩陣乘法、計數(shù)等并行算法中的一個常見操作[1-2]。并行掃描的應用包括排序(快速排序和基數(shù)排序)和合并、圖計算(如最小生成樹、連通分量、最大流、最大獨立集、雙連通分量等)，以及計算幾何(如凸包、多維二叉樹構建、平面最近點對等)[3-12]。此外，規(guī)約和掃描還對基本線性代數(shù)子程序中稀疏矩陣-向量乘(sparse matrix vector multiplication， SpMV)、稀疏矩陣-矩陣乘(general sparse matrix matrix multiplication， SpGEMM)等矩陣運算的性能具有顯著影響[13]，這些矩陣運算在氣象預報、大規(guī)模電力系統(tǒng)仿真等科學與工程計算中具有廣泛的應用。因此，規(guī)約與掃描原語的并行加速具有重要的研究價值。

加速規(guī)約與掃描原語的一般思路是利用CPU、GPU等多核或眾核處理器以并行的方式執(zhí)行算法，可以帶來成倍的性能提升[14]。然而，傳統(tǒng)的馮·諾依曼體系結構中計算單元與存儲單元之間頻繁的數(shù)據吞吐會嚴重影響總體計算性能。與計算本身功耗相比，操作數(shù)移動功耗可達10倍之多[15]。同時，為了滿足對內存帶寬不斷增長的需求，片外互連傳輸速率的增長速度快于每比特能量下降的速度，從而導致更高的峰值功耗[16]。

近來，采用基于憶阻器等新型非易失存儲器件的存算一體技術逐漸成為一個新的熱點研究內容[11]。由其構成的內存架構最顯著的特點是具有原位計算[9]的能力，可從根本上避免數(shù)據的移動。其中，應用較為廣泛的一種是氧化還原阻性存儲器(resistive RAM， ReRAM)。相比其他非易失存儲器，如相變存儲器(phase-change RAM， PCM)、自旋轉移扭矩存儲器(spin-transfer torque RAM， STT-RAM)等，ReRAM具有集成密度大、開關速度快、操作功耗低、開啟/關閉阻值比高、多值存儲、耐久性高，以及與CMOS制備工藝兼容性好等諸多優(yōu)點，是更具吸引力的方案[11]。

基于ReRAM的存算一體架構可使用結構化的交叉陣列和基本的歐姆定律并行地計算矩陣向量乘法(matrix-vector multiplication， GEMV)，可參見文獻[16-18]。ReRAM架構已在機器學習、圖計算等依賴GEMV的計算密集型應用中展現(xiàn)了巨大的潛力。Chi等[17]最早設計了基于ReRAM的深度學習加速器PRIME。He等[19]提出了考慮ReRAM狀態(tài)和功耗之間關系的神經網絡加速器SARA。3DICT[20]實現(xiàn)了神經網絡訓練中的反向傳播。在圖計算方面，Dai等[21]提出了一種在混合存儲多維數(shù)據集陣列上進行圖形處理的存內處理架構GraphH；Huang等[22]提出了基于三維ReRAM的大規(guī)模并行圖處理加速器RAGra； Nai等[23]提出了一種圖計算的全棧解決方案GraphPIM。然而，如何將規(guī)約和掃描原語應用到只適合GEMV運算的ReRAM架構上，仍存在以下多個關鍵挑戰(zhàn)。

1)如何將不依賴GEMV的規(guī)約與掃描原語在憶阻器陣列上實現(xiàn)加速，尤其是如何將不同長度的數(shù)據映射到固定尺寸的、只支持較小矩陣運算的交叉陣列上。

2)如何將科學計算中所需的較高精度數(shù)據映射到只支持2～6 bit的ReRAM單元上，并一步實現(xiàn)矩陣的乘加運算。

3)如何設計電路和架構使其盡可能地匹配加速算法并實現(xiàn)數(shù)據重用，減少擦寫次數(shù)，避免寫操作帶來額外功耗。

本文面向基于ReRAM的存算一體架構，以矩陣乘法的形式進行規(guī)約和掃描算法的加速，將其不同規(guī)模問題高效地映射到固定尺寸的憶阻器陣列上，同時展示實現(xiàn)上述算法所需的電路設計與硬件架構，實現(xiàn)軟硬件協(xié)同設計。并與當前最先進的GPU實現(xiàn)方法進行對比，驗證了所提算法的高性能與低功耗。

1 研究背景

1.1 規(guī)約和掃描算法

將在這一小節(jié)簡要介紹規(guī)約、掃描以及分段規(guī)約與分段掃描四個核心原語，簡單回顧其基本并行算法以及當前最先進的GPU加速并行算法。首先，給出如下基本定義。

定義1給定長度為n的輸入序列，如x1,x2,x3, …,xn, 規(guī)約原語計算并輸出結果：

(1)

定義2給定長度為n的輸入序列，如x1,x2,x3, …,xn, 掃描原語計算并輸出包含n個結果的序列：

(2)

定義3給定輸入序列包含k個長度為m的子段，分段規(guī)約原語計算并輸出包含k個結果的序列：

(3)

定義4給定輸入序列包含k個長度為m的子段，分段掃描原語計算并輸出包含km個結果的序列：

(4)

規(guī)約與掃描的一種常見并行方式是將其拆分為多個可并行的子任務，并對其結果進一步規(guī)約或掃描，通過多次迭代得到最終結果。GPU上的規(guī)約和掃描大多通過warp級、block級以及grid級三個層次聯(lián)合實現(xiàn)。一個block包含多個warp，warp級的規(guī)約結果在block級再次規(guī)約，在grid 級對block級結果進行規(guī)約，并形成最終完整的規(guī)約結果。warp級的規(guī)約和掃描操作通常通過shuffle指令來完成，算法1展示了其計算過程，一個warp中的多個線程通過寄存器來共享數(shù)據，而無須同步或共享內存。

算法1 GPU上使用shuffle的規(guī)約和掃描算法

1.2 ReRAM

ReRAM是一種新興的非易失性存儲器，具有高密度、快速讀取和低漏功率等優(yōu)點，是極具前途的構建未來存算一體體系結構的非線性元器件[9]。ReRAM可通過改變單元電阻來存儲信息，其中一種實現(xiàn)方式是以金屬氧化層作為阻變特性材料，其金屬-絕緣體-金屬結構如圖1(a)所示，由頂部電極、底部電極以及夾在電極之間的金屬氧化物層組成。通過施加外部激勵，ReRAM單元可以實現(xiàn)在高阻態(tài)(關閉狀態(tài))和低阻態(tài)(開啟狀態(tài))之間切換，這兩種狀態(tài)可分別用于表示邏輯的0和1。其伏安特性曲線如圖1(b)所示。

圖1 ReRAM物理結構及電子特性Fig.1 ReRAM physical structure and its electrical characteristics

ReRAM的crossbar交叉陣列[15]結構還可以天然地實現(xiàn)乘加運算，通過模擬計算的方式將O(n2)復雜度的GEMV計算變?yōu)镺(1)復雜度，極易應用到有大量矩陣向量乘計算的神經網絡及神經形態(tài)芯片中。ReRAM的交叉陣列結構如圖2所示，將ReRAM單元連接到同一行的稱為字線，連接到同一列的稱為位線，電壓從字線輸入，電流從位線輸出。將矩陣中的值編程為各ReRAM單元的電導G，向量以電壓的形式輸入，連接到相同字線的ReRAM單元共享同一個輸入電壓Vi，根據歐姆定律和基爾霍夫電流定律(Kirchhoff′s current law， KCL)，可得到流過各ReRAM單元的電流I=V·G，連接到相同位線的ReRAM單元輸出的電流之和即為GEMV的一個結果。

圖2 使用ReRAM的crossbar交叉陣列實現(xiàn)的乘加運算Fig.2 Implementation of GEMV operation through the ReRAM crossbar

ReRAM的交叉陣列被證明可以有效地加速神經網絡計算，其中主要考慮卷積層和全連接層，全連接層的本質為矩陣向量乘，卷積層則可轉化為矩陣矩陣乘，使得非常適合在ReRAM上進行計算，如將數(shù)值較為穩(wěn)定的學習參數(shù)(卷積層的卷積核和全連接層的權值)映射到計算單元，利用ReRAM天然的并行計算優(yōu)勢提高訓練效率[17]。ReRAM也被用于處理圖計算問題，通過稀疏矩陣壓縮[15]、切片技術或剪枝[24]，可將圖計算中的矩陣運算映射到ReRAM陣列中，提高計算效率?？偟膩碚f，通過壓縮稀疏格式和找到良好的映射方法，ReRAM可以很好地提高神經網絡、圖計算等應用的效率。

2 并行加速算法

與GPU類似，在基于ReRAM存算一體架構上的并行規(guī)約與掃描操作也可以被劃分到多個憶阻器陣列上并行計算，并將結果再次分配到多個憶阻器陣列上進行并行規(guī)約與掃描，通過多次迭代得到最終結果。因此，憶阻器陣列上的高效規(guī)約算法是憶阻器陣列間進一步并行的基礎和前提。這里，將重點闡述憶阻器陣列上對不同長度數(shù)據進行規(guī)約與掃描操作的計算方法，即憶阻器陣列級別的規(guī)約與掃描算法，陣列間的操作則與陣列上類似。核心在于將掃描與規(guī)約運算轉換為矩陣乘法或矩陣乘加的形式，映射到憶阻器陣列上。

2.1 規(guī)約

規(guī)約操作可較為直觀地變?yōu)槿缡?5)所示矩陣向量乘的方式，但憶阻器的陣列是固定且較小的，無法將任意尺寸的規(guī)約操作直接映射并實現(xiàn)到憶阻器陣列上。本文將以16×16的憶阻器陣列為例，介紹適用于固定尺寸憶阻器架構的、利用GEMV實現(xiàn)的規(guī)約算法。該方法可擴展至任意尺寸的憶阻器陣列。

(5)

首先，考慮較為簡單的兩種情況。①對包含16個子段(長度均為16)總長為256的輸入序列進行分段規(guī)約，其計算方式如圖3、圖4所示，將輸入序列以列優(yōu)先存儲的方式映射到憶阻器陣列上，則每個子段可被映射到憶阻器陣列的一列上，利用式(5)矩陣向量乘法的方式，以全1向量作為輸入電壓，每條位線上的輸出電流即為分段規(guī)約的結果。②對子段長度為256的輸入序列進行規(guī)約，并將元素以列優(yōu)先的方式將其映射至憶阻器陣列上，復用上述情況①的計算過程，將情況①獲得的結果再次以列優(yōu)先存儲的方式映射到憶阻器陣列上，與全1向量相乘，通過一次迭代即可獲得最終結果，如圖5、圖6所示，該過程共需完成兩次GEMV運算。

圖3 Reduction16的計算方式(矩陣形態(tài))Fig.3 Calculation method of reduction16(in matrix form)

圖4 Reduction16的計算方式(憶阻器形態(tài))Fig.4 Calculation method of reduction16(in crossbar form)

圖5 Reduction256的計算方式(矩陣形態(tài))Fig.5 Calculation method of reduction256(in matrix form)

圖6 Reduction256的計算方式(憶阻器形態(tài))Fig.6 Calculation method of reduction256(in crossbar form)

有上述兩個基本原語之后，任何子段規(guī)約均可以表示為16倍數(shù)或256倍數(shù)長度。這里將分別考慮這兩種情況：

1)一種對子段長度為16倍數(shù)的序列進行規(guī)約，將其中每16個元素看作一個基本單位塊，如圖7、圖8所示，以16N作為長度間隔，分別取出長度為16的基本單位塊，將其以列優(yōu)先存儲的方式寫入第一次運算的ReRAM陣列(即放入第一列與第二列的數(shù)據之間間隔為16N)，接著取16N中的第二塊數(shù)據并再次以16N為間隔，依次取出多個塊寫入下一次運算ReRAM陣列中，并與上一次運算的規(guī)約結果向量累加，則可得到每個16N分段前兩個塊的部分規(guī)約結果。以此類推，直至做完為止。即取各子段中前16個元素依次映射為憶阻器陣列上的一列，與全1向量相乘，得到各子段前16個元素的規(guī)約結果后，對各子段中第二組16個元素以同樣方式依次映射，并將第一次規(guī)約的結果映射至憶阻器陣列的第i+1行(i=16)，再次與全1向量相乘，則可以得到各子段前32個元素規(guī)約結果。計算16個16N長度的分段規(guī)約共需N次迭代，其詳細計算過程如算法2所示。這種方式更適合憶阻器陣列較少，單個憶阻器陣列上需計算數(shù)據的總長較長的情況。

圖7 Reduction16N的計算方式(矩陣形態(tài))Fig.7 Calculation method of reduction16N(in matrix form)

圖8 Reduction16N的計算方式(憶阻器形態(tài))Fig.8 Calculation method of reduction16N(in crossbar form)

算法2 Reduction16N的算法

2)另一種是對子段長度為256倍數(shù)的輸入序列進行規(guī)約，對N個長度為256的序列分別調用上述情況②的計算過程，并將每個256序列的規(guī)約結果標量累加到下一個256序列上。然而，該方法的缺點是共需2N次乘加運算，每一個256長度的規(guī)約都多計算了一次矩陣乘法。如圖9、圖10與算法3所示，將每一個256長度規(guī)約計算的結果映射至下一個256長度運算的憶阻器陣列的第i+1行(i=16)，與全1向量相乘后，前一個256長度規(guī)約計算的結果被直接累加在下一個256長度運算結果上，最終對累加后的結果進行一次規(guī)約操作即可，該方法進一步優(yōu)化了計算過程，將運算次數(shù)減少為N+1。

對于子段長度在(256m,256(m+1))區(qū)間的序列還可以結合上述兩種原語進一步優(yōu)化性能，即利用256倍數(shù)原語對于256m長度的數(shù)據進行規(guī)約，而對剩余序列則利用16倍數(shù)原語進一步加速。

圖9 Reduction256N的計算方式(矩陣形態(tài))Fig.9 Calculation method of reduction256N(in matrix form)

此外，在此基礎上，陣列間還可以進行并行規(guī)約，以256N長度的序列為例，將數(shù)據切分成N個長度為256的序列，調用情況①則可得到N個256序列中以長度為16劃分的分段結果，調用情況②將每個長度為256序列的部分結果寫進憶阻器陣列的每一列，給定輸入向量1，則可得到N個以256為長度的子段規(guī)約結果，將N個結果再調用一次情況②，以此類推，則共需兩次或多次迭代(log16256N次迭代)完成所需運算?？蓪㈥嚵屑壱?guī)約方法和陣列間并行規(guī)約方法相結合，對不同規(guī)模的輸入序列可自由選擇多種不同算法進行組合，以達到最優(yōu)性能。

圖10 Reduction256N的計算方式(憶阻器形態(tài))Fig.10 Calculation method of reduction256N(in crossbar form)

算法3 Reduction256N算法

2.2 掃描

憶阻器陣列級的掃描算法如圖11、圖12和算法4所示，與規(guī)約算法不同的是，該方法將輸入序列以行優(yōu)先存儲的方式映射至憶阻器陣列。首先將以行優(yōu)先存儲方式形成的矩陣C與數(shù)值均為1的上三角矩陣相乘，可得到每行數(shù)據的前綴和結果，記為矩陣CU。接著以數(shù)值為1的下三角矩陣(對角線為0)與矩陣C相乘，得到矩陣LC，其中第一行為0，第2～n行是C矩陣的前(n-1)行在列上的前綴和結果。最后，將LC矩陣與全1矩陣相乘，則可在每一行的每個位置上均得到該行的規(guī)約結果，即為每一行在其之前的所有數(shù)據的總和，將得到的結果加上CU矩陣即可得到最終掃描原語的結果。通過兩次矩陣乘法與一次矩陣加法共三個步驟，即可完成掃描的計算任務。以16×16的矩陣運算為例，則該運算可得到分段為256的序列前綴和結果，若分段長度為16，則僅需陣列級掃描算法即可完成16個子段長度為16的序列的掃描計算。對于子段為16倍數(shù)或256倍數(shù)序列的規(guī)約與掃描原語的計算思想類似，這里不再贅述。

圖11 基于ReRAM架構陣列級掃描算法(矩陣形態(tài))Fig.11 Array level scan algorithm ReRAM-based architecture(in matrix form)

圖12 基于ReRAM架構陣列級掃描算法(憶阻器形態(tài))Fig.12 Array level scan algorithm ReRAM-based architecture(in crossbar form)

算法4 分段掃描算法

陣列間的并行掃描方法如圖13所示(以迭代一次作為示例)，將輸入序列劃分到多個憶阻器陣列上，對每個劃分利用陣列級掃描原語進行操作，收集各劃分序列的最大數(shù)(最后一個結果)形成新的較短待掃描序列，迭代上述過程，直至最終掃描序列長度≤256(即1次可完成掃描操作的序列長度)，將掃描結果逐個累加至上一次迭代所掃描序列的各數(shù)值上(即將每個位置掃描結果矩陣的值均與上一次迭代相應矩陣進行加法操作)，重復回代加法的操作，直至迭代展開至最原始的序列，則得到整個序列的掃描結果。完整的計算流程如算法5所示。

圖13 陣列間的并行掃描算法Fig.13 Bank level parallel scan algorithm

算法5 陣列間并行掃描算法

2.3 憶阻器架構及映射

上述算法涉及多個如R=A×B+C模式的矩陣乘加運算，對于該類型運算可如圖14所示，將矩陣B映射到ReRAM交叉陣列的上半部分，其中每兩個ReRAM單元表示一個數(shù)據，矩陣C以相同方式被映射到ReRAM交叉陣列的下半部分，將A矩陣作為輸入向量的上半部分，下半部分以對角為1的矩陣補齊，通過如上操作，可一步實現(xiàn)矩陣的乘加操作。值得注意的是，本文所有的矩陣乘法、加法、乘加運算均可以這種方式映射到ReRAM交叉陣列上一步實現(xiàn)，即只需控制不同的輸入向量即可，如純粹的矩陣乘法將C矩陣或C矩陣對應的輸入向量設為0即可。

圖14 矩陣到ReRAM陣列的映射Fig.14 Mapping matrix to ReRAM crossbar

此外，為滿足科學計算等應用中對規(guī)約與掃描原語較高精度的需求，可將數(shù)據通過比特切片的方式映射到多個憶阻器陣列上，在單個交叉陣列上則利用兩個相鄰單元來存儲相同數(shù)據(如16×16的矩陣可被映射到16×32的憶阻器陣列上)，并通過移位與加法實現(xiàn)完整的運算得到最終結果。以32 bit精度的數(shù)據為例，該數(shù)據切片方式與上述映射方式相結合，則16×16矩陣乘加運算可在8個ReRAM陣列上一步實現(xiàn)(單個ReRAM單元存儲2 bit)。

圖15展示了基于上述電路設計的加速規(guī)約與掃描原語的存算一體系統(tǒng)架構，與上文所述的計算流程、映射方法以及數(shù)據切片相結合，達到軟硬件協(xié)同設計的目標。該架構包含多個bank，每個bank包含多個計算單元，每個計算單元包含多個ReRAM陣列，此外，還包含控制單元、輸入輸出buffer、數(shù)據buffer和互聯(lián)，以及數(shù)字模擬轉換器(digital-to-analog converter, DAC)、模擬數(shù)字轉換器(analog-to-digital converter, ADC)外圍電路與移加器等多個組成部分。單個ReRAM陣列可選擇從字線或位線輸入，多個ReRAM陣列之間可并行地進行運算。

圖15 ReRAM加速器的架構Fig.15 Architecture of ReRAM accelerator

在掃描原語中，步驟②和步驟③(見圖11)兩步中涉及對相同矩陣C的操作，可將C矩陣在ReRAM陣列上復用，而無須進行兩次較為耗時的ReRAM寫操作，其對應的電路設計如圖15所示，通過片選決定輸入與輸出的端口。將C矩陣編程寫入ReRAM陣列，步驟②需對矩陣C的行進行點積操作，而步驟③需對C矩陣的列進行點積操作。在步驟②中將U矩陣中的列向量以電壓的形式從位線輸入，在字線收集電流即為計算結果的一列；在步驟③中，將L矩陣的行向量以電壓的方式從字線輸入，在位線獲得輸出結果的一行。通過該方式無須多次擦寫即可實現(xiàn)對C矩陣的行或列有選擇地進行點積。該方式顯著增加數(shù)據的復用，減少寫操作的次數(shù)，提高性能減少功耗。

3 實驗結果與分析

3.1 實驗環(huán)境

本文將所提方法實現(xiàn)在了基于ReRAM的憶阻器陣列上，利用HSPICE仿真電路行為，NvSim仿真憶阻器陣列架構的延遲與功耗，以及高級語言C++模擬了規(guī)約與掃描原語的性能與功耗。如表1所示，本文中的憶阻器架構包含128個bank，每個bank包含128個計算單元，每個計算單元包含64個ReRAM陣列，ReRAM陣列尺寸為32×32，每個ReRAM單元可存儲2 bit，DAC精度為2 bit。ReRAM的讀延遲為1.332 ns，寫延遲為20.362 ns，每個ReRAM陣列的功耗為15.153 mW。此外，本文還對比了十核CPU和GPU上的規(guī)約與掃描算法，在Inter Core i7和GeForce RTX 2080硬件環(huán)境下，對thrust庫[25]進行了性能測試。輸入數(shù)據為32位int型。憶阻器架構上的并行算法可根據輸入序列長度在文中展示的多個優(yōu)化算法間進行調優(yōu)，即將多大長度的規(guī)約與掃描任務分配到多少憶阻器陣列上，如何劃分單個憶阻器陣列上需處理的子段長度，如何選擇合適的憶阻器陣列級的算法等，均可根據不同情況進行選擇，這里展示不同輸入參數(shù)下觀測到的最佳性能。

表1 ReRAM架構配置

3.2 算法性能分析

本文將規(guī)約和掃描算法分別在ReRAM加速架構和GPU、CPU上進行性能對比，共分為兩組對比實驗：第一組對比總長變化的規(guī)約和掃描算法；第二組對比總長不變情況下，子段長度變化的分段規(guī)約和掃描算法。通過兩組對比實驗，可以看到本文中所提出的算法在ReRAM加速架構上所獲得的良好加速效果。

理論上，對256長度的數(shù)據在GPU上實現(xiàn)warp級規(guī)約，基于shuffle指令的操作通常需要進行8次32個元素規(guī)約的迭代，共需要256個時鐘周期，因為每個 shuffle 指令和加法需要4個周期，而在ReRAM存算一體架構上則只需要2個時鐘周期。此外，基于ReRAM的存算一體架構單次時鐘周期的時間與功耗也較低。

如圖16和表2所示，對于總長改變的掃描原語，CPU、GPU和ReRAM架構的性能都隨著數(shù)據段的增長而緩慢增長，而ReRAM架構在數(shù)據段相同的情況下，最高比CPU加速75 302.82倍，比GPU加速906.66倍， CPU平均加速25 075.76倍，GPU平均加速302.49倍(圖中橫坐標為取log2對數(shù)處理的數(shù)據總長，縱坐標為取log10對數(shù)的每秒通量數(shù)據)。同樣地，如圖17和表3所示，對于總長改變的規(guī)約算法，ReRAM架構最高比CPU加速81 258.97倍，比GPU加速454.81倍，CPU平均加速30 090.39倍，GPU平均加速152.38倍。

圖16 總長可變的掃描算法在CPU、GPU和ReRAM架構的性能對比Fig.16 Performance comparison of scan algorithm with variable total length on CPU、GPU and ReRAM architectures

表2 掃描算法在GPU和ReRAM架構上性能對比

圖17 總長可變的規(guī)約算法在CPU、GPU和ReRAM架構的性能對比Fig.17 Performance comparison of reduction algorithm with variable total length on CPU、GPU and ReRAM architectures

表3 規(guī)約算法在GPU和ReRAM架構上性能對比

對于總長不變，即總長度為229的數(shù)據段，不同分段時規(guī)約和掃描算法的性能，ReRAM加速器都比傳統(tǒng)GPU快3～5個數(shù)量級，尤其在小分段的情況下，ReRAM架構可以達到4～5個數(shù)量級的加速效果。圖18為總長不變，分段size為215到228掃描算法的性能比較，相比GPU，最高加速比為92 342.39倍，平均性能加速比為13 261.39倍。相比CPU，最高加速比為34 759.34倍,平均加速比為15 925.73倍。圖19為總長不變，分段size為215到228規(guī)約算法性能比較，相比GPU最高加速比為367 733.57倍，平均性能加速比為55 680.80倍。相比CPU，最高加速比為372 421.71倍，平均性能加速比為173 853.25倍。綜上，ReRAM架構展現(xiàn)了明顯的加速優(yōu)勢，尤其是對于分段規(guī)模較小的問題可達到較大的性能提升效果，這類規(guī)模較小的分段規(guī)約與掃描原語在數(shù)值計算、神經網絡中具有極為廣泛的應用場景。此外，相比GPU，ReRAM加速架構上的功耗減少了79%。

圖18 總長不變、分段長變化的掃描算法在CPU、GPU和ReRAM架構的性能對比Fig.18 Performance comparison of scan algorithm with constant total length and variable segment length on CPU、GPU and ReRAM architectures

圖19 總長不變、分段長變化的規(guī)約算法在CPU、GPU和ReRAM架構的性能對比Fig.19 Performance comparison of reduction algorithm with constant total length and variable segment length on CPU、GPU and ReRAM architectures

本文針對不同規(guī)模的輸入序列均給出了較為適用的方法。對于不分段的規(guī)約與掃描來說，盡可能填滿所有ReRAM陣列并進行迭代統(tǒng)籌的方式最為高效，其所需時鐘周期是16為底的對數(shù)函數(shù)(16為單次可運算的矩陣階數(shù))。當分段規(guī)模大于等于256時，分段尺寸和交叉陣列規(guī)模也是影響計算結果的因素。以規(guī)約為例，假設對數(shù)據總長為2x的序列做分段規(guī)約，分段長度為2k，ReRAM陣列共M個，字段長度為16倍數(shù)的規(guī)約原語需要計算(2x-k-4%M+1)×2k-4次時鐘周期，而字段長度為256倍數(shù)的規(guī)約原語則需計算(2x-k%M+1)×(2k-8+1)次時鐘周期。根據所給定字段的長度和個數(shù)，可利用公式快速定位最優(yōu)算法。對于分段尺寸較小的情況，例如子段長為32、64等，采用字段長度為16倍數(shù)的規(guī)約原語會獲得較好的性能，而對于較大的分段規(guī)模，如512、1 024等，則是利用256倍數(shù)的計算方式較為高效。此外，還可根據情況對文中的不同算法進行組合。

4 結論

規(guī)約與掃描是并行計算中的核心原語，對科學計算、機器學習等諸多應用均具有顯著的性能影響。本文面向憶阻器陣列的存算一體架構，首次將規(guī)約與掃描以矩陣向量乘的形式實現(xiàn)并映射到憶阻器陣列上，提出將任意長度的輸入序列映射到固定尺寸的憶阻器陣列上的多種高效算法，以及與之相適應的電路設計與存算一體架構，盡可能地實現(xiàn)數(shù)據重用，避免寫操作，實現(xiàn)了軟硬件協(xié)同設計。此外，還對不同尺寸的輸入序列選擇何種算法可達到最優(yōu)性能進行了仿真與分析。與GPU上的實現(xiàn)相比，所提算法實現(xiàn)了多個數(shù)量級的性能提高，對于總長不變的分段規(guī)約與掃描，性能最高可加速5個數(shù)量級；總長改變的情況下，規(guī)約最高可加速454.81倍，平均加速可達152.38倍，掃描最高可加速906.66倍，平均加速302.49倍，同時降低了79%的功耗。