機(jī)器學(xué)習(xí)算法可近似性的量化評估分析

江樹浩 鄢貴海 李家軍 盧文巖 李曉維

1(計算機(jī)體系結(jié)構(gòu)國家重點實驗室(中國科學(xué)院計算技術(shù)研究所) 北京 100190)2(中國科學(xué)院大學(xué) 北京 100049)

機(jī)器學(xué)習(xí)算法可近似性的量化評估分析

江樹浩1,2鄢貴海1李家軍1,2盧文巖1,2李曉維1

1(計算機(jī)體系結(jié)構(gòu)國家重點實驗室(中國科學(xué)院計算技術(shù)研究所) 北京 100190)2(中國科學(xué)院大學(xué) 北京 100049)

(jiangshuhao@ict.ac.cn)

近年來，以神經(jīng)網(wǎng)絡(luò)為代表的機(jī)器學(xué)習(xí)算法發(fā)展迅速并被廣泛應(yīng)用在圖像識別、數(shù)據(jù)搜索乃至金融趨勢分析等領(lǐng)域.而隨著問題規(guī)模的擴(kuò)大和數(shù)據(jù)維度的增長，算法能耗問題日益突出，由于機(jī)器學(xué)習(xí)算法自身擁有的近似特性，近似計算這種犧牲結(jié)果的少量精確度降低能耗的技術(shù)，被許多研究者用來解決學(xué)習(xí)算法的能耗問題.我們發(fā)現(xiàn)，目前的工作大多專注于利用特定算法的近似特性而忽視了不同算法近似特性的差別對能耗優(yōu)化帶來的影響，而為了分類任務(wù)使用近似計算時能夠做出能耗最優(yōu)的選擇，了解算法“可近似性”上的差異對近似計算優(yōu)化能耗至關(guān)重要.因此，選取了支持向量機(jī)(SVM)、隨機(jī)森林(RF)和神經(jīng)網(wǎng)絡(luò)(NN) 3類常用的監(jiān)督型機(jī)器學(xué)習(xí)算法，評估了針對不同類型能耗時不同算法的可近似性，并建立了存儲污染敏感度、訪存污染敏感度和能耗差異度等指標(biāo)來表征算法可近似性的差距，評估得到的結(jié)論將有助于機(jī)器學(xué)習(xí)算法在使用近似計算技術(shù)時達(dá)到最優(yōu)化能耗的目的.

監(jiān)督機(jī)器學(xué)習(xí)算法；近似計算；可近似性；能耗優(yōu)化

機(jī)器學(xué)習(xí)算法被廣泛應(yīng)用在識別、數(shù)據(jù)分析和搜索等領(lǐng)域的分類問題上.由于這類問題往往涉及大量高維度數(shù)據(jù)、復(fù)雜的訓(xùn)練及預(yù)測方法，算法的執(zhí)行過程會消耗大量的能量.因此如何降低監(jiān)督學(xué)習(xí)算法的能耗已經(jīng)成為計算機(jī)領(lǐng)域研究熱點之一.

近似計算作為一種非常有潛力的技術(shù)被用來優(yōu)化機(jī)器學(xué)習(xí)算法的能耗.如文獻(xiàn)[1]通過多種近似方法使得KNN算法的能耗降低了55%，文獻(xiàn)[2]通過對人工神經(jīng)網(wǎng)的近似獲得了43%的能耗節(jié)省.這些近似計算工作的主要思路是利用算法訓(xùn)練或預(yù)測的過程中結(jié)果對誤差的容忍性，通過近似數(shù)據(jù)或省略部分非關(guān)鍵計算，只引入少量的輸出上的誤差而極大地降低算法的能耗.

我們發(fā)現(xiàn)，目前的工作大多專注于利用特定算法的近似特性而忽視了不同算法近似特性的差別對能耗優(yōu)化帶來的影響.我們定義“可近似性”(approximatability，Xbility)為近似計算所節(jié)省的能耗Esavings與輸出結(jié)果質(zhì)量下降Qloss的比值：

(1)

其中，對Qloss的度量需要根據(jù)具體的問題確定，如在圖像處理應(yīng)用中，Qloss通常以近似前后圖像峰值信噪比(PSNR)損失值為度量標(biāo)準(zhǔn)，在本文中Qloss為算法近似前后分類準(zhǔn)確度的損失值.可近似性表征了單位結(jié)果質(zhì)量的下降所能換取的能耗節(jié)省.了解不同算法“可近似性”的差異對近似計算優(yōu)化能耗有著非常重要的作用，對算法“可近似性”的評估可以保證應(yīng)用使用近似計算時選出能耗最優(yōu)的算法.

對算法可近似性的評估首先需要確定要優(yōu)化的能耗類型.機(jī)器學(xué)習(xí)算法處理分類問題時分為2個階段：訓(xùn)練階段和分類階段，相比于分類階段，訓(xùn)練階段中影響能耗因素較多，如學(xué)習(xí)率、batch大小和懲罰因子等，這些因素使得在訓(xùn)練階段中可近似性評估的公平性難以被保證；其次對應(yīng)用來說，訓(xùn)練過程的主要目的是確定分類所需的參數(shù)值，可以通過離線執(zhí)行預(yù)先設(shè)定好，而算法分類階段是解決問題的過程，對應(yīng)用的執(zhí)行不可或缺，因此本文主要關(guān)注分類階段的能耗.根據(jù)計算系統(tǒng)層次和耗能因素，我們將分類階段的能耗分解為

E=ESMS+ESMA+EMMA+EMCP,

(2)

其中，ESMS代表樣本數(shù)據(jù)的存儲能耗，本文中指樣本數(shù)據(jù)存儲在DRAM存儲單元中消耗的能量；ESMA代表樣本訪存的能耗.式(2)等號右邊前2項的能耗值主要由樣本數(shù)據(jù)量所決定而與算法類型無關(guān)，因此對不同算法，這2項的近似前能耗值相等，近似后的能耗差異由算法可近似性差異所決定.而式(2)的最后2項為算法相關(guān)能耗，其近似前能耗值與算法類型相關(guān)，近似后的能耗差異受算法可近似性和近似前能耗差異2方面的影響，其中EMMA代表訪存算法參數(shù)所消耗的能量，EMCP代表算法計算所消耗的能量.

本文選取了3類常用的機(jī)器學(xué)習(xí)算法：支持向量機(jī)(SVM)、隨機(jī)森林(RF)和神經(jīng)網(wǎng)絡(luò)(NN)算法(其中NN算法包括卷積神經(jīng)網(wǎng)(CNN)和多層感知機(jī)(MLP))，在保證初始分類準(zhǔn)確度一致的前提下，評估了針對上述不同類型的能耗不同算法可近似性的差異.

評估結(jié)果表明:算法可近似性的差異確實會對能耗優(yōu)化產(chǎn)生重要影響，并且針對不同能耗，算法的可近似性并不固定.首先，針對樣本存儲能耗，對近似產(chǎn)生的突變噪聲更加魯棒的RF算法的可近似性最高，與NN算法相比，可多節(jié)省14%的存儲能耗.其次，針對樣本訪存能耗，NN算法由于訓(xùn)練過程復(fù)雜易陷入局部最優(yōu)等不穩(wěn)定的特點使得在降低樣本數(shù)據(jù)精度時分類準(zhǔn)確度下降明顯，而SVM算法和RF算法對訪存近似更加魯棒，平均節(jié)省能耗比NN算法分別多16%和11%.最后，針對與算法有關(guān)的參數(shù)訪存能耗和計算能耗，由于不同算法近似前的能耗差異很大，算法的可近似性差異對能耗優(yōu)化的影響將十分有限，分類應(yīng)用選擇算法的依據(jù)將更多取決于參數(shù)訪存能耗和計算能耗的差異度.

為了量化不同算法針對不同能耗類型的可近似性，我們建立了樣本存儲污染敏感度、樣本訪存污染敏感度和能耗差異度等評估指標(biāo)，這些指標(biāo)可以為分類應(yīng)用選擇能耗最優(yōu)的算法提供依據(jù).

1 相關(guān)工作

近似計算技術(shù)利用了算法對誤差的容忍特性，其基本原理是通過誤差注入等靜態(tài)分析手段，得到并控制近似技術(shù)的近似程度，使得近似后的算法仍然滿足某些指標(biāo)(如PSNR、MSE、分類準(zhǔn)確度等)的要求.但目前的工作大多專注于利用特定算法，本文在此基礎(chǔ)上評估了不同算法的可近似性差異，并分析了這種差異對算法能耗優(yōu)化帶來的影響.

針對多種類型的能耗，近似計算技術(shù)提出了多種提高效能的方法，常用的方法包括降低存儲單元刷新率、電壓調(diào)節(jié)、使用非精確邏輯電路、省略非關(guān)鍵計算、比特位截斷等[1-12].下面根據(jù)能耗類型(對應(yīng)式(2))介紹近似計算技術(shù)的相關(guān)工作.

1) 針對存儲能耗.文獻(xiàn)[13-14]等工作發(fā)現(xiàn)大多數(shù)DRAM存儲單元數(shù)據(jù)可保持時間高于目前設(shè)定的刷新時間，因此可以適當(dāng)延長DRAM刷新時間，節(jié)省大量的存儲能耗，其中文獻(xiàn)[13]的方法能夠降低74.6%的刷新頻率、16.1%的DRAM能耗和8.6%的系統(tǒng)整體能耗.電壓調(diào)節(jié)技術(shù)也是降低存儲能耗的手段之一，文獻(xiàn)[15-17]分別通過適當(dāng)?shù)亟档蚦ache、寄存器和功能性單元的供電電壓來節(jié)省存儲能耗.

2) 針對訪存能耗.位截斷技術(shù)是通過近似數(shù)據(jù)來降低訪存能耗的重要方法之一，文獻(xiàn)[18]通過比特位截斷將k近鄰算法和高斯混合聚類算法的能耗平均降低了50%.文獻(xiàn)[19]通過省略非重要節(jié)點的訪存操作節(jié)省數(shù)據(jù)訪存能耗.此外，對數(shù)據(jù)進(jìn)行有損壓縮也是降低訪存能耗的方法之一，實驗表明通過對GPGPU和片外存儲間傳輸?shù)母↑c數(shù)進(jìn)行壓縮可以減少41%的GPGPU負(fù)載[20].

3) 針對計算能耗.文獻(xiàn)[21-23]等使用近似重用技術(shù)優(yōu)化計算能耗，通過對輸入相近程度的有效度量和條件分支結(jié)果的有效預(yù)測，相似的輸入結(jié)果只需被計算一次，實驗結(jié)果表明近似重用技術(shù)可獲得3.1倍的能耗節(jié)省.文獻(xiàn)[24-25]等工作通過設(shè)計近似加法器、乘法器等近似電路代替精確電路降低計算能耗，文獻(xiàn)[2,26]則根據(jù)神經(jīng)網(wǎng)絡(luò)中各個節(jié)點對分類結(jié)果的影響力，近似對結(jié)果影響較小的節(jié)點計算達(dá)到優(yōu)化網(wǎng)絡(luò)能耗的目的.

2 樣本存儲能耗的算法可近似性評估

樣本在主存中的存儲能耗ESMS是分類應(yīng)用整體能耗的重要部分，根據(jù)文獻(xiàn)[15,27]的能耗模型，表1評估了在不同應(yīng)用中式(2)中各部分能耗所占比例，其中樣本存儲能耗占整體能耗的比例平均為25%左右.需要指出的是，各部分能耗比例是隨具體的參數(shù)可變的，如存儲時長、樣本數(shù)目等，本文列出的能耗分布比例是通過評估NN算法分類單樣本的過程獲得.

Table 1 Distribution of Energy Consumption on Different Datasets

節(jié)省存儲能耗是近似計算優(yōu)化能耗的一個重要方面，而隨著DRAM密度越來越大，單位時間內(nèi)需要刷新的存儲單元越來越多，刷新操作的能耗開銷越來越大[25].降低DRAM刷新率已成為降低存儲能耗最常用的存儲近似手段[13-14].

DRAM刷新率的降低會造成一部分存儲單元的數(shù)據(jù)丟失，對于分類任務(wù)的樣本數(shù)據(jù)，這種近似手段將導(dǎo)致部分?jǐn)?shù)據(jù)產(chǎn)生較大偏差，這相當(dāng)于這些數(shù)據(jù)點受到噪聲干擾而導(dǎo)致數(shù)值突變.DRAM刷新率越低，受到干擾的數(shù)據(jù)點比例越高，算法分類精度受到的影響越大.為分析3種算法對降低刷新率方法的可近似性，我們評估了不同比例的噪聲數(shù)據(jù)下分類準(zhǔn)確度的下降程度.具體做法為：選擇4個常用數(shù)據(jù)集，分別為HAR,Iris,MNIST和Adult數(shù)據(jù)集，在每個數(shù)據(jù)集上，通過適當(dāng)?shù)挠?xùn)練保證3類算法的初始分類性能分類準(zhǔn)確度差異小于1%(NN算法在不同數(shù)據(jù)集上使用的結(jié)構(gòu)略有差異，在MNIST數(shù)據(jù)集上，算法為LeNet[28]的CNN結(jié)構(gòu)，而在其他3個數(shù)據(jù)集上算法使用多層感知機(jī)(MLP)結(jié)構(gòu))，最后設(shè)定不同數(shù)值的噪聲點比例，比較其對算法分類精度造成的影響，為使噪聲點數(shù)據(jù)和原數(shù)據(jù)有足夠大的差異，我們將噪聲點的值設(shè)定為原數(shù)據(jù)的相反數(shù).

評估結(jié)果如圖1所示，橫坐標(biāo)代表噪聲數(shù)據(jù)點占所有樣本數(shù)據(jù)的比例，縱坐標(biāo)代表算法的分類準(zhǔn)確度.從圖1中我們可以看到，不同算法的可近似性有明顯的差異，其中RF算法對噪聲的干擾有最好的可近似性，MLP算法的可近似性最差，SVM算法的可近似性介于二者之間.如在HAR數(shù)據(jù)集上，當(dāng)噪聲點比例為10%時，RF算法的分類準(zhǔn)確度仍能達(dá)到90%以上，而MLP算法的分類精度僅為53%左右.

Fig. 1 Comparison on memory storage (MS) approximatability of different algorithms圖1 不同算法的存儲可近似性比較

需要指出的是，這種差異性的大小也會受到應(yīng)用的影響，對于分類結(jié)果對輸入噪聲不敏感的應(yīng)用，算法間的可近似性差異較小.如在Adult數(shù)據(jù)集中，SVM，RF和MLP三種算法的曲線趨勢非常接近.另一個有趣的發(fā)現(xiàn)為：在MNIST數(shù)據(jù)集(圖1(c))上，CNN的可近似性要高于SVM算法，而在其他數(shù)據(jù)集上，相似結(jié)構(gòu)的MLP算法可近似性卻低于SVM算法，我們認(rèn)為這是由于卷積神經(jīng)網(wǎng)的池化層對特征的下采樣過程具有去除部分噪聲點的能力，因而增強(qiáng)了卷積神經(jīng)網(wǎng)的抗突變噪聲的能力.

為了以數(shù)值化的形式表征算法的可近似性的差異，我們對上述曲線進(jìn)行線性擬合，擬合斜率的絕對值我們定義為存儲污染敏感度SMS，SMS表征了單位比例的噪聲數(shù)據(jù)所造成的分類精度的平均下降程度，SMS越小，說明算法對存儲近似的敏感度越低，能獲得的存儲能耗節(jié)省越大.表2列出了3種算法各自的存儲污染敏感度，根據(jù)算法存儲污染敏感度的數(shù)值可以得出：噪聲數(shù)據(jù)比例每增加1%，SVM算法的分類精度平均下降1.78%，RF算法平均下降0.7%，NN算法平均下降1.95%.

Table 2 SMS of Three Algorithms表2 3種算法存儲污染敏感度

根據(jù)文獻(xiàn)[13]，DRAM存儲單元錯誤率和刷新時間呈對數(shù)關(guān)系，而存儲能耗隨刷新時間的增加線性遞減[14]，根據(jù)這2種關(guān)系，我們可以得到在滿足應(yīng)用對分類精度最低要求的情況下不同算法的能耗節(jié)省值.如圖2所示，橫坐標(biāo)軸括號內(nèi)數(shù)值代表了應(yīng)用對分類精度的最低要求，其決定了算法能容忍的存儲單元錯誤率;縱坐標(biāo)代表了通過降低刷新率延長刷新時間所能節(jié)省的能耗，初始刷新時間的設(shè)定參照了文獻(xiàn)[13]中的結(jié)果.總體上，RF算法在4個數(shù)據(jù)集中都能節(jié)省最多的存儲能耗，RF算法的平均節(jié)省能耗值比SVM算法多10%以上，比NN算法可節(jié)省能耗多14%以上.而在HAR數(shù)據(jù)集上，RF算法的節(jié)省能耗比NN算法可節(jié)省能耗多25%.

Fig. 2 The comparison on MS energy savings of different algorithms圖2 3種算法的可節(jié)省存儲能耗比較

上述分析說明，針對樣本存儲能耗ESMS，相比于其他2種算法，RF算法由于對突變噪聲的容忍程度最高，因而具有最低的存儲污染敏感度，在使用降低刷新率技術(shù)時能夠節(jié)省更多的存儲能耗.

Fig. 4 Comparison on memory access (MA) approximatability of different algorithms圖4 3種算法的訪存可近似性比較

3 樣本訪存能耗的算法可近似性評估

樣本訪存能耗ESMA，即從主存向緩存?zhèn)鬏敇颖緮?shù)據(jù)的能耗，樣本訪存能耗是分類應(yīng)用總能耗中不可忽略的一部分，而且隨樣本數(shù)據(jù)量增大而增多.根據(jù)文獻(xiàn)[29]，從主存?zhèn)鬏敂?shù)據(jù)到緩存的能耗為片內(nèi)數(shù)據(jù)傳輸能耗的19倍，表1顯示單樣本分類情況下ESMA占整體能耗的平均比例為18.79%，因此通過近似計算技術(shù)優(yōu)化樣本訪存能耗十分必要.

位截斷是最直觀和最常用的降低訪存能耗的近似計算方法，圖3表示了針對浮點數(shù)的比特位截斷技術(shù)的方式，該方法的近似對象是浮點數(shù)的尾數(shù)部分，通過舍棄尾數(shù)部分的部分低位而只保留數(shù)據(jù)的高位部分降低訪存能耗.

Fig. 3 Overview of precision scaling圖3 位截斷技術(shù)示意圖

位截斷技術(shù)會造成數(shù)據(jù)的精度下降，原本數(shù)值相近的數(shù)據(jù)差異變得更小，甚至可能會被表示為同一數(shù)值.隨著截斷位數(shù)的增多，樣本數(shù)據(jù)將更加“模糊”，更不容易被正確分類.對算法而言，算法對模糊數(shù)據(jù)的區(qū)分度越好，算法可近似性就會越高，可節(jié)省更多的訪存能耗.

為了評估算法針對樣本訪存能耗的可近似性，我們在不同數(shù)據(jù)集上分別用3種機(jī)器學(xué)習(xí)算法分類，在3種算法的初始分類精度一致(<1%)的前提下，比較不同程度的比特位近似下算法分類精度受到的影響.實驗結(jié)果如圖4所示，橫軸和縱軸分別代表被舍棄的低位位數(shù)和分類精度，虛線代表應(yīng)用對分類精度的最低要求.

我們從圖4中發(fā)現(xiàn)，不同于算法的存儲可近似性，使用位截斷技術(shù)時，隨著截斷比特位數(shù)的增加，算法分類準(zhǔn)確度的下降趨勢具有明顯的階段性.在截斷位數(shù)較少時(階段1)，截斷位數(shù)的增加只會造成分類精度的微量的降低；而當(dāng)截斷尾數(shù)增加到某一臨界位后(階段2)，分類準(zhǔn)確度明顯下降，截斷位數(shù)的增加對分類準(zhǔn)確度的影響十分顯著.

其次，圖4的結(jié)果表明在近似訪存能耗時，不同算法的可近似性有比較明顯的差異.如在HAR數(shù)據(jù)集上，SVM算法的臨界值為10位，而NN算法的臨界值僅為7位.此外，算法針對訪存能耗的可近似性差異也受到應(yīng)用的影響.在Iris數(shù)據(jù)集中，SVM算法和RF算法的臨界值均為10，而NN的算法的臨界值僅比其他2種算法少一位.總體來說，SVM算法和RF算法在使用比特位截斷技術(shù)時可近似性較好，而NN算法的可近似性較差.

我們通過訪存污染敏感度SMA來量化針對訪存能耗的算法可近似性，由于階段2的算法分類準(zhǔn)確度過低，而階段1的分類準(zhǔn)確度下降緩慢基本能夠滿足應(yīng)用要求，因此以臨界位定義訪存污染敏感度SMA：

(3)

其中,分子代表尾數(shù)范圍(本文中該值為11)，分母為臨界位的大小.SMA的范圍為1～+∞，1代表算法的臨界值達(dá)到了尾數(shù)的最大范圍，正無窮代表臨界值為0，即算法不能忍受對樣本數(shù)據(jù)的近似，SMA越小，說明算法對比特位截斷的敏感度越低，可節(jié)省的訪存能耗越多.

通過式(3)，我們得到3種算法在不同應(yīng)用的SMA值，如表3所示，根據(jù)平均訪存污染敏感度值，SVM算法的可近似性最高，NN算法的可近似性最低，RF算法介于兩者之間.

Table 3 SMA of Three Algorithms表3 3種算法訪存污染敏感度

節(jié)省訪存能耗的多少和截斷位數(shù)成正比，圖5表示了在滿足應(yīng)用對分類精度最低要求的情況下不同算法的能耗節(jié)省值.從圖5中可以看出，在HAR數(shù)據(jù)集上，SVM算法可節(jié)省的訪存能耗分別比NN算法和RF算法多37%和10%；而對于平均可節(jié)省能耗，SVM算法可比NN算法平均多節(jié)省16%的訪存能耗.

Fig. 5 The comparison on MA energy savings of different algorithms圖5 3種算法的可節(jié)省訪存能耗比較

上述分析說明，針對樣本存儲能耗ESMA，相比于其他2種算法，SVM算法由于對突變噪聲的容忍程度最高，因而具有最低的訪存污染敏感度，在使用比特位截斷技術(shù)時能夠節(jié)省更多的存儲能耗.

4 算法參數(shù)訪存能耗和計算能耗的評估方法

參數(shù)訪存能耗EMMA和計算能耗EMCP(這里統(tǒng)稱為分類能耗)均與算法類型有關(guān)，即在應(yīng)用近似計算技術(shù)前，不同算法的EMMA和EMCP是有差別的，不同算法近似后的能耗對比不僅取決于通過近似計算所能節(jié)省的能耗，還與算法的近似前能耗的差異有關(guān).因此在評估不同算法針對這部分能耗的可近似性時，需要首先考慮算法近似前的初始能耗.

需要指出的是，參數(shù)訪存能耗EMMA的評估不可省略，因為對于某些算法，其參數(shù)數(shù)據(jù)量很大，而且在樣本數(shù)量較少時，計算能耗所占比例并不高.

本節(jié)著重分析單樣本分類任務(wù)時的初始參數(shù)訪存能耗與計算能耗的評估方法，首先我們將建立參數(shù)訪存計算能耗模型，隨后我們在算法指令層分別介紹不同算法的參數(shù)訪存負(fù)載和計算負(fù)載組成.

4.1 參數(shù)訪存/計算能耗模型

正如引言所提到的，單樣本分類能耗(EMODEL)由2部分組成：算法參數(shù)的訪存能耗EMMA和計算能耗EMCP，以FMMA代表算法參數(shù)的訪存負(fù)載(訪存操作的數(shù)目)，EMCP代表算法計算負(fù)載(主要ALU操作的數(shù)目)，則分類能耗模型為

EMODEL=λμ×FMMA+μ×EMCP,

(4)

其中μ表示一個浮點數(shù)運算操作的平均能耗，λμ為一次訪存操作的能耗.根據(jù)文獻(xiàn)[27]，一個浮點數(shù)訪存操作所消耗的能量是一個浮點數(shù)運算能耗的15倍，即λ=15，下面的分析我們將沿用這一設(shè)定.

4.2 SVM算法的負(fù)載分析

支持向量機(jī)(SVM)算法的基本原理是通過訓(xùn)練數(shù)據(jù)尋找一個滿足分類要求的最優(yōu)分類超平面，算法中這個超平面被表達(dá)為一組支持向量并作為分類的依據(jù)，針對一個已訓(xùn)練好的二分類支持向量機(jī)，樣本的分類公式為

(5)

其中，x代表輸入樣本向量，xi表示第i個支持向量，yi和αi分別代表該支持向量對應(yīng)的類別和拉格朗日乘子,支持向量的總數(shù)目為m，b代表偏移項,κ(·)為核函數(shù).

對多分類問題，常被采用的策略有一對一方式和一對多等方式.本文采用一對一方式，對于一個c分類問題，該方式將產(chǎn)生c(c-1)2個上述二分類分類器，最終分類結(jié)果由這些分類器的投票結(jié)果產(chǎn)生.

SVM算法的訪存負(fù)載主要來自于對支持向量、拉格朗日乘子等必要的模型參數(shù)的訪存操作，假設(shè)樣本和支持向量的數(shù)據(jù)維度為d，支持向量的數(shù)據(jù)量取決于數(shù)據(jù)維度d和向量數(shù)目m，而拉格朗日乘子的數(shù)據(jù)量則正比于類別數(shù)c和向量數(shù)目m，因此對單樣本的c分類任務(wù)，SVM的參數(shù)訪存負(fù)載(即浮點數(shù)訪存操作的數(shù)量)為

(6)

SVM算法的計算負(fù)載主要分為2部分:1)核函數(shù)κ包含的計算操作，雖然核函數(shù)κ可以有很多種形式，但在大多數(shù)核函數(shù)中最頻繁的計算操作是點乘操作(即乘法和加法操作)，該部分的計算負(fù)載與樣本維度d以及支持向量的數(shù)目m成正比;2)核函數(shù)結(jié)果與拉格朗日乘子的乘積操作，其計算量正比于m，因此單樣本c分類任務(wù)的計算負(fù)載可表示為

(2d+1)m(c-1).

(7)

4.3 RF算法的負(fù)載分析

隨機(jī)森林算法(RF)是一種集成學(xué)習(xí)方法，它以決策樹為基學(xué)習(xí)器，通過多個基學(xué)習(xí)器的分類結(jié)果投票的方式?jīng)Q定最終的分類類別.

RF算法的參數(shù)訪存負(fù)載是所有決策樹的節(jié)點上包含的參數(shù)的總和：

(8)

其中,ρ是每個節(jié)點需存儲的數(shù)據(jù)量，l是每棵樹的平均節(jié)點數(shù)，t是RF算法包含的決策樹的數(shù)目.

RF算法的主要分類過程是決策樹的遍歷，從而得到每個基學(xué)習(xí)器的分類結(jié)果，主要的計算操作是樣本屬性值與節(jié)點值的比較操作，需要注意的是，因為分類時每層只需要比較一個節(jié)點，比較操作的數(shù)目正比于樹的深度而不是樹的節(jié)點數(shù)目，因此RF算法對單樣本的計算負(fù)載為

(9)

4.4 NN算法的負(fù)載分析

神經(jīng)網(wǎng)絡(luò)(NN)算法是模擬生物神經(jīng)系統(tǒng)的結(jié)構(gòu)，通過將多個神經(jīng)元節(jié)點按照一定的層次結(jié)構(gòu)連接起來的機(jī)器學(xué)習(xí)算法.

一個已訓(xùn)練好的NN算法模型的主要參數(shù)是神經(jīng)元之間連接的權(quán)重和常數(shù)項，其數(shù)量與神經(jīng)網(wǎng)絡(luò)的層數(shù)相關(guān).因此，神經(jīng)網(wǎng)絡(luò)的參數(shù)訪存負(fù)載表示為

(10)

NN算法的分類方式是前向傳播算法，即從輸入層開始逐層計算每層的神經(jīng)元的數(shù)值，直至到達(dá)輸出層，主要的計算操作是神經(jīng)元節(jié)點值與連接權(quán)重的點乘操作，因此NN算法單樣本的計算負(fù)載可表示為

(11)

需要指出的是，由于多層感知機(jī)(MLP)和卷積神經(jīng)網(wǎng)(CNN)結(jié)構(gòu)上的差異，2種神經(jīng)網(wǎng)絡(luò)的訪存負(fù)載和計算負(fù)載有一定差異.多層感知機(jī)為全互連結(jié)構(gòu)，而卷積神經(jīng)網(wǎng)為權(quán)值共享的連接方式，因此在相同層數(shù)和節(jié)點數(shù)的情況下，卷積神經(jīng)網(wǎng)的模型參數(shù)更少，訪存負(fù)載更低，而在計算負(fù)載上，卷積神經(jīng)網(wǎng)的點乘操作被限制在“感受野”范圍內(nèi)，因此計算負(fù)載也小于多層感知機(jī).

5 算法參數(shù)訪存能耗和計算能耗的評估結(jié)果

通過第4節(jié)分析，我們得到3類算法的參數(shù)訪存負(fù)載和計算負(fù)載的估算公式.我們在4個不同的數(shù)據(jù)集上訓(xùn)練得到的算法參數(shù)如表4所示.

由表4的參數(shù)數(shù)據(jù)以及4.1節(jié)的分類能耗模型可以得到3類算法的分類能耗，如圖6所示.圖6(a)表示分類能耗，圖6(b)(c)分別代表參數(shù)訪存能耗和計算能耗，圖6(d)代表參數(shù)訪存能耗和計算能耗的差異度.根據(jù)評估結(jié)果，我們針對參數(shù)訪存能耗EMMA和計算能耗EMCP可以得出3點結(jié)論，詳見5.1～5.3節(jié)所述.

Table 4 The Value of Model Parameters表4 3種算法參數(shù)設(shè)置

*: As for NN algorithm, we use the classical LeNet network to classify MNIST dataset and use MLP network to other datasets. The numeral value of MLP represents the number of nodes in each layer.

Fig. 6 Comparison on classification energy of different algorithms圖6 3種算法分類能耗比較

5.1EMMA和EMCP的算法可近似性分析

結(jié)論1. 針對參數(shù)訪存能耗EMMA和計算能耗EMCP，算法可近似性的差異對能耗優(yōu)化的影響有限，算法的選擇主要決定于算法初始能耗的差別.從圖6(a)中可以看出，不同算法的初始分類能耗差異很大，SVM算法由于參數(shù)訪存負(fù)載和計算負(fù)載均正比于支持向量的數(shù)目，而在復(fù)雜應(yīng)用中這一數(shù)目往往很大，因此分類能耗最高;RF算法由于節(jié)點數(shù)量多，參數(shù)數(shù)據(jù)量大，訪存能耗很高，幾乎與SVM算法的訪存能耗相當(dāng)，分類能耗略低于SVM算法;而NN算法由于其參數(shù)數(shù)量和神經(jīng)網(wǎng)絡(luò)層數(shù)均較少，分類能耗在3類算法中最低.對比平均分裂能耗，SVM算法平均分類能耗約為NN算法分類能耗的29倍，RF算法的平均分類能耗是NN算法的12倍.因此這樣初始能耗的巨大差異，使得算法可近似性的差異對能耗的影響十分有限.

5.2EMMA和EMCP的算法能耗結(jié)構(gòu)分析

結(jié)論2. 不同算法的參數(shù)訪存能耗和計算能耗的比例有明顯的差異.通過圖6(b)和圖6(c)可以發(fā)現(xiàn)，SVM算法的參數(shù)訪存能耗和計算能耗大小處于同一數(shù)量級，其主要原因在于SVM算法的參數(shù)訪存負(fù)載和計算負(fù)載均與支持向量的數(shù)目成正比，因此2類能耗的差異較小;RF算法參數(shù)訪存能耗很高但計算能耗卻很低，其主要原因在于RF算法的節(jié)點數(shù)量很大，因此需要訪存的參數(shù)很多，而計算負(fù)載與節(jié)點的對數(shù)成正比并且計算操作簡單，因此計算能耗遠(yuǎn)遠(yuǎn)低于參數(shù)訪存能耗;NN算法參數(shù)訪存能耗和計算能耗正比于網(wǎng)絡(luò)層數(shù)，平均訪存能耗約為計算能耗的12倍.

為了更好地表征算法在能耗結(jié)構(gòu)上的差異性，我們將參數(shù)訪存能耗與分類能耗的比值關(guān)系定義為算法的能耗結(jié)構(gòu)差異度，簡稱能耗差異度(energy diversity)，即

(12)

3類算法能耗差異度的對比如圖6(d)所示，RF算法由于計算能耗遠(yuǎn)遠(yuǎn)低于參數(shù)訪存能耗，能耗差異度接近為0，平均能耗差異度為0.001；SVM算法的平均能耗差異度最高，約為0.3；NN算法介于二者之間，能耗差異度為0.17.

5.3EMMA和EMCP的算法能耗差異度影響

結(jié)論3. 我們將問題擴(kuò)展到多樣本分類情況，算法能耗差異度的差別可以幫助多樣本分類過程選擇能耗最優(yōu)的算法.多樣本分類能耗的計算需要考慮到分類應(yīng)用的樣本處理模式，我們將樣本處理模式分為2種:1)批量處理模式，該模式對應(yīng)在專用的機(jī)器學(xué)習(xí)加速器或大型的數(shù)據(jù)中心上的分類應(yīng)用，這種模式下樣本數(shù)據(jù)往往被批量處理，算法模型參數(shù)只需被訪存一次，因此算法的參數(shù)訪存能耗不受樣本數(shù)量的影響，而計算能耗由于樣本數(shù)量的增加而成為分類能耗的主要部分；2)非批量處理模式，對應(yīng)于多任務(wù)平臺如手機(jī)等移動設(shè)備的分類應(yīng)用，由于其他任務(wù)對資源的搶占，該模式下的樣本數(shù)據(jù)往往無法批量處理樣本數(shù)據(jù)，算法參數(shù)由于資源受限而被頻繁地?fù)Q入換出，參數(shù)訪存能耗和計算能耗均隨樣本數(shù)量上升而增加，此時參數(shù)訪存能耗占分類能耗的主要部分.因此在分類多樣本時，應(yīng)用應(yīng)該根據(jù)算法能耗差異度和樣本處理模式選擇合適的算法，具體地，在批量數(shù)據(jù)處理時，應(yīng)選擇算法能耗差異度低的算法如RF算法，這樣可以充分利用這類算法計算能耗低的優(yōu)勢，而在非批量處理模式下，能耗差異度高的算法如NN算法等將有助于減少參數(shù)訪存能耗帶來的開銷，從而降低整體分類能耗.

6 總 結(jié)

算法“可近似性”的差異對近似計算優(yōu)化能耗問題有著重要的影響，本文評估了3種機(jī)器學(xué)習(xí)算法SVM算法、RF算法和NN算法在優(yōu)化樣本存儲能耗、樣本訪存能耗、參數(shù)訪存能耗和計算能耗的可近似性差異，并提出了存儲污染敏感度、訪存污染敏感度和能耗差異度等評估指標(biāo)以表征可近似性的差距.這些評估指標(biāo)將有助于分類應(yīng)用選擇合適的機(jī)器學(xué)習(xí)算法實現(xiàn)能效最優(yōu).

評估結(jié)果表明：算法可近似性的差異確實對能耗優(yōu)化具有重要的作用，并且針對不同類型的能耗，算法的可近似性并不固定.SVM算法對比特位截斷技術(shù)造成的數(shù)據(jù)模糊容忍能力更高，因此針對訪存能耗的可近似性更好，訪存污染敏感度最低，適合優(yōu)化樣本訪存能耗時被選用；RF算法對降低刷新率帶來的樣本突變噪聲更加魯棒，存儲污染敏感度更低，適合優(yōu)化樣本存儲能耗時被采用；而對于參數(shù)訪存能耗和計算能耗，由于算法初始能耗的差異很大，可近似性的差異對能耗優(yōu)化的影響將非常有限，經(jīng)驗性的結(jié)果表明針對單樣本分類，NN算法的參數(shù)訪存能耗和計算能耗最低.此外，算法能耗結(jié)構(gòu)上的差異也十分顯著，有助于多樣本分類過程的算法選擇，具體地，RF算法等能耗差異度低的算法適合數(shù)據(jù)批量處理模式來盡量降低計算能耗，而非批量處理模式為減少參數(shù)訪存能耗更適合選擇NN算法等能耗差異度高的算法.

[1]Chippa V K, Mohapatra D, Raghunathan A, et al. Scalable effort hardware design: Exploiting algorithmic resilience for energy efficiency[C] //Proc of the 47th ACM/IEEE Design Automation Conf (DAC 2010). Piscataway, NJ: IEEE, 2010: 555-560

[2]Venkataramani S, Ranjan A, Roy K, et al. AxNN: Energy-efficient neuromorphic systems using approximate computing[C] //Proc of the 2014 Int Symp on Low Power Electronics and Design. New York: ACM, 2014: 27-32

[3]Shafique M, Hafiz R, Rehman S, et al. Invited: Cross-layer approximate computing: From logic to architectures[C] //Proc of the 53rd ACM/EDAC/IEEE Design Automation Conf (DAC 2016). Piscataway, NJ: IEEE, 2016: 1-6

[4]Xu Qiang, Mytkowicz T, Kim N S. Approximate computing: A survey[J]. IEEE Design & Test, 2016, 33(1): 8-22

[5]Moons B, Verhelst M. Dvas: Dynamic voltage accuracy scaling for increased energy-efficiency in approximate computing[C] //Proc of 2015 IEEE/ACM Int Symp on Low Power Electronics and Design (ISLPED). Piscataway, NJ: IEEE, 2015: 237-242

[6]Raha A, Venkataramani S, Raghunathan V, et al. Quality configurable reduce-and-rank for energy efficient approximate computing[C] //Proc of the 2015 Design, Automation & Test in Europe Conf & Exhibition (DATE 2015). Piscataway, NJ: IEEE, 2015: 665-670

[7]Wunderlich H J, Braun C, Sch?ll A. Pushing the limits: How fault tolerance extends the scope of approximate computing[C] //Proc of the 22nd IEEE Int Symp on On-Line Testing and Robust System Design (IOLTS 2016). Piscataway, NJ: IEEE, 2016: 133-136

[8]Mazahir S, Hasan O, Hafiz R, et al. An area-efficient consolidated configurable error correction for approximate hardware accelerators[C] //Proc of the 53rd ACM/EDAC/IEEE Design Automation Conf (DAC 2016). Piscataway, NJ: IEEE, 2016: 1-6

[9]Shim Y, Sengupta A, Roy K. Low-power approximate convolution computing unit with domain-wall motion based “Spin-Memristor” for image processing applications[C] //Proc of the 53rd ACM/EDAC/IEEE Design Automation Conf (DAC 2016). Piscataway, NJ: IEEE, 2016: 1-6

[10]Sarbishei O, Radecka K. Analysis of precision for scaling the intermediate variables in fixed-point arithmetic circuits[C] //Proc of the Int Conf on Computer-Aided Design. Piscataway, NJ: IEEE, 2010: 739-745

[11]Samadi M, Lee J, Jamshidi D A, et al. Sage: Self-tuning approximation for graphics engines[C] //Proc of the 46th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2013: 13-24

[12]Esmaeilzadeh H, Sampson A, Ceze L, et al. Neural acceleration for general-purpose approximate programs[C] //Proc of the 45th Annual IEEE/ACM Int Symp on Microarchitecture. Los Alamitos, CA: IEEE Computer Society, 2012: 449-460

[13]Liu J, Jaiyen B, Veras R, et al. RAIDR: Retention-aware intelligent DRAM refresh[C] //Proc of ACM SIGARCH Computer Architecture News. Los Alamitos, CA: IEEE Computer Society, 2012, 40(3): 1-12

[14]Liu S, Pattabiraman K, Moscibroda T, et al. Flikker: Saving DRAM refresh-power through critical data partitioning[C] //Proc of the 16th Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI). New York: ACM, 2011: 213-224

[15]Sampson A, Dietl W, Fortuna E, et al. EnerJ: Approximate data types for safe and general low-power computation[C] //Proc of ACM SIGPLAN Notices. New York: ACM, 2011: 164-174

[16]Filippou F, Keramidas G, Mavropoulos M, et al. Recovery of performance degradation in defective branch target buffers[C] //Proc of the 22nd IEEE Int Symp on On-Line Testing and Robust System Design (IOLTS 2016). Piscataway, NJ: IEEE, 2016: 96-102

[17]Mohapatra D, Chippa V K, Raghunathan A, et al. Design of voltage-scalable meta-functions for approximate computing[C] //Proc of the 2011 Design, Automation & Test in Europe Conf & Exhibition (DATE 2011). Piscataway, NJ: IEEE, 2011: 1-6

[18]Tian Ye, Zhang Qian, Wang Ting, et al. ApproxMA: Approximate memory access for dynamic precision scaling[C] //Proc of the 25th Edition on Great Lakes Symp on VLSI. New York: ACM, 2015: 337-342

[19]Zhang Qian, Wang Ting, Tian Ye, et al. ApproxANN: An approximate computing framework for artificial neural network[C] //Proc of the 2015 Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2015: 701-706

[20]Sathish V, Schulte M J, Kim N S. Lossless and lossy memory I/O link compression for improving performance of GPGPU workloads[C] //Proc of the 21st Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2012: 325-334

[21]He Xin, Lu Wenyan, Yan Guihai, et al. Exploiting the potential of computation reuse through approximate computing[J]. IEEE Trans on Multi-Scale Computing Systems, 2016, DOI: 10.1109/TMSCS.2016.2617343

[22]He Xin, Yan Guihai, Han Yinhe, et al. ACR: Enabling computation reuse for approximate computing[C] //Proc of the 21st Asia and South Pacific Design Automation Conf (ASP-DAC 2016). Piscataway, NJ: IEEE, 2016: 643-648

[23]Alvarez C, Corbal J, Valero M. Fuzzy memoization for floating-point multimedia applications[J]. IEEE Trans on Computers, 2005, 54(7): 922-927

[24]Kahng A B, Kang S. Accuracy-configurable adder for approximate arithmetic designs[C] //Proc of the 49th Annual Design Automation Conf. New York: ACM, 2012: 820-825

[25]Fang Shuangde, Du Zidong, Fang Yuntan, et al. Run-time technology for low-power oriented inexact heterogeneous multi-core[J]. Chinese High Technology Letters, 2014, 24(8): 791-799 (in Chinese)

(房雙德, 杜子?xùn)|, 方運潭, 等. 面向低能耗的非精確異構(gòu)多核上的運行時技術(shù)[J]. 高技術(shù)通訊, 2014 (8): 791-799)

[26]Venkataramani S, Raghunathan A, Liu Jie, et al. Scalable-effort classifiers for energy-efficient machine learning[C] //Proc of the 52nd Annual Design Automation Conf (DAC’15). New York: ACM, 2015: 61-67

[27]Düben P, Schlachter J, Parishkrati, et al. Opportunities for energy efficient computing: A study of inexact general purpose processors for high-performance and big-data applications[C] //Proc of the 2015 Design, Automation & Test in Europe Conf & Exhibition (DATE’15). Piscataway, NJ: IEEE, 2015: 764-769

[28]LeCun Y, Jackel L D, Bottou L, et al. Comparison of learning algorithms for handwritten digit recognition[C] //Proc of Int Conf on Artificial Neural Networks. Paris, France: EC2 & Cie, 1995: 53-60

[29]Arumugam G P, Srikanthan P, Augustine J, et al. Novel inexact memory aware algorithm co-design for energy efficient computation: Algorithmic principles[C] //Proc of the 2015 Design, Automation & Test in Europe Conf & Exhibition (DATE 2015). Piscataway, NJ: IEEE, 2015: 752-757

Jiang Shuhao, born in 1993. PhD, candidate. Student member of IEEE. His main research interests include machine learning and approximate computing.

Yan Guihai, born in 1981. PhD, professor. Member of IEEE, ACM, and CCF. His main research interests focus on energy-efficient and resilient architectures.

Li Jiajun, born in 1990. PhD candidate. Student member of IEEECCF. His main research interests include machine learning and heterogeneous computer architecture.

Lu Wenyan, born in 1988. PhD candidate. Student member of IEEECCF. His main research interests include heterogeneous computing and deep learning accelerator.

Li Xiaowei, born in 1964. PhD, professor, PhD supervisor. Senior member of IEEE. His main research interests include VLSI testing and design verification, dependable computing, wireless sensor networks.

A Quantitative Analysis on the “Approximatability” of Machine Learning Algorithms

Jiang Shuhao1,2, Yan Guihai1, Li Jiajun1,2, Lu Wenyan1,2, and Li Xiaowei1

1(StateKeyLaboratoryofComputerArchitecture(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

Recently, Machine learning algorithms, such as neural network, have made a great progress and are widely used in image recognition, data searching and finance analysis field. The energy consumption of machine learning algorithms becomes critical with more complex issues and higher data dimensionality. Because of the inherent error-resilience of machine learning algorithms, approximate computing techniques, which trade the accuracy of results for energy savings, are applied to save energy consumption of these algorithms by many researchers. We observe that most works are dedicated to leverage the error-resilience of certain algorithm while they ignore the difference of error-resilience among different algorithms. Understanding the difference on “approximatability” of different algorithms is very essential because when the approximate computing techniques are applied, approximatability can help the classification tasks choose the best algorithms to achieve the most energy savings. Therefore, we choose 3 common supervised learning algorithms, that is, SVM, random forest (RF) and neural network (NN), and evaluate their approximatibility targeted to different kinds of energy consumption. Meanwhile, we also design several metrics such as memory storage contamination sensitivity, memory access contamination sensitivity and energy diversity to quantify the difference on approximatability of learning algorithms. The conclusion from evaluation will assist in choosing the appropriate learning algorithms when the classification applications apply approximate computing techniques.

supervised machine learning algorithm; approximate computing; approximatability; energy consumption optimization; quantitative model

2017-02-22；

2017-04-13

國家自然科學(xué)基金項目(61572470,61532017,61522406,61432017,61376043,61521092)；中國科學(xué)院青年創(chuàng)新促進(jìn)會項目(404441000) This work was supported by the National Natural Science Foundation of China (61572470, 61532017, 61522406, 61432017, 61376043, 61521092) and the Youth Innovation Promotion Association, CAS (404441000).

李曉維(lxw@ict.ac.cn)

TP391