基于數據冗余性的近似計算技術

陳折桂，王 晶,2+，張偉功,3

(1.首都師范大學 信息工程學院，北京 100048；2.首都師范大學 北京成像理論與技術高精尖創新中心，北京 100048；3.首都師范大學 電子系統可靠性技術北京市重點實驗室，北京 100048)

0 引 言

伴隨著神經網絡應用范圍的擴展，近年來涌現出了大量針對不同需求的機器學習框架[1-3]，用于處理現代社會爆炸式增長的信息和數據。隨之而來的是數以千計的計算機組成的數據中心，為機器學習框架的執行和數據的處理提供算力支持。然而，爆炸式增長的數據使得數據中心所需的計算成本更加昂貴，存儲墻問題更加嚴重。有限物理存儲容量限制了訓練的規模和推理的速度。

壓縮方案是應用廣泛且實施簡單的拓展有限存儲容量的方法，然而這些只能對特定特征的數據進行壓縮的無損方法會在壓縮解壓縮的過程中帶來很大的開銷。針對存儲墻和高開銷問題，本文提出一種基于數據冗余性的近似計算技術(redundant data approximation)，主要貢獻如下：

(1)提出基于神經網絡中冗余數據存儲特征的冗余數據近似算法，針對權值矩陣稀疏化、輸入數據重復化等不同的冗余模式選擇壓縮算法，針對相似數據小范圍浮動型的冗余模式選擇近似算法，提高數據存儲密度。

(2)針對神經網絡的結構設計了支持拓撲感知的冗余數據近似算法，根據不同的網絡拓撲，冗余數據近似算法能夠尋找到較為優化的近似方式，進而提高壓縮效率和計算效率。

(3)實驗結果表明，采用本方案近似壓縮率平均達到了51.38%，為提高數據密集型應用的系統加速比提供了廣闊的可行性。

1 研究動機

為克服神經網絡訓練的內存容量瓶頸，理想化的解決方案就是讓訪存和搬運數據所需時間等于計算所需要的時間，如式(1)

(1)

目前典型的壓縮算法包括：ZCA(zero-content augmented)壓縮，該算法針對的存儲數據值大多為0，或NULL；FVC(frequent value compression)壓縮，該算法可將存儲的大量重復數據進行壓縮，以此減少源數據所占的空間；FPC(frequent pattern compression)壓縮試圖把幾種可壓縮的模式進行壓縮，比如4位符號擴展，8位符號擴展等。這些壓縮算法都能夠保證無損壓縮，但是都只能對特定特征的數據進行壓縮，對其它數據特征無法進行有效壓縮，并且壓縮解壓縮過程中帶來的開銷很大。傳統的無損壓縮方法能夠消除冗余數據提高系統性能，然而對于神經網絡應用，其自身具有一定的錯誤容忍能力，對于結果要求并不那么精確，神經網絡的冗余數據以及對不精確結果的可容忍性為降低無損壓縮帶來的壓縮和解壓縮等額外開銷提供了可能。

神經網絡的容錯特性使得其可以接受近似計算的存在。近似計算利用了應用程序對不精確結果的容忍度和用戶的感知限制，放松了對精確計算的要求，實現了計算精度與能效的折中。在很多既具有冗余數據又具有容錯能力的新興領域中，如圖像和聲音處理、計算機視覺、數據挖掘等得到廣泛應用。近似計算技術通常分為兩類，基于軟件的近似計算技術和基于硬件的近似計算技術。軟件近似機制通過對應用程序的特殊代碼段近似執行來達到減少計算開銷的目的[5]。基于硬件的近似計算又可以大致分為基于計算的近似和基于存儲的近似?；诖鎯Φ慕瓶梢蕴剿鞔鎯ζ黧w系結構中的數據相似性，如文獻[6]就探索了高速緩存行之間的近似；根據高速緩存的空間/時間相關性提出的跳過一些內存訪問也是一種好方法[7]。最常見的基于計算的近似就是精度縮放技術[8]，該技術在質量約束下調整操作數位寬以提高能量效率。目前針對數據方面比較常用的近似方法就是跳過內存訪問和尾數截斷，但它們不考慮數據本身的特性，比如尾數截斷的方法，就是簡單粗暴地裁減掉尾數后幾位，雖然它能夠相對應地減少操作數位數，但沒有考慮數據與相鄰數據之間的關系。針對此，本文提出的方案在處理數據時考慮到了相鄰數據的相似性，在質量約束下有選擇地調整操作數位寬，可以實現壓縮率的提升進而顯著地提高運算加速比。

2 基于數據冗余模式的近似方案

基于數據冗余性的近似計算技術方案的主要目標是實現精確度和性能的折中。為實現此目標，本方案接受擁有可近似代碼段的程序和用戶的資源約束作為輸入，并使用針對冗余數據類型設計的優化生成具有不同精度的近似方案。圖1顯示了基于數據冗余性的近似計算技術方案的整體框架和運行時的整體操作。

圖1 基于冗余數據的近似方案概況

通過對應用程序中冗余數據模式的分析可知，常見的程序時間和空間的開銷都由數據信息位的長度決定，而由于數據局部性和相似性特征，神經網絡應用中的數據又存在著冗余信息，那么可以通過消除冗余信息，減少數據信息位的長度，提升數據壓縮率，進而降低程序的時間開銷和空間開銷。因此，本文提出基于數據特征的冗余近似方案：2.1.1節描述了針對稀疏矩陣這種數據存儲特征的冗余數據處理方案；2.1.2節描述了針對輸入數據中重復型數據的處理方案；2.1.3節展現了近似值的產生，根據分析神經網絡中相鄰數據間的相似數據小范圍浮動型而得到的冗余模式，選擇相應的近似算法；2.2節描述了具有神經網絡拓撲感知的冗余數據近似計算技術，展現了本方案在不同網絡結構下的應用。

基于數據冗余性的近似計算技術通過將冗余數據消除和近似以便在緩沖區存儲更多數據，一方面提高系統運行加速比，另一方面消除從存儲器檢索數據的等待時間和能量。在傳統的存儲系統中，會經常性發生未命中后從存儲器層次結構中的下一級獲取。而在本方案中，對于可近似代碼段中的輸入數據近似后存放在緩沖區中，能夠在相同的容量下存放更多的數據，從而消除一定的缺失率。之后取出近似值，處理器假定這是實際精確值并繼續執行。

2.1 數據的近似存儲

神經網絡中存在大量的輸入和權值數據，輸入和權值的變化都可能會導致輸出質量的變化。神經網絡中同樣存在大量利于近似的規整數據，例如大量的0值，重復型數據以及數據差值范圍浮動較小的相似數據集?，F有冗余數據消除算法只針對具有某一種數據特征的存儲塊進行設計，難以靈活高效處理不同特征的數據，為提高壓縮率，本文提出針對不同數據冗余模式的近似消除技術。圖2為形式化算法流程，其中，將近似代碼段的輸入數據值視為一組固定大小的值的集合(如8/4/2字節)，按固定大小依次比較，匹配冗余模式，當為稀疏型時僅保留一個零值，其余舍棄；當為重復型時，僅保留一組重復值，其余舍棄；當為小范圍浮動型時，僅保留基值。成功通過匹配近似并且存儲長度最短的保留值即為近似值用以計算和存儲，而未能夠匹配到冗余模式的輸入數據則視為不可近似，直接使用真實值進行計算和存儲。

圖2 數據近似存儲策略的形式化算法流程

2.1.1 權值矩陣稀疏化

首先是針對于稀疏矩陣型冗余數據的消除。在神經網絡中，其權值矩陣中存在大量的0值，如圖3所示，去除冗余權值，將稠密權值矩陣(圖3(a))轉換為稀疏矩陣(圖3(b))。之后計算輸出元素時會去掉零權重的乘法累加操作，使得整個操作過程中計算操作數減少，并且能達到存儲空間的降低。針對于稀疏矩陣中0值的冗余，本文提出的方案是只需存儲一個數值。

圖3 稀疏矩陣性冗余數據的處理

2.1.2 重復型輸入數據壓縮

神經網絡的輸入有大量的圖像視頻等應用，在這些應用領域中，彼此相鄰的元素可能具有相同的值，于是，輸入時利用一部分元素的值代替其它重復的元素值進行計算也可以得到符合要求的目標輸出質量。針對于輸入數據中存在著的重復數值，本文根據重復值的字節數的不同，基于數據的對齊存儲特性可分為4字節和8字節重復值存儲，并標記其它重復值的個數。圖4反映了輸入數據中重復數值的處理和復用方式，利用這種方式可以大量壓縮冗余數據，提高壓縮率。

圖4 輸入數據中重復型冗余數據的處理

2.1.3 小范圍浮動型近似

實際過程中的很多應用并不需要執行完全精確的計算。一方面，精度較低的數據并不總是導致功能錯誤；另一方面，由于許多數據密集型神經網絡應用本身具有抗錯誤能力，有時甚至可以恢復，其可以接受一定數量的功能錯誤，并且不會影響最終輸出質量。因此，在此部分，我們提出了相鄰數據具有近似可能性的小范圍浮動相似值的近似計算方案，如圖5所示。對小范圍浮動值冗余模式，需要判斷基值和差值。由于基值越多，算法越復雜，時間開銷越大，壓縮率越低，基于性能和開銷的折中考慮，方案選用2個基值，一個基值為0值，另一個基值根據具體的神經網絡矩陣中的數值進行選取，利用精度擴縮舍去矩陣行中的數據與基值進行向量減操作得到的增值，僅保留2個基值。由于應用程序的數據存在多樣性，因而支持多種數據長度，基值可支持2字節、4字節和8字節。此方案相對于無損壓縮由于舍掉增值而引入了誤差，但同時，由于舍掉增值僅存儲基值而使源數據信息位的長度變短，提升了數據壓縮率，空間開銷和延遲開銷也會相比于無損壓縮進一步減少，系統的運行加速比增高，同時相較于無損壓縮還省去了壓縮和解壓縮的額外開銷。另外，本文提出的方案不僅能夠減少操作數位寬，還能相對應地減少操作數計算個數，進而減少神經網絡中的計算量。

圖5 相鄰數據小范圍浮動值近似

表1給出了支持的小范圍浮動型數據的近似方式，小范圍浮動值根據所選基值的不同，分為3種。

2.2 網絡拓撲感知的冗余數據近似方案

神經網絡的拓撲結構，包括層數和每層的神經元數量都可以變化。并且不同層的輸入數據之間沒有關聯，其相似度往往較差。而針對小范圍浮動值的近似技術中，近似數據的范圍是影響壓縮效果和網絡精度的關鍵。例如，對

表1 近似壓縮方式

于①3-8結構的網絡：有3層(包含input、output和1個隱藏層)，隱藏層有8個神經元；和②4-4-4結構的網絡：有4層(包含input、output和2個隱藏層)，每個隱藏層有4個神經元。兩個網絡隱藏層神經元數量都是一樣的，此時想要近似就得考慮這些神經元相對應的數據究竟是在同一層里還是在不同層里，雖然8個數據同時在存儲區，但是對于3-8的網絡，這8個數據是一起使用，而對于4-4-4，是先使用前4個數據再使用后4個。見表2，如果不去分析拓撲，而是采用一個固定的范圍如每4個數據一組去做冗余數據近似，那么對于3-8網絡中的8個數據，每4個近似需要2個基值，相比于每8個一組不能最大化近似效果，造成時間和能量的開銷；同樣的，若統一采用每8個數據一組做近似，那么對于4-4-4網絡，相比于每4個一組，由于兩層隱藏層之間數據相似性可能并不大，在這些相鄰數據之間找到的近似值可能誤差會很大。這就要求近似方法能夠感知網絡拓撲，能根據網絡的結構調整近似的范圍，產生合適的冗余數據近似方案。

基于上述的分析，本文提出的網絡拓撲感知的冗余數據近似方案首先會分析網絡結構，確定網絡的層數、順序和每層神經元的個數，從而針對每一層節點的數量對神經網絡中的各層輸入數據做近似范圍地劃分，之后在這些范圍內對數據實施2.1節所述的冗余數據近似方案。通過感知網絡拓撲，可以解決對數據進行固定范圍近似所帶來的問題，能夠更加優化壓縮效果，減少網絡精度的損失。

表2 網絡拓撲感知的冗余數據近似方案

3 評測與分析

實驗選擇對比了不壓縮不近似的基準方案(base)，使用收縮神經網絡加速器的近似方案(SNNAP)[9]以及本文提出的冗余數據近似(RDA)方案。實驗首先面向Axbench基準測試程序進行精度和壓縮率的對比，其次面向神經網絡應用進行評測對比，最后探索了當神經網絡拓撲變化時冗余數據近似方案對神經網絡應用的影響。

3.1 面向Axbench程序的評測

3.1.1 實驗平臺與基準測試程序

我們在sniper[10]模擬環境中運行Axbench[11]基準測試程序對本文方案進行評估。體系結構參數具體見表3。

表3 體系結構參數

Axbench是代表了現代和新興應用并可以應用到神經網絡等廣泛領域的基準數據集。其中JPEG是針對彩色圖像的有損壓縮技術，輸入是未壓縮的圖像，實驗中讓JPEG算法執行有損壓縮并生成與原文件大小相比減小的類似圖像。Sobel廣泛用于圖像處理和計算機視覺應用，在Sobel的實驗中，RGB圖像作為輸入，最終生成邊緣被重點標注的近似灰度圖像。K-means是一種常用的聚類算法，廣泛用于機器學習和數據挖掘，它旨在將多個n維輸入點劃分為k個不同的簇，使用RGB圖像作為輸入，輸出是聚集在不同顏色區域的近似圖像。FFT算法主要計算序列的離散傅里葉變換或其逆，輸入是時域中的信號序列，輸出是頻域中信號值的近似表示。

3.1.2 程序近似敏感度和近似閾值分析

我們使用相對誤差作為實驗的精度測量標準。把base方案和SNNAP方案作為兩個比較基準。對輸入數據所能夠近似的變化范圍稱之為近似閾值，應用程序使用者所能接受的最小輸出結果精確度稱之為目標輸出質量。

分析JPEG、Sobel、K-means、FFT在不同近似閾值(即不同近似程度)下的敏感度研究實驗，可以得到，在這些基準程序的實驗中，對于每一個實驗樣本，當所能夠容忍的近似閾值變大時，最終基準程序的輸出誤差也隨之增大，即輸出精度隨之降低；反之，輸出誤差減小。并且通過幾個基準程序的敏感度實驗對比可以發現，如圖6所示，像圖像處理、機器學習、數據挖掘這些具有大量重復和相似數據的應用程序，其實驗中的樣本對于近似閾值的變化都很敏感，本文提出的冗余數據近似方案十分適用；而對于像FFT這樣的并不存在大量重復相似的應用程序，近似閾值可選度非常小，輸出誤差也基本沒變化。并且這幅圖給使用者提供了一個動態的可調整的方案，以不同近似程度的實驗作為支撐，程序使用者可以根據自己所需求的目標輸出質量選擇各基準程序在最合適近似程度下的近似方案。

圖6 各基準程序敏感度研究

3.1.3 近似效果分析

圖7左側坐標軸是base方案、SNNAP方案、RDA方案的輸出質量比較。為使實驗數據圖表呈現最好效果，在本文的RDA方案實驗中，我們對JPEG、Sobel、K-means這3種基準程序選擇當近似閾值為63時的輸出質量作為比較，FFT選擇近似閾值為127時的輸出質量作為比較。實驗結果表明：在FFT的實驗中3種方案相差不大，因為在FFT中并不存在大量的重復和相似數據，可壓縮與可近似程度非常小，因此質量損失并沒有太大變化。在JPEG實驗中，RDA方案相較于base方案質量下降了6.45%，相較于SNNAP方案質量提高了2.27%；在Sobel實驗中，RDA方案相比于另外兩種方案質量分別下降了23.25%，提高了11.53%；在K-means實驗中，RDA方案相比于另外兩種方案質量分別下降了1.35%，提高了10.67%。這3種基準程序都是與圖像處理、機器學習等有關的具有大量重復和相似數據的應用程序，它們的冗余數據可壓縮性和可近似性非?？捎^，通過近似后便會產生一定的質量損失。但通過實驗數據可以看到，綜合來看，本文提出的方案并不會對應用程序輸出質量產生大的影響，平均降低了10.35%，并且，本文的方案相較于SNNAP方案效果更好，平均提高了8.16%。

圖7右側坐標軸是使用了RDA方案后的數據壓縮率的情況。近似壓縮率定義為可被近似壓縮的數據總量和壓縮前的數據總量的比值(式(2))，近似壓縮率的值越高表明壓縮效果越好，系統加速比提升空間更大，帶寬利用率也會隨之提高。根據實驗結果顯示，圖像處理、機器學習等應用程序的代表程序JPEG、Sobel、K-means，近似壓縮率分別達到了61.88%、67.20%、25.07%，為我們提供了廣闊的可行性

(2)

圖7 各方案下應用的近似效果比較

3.2 面向神經網絡的近似技術評測

Axbench中還引入了神經網絡近似方案[9,11]，于是，我們面向神經網絡應用，以該神經網絡近似方案為基準方案(base)，與神經網絡應用背景下的RDA方案進行比較。

3.2.1 近似效果分析

由上面的實驗評估和討論可以看到，本文提出的冗余數據近似方案對圖像處理、機器學習、數據挖掘這些具有大量重復和相似數據的神經網絡應用程序十分適用，因此，本小節便對這些神經網絡應用進行探索與討論，以代表程序JPEG、Sobel、K-means為例。

在面向神經網絡近似環境下，通過冗余數據近似方案對神經網絡應用影響的探究實驗可得，敏感度和之前3.1.2節討論的典型程序的敏感度類似，對于每一個實驗樣本，當所能夠容忍的近似閾值變大時，最終基準程序的輸出誤差也隨之增大，即輸出精度隨之降低；反之，輸出誤差減小。

圖8是面向神經網絡應用的RDA和base方案的輸出質量比較。為使實驗數據圖表呈現最好效果，在本文的神經網絡探索實驗中，對JPEG、Sobel、K-means這3個程序同樣選擇當近似閾值為63時的輸出質量作為比較。實驗結果表明：在JPEG實驗中，面向神經網絡應用的RDA方案較于base方案質量下降了0.92%，在Sobel實驗中，提高了11.56%，在K-means實驗中，輸出質量基本持平。通過實驗數據可以看到，綜合來看，面向神經網絡的RDA方案不會對應用程序輸出質量產生太大影響。

圖8 冗余數據近似對神經網絡精度的影響

本次神經網絡探索實驗中的近似壓縮率也與3.1.3節的差別不大，在此不過多敘述。綜合輸出精度與近似壓縮率，可以看到冗余數據近似方案對于圖像處理、機器學習、數據挖掘這類需要神經網絡處理大量重復和相似數據的應用程序十分適用，為神經網絡量化加速提供了廣闊的前景。

3.2.2 不同網絡拓撲下近似效果分析

本小節研究內容是通過冗余數據近似方案對神經網絡應用可近似區域的輸入數據量化之后，探究神經網絡網絡拓撲的改變對輸出質量的影響。圖9為以JPEG為例的實驗數據所繪制的結果，橫坐標為不同網絡拓撲結構，3-2表示神經網絡最大層數為3層，隱藏層最多神經元個數是2，其余同理；縱坐標是JPEG在不同網絡拓撲下的輸入誤差平均值。通過圖9可知，無論網絡拓撲變化得多復雜，面向神經網絡采用冗余數據近似方案其輸出誤差最大不會超過1.5%，表明了本文提出的冗余數據近似方案在神經網絡應用中優秀的魯棒性和穩定性。

圖9 誤差隨網絡拓撲變化情況

4 相關工作

近似計算利用了應用對不精確結果的容忍特性和用戶的感知限制，使得近似后的結果仍然能滿足某些指標的要求。近年來提出了很多提高效能的近似計算方法，下面介紹與本文相關的近似計算技術工作。

神經網絡通常過度參數化，源于在用參數表示近似模型的方式中存在著顯著冗余。因此，一系列提案旨在通過減輕網絡冗余來減少神經網絡內存使用。特別是網絡裁剪策略已經被先前文獻[12,13]廣泛研究。網絡裁剪通過刪除那些滿足給定裁剪標準的冗余網絡連接，可以有助于減少模型權重分配的內存。但這些提議為節省內存使用提供了有限的機會，因為權重僅占神經網絡訓練所需的總內存分配的一小部分。最近還有不少方案為卷積神經網絡提出了一系列加速器設計[14-16]。這些先前提案屬于神經網絡的推理領域，而我們的工作重點是神經網絡訓練中的數據。更重要的是，這些先前的工作都沒有解決由于神經網絡內存虛擬化而產生的通信瓶頸。

除此之外，大量文獻也著眼于與存儲空間有關的近似所帶來的性能和效率的提高。可在DRAM中支持近似存儲以節省能量，當然也會帶來一定的錯誤[17]。也有工作將寄存器中的冗余數據量[18]作為探索點，通過壓縮消除寄存器中冗余數據更有效地節省能量。還有的工作著眼于精度縮放這種常用的近似技術，通過調節輸入操作數的位寬來實現能量和質量的權衡[19]。

5 結束語

神經網絡和機器學習框架在視覺、語言等眾多應用領域發揮了重要作用，但是隨著數據的爆炸式增長，計算和存儲成本將變得更加昂貴，精確度和開銷也難達到更好的平衡。為此本文提出了基于數據冗余性的近似計算技術，它是通過分析數據密集型神經網絡的數據冗余特征，針對頻繁出現的稀疏矩陣型、數據重復型、相似數據小范圍浮動型這3種數據分別提出各自的壓縮方案和近似方案，進而降低開銷，提高存儲密度。研究結果表明本文方案相比于SNNAP方案輸出質量平均提高了8.16%，對擁有神經網絡的基準程序進行近似和量化后輸出質量平均提高了10.5%。另外，圖像處理、機器學習、數據挖掘這些具有大量重復和相似數據的數據密集型應用程序更加適用于本方案，平均壓縮率能達到51.38%，為提高系統加速比提供了廣闊的可行性。至于未來工作還有許多問題有待進一步研究，例如如何快速有效精準地對輸入數據的重要性進行評價，以達到更好的輸出質量更大的壓縮率，以及提高壓縮率對提高系統加速比的具體影響，都值得深入探究。