ReCG:?在ReRAM上利用存算一體加速稀疏共軛梯度解法
中文題目：ReCG: 在ReRAM上利用存算一體加速稀疏共軛梯度解法器
論文題目：ReCG: ReRAM-Accelerated Sparse Conjugate Gradient
錄用期刊/會議：The 61st Design Automation Conference (DAC)（CCF-A類會議）
錄用/見刊時間：2024年2月27日
原文DOI：https://doi.org/10.1145/3649329.3656515
作者列表：
1）范明嘉 中國石油大學(xué)（北京）人工智能學(xué)院 計算機技術(shù) 碩21
2）陳曉明 中國科學(xué)院計算技術(shù)研究所
3）楊德闖 中國石油大學(xué)（北京）人工智能學(xué)院 計算機技術(shù) 碩21
4）金 洲 中國石油大學(xué)（北京）人工智能學(xué)院 計算機系教師
5）劉偉峰 中國石油大學(xué)（北京）人工智能學(xué)院 計算機系教師
文章簡介:
在本工作中，我們提出了一種利用電阻式隨機存取存儲器 (ReRAM) 來加速稀疏共軛梯度 (CG)的存算一體架構(gòu)ReCG，相比于存算分離的CPU、GPU和FPGA架構(gòu)，ReCG在更低能耗的情況下獲得了更高的性能。
摘要:
稀疏線性系統(tǒng)求解在科學(xué)計算中是至關(guān)重要的。稀疏共軛梯度（CG）是最著名的迭代法解法器之一，具有效率高、存儲要求低的特點。然而，在存儲和計算分離的架構(gòu)上實現(xiàn)的稀疏CG解法器，其性能受到不規(guī)則內(nèi)存訪問和大量數(shù)據(jù)傳輸?shù)臉O大限制。在本工作中，我們提出了一種基于電阻式隨機存取存儲器（ReRAM）的存算一體（PIM）架構(gòu)ReCG，用于加速稀疏CG解法器。ReCG的設(shè)計面臨三大挑戰(zhàn)：（1）如何使復(fù)雜的稀疏CG更適合使用基于ReRAM的架構(gòu)進(jìn)行加速；（2）如何將稀疏和不規(guī)則操作映射到更適合密集操作的規(guī)則crossbars上；（3）如何協(xié)調(diào)硬件單元之間的數(shù)據(jù)流，以盡量減少ReRAM寫耐久性較差對加速CG的影響。為了解決這些挑戰(zhàn)，我們（1）通過詳細(xì)分析了算法中操作的共性來對稀疏CG的kernels進(jìn)行分類，并設(shè)計一個靈活的專用架構(gòu)；（2）利用內(nèi)容可尋址存儲器（CAM）和MAC crossbars來有效地實現(xiàn)稀疏和不規(guī)則的操作；（3）提出一種新的數(shù)據(jù)流調(diào)度策略。實驗結(jié)果表明，與CPU和GPU上的PETSc以及FPGA上的CALLIPEPLA相比，ReCG的性能分別最高提高了3個數(shù)量級、1個數(shù)量級和1個數(shù)量級，能耗分別最高降低了2個數(shù)量級、2個數(shù)量級和1個數(shù)量級。
背景與動機:
稀疏CG是科學(xué)計算領(lǐng)域里最為重要的線性解法器之一。然而目前稀疏CG加速工作都是在存算分離架構(gòu)上實現(xiàn)的，導(dǎo)致在處理器和內(nèi)存之間的數(shù)據(jù)移動開銷很大。為了突破存算分離架構(gòu)的限制，快速讀取訪問數(shù)據(jù)，本工作提出了一個用于稀疏CG加速的基于ReRAM的PIM架構(gòu)ReCG。
設(shè)計與實現(xiàn):
整個CG算法是相當(dāng)復(fù)雜的，涉及由標(biāo)量、向量、矩陣和稀疏類型等多種算子組成的各種操作，總共超過10種（如Algorithm 1所示）。在基于ReRAM的硬件上直接實現(xiàn)CG需要實現(xiàn)所有操作。然而，這種方法需要構(gòu)建10多個不同的硬件模塊，并在每個模塊內(nèi)為不同類型的算子設(shè)計單獨的組件。對于矩陣規(guī)模稍大的問題，這種架構(gòu)會變得復(fù)雜且龐大，導(dǎo)致巨大的硬件成本。
我們注意到整個CG算法中算子的共性，將所有操作分為三類：稀疏算子計算，即SpMV；Reduction操作；向量計算。根據(jù)這三類操作，我們設(shè)計了一個專用的架構(gòu)，如圖1所示，其包括五個主要組件：（1）SFU、（2） VFU、（3）SPU、（4）Central Controller和（5）Global Buffer。
圖1:架構(gòu)圖
其次，我們發(fā)現(xiàn)SpMV在加速CG過程中具有關(guān)鍵作用，是算法迭代中的核心步驟。我們使用圖2的例子去描述用ReCG架構(gòu)中的SPU模塊去實現(xiàn)SpMV的工作流程。將實現(xiàn)SpMV的過程分為了四個階段：壓縮階段，加載階段，搜索階段和計算階段。這四個階段是順序執(zhí)行的，但在同一個階段中可以同時并行執(zhí)行多組數(shù)據(jù)。
圖2:SpMV過程
最后，我們對算法每個步驟中的標(biāo)量、向量和矩陣依賴關(guān)系進(jìn)行了詳細(xì)分析，并制定了新的數(shù)據(jù)流調(diào)度策略，如圖3所示。我們發(fā)現(xiàn)階段內(nèi)操作可以并行執(zhí)行，整個架構(gòu)中的模塊也具備并行執(zhí)行能力，從而提高了并行性，加速了算法的執(zhí)行過程。同時，我們減少了數(shù)據(jù)搬運次數(shù)和寫次數(shù)，盡可能地減少ReRAM寫耐久性差對加速算法的影響。
圖3:調(diào)度策略
實驗結(jié)果及分析:
本工作評估了來自SuiteSparse Matrix Collection的36個稀疏矩陣，它們來自計算流體力學(xué)問題、電力網(wǎng)絡(luò)問題、結(jié)構(gòu)問題等不同領(lǐng)域，表1提供了每個矩陣的信息。我們使用NeuroSim和NVSim對ReCG的性能和能耗進(jìn)行仿真，并與CPU和GPU上的PETSc以及FPGA上的CALLIPEPLA進(jìn)行性能和能耗比較。
表1:矩陣信息
本工作測試了36個矩陣在四種平臺（CPU、GPU、FPGA 和 ReRAM）上的求解時間，其實驗結(jié)果如圖4所示。通過進(jìn)行分析比較后發(fā)現(xiàn)，對于前11個較小規(guī)模的矩陣（即從矩陣ex_9到矩陣cbuckle），ReCG 的求解時間平均比CPU上的PETSc快一個數(shù)量級，平均比GPU上的PETSc快兩倍。然而，與FPGA上的加速器CALLIPEPLA相比，ReCG卻需要更多的時間進(jìn)行求解。對于后25個較大規(guī)模的矩陣（即從矩陣olafu到矩陣Flan_1565），ReCG展示出更好的加速。與CPU、GPU和FPGA這三種平臺上加速器相比，ReCG分別達(dá)到了3個數(shù)量級、1個數(shù)量級和1個數(shù)量級的最高加速水平。此外，根據(jù)實驗結(jié)果還可以看出，隨著矩陣規(guī)模的增加，ReCG的加速效果越好，這表明ReCG具有良好的可擴(kuò)展性。
圖4：四種加速器：CPU和GPU上的PETSc，CALLIPEPLA和ReCG的求解時間
圖5顯示了在不同平臺 （CPU、GPU、FPGA 和 ReRAM）上的能耗。對于不同規(guī)模的稀疏矩陣來說，相比于在CPU、GPU和FPGA上加速JPCG，ReCG都是能耗最低的，分別最高可降低了2個數(shù)量級，2個數(shù)量級和1個數(shù)量級。
圖5：四種加速器：CPU和GPU上的PETSc，CALLIPEPLA和ReCG的能耗
為了盡可能減少ReRAM寫耐久性差對加速JPCG所帶來的影響，我們制定了新的調(diào)度策略。在這個調(diào)度策略之下，大大減少了在ReRAM上的寫時間，如圖6所示。我們可以看出采用新的調(diào)度策略后，寫時間減少了50%左右，驗證了調(diào)度策略的有效性。
圖6:采用調(diào)度策略后的寫時間和減少的寫時間
結(jié)論:
ReRAM crossbars支持的原位矩陣向量乘法為利用PIM硬件加速數(shù)值計算應(yīng)用開辟了一個新方向。然而，當(dāng)規(guī)則的crossbars遇到不規(guī)則稀疏矩陣時，必須解決工作負(fù)載映射和數(shù)據(jù)流調(diào)度等關(guān)鍵挑戰(zhàn)，才能在規(guī)則的ReRAM crossbars上高效運行不規(guī)則矩陣運算。在本工作中，我們提出了一種基于ReRAM架構(gòu)的加速器ReCG，它能有效加速JPCG。對于JPCG，我們設(shè)計了多個模塊來實現(xiàn)JPCG的各種kernels。我們還提出了一種新的數(shù)據(jù)流調(diào)度策略來減少數(shù)據(jù)搬運。實驗結(jié)果表明，與CPU和GPU上的PETSc以及FPGA上的CALLIPEPLA相比，ReCG的性能分別最高提高了3個數(shù)量級、1個數(shù)量級和1個數(shù)量級，能耗分別最高降低了2個數(shù)量級、2個數(shù)量級和1個數(shù)量級。
通訊作者簡介:
金洲，中國石油大學(xué)（北京）計算機系副教授，入選北京市科協(xié)青年人才托舉工程、校青年拔尖人才。主要從事集成電路設(shè)計自動化（EDA）、面向科學(xué)計算的DSA軟硬件協(xié)同設(shè)計等方面的研究工作。主持并參與國家自然科學(xué)基金青年項目、重點項目，科技部重點研發(fā)微納電子專項、高性能計算專項青年科學(xué)家項目，國家重點實驗室開放課題、企業(yè)橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國際會議和期刊上發(fā)表60余篇高水平學(xué)術(shù)論文。獲EDA2青年科技獎、SC23最佳論文獎、ISEDA23榮譽論文獎、IEEJ九州支部長獎等。
聯(lián)系方式：jinzhou@cup.edu.cn