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

（1.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049；3.北京航空航天大學(xué) 軟件學(xué)院，北京 100191；4.中國原子能科學(xué)研究院，北京 102413）

0 概述

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

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

本文構(gòu)建一個(gè)SpMV 性能預(yù)測模型，將稀疏矩陣的特征以及硬件平臺的特征作為輸入、SpMV 運(yùn)算時(shí)間作為輸出。設(shè)計(jì)CNN 網(wǎng)絡(luò)結(jié)構(gòu)，對各部分特征輸入分別獨(dú)立進(jìn)行特征處理。引入特征融合模塊，將特征融合延遲到CNN 網(wǎng)絡(luò)后期，使CNN 網(wǎng)絡(luò)更好地適應(yīng)SpMV 的輸入表示形式，并使用稀疏矩陣集合進(jìn)行實(shí)驗(yàn)驗(yàn)證。

1 基于CNN 的SpMV 運(yùn)算時(shí)間預(yù)測模型

1.1 模型構(gòu)建

SpMV 運(yùn)算時(shí)間預(yù)測模型為三通道獨(dú)立CNN 模型，網(wǎng)絡(luò)添加了特征融合模塊，如圖1 所示。該模型主要由雙通道稀疏矩陣特征融合以及稀疏矩陣特征與體系結(jié)構(gòu)特征融合兩部分組成，每個(gè)部分的作用如下：

圖1 特征融合CNN 模型結(jié)構(gòu)Fig.1 Structure of feature fusion CNN model

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

2）稀疏矩陣特征與體系結(jié)構(gòu)特征融合。同樣采用特征后融合的方法，首先將融合后的稀疏矩陣特征與體系結(jié)構(gòu)參數(shù)特征分別使用BN（Batch Normalization）層［21］規(guī)范化后進(jìn)行特征融合，得到稀疏矩陣與體系結(jié)構(gòu)參數(shù)的融合特征，然后經(jīng)過Softmax 函數(shù)，最后輸出四分類的預(yù)測值。

在圖像處理領(lǐng)域，對一幅給定RGB 圖像，每個(gè)通道中的第i個(gè)元素都對應(yīng)原始圖像的第i個(gè)像素。在本文所研究的問題中，由于稀疏矩陣采用直方采樣算法提取特征，行特征矩陣和列特征矩陣在數(shù)值上具有不同的統(tǒng)計(jì)意義，即一個(gè)是對行的直方統(tǒng)計(jì)，另一個(gè)是對列的直方統(tǒng)計(jì)，因此并沒有圖像處理中點(diǎn)對點(diǎn)的對應(yīng)關(guān)系［20］?；谏鲜隹紤]，特征融合模塊將對來自稀疏矩陣的特征矩陣以及來自運(yùn)行平臺的體系結(jié)構(gòu)參數(shù)特征分別進(jìn)行處理，在網(wǎng)絡(luò)后期將兩者特征融合，避免了多類別特征過早融合導(dǎo)致特征提取時(shí)造成的相互干擾，同時(shí)降低了算法復(fù)雜度。

1.2 特征數(shù)據(jù)的選取和構(gòu)建

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

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

稀疏矩陣特征包括行特征矩陣、列特征矩陣，以及稀疏矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)。其中，對于稀疏矩陣，采用直方采樣算法對原稀疏矩陣分別進(jìn)行行直方采樣以及列直方采樣，從而得到行特征矩陣以及列特征矩陣。稀疏矩陣的行數(shù)和列數(shù)表征了稀疏矩陣的規(guī)模大小，對于規(guī)模很小的稀疏矩陣，執(zhí)行SpMV 自動調(diào)優(yōu)的耗時(shí)較短，對其進(jìn)行時(shí)間預(yù)測的意義較小。因此，本文實(shí)驗(yàn)剔除了規(guī)模較小的矩陣，即行數(shù)或列數(shù)小于100 的矩陣。

在選定模型的輸入特征后，需要進(jìn)行數(shù)據(jù)采集以及數(shù)據(jù)預(yù)處理，構(gòu)建完整的特征數(shù)據(jù)集。適當(dāng)?shù)臄?shù)據(jù)預(yù)處理能夠提高整個(gè)預(yù)測模型的準(zhǔn)確性，圖2給出了數(shù)據(jù)預(yù)處理的過程，其中，實(shí)線表示數(shù)據(jù)預(yù)處理的流程，虛線表示模型的特征數(shù)據(jù)和標(biāo)注數(shù)據(jù)。由于CNN 網(wǎng)絡(luò)需要大量數(shù)據(jù)作為訓(xùn)練樣本，進(jìn)而獲得樣本間的知識，因此應(yīng)用數(shù)據(jù)增強(qiáng)技術(shù)來獲取足量數(shù)據(jù)。首先，對原始稀疏矩陣進(jìn)行轉(zhuǎn)置，對現(xiàn)有的數(shù)據(jù)進(jìn)行擴(kuò)充產(chǎn)生更多訓(xùn)練數(shù)據(jù)，以便模型學(xué)習(xí)到更多矩陣特征。其次，對擴(kuò)充后的數(shù)據(jù)進(jìn)行篩選和過濾，包括處理無效數(shù)據(jù)、過濾不符合要求的數(shù)據(jù)等。最后，采用直方采樣算法提取稀疏矩陣的行特征以及列特征，并借助yaSpMV［10］工具獲取體系結(jié)構(gòu)參數(shù)以及SpMV 運(yùn)算時(shí)間。

圖2 數(shù)據(jù)預(yù)處理過程Fig.2 Process of data preprocessing

1.3 基于箱圖的時(shí)間標(biāo)簽分類

基于深度學(xué)習(xí)的模型訓(xùn)練需要海量的標(biāo)注數(shù)據(jù)。本文使用箱形圖［22］統(tǒng)計(jì)時(shí)間信息，箱形圖能夠顯示出一組數(shù)據(jù)的最大值、最小值、中位數(shù)以及上下四分位數(shù)，可以用來反映數(shù)據(jù)分布的中心位置和散布范圍，并且可以直觀地識別批量數(shù)據(jù)中的異常值。在箱形圖中，異常值被定義為小于Q1-1.5IIQR或大于Q3+1.5IIQR的值，其中，Q1為第1 個(gè)四分位數(shù)，Q3為第3 個(gè)四分位數(shù)，IIQR為Q3與Q1的差距，即IIQR=Q3-Q1?；谙湫螆D的時(shí)間信息統(tǒng)計(jì)結(jié)果如表2 所示。

表2 基于箱形圖的時(shí)間統(tǒng)計(jì)信息Table 2 Time statistics based on box plot

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

其中：SpMV 運(yùn)算時(shí)間在［0，Q1）、［Q1，Q2）、［Q2，Q3）、［Q3，Q3+1.5IIQR）區(qū)間范圍內(nèi)的分類標(biāo)簽分別為0、1、2、3。SpMV 運(yùn)算時(shí)間預(yù)測模型的訓(xùn)練和推理過程如下：

1）對原始稀疏矩陣數(shù)據(jù)進(jìn)行預(yù)處理，提取稀疏矩陣的特征，得到特征矩陣，包括行特征矩陣和列特征矩陣。

2）獲取硬件平臺的體系結(jié)構(gòu)參數(shù)組合，構(gòu)建多類別特征數(shù)據(jù)集，同時(shí)對每一組參數(shù)設(shè)置執(zhí)行SpMV 運(yùn)算，得到對應(yīng)的SpMV 運(yùn)算時(shí)間，作為訓(xùn)練標(biāo)簽。

3）設(shè)計(jì)基于卷積神經(jīng)網(wǎng)絡(luò)的模型結(jié)構(gòu)，利用步驟1、步驟2 中得到的特征數(shù)據(jù)和標(biāo)簽組成數(shù)據(jù)集，輸入模型中進(jìn)行訓(xùn)練，不斷進(jìn)行參數(shù)優(yōu)化調(diào)整，直至得到訓(xùn)練好的模型。

4）使用新的稀疏矩陣，經(jīng)過數(shù)據(jù)預(yù)處理得到特征數(shù)據(jù)，輸入訓(xùn)練好的模型中得到預(yù)測結(jié)果。

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

為驗(yàn)證本文特征融合CNN 模型的準(zhǔn)確性和有效性，實(shí)驗(yàn)選擇佛羅里達(dá)稀疏矩陣數(shù)據(jù)集［23］進(jìn)行驗(yàn)證，選用格式為MM 格式［24］，獲取并擴(kuò)充得到稀疏矩陣文件1 538 個(gè)。實(shí)驗(yàn)平臺相關(guān)信息如表3 所示。

表3 實(shí)驗(yàn)平臺相關(guān)信息Table 3 Experimental platform related informations

本文特征融合CNN 模型采取將稀疏矩陣特征與體系結(jié)構(gòu)參數(shù)特征先分別卷積池化再進(jìn)行融合的模型進(jìn)行處理，旨在消除輸入特征之間的相互干擾。為驗(yàn)證該模型的有效性，建立一個(gè)對比模型，記為非特征融合CNN 模型。在該模型中，稀疏矩陣特征與體系結(jié)構(gòu)參數(shù)特征在網(wǎng)絡(luò)后期直接融合，這與圖1所展現(xiàn)的特征先消融再融合的結(jié)構(gòu)有著本質(zhì)區(qū)別。

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

表4 數(shù)據(jù)集劃分Table 4 Dataset division

選取以下評價(jià)指標(biāo)對特征融合CNN 三通道獨(dú)立CNN 模型進(jìn)行預(yù)測性能分析：

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

其中：n表示數(shù)據(jù)數(shù)目；yi和′ 分別表示 第i條SpMV執(zhí)行時(shí)間的真實(shí)值和預(yù)測值。

2）ACC 值。使用ACC 值作為準(zhǔn)確率的值，ACC計(jì)算公式如下：

其中：Ctrue和Call分別表示預(yù)測結(jié)果正確的數(shù)目以及全部預(yù)測結(jié)果的數(shù)目。

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

圖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 模型平均預(yù)測準(zhǔn)確率對比Table 5 Comparison of average prediction accuracy between models %

3 結(jié)束語

預(yù)測SpMV 的運(yùn)算時(shí)間有利于加快SpMV 自動調(diào)優(yōu)速度。本文建立基于深度學(xué)習(xí)的SpMV 運(yùn)算時(shí)間預(yù)測模型，結(jié)合稀疏矩陣的行特征、列特征以及運(yùn)行平臺的體系結(jié)構(gòu)參數(shù)等因素，分類別對SpMV 的運(yùn)算時(shí)間進(jìn)行預(yù)測。實(shí)驗(yàn)結(jié)果表明，基于特征融合CNN 的SpMV 運(yùn)算時(shí)間預(yù)測模型的預(yù)測準(zhǔn)確率較高，運(yùn)行速度較快，適合處理不同特點(diǎn)的稀疏矩陣。后續(xù)將對SpMV 自動調(diào)優(yōu)過程中的每組調(diào)優(yōu)參數(shù)均進(jìn)行運(yùn)算時(shí)間預(yù)測，從而尋得耗時(shí)最短的調(diào)優(yōu)參數(shù)組合，以達(dá)到快速自動調(diào)優(yōu)的目的。