點擊上方關注，All in AI中國
這是麻省理工學院機器智能社區（MIC）的“機器學習”系列論文中的一篇。麻省理工學院MIC旨在對整個社區進行進行關於機器學習的教育，使得大家能夠更快的進入機器學習這個領域。
深度神經網絡（DNN）在越來越廣泛的工業應用中提供無與倫比的精度和性能，例如圖像識別、自然語言處理和其他複雜問題，如自動駕駛車輛的控制。儘管與舊機器學習算法相比有了巨大的成果改進，但DNN在計算方面要求很高，並且需要大量數據集的訓練，同時也需要花費大量時間。因此，已經進行了許多努力來加速訓練時間以及推斷時間（在給定訓練模型的情況下實際進行預測所花費的時間）。
這使我們能夠在更短的時間內訓練更多的數據，並在移動電話或嵌入式系統等功能較弱的設備上進行更快的推理。在他們的論文“Optimal DNN Primitive Selection with Partitioned Boolean Quadratic Programming (PBQP）”中，Andrew Anderson和David Gregg採用混合方法來優化DNN計算。他們專注於尋找DNN原語選擇問題的解決方案，可以將其描述為決定使用哪些算法和庫來運行DNN的每一層，下面將詳細解釋該問題。它們還將問題簡化為已知的NP難圖問題PBQP，並使用現成的PBQP求解器來解決它。
在評估結果時，特別強調卷積運算，這是一種計算極其密集的運算，並且幾乎在所有圖像處理DNN中都會使用，這種網絡被稱為卷積神經網絡（CNN）。
DNN原語及其重要性
DNN由層的有向圖組成，並且在這些圖層之間的有向邊上發生數據流。每個層都是處理數據的，它由標準數學運算符組成，如卷積、激活、池化或完全連接的層。一層的輸出會饋送到下一層，這可以對應到數據流。這些層實現為一組原始例程，其中每個原語都是這些數學運算的優化實現。層有許多可能的算法和實現，這與說有許多可供使用的原始例程選擇相同，包括開源實現和專有庫。
例如，Winograd和FFT是兩種可用於實現卷積的算法。值得注意的是，這些基元在不同場景中的表現不同，具體取決於圖層的規格。目的是為每一層選擇最佳的原始例程，以便最小化整個網絡的整體運行時間，這個問題被稱為最佳DNN原語選擇。
什麼是卷積層？
儘管所使用的方法是通用的，並且很容易可以針對任何類型的層實施和測試，但評估焦點僅保留在卷積層上。它們通常主導運行時間，並且在許多重要的CNN中用於圖像處理。卷積層的輸入通常是張量，一般以2-D圖像的三維或四維表示。例如，對於典型的彩色2-D圖像的三維表示，前兩個維度通常編碼像素的水平和垂直位置，第三維度通常存儲紅色、綠色和藍色的量。像素，卷積層通過在圖像上滑動一系列小“濾波器”或“內核”來處理該張量，以執行數學卷積運算。在下圖中示出了輪廓，其中尺寸為H×W×C的圖像與尺寸為k×k×C的核進行卷積以獲得尺寸為H×W的輸出圖像（稱為“特徵圖”），並且由於存在M個這樣的內核，因此輸出表示為大小H×W×M的張量。
多個內核是很重要的，因為它們可以使網絡“學習”不同的功能和模式。例如，一個內核可能會嘗試檢測圖像中是否存在貓，另一個內核可能會學會檢測狗。得到的張量 - 來自所有內核的輸出 - 然後可以被送入最大池層，這將檢測這些M模式中哪一個最重要，例如負責貓的那個內核是否發現了比狗內核更好的匹配 - 這使得高精度圖像分類。
圖1:卷積層示出尺寸為H×W的圖像，其中C通道經歷與大小為k×k×C的M個核的卷積
卷積層中的原始選擇和數據格式協議
存在大量用於卷積的不同基元。直接循環方法，im2、kn2、Winograd和FFT（使用快速傅立葉變換算法），都是可用於實現卷積的算法系列。如前所述，每種算法的性能取決於卷積層的參數和規格。例如，直接循環方法在步長卷積上表現良好，其中內核跳過一些輸入像素以給出較小的輸出圖像，並且im2在這種情況下也表現良好。但是，直接循環方法通常較慢，而im2算法非常耗費內存， Winograd非常快，但無法預測。
FFT也是一種性能優勢平衡的選擇，但對小內核不利;儘管具有較低的漸近複雜度，但它具有較大的開銷，因此導致較低的複雜度僅在輸入較大時才有益。其他參數，如通道數（即上圖中C的值）也會影響基元的最佳選擇。
由於在典型的CNN中，每個層的參數變化很大，因此對於每個層具有不同的基元選擇是有意義的，以便最小化計算在整個網絡上的總運行時間。乍一看，這似乎是一個非常容易解決的問題：在實際運行整個網絡之前，我們可以簡單地嘗試每個層上的每個原語並記下列表中的運行時間（讓我們將此列表稱為“成本向量”） 。對於此試運行，我們可以使用隨機輸入值，因為運行時間實際上並不取決於值本身，而是它們的總數。事實上，這實際上是作者的出發點。
在對運行時間進行採樣後，我們可以通過查看哪一個在試驗中表現最佳來為每一層選擇最佳算法，這樣，問題解決了！該過程如下所示：
圖2：顯示3層CNN的圖。每層旁邊顯示的“成本向量”表示每層的基元A、B和C的成本。例如，在層conv1上，基元A的運行成本為8，基元B的成本為6，C的成本為10，其他層也是如此。
這裡卷積層表示為節點：conv1、conv2和conv3。三個基元是A、B和C，顯示了每個層的原始成本向量（由試運行確定），我們可以看到優化整個網絡只是選擇最小成本原語。在這種情況下，它對應於conv1的選擇算法B，conv2的算法C和conv3的算法B。網絡的總成本只是每層成本的總和。
然而，這種天真的解決方案缺少一個關鍵方面。它沒有考慮每個基元對不同數據格式的數據進行操作的事實。例如，一些基元接收並以16位浮點格式生成輸出值，而其他基元使用32位浮點。一些基元還需要輸入圖像的尺寸的特定排列，CHW（通道×高度×寬度）和HWC（高度×寬度×通道）是兩種不同的數據格式，並且特定基元可以僅對一種格式進行操作。
另一個例子是，如果對信號進行操作，則數據可以用頻域表示或時域表示（這些只是表示相同信號的不同方式），並且不同的基元可能僅支持這些格式中的一種。必須考慮這一點，如上圖所示，可能是conv1使用與conv2不同的數據格式，數據需要從conv1的格式轉換為conv2格式才能在它們之間傳遞，這樣就會有轉換成本產生。因此，我們還需要在優化中考慮數據格式轉換的成本。
PBQP
由此產生的優化問題現在不僅考慮了圖元的運行時間，還考慮了連續圖層中使用的圖元之間的數據格式轉換時間。作者表明，這相當於已知的NP難問題，即分區布爾二次問題（PBQP）。在PBQP中，我們給出了一個圖表，並且必須從表示成本的給定標籤集合中為每個節點分配標籤。
因此，每個節點都具有所有標籤的“成本向量”，這與前一圖中的問題類似。為節點選擇標籤的成本會將相應的成本添加到我們目標的總成本中，這是我們想要最小化的。但除了節點的成本之外，每個邊緣還有成本。邊緣的成本取決於源節點的標籤選擇，以及目標節點的標籤選擇。由於它取決於連接節點的標籤，因此可以將其視為矩陣（因為它由兩個標籤索引）。
如下圖所示：
圖3：顯示3層CNN的圖。還示出了與圖1類似的基元a、b和c的成本向量。還示出了邊緣成本矩陣，其中行表示源節點的標籤，列表示目標節點的標籤。例如，為conv1選擇基元c成本為10，為conv2選擇基元b成本為19。但是邊緣成本矩陣給出的附加邊緣成本也為5。
我們可以在上圖中看到，conv1的最低成本原語是原始b，成本為6，而conv2的最低成本原語是原始c，成本為14。但是現在我們還必須考慮邊緣成本和使用此賦值通過適當地索引到邊緣成本矩陣給出額外的邊緣成本5。因此實際上為conv1選擇原始c更好，因為它給出的邊緣成本為零。那麼總成本就是所有節點和邊緣成本的總和，這是我們想要最小化的目標。
實施和測試
現在我們有正確的問題需要解決，我們可以實現並測試它。為此，我們首先需要運行基元的成本以及數據格式之間轉換的成本。通過為每個層運行實際大小的隨機輸入來預先計算運行基元的成本，並且這應該是相當準確的，因為層的運行時間取決於輸入大小而不是實際值。
數據格式轉換成本也通過運行轉換和時間採樣來預先計算。在不可能直接轉換的情況下，使用最低成本轉換路徑的成本。這意味著如果數據格式A，例如不能轉換為數據格式B。但是A可以轉換為數據格式C，而數據格式C又可以轉換為B，然後使用轉換成本的總和（這是建模的）作為All-Pairs-Shortest-Paths問題並輕鬆解決）。
一旦成本向量和矩陣準備就緒，就可以使用現成的PBQP求解器來獲得DNN的最佳基元選擇，以便進行基準測試。性能在三個流行的神經網絡上進行了測試：AlexNet，VGG Model E和GoogleNet。將運行時與整個使用單個基元以及Caffe（一種流行的深度學習框架）的性能進行比較。還包括英特爾MKL-DNN庫的基準測試，這是針對DNN基元的優化JIT編譯器。實驗在不同的硬件架構上進行，Intel Haswell的速度結果如下所示（越高越好）：
圖4.用於運行各種流行DNN的不同算法的Intel Haswell加速
我們可以看到，在Intel Haswell上，PBQP原語賦值在多線程的情況下優於所有其他方法，甚至是英特爾自己的MKL-DNN神經網絡編譯器。在單線程運行的情況下，MKL-DNN在AlexNet和GoogleNet網絡中的性能稍好一些，但PBQP方法非常接近並且仍然優於其他方法。對於VGG，PBQP方法也超過MKL-DNN。
ARM Cortex的性能結果如下所示（越高越好）：
圖5.用於運行各種流行DNN的不同算法的ARM Cortex上的加速
在這裡，我們還可以看到PBQP分配優於ARM Cortex-A57架構上網絡的所有其他實現。
討論與結論
從實驗結果可以清楚地看出，PBQP公式在選擇實施DNN的最佳基元方面非常有效。存在其他DNN優化框架，並且可以使用一些類似技術來實現更快的DNN計算。也許最快的例子是NVIDIA的cuDNN，它使用最有可能是給定層最快的實現/原語。這與PBQP解析器形成對比，因為它沒有考慮邊緣成本，即數據格式轉換的時間。Tensorflow XLA是另一個框架，它基本上是DNN的提前編譯器。它計算跨層轉換和數據格式轉換的成本，並嘗試合併層以避免這些成本，這與PBQP方法有些並行。
結果表明，PBQP方法改善了DNN運行時間，因此可能非常適合DNN優化框架的改進。作者在2018年代碼生成和優化國際研討會（CGO）上發表了這篇論文，本文采用的方法使我們能夠更快地訓練DNN，並對越來越多的廉價移動和嵌入式系統進行深度學習和推理。
運營：李佳惠
閱讀更多 AI中國 的文章
