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