機器之心發布
機器之心編輯部
阿里巴巴有諸多的複雜端智能業務場景，對於深度學習引擎的性能、包大小、普適性都要很高的要求。在這樣的背景下，阿里巴巴自研的端上推理引擎 MNN 應運而生。
目前，它已經大規模應用在阿里巴巴移動端及 IOT 設備上，支撐了億級的終端設備以及數十種不同類型的應用場景。在 2019 年的雙 11，更是作為底層的技術設施，承擔了數千億級的計算。
MNN 在推理引擎設計與優化方面提出了一系列創新性的思想，論文近期在 MLSys 2020 上發表，並進行了遠程 Oral 演講。
論文地址：https://proceedings.mlsys.org/static/paper_files/mlsys/2020/7-Paper.pdf
MNN 開源地址：https://github.com/alibaba/MNN
註：受 Conv-19 疫情影響，今年包括 AAAI 等會議在內的諸多受邀進行的 Oral 演講都通過遠程的方式進行。
具體而言，MNN 提出了三大核心創新：
運行時半自動搜索架構卷積算法優化創新異構設備混合調度
MNN 的整體框架如下圖：
運行時半自動搜索架構
半自動搜索，是在模型結構已知的情況下，在已有的高性能計算模塊中，按照一定規則，搜索、組合出最適應該模型的計算方案。它是介於以 TVM 為代表的的全自動搜索（i.e. 自動調優）和以 NCNN 為代表的全手動搜索（i.e. 手工實現每個 case）之間一種新穎的設計思想。它的核心洞察在於，TVM 的自動編譯優化，難以匹敵針對硬體特性和算子的手寫彙編；同時，模型算子、參數的 case 組合無窮多，無法針對每個 case 進行優化。在最後的「數據論證」部分，我們會用實驗數據展示 MNN 相對於全自動搜索（TVM）和全手動搜索（NCNN）的優勢。
為了支撐運行時半自動搜索的能力，MNN 提出了一個特殊的處理過程，稱為「預推理」。預推理過程中，會提前進行算子的計算策略選擇和資源分配。
一般情況下深度學習的應用輸入尺寸變動的頻率比較小或者可以經過特定的預處理階段變成相對歸一的尺寸。而在輸入尺寸確定的情況下，我們可以對模型中每個 Op，計算出它的輸出大小以及不同計算策略的消耗以及資源需求量，並以此為依據決定每個 Op 的計算策略，提前進行資源的分配。
計算策略選擇
算子的計算策略，包含算法與運行後端的選擇。每種算子可以有多種計算策略，不同計算策略適用於不同的輸入尺寸，MNN 採用 Cost 計算的方式，去決定計算策略的選取。算法的 Cost 與運行後端的調度 Cost 共同決定了一種計算策略的 Cost。公式如下：
運行後端的調度 Cost，我們通過在大量實際的機器上測試獲得。而需要重點關注的是不同算法實現的 Cost。
以卷積為例，假定輸入尺寸為
，輸出尺寸為
，卷積核大小為
，則有兩種計算策略：
滑窗/矩陣乘 與 Winograd 算法。
滑窗/矩陣乘的 Cost 為：
Winograd 算法需要先把圖像劃分為
個小塊（
，自行指定），然後針對這些小塊執行四個步驟：
其中
可以預先計算，實際計算過程為後三個步驟，這三步的計算量分別是
和
，
所以
為：
n 增大時，前後變換耗時增加，中間的乘法數減少，因此
先降後升，需要找最小值。
與
相比，取最小，即為卷積的計算策略 Cost：
具體的滑窗/矩陣乘、Winograd 算法的選擇流程，可參考下圖：
資源預分配
大多數推理框架都會提到「內存復用」，即在網絡運行前離線或在線算好每個 feature map 的大小，然後根據數據依賴關係計算一個最大所需內存，申請並把各個 feature map 的指針計算出來。這樣做存在一些不易擴展的問題：
沒有考慮算子內部需要緩存的問題，在不同的計算策略下，算子自身可能需要或不需要緩存（比如卷積用滑窗不需要緩存，用 Winograd 算法需要），這時候算子內部的緩存無法復用或預先分配，會增加內存佔用或者影響性能。Feature map 對於異構設備而言（主要是 GPU），所需要的資源往往不僅是一塊連續內存，因此異構端無法用同一套內存復用機制，往往需要另外寫。網絡中有可能需要做多路並行，比如 CPU、GPU 各一路，這樣之前按整個網絡算出來的內存地址就無效了。
MNN 採用一種靈活而簡單的策略，解決了資源預分配與復用的問題：
1.計算一遍數據依賴，為每個 Tensor 計算引用計數
2.針對每個算子，把資源管理與計算的代碼分開，其中資源管理的代碼包括：
（1）計算輸出大小
（2）依據輸出大小申請 Tensor 資源
（3）算子做 resize 準備：計算策略選擇-申請並回收緩存
（4）回收引用計數清零後的輸入 Tensor 的資源，回收之後可供下次分配使用
3.在預推理過程中，僅執行資源管理的代碼。在推理過程中，僅執行計算的代碼。
對於 CPU 而言，資源管理就是內存的申請與釋放，資源預分配分別在 MI6 和 P10 上降低了 6.5% 和 7.6% 的推理延時。而在使用 Vulkan 時，資源管理包括顯存的申請與釋放、Pipeline 資源的創建、Command Buffer 的創建等，這時資源預分配的收益十分可觀，分別在 MI6 和 P10 上降低了 75.2 % 和 49.5 % 的推理延時。
卷積算法優化創新
NC4HW4 格式
在推理應用中，大部分算子的輸入輸出是 NCHW 四維，算子一般可在 N 和 C 方向天然並行，且 N 一般為 1。因此，MNN 採用 NC4HW4 格式，便於算子的 SIMD 優化。下圖以向量乘 VMUL 指令為例，說明為什麼 NC4HW4 對於性能優化更加合適：
端上硬體支持以 4 為單元的向量運算。CPU SIMD 與 GPU SIMT+SIMD 均是如此。深度學習領域中大部分算子具有通道可拆分特性
基於以上兩點原因，MNN 大範圍地採用了 NC4HW4 的格式。
Winograd 算法創新
前文所提的 Winograd 算法，在最理想情況下，可以把 卷積的複雜度降到 的複雜度。一般情況下也有 2-4 倍的加速，但它的應用受到如下限制：
Winograd 每次需要計算更多的像素，對於尺寸比較小的 feature map 會有冗餘，影響性能在一些情況下，Winograd 需要前處理/後處理，有可能抵消掉其減少的乘法數收益針對每一種卷積核大小與計算數的組合，都需要實現一份代碼，優化的工程成本高昂
因此其他框架實現 Winograd，僅對用得最多的 的卷積作多套實現，比如 等。
MNN 提出一種新的實現方案，可以較低的代碼編寫成本來對所有類型的卷積達到足夠的加速：
1.內置 Winograd 因子生成器，可根據需要的 生成 Winograd 變換所需要的 A, B, G 矩陣，矩陣生成需要初始化一個多項式：
業界常見的方案是設，但這樣 較大時會導致 G 矩陣中的數用浮點表示的誤差變大，MNN 為了避免太大的誤差，設置。
2.將 Winograd 的算法實現改寫為 源變換——重排——矩陣乘——重排——目標變換 的流程，使核心運算由多個點乘轉換為更高效的矩陣乘法：
3.權重進行預計算，使用 A , B 矩陣進行源變換和目標變換的計算
這樣只需要寫一份代碼，就可以實現任意 F(N, K) 的 Winograd 優化，儘管相對於完全手寫的版本性能會差一些，結合前面的半自動搜索的機制，仍然能起到比較明顯的加速效果。
基於任意卷積的 Winograd 優化算法，MNN 可以優化 stride > 1 的反卷積實現，參考：
https://github.com/alibaba/MNN/blob/master/source/backend/cpu/compute/DeconvolutionWithStride.cpp
Strassen 算法創新
對於大矩陣乘 C=AB 的計算，學界很早就有 Strassen 算法，其思路是把 A, B 等分拆成 4 個小塊，進行一系列的加減計算後，進行 7 次小塊矩陣乘，再經過一系列加減計算組裝成 C。這樣，原本需要 8 次小矩陣乘，現在只需要 7 次，就減少了 1 次矩陣乘。
但這個算法在通常的計算優化中難以應用，原因在於：
需要遞歸，影響效率在矩陣不是足夠大時，不如通常的矩陣乘有效率計算過程中需要申請-釋放內存，影響運行效率。
而 MNN 通過預推理機制，解決了 Strassen 算法的落地問題：
把遞歸申請-"執行"-釋放的放到預推理中完成，"執行"步驟僅產生 lambda 函數，供推理時調用用內存讀寫的大小去估 Strassen 算法的收益，判斷是否進一步遞歸，對 的矩陣乘法，判斷公式為 在推理過程中：按順序調用預推理產生的 lambda 函數數組即可，無需遞歸或者申請/釋放資源。
代碼詳見：
https://github.com/alibaba/MNN/blob/master/source/backend/cpu/compute/StrassenMatmulComputor.cpp
https://github.com/alibaba/MNN/blob/master/source/backend/cpu/compute/Convolution1x1Strassen.cpp
異構設備混合調度
與其他深度學習框架的後端 API 不同，MNN 後端 API 的設計理念的獨特性在於兩點：
MNN 後端 API 幫助實現異構設備的「混合調度」：TFLite 這樣的後端 Delegate，會在遇到不支持的算子的時候，回退到算子的 CPU 實現。可以說，TFLite 後端設計是「被動式」的。與 TFLite 這樣的後端 Delegate 不同，MNN 的異構調度是「主動式」的，我們稱之為「混合調度」：MNN 在創建推理會話時，可以針對算子配置後端，且配置多於一個後端時，會根據後端實現動態選擇對性能最優的後端。同時，會話負責銜接後端間的數據拷貝，單一後端僅需實現到數據緩存區域的讀寫，而無需感知其他後端的存在。這樣，就可以在單會話內或多會話間實現後端的自由組合。在後端不支持或性能不適合實現特定算子時，就可以藉助其他後端的實現，完成整個推理過程。MNN 後端 API 的為算子抽象級別，而非例如 TFLite 的子圖抽象級別。也就是說，在 MNN 的後端實現中，每個算子是單獨實現的，後端實現不需要考慮子圖的拓撲結構與優化。這一點，與前文所提的「半自動搜索」有關：在預處理過程中，整個計算圖的圖優化已經統一提前完成，所以不需要在後端子圖實現。另外，算子級別的後端抽象，也極大的提高了後端實現的可調試性：可以將實現有誤的後端算子快速定位。
MNN 後端 API 設計如下圖所示：
藉助於統一的後端 API，MNN 在通用性上取得了很大的成果，支持了目前最廣泛的計算設備，包括 CPU（ArmV7, ARM64, ARM64e），Vulkan，OpenCL，OpenGL，Metal 以及 NPU 等。
數據論證
備註：所有的數據均測試於各框架提供的 benchmark 標準下，時間為 2019.9 月論文提交截稿前。
通用性能測試
我們在移動端上最常見的模型和設備上將 MNN 和其他框架進行了對比。模型層面包含 MobileNet V1, SqueezeNet v1.1 以及 ResNet-18。而設備則採用了業界較為普及的 iPhone 8，iPhone X，小米 6（處理器：驍龍 835）以及 華為 Mate 20（處理器：麒麟 980）。性能實驗考慮了 CPU 和 GPU 兩種類型計算設備，在 CPU 推理性能評測中，我們分別評測了 2 線程及 4 線程的情況；而在 GPU 推理性能評測部分我們則分別對 MNN 支持的所有計算後端都進行了對比。
1. 從上述實驗中不難看出，在絕大多數模型、設備、計算後端上，MNN 比其他現有的推理引擎在性能上快了大約 20% - 40%。
2. 對於 CPU 上的推理來說，由於 MNN 自身實現了高性能的線程池等底層優化，在 4 線程的並行推理實驗中，iOS 平臺上的表現相對其他推理引擎快了 30%，在 Android 平臺上相對其他框架快了 34%。
3. 而對於利用 GPU 做推理：
（1）在 iOS 平臺上，MNN 比起 TF-lite 有較大幅度的性能優勢；而跟蘋果自身的 CoreML 相比則有這略微的劣勢，這一方面經過我們的一些探索，發現和蘋果自身的特殊優化息息相關。
（2）而在 Android 平臺部分，不同的框架都或多或少在支持不同計算後端時上有一些性能缺陷的情況。比如在 小米 6 之類的設備上，NCNN 運行 Vulkan 後端會有明顯的性能差距；而 TF-Lite 的 OpenGL 後端在運行 ResNet-18 表現不盡如人意。而 MNN 則由於自身半自動搜索架構的設計，可以在不同的計算後端中都取得較為優秀的性能表現。
4. MNN 因為採用了比較合理的性能優化手段，在部分高端行動裝置上，多線程下的 CPU 推理性能可以和 GPU 相媲美。
半自動搜索性能優勢對比
為了更充分的證明 MNN 運行時半自動搜索的合理性，我們提出了兩個對照實驗。
第一個對照實驗是針對那些存在比較邊角的算子屬性的情況下，各個框架的表現情況。
因為 Inception-V3 的模型存在諸如 1×7 and 7×1 卷積這樣的邊界條件，所以採用傳統手動彙編逐一優化的方式下，會存在很多性能盲點。因此在結果中可以明顯看出 NCNN 在這種情形下性能會大幅下降。而 MNN 雖然沒有針對這樣的算子屬性進行針對性的優化，但是運行時半自動搜索架構的適應性可以較好的應對這種情況，取得不錯的運行性能。
第二個對照實驗是 MNN 與 TVM 的性能對比。
可以看出，在沒有針對任何模型特定的優化的情況下，MNN 相比於 TVM 有可觀的性能優勢。另外考慮到 TVM 還有模型編譯、調優的過程耗時，MNN 更加適合移動端智能的應用。
總結與展望
MNN 通過半自動搜索，卷積算法優化創新和異構設備的混合調度，達到了在絕大多數情況下，領先於業界的性能。我們意識到性能是端側智能應用非常重要的一環，會在未來持續投入更多創新性的性能優化方案，比如把半自動搜索應用於 MNN 正在建設的動態圖訓練能力中，讓動態搭建的計算圖可以選擇出最適合當前參數的算子實現。另外，我們還看到端智能應用場景正在往 NLP 和 IOT 方向飛速發展。由於 NLP 的模型普遍較大，IOT 設備相比於移動端算力受限，這些都對模型壓縮提出了更高的要求。所以，MNN 在未來除了投資性能優化以外，還會致力於研究更大壓縮比、更好性能提升的模型壓縮算法，讓 MNN 成為端側推理性能、壓縮能力最好的深度學習引擎。