機器學習算法可近似性的量化評估分析

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

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100049)

機器學習算法可近似性的量化評估分析

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

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100049)

(jiangshuhao@ict.ac.cn)

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

監督機器學習算法；近似計算；可近似性；能耗優化

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

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

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

(1)

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

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

E=ESMS+ESMA+EMMA+EMCP,

(2)

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

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

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

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

1 相關工作

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

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

1) 針對存儲能耗.文獻[13-14]等工作發現大多數DRAM存儲單元數據可保持時間高于目前設定的刷新時間，因此可以適當延長DRAM刷新時間，節省大量的存儲能耗，其中文獻[13]的方法能夠降低74.6%的刷新頻率、16.1%的DRAM能耗和8.6%的系統整體能耗.電壓調節技術也是降低存儲能耗的手段之一，文獻[15-17]分別通過適當地降低cache、寄存器和功能性單元的供電電壓來節省存儲能耗.

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

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

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

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

Table 1 Distribution of Energy Consumption on Different Datasets

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

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

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

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

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

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

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

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

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

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

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

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

樣本訪存能耗ESMA，即從主存向緩存傳輸樣本數據的能耗，樣本訪存能耗是分類應用總能耗中不可忽略的一部分，而且隨樣本數據量增大而增多.根據文獻[29]，從主存傳輸數據到緩存的能耗為片內數據傳輸能耗的19倍，表1顯示單樣本分類情況下ESMA占整體能耗的平均比例為18.79%，因此通過近似計算技術優化樣本訪存能耗十分必要.

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

Fig. 3 Overview of precision scaling圖3 位截斷技術示意圖

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

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

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

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

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

(3)

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

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

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

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

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

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

4 算法參數訪存能耗和計算能耗的評估方法

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

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

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

4.1 參數訪存/計算能耗模型

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

EMODEL=λμ×FMMA+μ×EMCP,

(4)

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

4.2 SVM算法的負載分析

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

(5)

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

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

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

(6)

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

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

(7)

4.3 RF算法的負載分析

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

RF算法的參數訪存負載是所有決策樹的節點上包含的參數的總和：

(8)

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

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

(9)

4.4 NN算法的負載分析

神經網絡(NN)算法是模擬生物神經系統的結構，通過將多個神經元節點按照一定的層次結構連接起來的機器學習算法.

一個已訓練好的NN算法模型的主要參數是神經元之間連接的權重和常數項，其數量與神經網絡的層數相關.因此，神經網絡的參數訪存負載表示為

(10)

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

(11)

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

5 算法參數訪存能耗和計算能耗的評估結果

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

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

Table 4 The Value of Model Parameters表4 3種算法參數設置

*: 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的算法可近似性分析

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

5.2EMMA和EMCP的算法能耗結構分析

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

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

(12)

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

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

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

6 總 結

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

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

(房雙德, 杜子東, 方運潭, 等. 面向低能耗的非精確異構多核上的運行時技術[J]. 高技術通訊, 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

國家自然科學基金項目(61572470,61532017,61522406,61432017,61376043,61521092)；中國科學院青年創新促進會項目(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