圖優(yōu)化
圖優(yōu)化的概念：
深度神經(jīng)網(wǎng)絡(luò)模型可以看做由多個(gè)算子連接而成的有向無環(huán)圖，圖中每個(gè)算子代表一類操作（如乘法、卷積），連接各個(gè)算子的邊表示數(shù)據(jù)流動(dòng)。在部署深度神經(jīng)網(wǎng)絡(luò)的過程中，為了適應(yīng)硬件平臺(tái)的優(yōu)化、硬件本身支持的算子等，需要調(diào)整優(yōu)化網(wǎng)絡(luò)中使用的算子或算子組合，這就是深度學(xué)習(xí)編譯工具鏈中的核心——圖優(yōu)化。

圖優(yōu)化是指對深度學(xué)習(xí)模型的計(jì)算圖進(jìn)行分析和優(yōu)化的過程，通過替換子圖（算子）為在推理平臺(tái)上性能更佳的另一個(gè)等價(jià)子圖、或優(yōu)化數(shù)據(jù)流動(dòng)，來提高模型推理的性能。圖優(yōu)化的出現(xiàn)很大程度上是因?yàn)?a target="_blank">算法開發(fā)人員不熟悉硬件，在算法層面上可以靈活表達(dá)的一種計(jì)算方式，在硬件底層和推理方式上可能存在顯著的性能差異[1]。

為了更好的理解圖優(yōu)化，我們需要先了解幾個(gè)圖相關(guān)的基本概念。

（1）節(jié)點(diǎn)（Vertex）：圖的重要概念，也是圖的基本單位，可以代表網(wǎng)絡(luò)中的一個(gè)實(shí)體；

（2）邊（Edge）：圖的重要概念，是連接兩個(gè)節(jié)點(diǎn)的線，可以是有向的（箭頭指向一個(gè)方向）或無向的。邊可以表示頂點(diǎn)之間的關(guān)系，如距離、相似性等；

（3）權(quán)重（Weights）：邊的屬性，表示從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的“成本”（如距離、時(shí)間或其他資源消耗）；

（4）路徑（Path）：節(jié)點(diǎn)的序列，其中任意相鄰的節(jié)點(diǎn)都通過圖中的邊相連。

圖 1 圖的基本概念

基于這些基本的概念，我們可以將優(yōu)化問題引入到圖中來，比如最短路徑問題、最小生成樹問題、網(wǎng)絡(luò)流問題、匹配問題等等；為了解決這些優(yōu)化問題，我們也提出了一系列優(yōu)化算法，比如Dijkstra算法、Kruskal算法、Ford-Fulkerson算法等等。

圖優(yōu)化的分類：
圖優(yōu)化問題通常根據(jù)解空間的連續(xù)性可分為“組合優(yōu)化問題”和“連續(xù)優(yōu)化問題”，其中前者的解空間是離散的，后者的解空間是連續(xù)的。

圖 2 組合優(yōu)化問題之“旅行商問題”[2]

（1）組合優(yōu)化問題

組合優(yōu)化問題涉及到在一個(gè)有限的、離散的可能解集合中尋找最優(yōu)解的問題。這類問題的特點(diǎn)是解空間通常由一組離散的選擇構(gòu)成，解決問題的關(guān)鍵在于如何從這些離散的選擇中找到滿足約束條件的最優(yōu)組合。

i.旅行商問題（TSP）：旅行商問題要求找到一條經(jīng)過圖中每個(gè)頂點(diǎn)恰好一次并返回起點(diǎn)的最短可能路徑。這是組合優(yōu)化中的一個(gè)典型問題。

ii.圖著色問題：給定一個(gè)圖，目標(biāo)是使用最少的顏色給圖中的每個(gè)頂點(diǎn)著色，使得任何兩個(gè)相鄰的頂點(diǎn)顏色不同。這是一個(gè)經(jīng)典的NP難（NP-hard）問題。

（2）連續(xù)優(yōu)化問題

與組合優(yōu)化不同，連續(xù)優(yōu)化問題的解空間是連續(xù)的。這意味著問題的變量可以在某個(gè)連續(xù)的范圍內(nèi)取值。連續(xù)優(yōu)化問題在工程、經(jīng)濟(jì)學(xué)、物理學(xué)等多個(gè)領(lǐng)域都有廣泛應(yīng)用。

i.最小二乘問題：在統(tǒng)計(jì)學(xué)和數(shù)據(jù)分析中，最小二乘問題是一種常見的連續(xù)優(yōu)化問題，目標(biāo)是找到一組參數(shù)，使得模型預(yù)測值和實(shí)際觀測值之間的誤差平方和最小。

ii.線性規(guī)劃問題：雖然線性規(guī)劃問題的解可能是離散的，但大多數(shù)情況下它被視為連續(xù)優(yōu)化問題，因?yàn)閱栴}的變量可以在連續(xù)范圍內(nèi)取值。線性規(guī)劃問題的目標(biāo)是在滿足一組線性約束的條件下，最大化或最小化一個(gè)線性目標(biāo)函數(shù)。

綜上所述，在圖優(yōu)化的背景下，組合優(yōu)化問題通常涉及到圖的結(jié)構(gòu)和圖上的離散決策，例如路徑選擇、網(wǎng)絡(luò)設(shè)計(jì)、資源分配等。而連續(xù)優(yōu)化問題可能涉及到圖的邊權(quán)重的連續(xù)調(diào)整，或者在圖表示的某種物理系統(tǒng)中尋找最優(yōu)的連續(xù)狀態(tài)。

圖優(yōu)化的策略：
傳統(tǒng)意義上，圖優(yōu)化包含的具體策略有：

算子融合，將多個(gè)操作融合為一個(gè)復(fù)合操作，減少內(nèi)存訪問次數(shù)和中間數(shù)據(jù)的存儲(chǔ)需求；
常量折疊，在編譯時(shí)期預(yù)先確定結(jié)果的表達(dá)式，減少運(yùn)行時(shí)的計(jì)算量；
內(nèi)存復(fù)用，識(shí)別和優(yōu)化計(jì)算圖中的內(nèi)存使用，減少內(nèi)存分配和釋放操作；
數(shù)據(jù)布局轉(zhuǎn)換，根據(jù)硬件特性調(diào)整數(shù)據(jù)的存儲(chǔ)格式，提高內(nèi)存訪問效率；
算子集并行化，識(shí)別可以并行執(zhí)行的操作，利用硬件處理單元的并行計(jì)算能力；
子圖替換/合并，如圖3所示，將計(jì)算圖中的某些算子替換為在轉(zhuǎn)為硬件優(yōu)化的版本或效率更高的實(shí)現(xiàn)方式。

圖3 深度神經(jīng)網(wǎng)絡(luò)模型中的子圖合并示意圖

對于采用存算一體架構(gòu)設(shè)計(jì)的硬件而言，圖優(yōu)化需要特別考慮減少數(shù)據(jù)移動(dòng)。具體到圖優(yōu)化策略中，考慮到存算一體加速乘累加的特點(diǎn)及硬件資源，主要考慮的圖優(yōu)化策略有：

（1）子圖替換/合并，由于存算一體架構(gòu)芯片支持的加速算子類型有限，如果深度學(xué)習(xí)模型中使用了不受支持的算子，則必須被替換；

（2）數(shù)據(jù)局部性優(yōu)化，確保負(fù)責(zé)計(jì)算卷積的存算一體核心所存儲(chǔ)的權(quán)重在一次計(jì)算中不需要重新寫入，依靠數(shù)據(jù)流動(dòng)到存儲(chǔ)不同權(quán)重的核心進(jìn)行計(jì)算，同時(shí)確立統(tǒng)一的數(shù)據(jù)存儲(chǔ)格式，避免計(jì)算過程中為對其存儲(chǔ)數(shù)據(jù)付出額外的時(shí)間。

圖優(yōu)化的應(yīng)用場景：
圖優(yōu)化的應(yīng)用場景主要體現(xiàn)在優(yōu)化神經(jīng)網(wǎng)絡(luò)以匹配硬件或適應(yīng)需求。圖優(yōu)化針對特定硬件優(yōu)化神經(jīng)網(wǎng)絡(luò)，減少模型的硬件需求、使用針對硬件優(yōu)化的算子，以在終端設(shè)備部署神經(jīng)網(wǎng)絡(luò)模型；針對CPU、GPU、FPGA等不同平臺(tái)進(jìn)行特定優(yōu)化，保證模型的可移植性。圖優(yōu)化針對特定需求，優(yōu)化模型吞吐量，提升云端模型服務(wù)單位時(shí)間可處理的訪問次數(shù)；降低模型處理的延時(shí)，以更快速地處理高分辨率視頻、滿足音頻處理的實(shí)時(shí)性需求。

工具鏈的圖優(yōu)化
圖優(yōu)化和其他網(wǎng)絡(luò)優(yōu)化方法共同支持深度學(xué)習(xí)模型的開發(fā)、訓(xùn)練、優(yōu)化、部署和執(zhí)行過程，是深度學(xué)習(xí)工具鏈的重要組成部分。下面我們將從文獻(xiàn)研究和企業(yè)產(chǎn)品兩個(gè)方面介紹工具鏈圖優(yōu)化的發(fā)展現(xiàn)狀。

1.文獻(xiàn)研究相關(guān)：

圖優(yōu)化有許多經(jīng)典算法，以下列舉了幾個(gè)經(jīng)典算法及其參考文獻(xiàn)，這些圖優(yōu)化經(jīng)典算法為工具鏈的圖優(yōu)化提供了具體的思路與方案。

（1）Dijkstra算法（最短路徑問題）：用于尋找圖中某一節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑，特別適用于帶權(quán)重的有向圖和無向圖[3]。

（2）Kruskal算法（最小生成樹問題）：該算法用于在一個(gè)加權(quán)連通無向圖中尋找最小生成樹，即找到一個(gè)邊的子集，使得這些邊構(gòu)成的樹包括圖中的所有節(jié)點(diǎn)，并且樹的總權(quán)值盡可能小[4]。

（3）Ford-Fulkerson算法（最大流問題）：該算法用于計(jì)算網(wǎng)絡(luò)流中的最大流，通過不斷尋找增廣路徑來增加從源點(diǎn)到匯點(diǎn)的流量，直到無法再增加為止[5]。

（4）Hungarian算法（二分圖最大匹配問題）：該算法用于解決二分圖的最大匹配問題，特別是在工作分配等應(yīng)用中，尋找最優(yōu)匹配方式，使總成本最低[6]。

2.企業(yè)產(chǎn)品相關(guān)：

（1）英偉達(dá)（NVIDIA）[7]

i.產(chǎn)品與技術(shù)：

英偉達(dá)是全球領(lǐng)先的 GPU 龍頭廠商，所生產(chǎn)的GPU被廣泛應(yīng)用于圖計(jì)算，尤其是在需要大量并行處理的場景中。CUDA（Compute Unified Device Architecture）是NVIDIA推出的一個(gè)并行計(jì)算平臺(tái)和編程模型，它允許軟件開發(fā)者和軟件工程師使用C語言等高級(jí)編程語言來編寫程序。

ii.圖優(yōu)化工具鏈：

NVIDIA提供了CUDA圖分析庫（cuGraph），這是一個(gè)基于GPU加速的圖分析算法庫，旨在處理大規(guī)模圖形數(shù)據(jù)。cuGraph提供了一系列優(yōu)化的圖算法，包括最短路徑、PageRank、個(gè)性化PageRank、最大流和最小割等，為工具鏈的圖優(yōu)化提供新的思路。通過利用GPU的并行處理能力，cuGraph能夠顯著加速圖計(jì)算任務(wù)。

（2）谷歌（Google）

i.產(chǎn)品與技術(shù)：

谷歌開發(fā)了TPU（Tensor Processing Unit），專門為深度學(xué)習(xí)應(yīng)用設(shè)計(jì)，其高效的矩陣運(yùn)算能力也可以被應(yīng)用于圖計(jì)算場景，尤其是在圖神經(jīng)網(wǎng)絡(luò)（GNN）等領(lǐng)域。

ii.圖優(yōu)化工具鏈：

TensorFlow是Google開發(fā)的一個(gè)開源機(jī)器學(xué)習(xí)框架，它支持廣泛的機(jī)器學(xué)習(xí)任務(wù)，包括圖計(jì)算。TensorFlow可以利用TPU進(jìn)行加速，從而提高圖計(jì)算的效率。此外，Google也在研究如何優(yōu)化圖算法的執(zhí)行，如圖4所示，為GraphX的架構(gòu)圖，通過GraphX在圖頂點(diǎn)信息和邊信息存儲(chǔ)上進(jìn)行優(yōu)化，使得圖計(jì)算框架性能得到較大提升，接近或到達(dá) GraphLab 等專業(yè)圖計(jì)算平臺(tái)的性能，可以在其大數(shù)據(jù)處理工具Apache Spark上進(jìn)行圖處理[8]。

圖 4 GraphX架構(gòu)圖[8]

（3）Graphcore[9]

i.產(chǎn)品與技術(shù)：

Graphcore公司專注于為機(jī)器學(xué)習(xí)和AI應(yīng)用開發(fā)創(chuàng)新的處理器，稱為智能處理單元（IPU）。IPU設(shè)計(jì)目標(biāo)是提高圖計(jì)算的效率，其架構(gòu)優(yōu)化了復(fù)雜的數(shù)據(jù)結(jié)構(gòu)處理，特別是圖形數(shù)據(jù)結(jié)構(gòu)，這使得其非常適合執(zhí)行圖神經(jīng)網(wǎng)絡(luò)和其他圖計(jì)算任務(wù)。

ii.圖優(yōu)化工具鏈：

Graphcore提供了Poplar軟件開發(fā)工具鏈，這是一個(gè)專為IPU設(shè)計(jì)的軟件堆棧。Poplar包含了一系列圖計(jì)算庫和工具，支持開發(fā)者高效地在IPU上實(shí)現(xiàn)和運(yùn)行圖計(jì)算任務(wù)，從而充分發(fā)揮IPU在圖處理上的優(yōu)勢，專門針對AI和圖計(jì)算任務(wù)提供了優(yōu)化的解決方案，為工具鏈的圖優(yōu)化提供了新的思路。

圖 5 Poplar整體架構(gòu)示意圖[9]

知存科技[10]
i.產(chǎn)品與技術(shù)：

知存科技是全球領(lǐng)先的存內(nèi)計(jì)算芯片企業(yè)。公司針對AI應(yīng)用場景，在全球率先商業(yè)化量產(chǎn)基于存內(nèi)計(jì)算技術(shù)的神經(jīng)網(wǎng)絡(luò)芯片，已有WTM1001、WTM2101、WTM-8等存算一體芯片。

ii.圖優(yōu)化工具鏈：

如圖6所示，WITIN_MAPPER是知存科技自研的用于神經(jīng)網(wǎng)絡(luò)映射的編譯軟件棧，可以將量化后的神經(jīng)網(wǎng)絡(luò)模型映射到WTM2101 MPU加速器上，是一種包括RISC-V和MPU的完整解決方案。WITIN_MAPPER工具鏈可以完成算子和圖級(jí)別的轉(zhuǎn)換和優(yōu)化，將預(yù)訓(xùn)練權(quán)重編排到存算陣列中，并針對網(wǎng)絡(luò)結(jié)構(gòu)和算子給出存算優(yōu)化方案，同時(shí)將不適合MPU運(yùn)算的算子調(diào)度到CPU上運(yùn)算，實(shí)現(xiàn)整網(wǎng)的調(diào)度，讓神經(jīng)網(wǎng)絡(luò)開發(fā)?員高效快捷的將訓(xùn)練好的算法運(yùn)行在WTM2101芯片上，極大縮短模型移植的開發(fā)周期并提高算法開發(fā)的效率。

圖 6 WITIN_MAPPER工具鏈軟件架構(gòu)圖[10]

三．未來展望

當(dāng)前工具鏈的圖優(yōu)化研究相對較多，然而存算一體編譯工具鏈的圖優(yōu)化仍處于起步階段，面臨著許多科學(xué)與技術(shù)問題。此外，由于存算一體架構(gòu)規(guī)模有限，目前存算一體編譯工具鏈的圖優(yōu)化主要是針對硬件的適配，通過層間的調(diào)度優(yōu)化，提高硬件的利用率等。為了解決以上問題，科研工作者仍需進(jìn)行不斷的探索。

同時(shí)，隨著人工智能技術(shù)的持續(xù)發(fā)展，神經(jīng)網(wǎng)絡(luò)的參數(shù)數(shù)量已經(jīng)從Alexnet的6000萬個(gè)增長到OpenAI GPT-3的1750億個(gè)，參數(shù)量以指數(shù)級(jí)別增長，人工智能已進(jìn)入大模型時(shí)代，存算一體編譯工具鏈技術(shù)的研究也逐漸增多。在大模型時(shí)代，存算一體工具鏈的圖優(yōu)化將會(huì)更多地涉及整網(wǎng)的優(yōu)化調(diào)度，從而極大地加快模型的部署與開發(fā)，相信更加成熟全面的存算一體工具鏈圖優(yōu)化技術(shù)指日可待！

參考文獻(xiàn)：

[1] Luchang-Li：深度學(xué)習(xí)性能優(yōu)化之圖優(yōu)化(blog.csdn.net).

[2] 知乎@玻色量子.

[3] E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.

[4]J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.

[5]L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.

[6]H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97.

[7]機(jī)器學(xué)習(xí)和分析 | NVIDIA 開發(fā)者.

[8]Spark GraphX_存儲(chǔ)-CSDN博客.

[9]Poplar? 軟件 (graphcore.ai).

[10]WITMEM 2023.ALL RIGHTS，知存科技.

審核編輯 黃宇