摘要：聯合查找算法是并查集數據結構一種應用。并查集是一種樹型的數據結構，其保持著用于處理一些不相交集合的合并及查詢問題。的特征是刪除節點。目前就職于騰訊事業部，從事神經機器翻譯工作。

5. TF - Graph模塊

TF把神經網絡模型表達成一張拓撲結構的Graph，Graph中的一個節點表示一種計算算子。Graph從輸入到輸出的Tensor數據流動完成了一個運算過程，這是對類似概率圖、神經網絡等連接式算法很好的表達，同時也是對Tensor + Flow的直觀解釋。

5.1 Graph視圖

Tensorflow采用符號化編程，形式化為Graph計算圖。Graph包含節點（Node）、邊（Edge）、NameScope、子圖（SubGraph），圖 5 1是Graph的拓撲描述。

? ?節點分為計算節點(Compute Node)、起始點（Source Node）、終止點（Sink Node）。起始點入度為0，終止點出度為0。

? ?NameScope為節點創建層次化的名稱，圖 3 4中的NameSpace類型節點就是其中一種體現。

? ?邊分為普通邊和依賴邊（Dependecy Edge）。依賴邊表示對指定的計算節點有依賴性，必須等待指定的節點計算完成才能開始依賴邊的計算。

圖 5 1 Graph的拓撲描述

圖 5 2是Graph的UML視圖模型，左側GraphDef類為protobuf中定義的graph結構，可將graph結構序列化和反序列化處理，用于模型保存、模型加載、分布式數據傳輸。右側Graph類為/core/graph模塊中定義的graph結構，完成graph相關操作，如構建(construct)，剪枝(pruning)、劃分(partitioning)、優化(optimize)、運行(execute)等。GraphDef類和Graph類可以相關轉換，如圖中中間部分描述，函數Graph::ToGraphDef()將Graph轉換為GraphDef，函數ConvertGraphDefToGraph將GraphDef轉換為Graph，借助這種轉換就能實現Graph結構的網絡傳輸。

圖 5 2 Graph的UML視圖

Graph-UML圖中還定義了Node和Edge。Node定義函數操作和屬性信息，Edge連接源節點和目標節點。類NodeDef中定義了Op、Input、Device、Attr信息，其中Device可能是CPU、GPU設備，甚至是ARM架構的設備，說明Node是與設備綁定的。類FunctionDefLibrary主要是為了描述各種Op的運算，包括Op的正向計算和梯度計算。FunctionDef的定義描述見圖 5 3。

圖 5 3 FunctionDef的定義

圖 5 4是FunctionDef舉例，對MatMulGrad的梯度描述，其中包含函數參數定義、函數返回值定義、模板數據類型定義、節點計算邏輯。

圖 5 4 FunctionDef舉例：MatMulGrad

5.2 Graph構建

有向圖（DAG）由節點和有向邊組成。本章節主要講述TF如何利用組合成完整的graph的。假設有如下計算表達式：t1=MatMul(input, W1)。

圖 5 5 Graph簡單示例

圖 5 5中圖計算表達式包含3個節點，2條邊，描述為字符串形式如下。

5.3 Graph局部執行

Graph的局部執行特性允許使用者從任意一個節點輸入（feed），并指定目標輸出節點（fetch）。圖 5 6是TF白皮書中描述Graph局部執行的圖。[15]

圖 5 6 Graph局部執行

5.4 Graph設備分配

TF具有高度設備兼容性，支持X86和Arm架構，支持CPU、GPU運算，可運行于Linux、MacOS、Android和IOS系統。而且，TF的設備無關性特征在多設備分布式運行上也非常有用。

Graph中每個節點都分配有設備編號，表示該節點在相應設備上完成計算操作。用戶既可以手動指定節點設備，也可以利用TF自動分配算法完成節點設備分配。設備自動算法需要權衡數據傳輸代價和計算設備的平衡，盡可能充分利用計算設備，減少數據傳輸代價，從而提高計算性能。

Graph設備分配用于管理多設備分布式運行時，哪些節點運行在哪個設備上。TF設備分配算法有兩種實現算法，第一種是簡單布放算法（Simple Placer），第二種基于代價模型（Cost Model）評估。簡單布放算法按照指定規則布放，比較簡單粗放，是早期版本的TF使用的模型，并逐步被代價模型方法代替。

5.4.1 Simple Placer算法

TF實現的Simple Placer設備分配算法使用union-find方法和啟發式方法將部分不相交且待分配設備的Op節點集合合并，并分配到合適的設備上。

Union-find（聯合-查找）算法是并查集數據結構一種應用。并查集是一種樹型的數據結構，其保持著用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。Union-find定義了兩種基本操作：Union和Find。

? ?Find：確定元素屬于哪一個子集。它可以被用來確定兩個元素是否屬于同一子集。

? ?Union：將兩個子集合并成同一個集合。即將一個集合的根節點的父指針指向另一個集合的根節點。

啟發式算法（Heuristic Algorithm）定義了節點分配的基本規則。Simple Placer算法默認將起始點和終止點分配給CPU，其他節點中GPU的分配優先級高于CPU，且默認分配給GPU:0。啟發式規則適用于以下兩種場景：

? ?對于符合GeneratorNode條件（0-indegree, 1-outdegree, not ref-type）的節點，讓node與target_node所在device一致，參見圖 5 7。

TF中Simple Placer的實現定義在文件core/common_runtime/simple_placer.cc。文件中主要定義了兩個類：ColocationGraph和SimplePlacer。ColocationGraph類利用Union-find算法將節點子集合合并成一個節點集合，參考成員函數ColocationGraph:: ColocateNodes實現。SimplePlacer類實現節點分配過程，下面將主要介紹SimplePlacer:: Run()函數的實現過程。

5.4.2 代價模型

TF使用代價模型（Cost Model）會在計算流圖生成的時候模擬每個device上的負載，并利用啟發式策略估計device上的完成時間，最終找出預估時間較低的graph設備分配方案。[1]

Cost model預估時間的方法有兩種：

? ?使用啟發式的算法，通過把輸入和輸出的類型以及tensor的大小輸入進去，得到時間的預估

? ?使用模擬的方法，對圖的計算進行一個模擬，得到各個計算在其可用的設備上的時間。

啟發式策略會根據如下數據調整device的分配：節點任務執行的總時間；單個節點任務執行的累計時間；單個節點輸出數據的尺寸。

圖 5 9代價模型UML視圖

TF中代價模型的實現定義在文件core/graph/costmodel.cc和core/common_runtime/ costmodel_manager.cc，其UML視圖參見圖 5 9。

Cost model manager從graph創建cost model，再評估計算時間，如下。

? ?Function Inlining (函數內聯)

函數內聯處理可減少方法調用的成本。在TF中包含以下幾種方法：

? ?RemoveListArrayConverter(g)：” Rewrites _ListToArray and _ArrayToList to a set of Identity nodes”.

? ?RemoveDeadNodes(g)：刪除DeatNode。DeatNode的特征是”not statefull, not _Arg, ?not reachable from _Retval”.

? ?RemoveIdentityNodes(g)：刪除Identity節點。如n2=Identity(n1) + Identity(n1); ?優化后: ?n2=n1 + n1;

? ?FixupSourceAndSinkEdges(g)：固定source和sink的邊

? ?ExpandInlineFunctions(runtime, g)：展開內聯函數的嵌套調用

其中_ListToArray、_ArrayToList、_Arg、_Retval均在core/ops/function_ops.cc中定義。

Graph優化相關測試文件在common_runtime/function_test.cc，調試方法：

作者簡介：

姚健，畢業于中科院計算所網絡數據實驗室，畢業后就職于360天眼實驗室，主要從事深度學習和增強學習相關研究工作。目前就職于騰訊MIG事業部，從事神經機器翻譯工作。聯系方式： yao_62995@163.com