科研動(dòng)態(tài)
Mille-feuille：GPU上的分塊混合精度單內(nèi)核共軛梯度解法器
中文題目：Mille-feuille：GPU上的分塊混合精度單內(nèi)核共軛梯度解法器
論文題目：Mille-feuille: A Tile-Grained Mixed Precision Single-Kernel Conjugate Gradient Solver on GPUs
錄用期刊/會(huì)議：37th International Conference for High Performance Computing, Networking, Storage, and Analysis (CCF A)
錄用/見(jiàn)刊時(shí)間：2024-6-15（錄用時(shí)間）
作者列表：
1）楊德闖 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)技術(shù) 碩21
2）趙雨軒 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 碩22
3）牛一多 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 本21
4）賈偉樂(lè) 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 研究員
5）邵 恩 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 高級(jí)工程師
6）劉偉峰 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系教師
6）譚光明 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 研究員
7）金 洲 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系教師
摘要:
共軛梯度法（CG）和雙共軛梯度穩(wěn)定法（BiCGSTAB）是用于求解稀疏線(xiàn)性系統(tǒng)的有效方法。本文提出了一種新的求解器——Mille-feuille，用于加速GPU上的CG和BiCGSTAB?；贜VIDIA A100和AMD MI210的實(shí)驗(yàn)結(jié)果表明，Mille-feuille求解器在CG中相比基準(zhǔn)實(shí)現(xiàn)（包括廠(chǎng)商支持的cuSPARSE/hipSPARSE以及兩個(gè)最先進(jìn)的庫(kù)PETSc和Ginkgo）取得平均3.03倍/2.68倍，5.37倍，4.36倍（最高可達(dá)8.77倍/7.14倍，16.54倍，15.69倍）的加速比；在BiCGSTAB中，平均加速比為2.65倍/2.32倍，3.57倍，3.78倍（最高可達(dá)7.51倍/6.63倍，16.64倍，11.73倍）；在預(yù)條件CG（PCG）中，平均加速比為3.82倍/3.47倍（最高可達(dá)40.38倍/47.75倍）；在預(yù)條件BiCGSTAB（PBiCGSTAB）中，平均加速比為1.79倍/1.63倍（最高可達(dá)45.63倍/44.34倍）。
背景與動(dòng)機(jī):
在迭代法解法器中，共軛梯度方法和穩(wěn)定雙共軛梯度方法分別因在處理對(duì)稱(chēng)正定、非對(duì)稱(chēng)或不正定線(xiàn)性系統(tǒng)中的有效性而突出。目前的迭代法解法器往往忽略了一些對(duì)性能至關(guān)重要的因素，如稀疏矩陣中非零元素?cái)?shù)值精度的分布、內(nèi)核間的同步開(kāi)銷(xiāo)以及解向量x的部分收斂等。本文擬利用稀疏矩陣的數(shù)值特征、硬件平臺(tái)特性以及算法本身的實(shí)現(xiàn)原理對(duì)共軛梯度解法器進(jìn)行優(yōu)化。
設(shè)計(jì)與實(shí)現(xiàn):
一、稀疏存儲(chǔ)格式
我們?cè)O(shè)計(jì)了一種細(xì)粒度的兩級(jí)分塊稀疏矩陣存儲(chǔ)格式，高級(jí)存儲(chǔ)以COO的結(jié)構(gòu)捕獲塊間的信息用于確保SpMV計(jì)算過(guò)程的負(fù)載均衡，并且根據(jù)稀疏矩陣中非零元素初始值的范圍使用四種不同精度進(jìn)行存儲(chǔ)，對(duì)于低級(jí)存儲(chǔ)，我們使用 CSR 方式來(lái)記錄塊內(nèi)信息，使用額外的數(shù)組記錄塊內(nèi)非空行的信息，用于避免在 SpMV 操作期間遍歷塊中的空行，從而進(jìn)一步提高 SpMV的性能。
圖1. 兩級(jí)分塊的存儲(chǔ)結(jié)構(gòu)
二、單內(nèi)核共軛梯度解法器
接下來(lái)，為了減少GPU上不同內(nèi)核之間的同步開(kāi)銷(xiāo)，我們利用原子操作使整個(gè)迭代法求解過(guò)程在單個(gè)GPU內(nèi)核內(nèi)運(yùn)行。為了實(shí)現(xiàn)同步，我們構(gòu)建多個(gè)依賴(lài)數(shù)組來(lái)定義數(shù)據(jù)和操作之間的依賴(lài)關(guān)系，并允許原子操作調(diào)度warp以執(zhí)行不同操作的任務(wù)。我們根據(jù)依賴(lài)關(guān)系將CG算法分為四個(gè)部分，內(nèi)核啟動(dòng)之前，矩陣A的非空塊以負(fù)載均衡的方式分配給每個(gè)warp并且被加載到共享內(nèi)存中一次，并在迭代過(guò)程中被重復(fù)利用，這樣可以提升程序的訪(fǎng)存效率。
圖2. 單內(nèi)核共軛梯度解法器
三、部分收斂感知混合精度策略
最后，為了在迭代過(guò)程中利用解向量x 中已經(jīng)收斂的元素來(lái)優(yōu)化SpMV的性能，我們根據(jù)收斂閾值ε設(shè)定了四個(gè)范圍并實(shí)現(xiàn)了一種部分收斂感知混合精度策略，運(yùn)行時(shí)在單個(gè)內(nèi)核內(nèi)實(shí)現(xiàn)塊粒度的片上動(dòng)態(tài)精度轉(zhuǎn)換。我們的精度轉(zhuǎn)換僅在共享內(nèi)存中進(jìn)行一次，減少了訪(fǎng)問(wèn)全局內(nèi)存或執(zhí)行精度轉(zhuǎn)換的高昂開(kāi)銷(xiāo)。
圖3. 部分收斂感知混合精度策略
實(shí)驗(yàn)結(jié)果及分析:
一、Mille-feuille與基準(zhǔn)實(shí)現(xiàn)的對(duì)比（cuSPARSE/hipSPARSE）
在 CG 算法上，與基準(zhǔn)實(shí)現(xiàn)相比，我們的算法的平均加速比為 3.03 倍和 2.68 倍（最高分別為 8.77 倍和 7.14 倍）。在 BiCGSTAB 算法上，與基準(zhǔn)實(shí)現(xiàn)相比，我們的算法的平均加速比為 2.65 倍和 2.32 倍（最高分別為 7.51 倍和 6.63倍）。
在PCG算法上，與基準(zhǔn)實(shí)現(xiàn)相比，我們的算法的平均加速比為 3.82 倍和 3.47 倍（最高分別為 40.38 倍和 47.75 倍）。在PBiCGSTAB 算法上，與基準(zhǔn)實(shí)現(xiàn)相比，我們的算法的平均加速比為 1.79 倍和 1.63 倍（最高分別為45.63倍和44.34倍）。
圖4. 與cuSPARSE和hipSPARSE實(shí)現(xiàn)的CG和BiCGSTAB基準(zhǔn)算法的性能比較
圖5. 與cuSPARSE和hipSPARSE實(shí)現(xiàn)的PCG和PBiCGSTAB基準(zhǔn)算法的性能比較
二、Mille-feuille與PETSc和Ginkgo對(duì)比
對(duì)于 CG 方法，我們的算法相較于 PETSc 和 Ginkgo分別實(shí)現(xiàn)了 5.37 倍和 4.36 倍的幾何平均速度提升（最高分別可達(dá) 16.54 倍和 15.69 倍）。對(duì)于 BiCGSTAB 方法，我們的算法相較于 PETSc 和 Ginkgo 分別實(shí)現(xiàn)了3.57倍和 3.78 倍的幾何平均速度提升（最高分別可達(dá) 16.64 倍和 11.73 倍）。
圖 6：與PETSc和Ginkgo的性能比較
通訊作者簡(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]