并行規(guī)約與掃描原語在ReRAM架構(gòu)上的性能優(yōu)化*

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

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

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

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

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

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

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

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

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

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

1 研究背景

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

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

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

(1)

定義2給定長(zhǎng)度為n的輸入序列，如x1,x2,x3, …,xn, 掃描原語計(jì)算并輸出包含n個(gè)結(jié)果的序列：

(2)

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

(3)

定義4給定輸入序列包含k個(gè)長(zhǎng)度為m的子段，分段掃描原語計(jì)算并輸出包含km個(gè)結(jié)果的序列：

(4)

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

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

1.2 ReRAM

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

圖1 ReRAM物理結(jié)構(gòu)及電子特性Fig.1 ReRAM physical structure and its electrical characteristics

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

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

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

2 并行加速算法

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

2.1 規(guī)約

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

(5)

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

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

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

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

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

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

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

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

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

算法2 Reduction16N的算法

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

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

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

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

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

算法3 Reduction256N算法

2.2 掃描

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

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

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

算法4 分段掃描算法

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

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

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

2.3 憶阻器架構(gòu)及映射

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

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

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

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

圖15 ReRAM加速器的架構(gòu)Fig.15 Architecture of ReRAM accelerator

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

表1 ReRAM架構(gòu)配置

3.2 算法性能分析

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

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

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

圖16 總長(zhǎng)可變的掃描算法在CPU、GPU和ReRAM架構(gòu)的性能對(duì)比Fig.16 Performance comparison of scan algorithm with variable total length on CPU、GPU and ReRAM architectures

表2 掃描算法在GPU和ReRAM架構(gòu)上性能對(duì)比

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

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

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

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

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

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

4 結(jié)論

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