基于深度學習的稀疏矩陣向量乘運算性能預測模型

曹中瀟，馮仰德，王 玨，閔維瀟，姚鐵錘，高 岳，王麗華，高付海

（1.中國科學院計算機網絡信息中心，北京 100190；2.中國科學院大學，北京 100049；3.北京航空航天大學 軟件學院，北京 100191；4.中國原子能科學研究院，北京 102413）

0 概述

在科學計算和工程應用領域中，很多實際問題的求解通常可以轉換為求解線性代數方程組Ax=b，而大部分實際問題中遇到的矩陣A往往是稀疏的，因此稀疏矩陣向量乘（Sparse Matrix Vector Multiplication，SpMV）是數值計算的主要組成部分，也是計算耗時最多的部分。在使用迭代法求解大規模稀疏線性方程組時，SpMV 被重復調用，SpMV 計算效率直接影響了整體求解效率［1］。由于存儲訪問不規則等特性，SpMV 運行效率一般低于單個處理器浮點性能峰值的10%［2］，在實際應用中往往成為性能瓶頸。文獻［3-4］介紹了BCSR和BELLPACK 存儲格式的變體。文獻［5］提出一種新型存儲格式CSX，該格式利用矩陣中的子結構來壓縮元數據。文獻［6］提出一種CSR5格式，該格式能在CPU、GPU、Xeon Phi等平臺上提供高吞吐量SpMV。文獻［7］提出一種在向量多處理機上實現稀疏矩陣乘法的算法SEGMV。文獻［8］提出一種新型存儲格式Cocktail 并基于該格式開發clSpMV 框架，clSpMV 框架能夠在運行時分析各種稀疏矩陣，在給定目標平臺上為其推薦最優存儲格式。文獻［9］提出一種新型存儲格式CVR，該格式同時處理輸入矩陣中的多個行以提高緩存效率，并將它們分成多個SIMD 通道，以便利用現代處理器中的向量處理單元。文獻［10］提出一種基于COO 格式的BCCOO 格式。文獻［11-13］利用自動調優技術來提高SpMV 性能以及跨平臺的可移植性。傳統自動調優方法主要關注在硬件上的參數搜索空間中進行搜索，搜索空間大，且對每一次搜索的參數設置都要執行SpMV運算，導致自動調優的耗時大幅增加。因此，研究SpMV的性能模型對提高自動調優性能具有重要意義。

一些學者基于機器學習方法構建SpMV 算法生成庫。李佳佳等［14］提出一個SMAT 自動調優器，對于一個給定的稀疏矩陣，SMAT 結合矩陣特征選擇并從DIA、ELL、CSR、COO 等4 種格式中返回最優的存儲格式。SEDAGHATI 等［15］構建一個決策模型，實現對給定目標平臺上的稀疏矩陣自動選擇最優存儲格式。BENATIA 等［16］采用SVM 方法來解決存儲格式選擇問題。NISA 等［17］結合決策樹和SVM 兩種方法，實現一個存儲格式預測模型。ZHAO 等［18-19］考慮運行時預測開銷以及格式轉換開銷的影響，設計回歸模型以及基于神經網絡的時間序列預測模型，有效捕獲了開銷以及格式預測和轉換對整體程序性能的影響。ZHAO 等［20］將深度學習方法引入SpMV的最優稀疏矩陣存儲格式選擇中，提出Late-merging卷積神經網絡（Convolutional Neural Network，CNN）結構，有效地將深度學習方法應用于高性能計算問題，但該模型缺乏對體系結構參數的考慮。上述方法主要用于稀疏矩陣存儲格式選擇，并不適用于SpMV 性能預測。對于SpMV，由于輸入的特征數據來源于稀疏矩陣和體系結構參數，數據含義以及表示形式與圖像處理網絡中的輸入數據不同，因此圖像處理領域中的CNN 網絡結構不再適用，需要設計新的CNN 網絡來滿足SpMV 運算時間預測的需求。

本文構建一個SpMV 性能預測模型，將稀疏矩陣的特征以及硬件平臺的特征作為輸入、SpMV 運算時間作為輸出。設計CNN 網絡結構，對各部分特征輸入分別獨立進行特征處理。引入特征融合模塊，將特征融合延遲到CNN 網絡后期，使CNN 網絡更好地適應SpMV 的輸入表示形式，并使用稀疏矩陣集合進行實驗驗證。

1 基于CNN 的SpMV 運算時間預測模型

1.1 模型構建

SpMV 運算時間預測模型為三通道獨立CNN 模型，網絡添加了特征融合模塊，如圖1 所示。該模型主要由雙通道稀疏矩陣特征融合以及稀疏矩陣特征與體系結構特征融合兩部分組成，每個部分的作用如下：

圖1 特征融合CNN 模型結構Fig.1 Structure of feature fusion CNN model

1）雙通道稀疏矩陣特征融合。考慮到稀疏矩陣的表示以及CNN 具備提取矩陣特征的能力，本文設計雙通道稀疏矩陣特征融合模塊，獲取稀疏矩陣的特征。通過直方采樣算法從稀疏矩陣中提取出行特征矩陣以及列特征矩陣，采用特征后融合的方法，將它們分別輸入各自的卷積神經網絡中，在后期進行線性拼接融合，并輸入至全連接層，進而得到稀疏矩陣的融合特征。

2）稀疏矩陣特征與體系結構特征融合。同樣采用特征后融合的方法，首先將融合后的稀疏矩陣特征與體系結構參數特征分別使用BN（Batch Normalization）層［21］規范化后進行特征融合，得到稀疏矩陣與體系結構參數的融合特征，然后經過Softmax 函數，最后輸出四分類的預測值。

在圖像處理領域，對一幅給定RGB 圖像，每個通道中的第i個元素都對應原始圖像的第i個像素。在本文所研究的問題中，由于稀疏矩陣采用直方采樣算法提取特征，行特征矩陣和列特征矩陣在數值上具有不同的統計意義，即一個是對行的直方統計，另一個是對列的直方統計，因此并沒有圖像處理中點對點的對應關系［20］。基于上述考慮，特征融合模塊將對來自稀疏矩陣的特征矩陣以及來自運行平臺的體系結構參數特征分別進行處理，在網絡后期將兩者特征融合，避免了多類別特征過早融合導致特征提取時造成的相互干擾，同時降低了算法復雜度。

1.2 特征數據的選取和構建

SpMV 實際運行的時間與多種因素有關，例如矩陣的規模大小、矩陣的非零元素個數、運行平臺的體系結構參數等。在構建模型時，單一特征通常只側重于某一方面，為了提高模型的可靠性和準確性，采取特征融合的方法來兼顧多種特征的信息。為此，本文選取并構建SpMV 運算時間預測的多類別輸入特征，將SpMV 數據特征分為兩類，即稀疏矩陣特征和硬件平臺特征，如表1 所示。

表1 輸入特征信息Table 1 Input feature information

稀疏矩陣特征包括行特征矩陣、列特征矩陣，以及稀疏矩陣的行數、列數、非零元素的個數。其中，對于稀疏矩陣，采用直方采樣算法對原稀疏矩陣分別進行行直方采樣以及列直方采樣，從而得到行特征矩陣以及列特征矩陣。稀疏矩陣的行數和列數表征了稀疏矩陣的規模大小，對于規模很小的稀疏矩陣，執行SpMV 自動調優的耗時較短，對其進行時間預測的意義較小。因此，本文實驗剔除了規模較小的矩陣，即行數或列數小于100 的矩陣。

在選定模型的輸入特征后，需要進行數據采集以及數據預處理，構建完整的特征數據集。適當的數據預處理能夠提高整個預測模型的準確性，圖2給出了數據預處理的過程，其中，實線表示數據預處理的流程，虛線表示模型的特征數據和標注數據。由于CNN 網絡需要大量數據作為訓練樣本，進而獲得樣本間的知識，因此應用數據增強技術來獲取足量數據。首先，對原始稀疏矩陣進行轉置，對現有的數據進行擴充產生更多訓練數據，以便模型學習到更多矩陣特征。其次，對擴充后的數據進行篩選和過濾，包括處理無效數據、過濾不符合要求的數據等。最后，采用直方采樣算法提取稀疏矩陣的行特征以及列特征，并借助yaSpMV［10］工具獲取體系結構參數以及SpMV 運算時間。

圖2 數據預處理過程Fig.2 Process of data preprocessing

1.3 基于箱圖的時間標簽分類

基于深度學習的模型訓練需要海量的標注數據。本文使用箱形圖［22］統計時間信息，箱形圖能夠顯示出一組數據的最大值、最小值、中位數以及上下四分位數，可以用來反映數據分布的中心位置和散布范圍，并且可以直觀地識別批量數據中的異常值。在箱形圖中，異常值被定義為小于Q1-1.5IIQR或大于Q3+1.5IIQR的值，其中，Q1為第1 個四分位數，Q3為第3 個四分位數，IIQR為Q3與Q1的差距，即IIQR=Q3-Q1。基于箱形圖的時間信息統計結果如表2 所示。

表2 基于箱形圖的時間統計信息Table 2 Time statistics based on box plot

為使數據類別劃分盡可能均勻，實驗采用Q1、Q2、Q3這3 個四分位點作為分界點，將摒棄異常值之后的數據劃分為4 個部分，分別對應0、1、2、3 等4 個類別（Class）。不同類別對應的時間（t）情況如式（1）所示：

其中：SpMV 運算時間在［0，Q1）、［Q1，Q2）、［Q2，Q3）、［Q3，Q3+1.5IIQR）區間范圍內的分類標簽分別為0、1、2、3。SpMV 運算時間預測模型的訓練和推理過程如下：

1）對原始稀疏矩陣數據進行預處理，提取稀疏矩陣的特征，得到特征矩陣，包括行特征矩陣和列特征矩陣。

2）獲取硬件平臺的體系結構參數組合，構建多類別特征數據集，同時對每一組參數設置執行SpMV 運算，得到對應的SpMV 運算時間，作為訓練標簽。

3）設計基于卷積神經網絡的模型結構，利用步驟1、步驟2 中得到的特征數據和標簽組成數據集，輸入模型中進行訓練，不斷進行參數優化調整，直至得到訓練好的模型。

4）使用新的稀疏矩陣，經過數據預處理得到特征數據，輸入訓練好的模型中得到預測結果。

2 實驗與結果分析

為驗證本文特征融合CNN 模型的準確性和有效性，實驗選擇佛羅里達稀疏矩陣數據集［23］進行驗證，選用格式為MM 格式［24］，獲取并擴充得到稀疏矩陣文件1 538 個。實驗平臺相關信息如表3 所示。

表3 實驗平臺相關信息Table 3 Experimental platform related informations

本文特征融合CNN 模型采取將稀疏矩陣特征與體系結構參數特征先分別卷積池化再進行融合的模型進行處理，旨在消除輸入特征之間的相互干擾。為驗證該模型的有效性，建立一個對比模型，記為非特征融合CNN 模型。在該模型中，稀疏矩陣特征與體系結構參數特征在網絡后期直接融合，這與圖1所展現的特征先消融再融合的結構有著本質區別。

對于兩個模型，將預處理得到的數據按10∶1 的比例分為訓練集和驗證集，數據量信息如表4 所示。模型均在相同的訓練集以及驗證集上進行實驗。由于數據量較大，如果直接將訓練數據輸入預測模型進行訓練，每輪迭代時間較長，參數更新緩慢，因此采用梯度下降法中的mini-batch 訓練方法進行小批量訓練，結合反向傳播算法優化參數，降低內存負載，提高訓練速度。模型訓練參數設置如下：損失函數為CrossEntropyLoss，優化器為optim.Adam，學習率為1e-2，共訓練50 批次，每批次數據量為1 024。

表4 數據集劃分Table 4 Dataset division

選取以下評價指標對特征融合CNN 三通道獨立CNN 模型進行預測性能分析：

1）Loss 值。使用平均絕對誤差（Mean Absolute Error，MAE）值表示Loss 值，MAE 計算公式如下：

其中：n表示數據數目；yi和′ 分別表示 第i條SpMV執行時間的真實值和預測值。

2）ACC 值。使用ACC 值作為準確率的值，ACC計算公式如下：

其中：Ctrue和Call分別表示預測結果正確的數目以及全部預測結果的數目。

圖3給出了未添加特征融合模塊的非特征融合CNN模型以及添加了特征融合模塊的三通道獨立CNN 模型的Loss 值隨迭代輪次的變化趨勢圖。從圖3 中可以看出，特征融合CNN 模型比非特征融合CNN 模型的收斂速度更快，收斂效果更好。圖4 給出了兩個模型的ACC 值隨迭代輪次的變化趨勢圖，兩個模型在訓練集以及驗證集上的平均準確率如表5 所示。可見，特征融合CNN 模型在收斂過程中的預測準確率更高，表現出更好的泛化能力，說明本文對不同特征之間關聯性的考慮及處理使得特征提取更加全面多樣且層次性更強，從而進一步提升了預測準確率。

圖3 特征融合CNN模型與非特征融合CNN模型的Loss值對比Fig.3 Comparison of Loss values between feature fusion CNN model and non-feature fusion CNN model

圖4 特征融合CNN模型與非特征融合CNN模型的ACC值對比Fig.4 Comparison of ACC values between feature fusion CNN model and non-feature fusion CNN model

表5 模型平均預測準確率對比Table 5 Comparison of average prediction accuracy between models %

3 結束語

預測SpMV 的運算時間有利于加快SpMV 自動調優速度。本文建立基于深度學習的SpMV 運算時間預測模型，結合稀疏矩陣的行特征、列特征以及運行平臺的體系結構參數等因素，分類別對SpMV 的運算時間進行預測。實驗結果表明，基于特征融合CNN 的SpMV 運算時間預測模型的預測準確率較高，運行速度較快，適合處理不同特點的稀疏矩陣。后續將對SpMV 自動調優過程中的每組調優參數均進行運算時間預測，從而尋得耗時最短的調優參數組合，以達到快速自動調優的目的。