摘要：聯(lián)合查找算法是并查集數(shù)據(jù)結(jié)構(gòu)一種應(yīng)用。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，其保持著用于處理一些不相交集合的合并及查詢問題。的特征是刪除節(jié)點(diǎn)。目前就職于騰訊事業(yè)部，從事神經(jīng)機(jī)器翻譯工作。

5. TF - Graph模塊

TF把神經(jīng)網(wǎng)絡(luò)模型表達(dá)成一張拓?fù)浣Y(jié)構(gòu)的Graph，Graph中的一個(gè)節(jié)點(diǎn)表示一種計(jì)算算子。Graph從輸入到輸出的Tensor數(shù)據(jù)流動(dòng)完成了一個(gè)運(yùn)算過程，這是對(duì)類似概率圖、神經(jīng)網(wǎng)絡(luò)等連接式算法很好的表達(dá)，同時(shí)也是對(duì)Tensor + Flow的直觀解釋。

5.1 Graph視圖

Tensorflow采用符號(hào)化編程，形式化為Graph計(jì)算圖。Graph包含節(jié)點(diǎn)（Node）、邊（Edge）、NameScope、子圖（SubGraph），圖 5 1是Graph的拓?fù)涿枋觥?/p>

? ?節(jié)點(diǎn)分為計(jì)算節(jié)點(diǎn)(Compute Node)、起始點(diǎn)（Source Node）、終止點(diǎn)（Sink Node）。起始點(diǎn)入度為0，終止點(diǎn)出度為0。

? ?NameScope為節(jié)點(diǎn)創(chuàng)建層次化的名稱，圖 3 4中的NameSpace類型節(jié)點(diǎn)就是其中一種體現(xiàn)。

? ?邊分為普通邊和依賴邊（Dependecy Edge）。依賴邊表示對(duì)指定的計(jì)算節(jié)點(diǎn)有依賴性，必須等待指定的節(jié)點(diǎn)計(jì)算完成才能開始依賴邊的計(jì)算。

圖 5 1 Graph的拓?fù)涿枋?/p>

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

圖 5 2 Graph的UML視圖

Graph-UML圖中還定義了Node和Edge。Node定義函數(shù)操作和屬性信息，Edge連接源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。類NodeDef中定義了Op、Input、Device、Attr信息，其中Device可能是CPU、GPU設(shè)備，甚至是ARM架構(gòu)的設(shè)備，說明Node是與設(shè)備綁定的。類FunctionDefLibrary主要是為了描述各種Op的運(yùn)算，包括Op的正向計(jì)算和梯度計(jì)算。FunctionDef的定義描述見圖 5 3。

圖 5 3 FunctionDef的定義

圖 5 4是FunctionDef舉例，對(duì)MatMulGrad的梯度描述，其中包含函數(shù)參數(shù)定義、函數(shù)返回值定義、模板數(shù)據(jù)類型定義、節(jié)點(diǎn)計(jì)算邏輯。

圖 5 4 FunctionDef舉例：MatMulGrad

5.2 Graph構(gòu)建

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

圖 5 5 Graph簡單示例

圖 5 5中圖計(jì)算表達(dá)式包含3個(gè)節(jié)點(diǎn)，2條邊，描述為字符串形式如下。

5.3 Graph局部執(zhí)行

Graph的局部執(zhí)行特性允許使用者從任意一個(gè)節(jié)點(diǎn)輸入（feed），并指定目標(biāo)輸出節(jié)點(diǎn)（fetch）。圖 5 6是TF白皮書中描述Graph局部執(zhí)行的圖。[15]

圖 5 6 Graph局部執(zhí)行

5.4 Graph設(shè)備分配

TF具有高度設(shè)備兼容性，支持X86和Arm架構(gòu)，支持CPU、GPU運(yùn)算，可運(yùn)行于Linux、MacOS、Android和IOS系統(tǒng)。而且，TF的設(shè)備無關(guān)性特征在多設(shè)備分布式運(yùn)行上也非常有用。

Graph中每個(gè)節(jié)點(diǎn)都分配有設(shè)備編號(hào)，表示該節(jié)點(diǎn)在相應(yīng)設(shè)備上完成計(jì)算操作。用戶既可以手動(dòng)指定節(jié)點(diǎn)設(shè)備，也可以利用TF自動(dòng)分配算法完成節(jié)點(diǎn)設(shè)備分配。設(shè)備自動(dòng)算法需要權(quán)衡數(shù)據(jù)傳輸代價(jià)和計(jì)算設(shè)備的平衡，盡可能充分利用計(jì)算設(shè)備，減少數(shù)據(jù)傳輸代價(jià)，從而提高計(jì)算性能。

Graph設(shè)備分配用于管理多設(shè)備分布式運(yùn)行時(shí)，哪些節(jié)點(diǎn)運(yùn)行在哪個(gè)設(shè)備上。TF設(shè)備分配算法有兩種實(shí)現(xiàn)算法，第一種是簡單布放算法（Simple Placer），第二種基于代價(jià)模型（Cost Model）評(píng)估。簡單布放算法按照指定規(guī)則布放，比較簡單粗放，是早期版本的TF使用的模型，并逐步被代價(jià)模型方法代替。

5.4.1 Simple Placer算法

TF實(shí)現(xiàn)的Simple Placer設(shè)備分配算法使用union-find方法和啟發(fā)式方法將部分不相交且待分配設(shè)備的Op節(jié)點(diǎn)集合合并，并分配到合適的設(shè)備上。

Union-find（聯(lián)合-查找）算法是并查集數(shù)據(jù)結(jié)構(gòu)一種應(yīng)用。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，其保持著用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。Union-find定義了兩種基本操作：Union和Find。

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

? ?Union：將兩個(gè)子集合并成同一個(gè)集合。即將一個(gè)集合的根節(jié)點(diǎn)的父指針指向另一個(gè)集合的根節(jié)點(diǎn)。

啟發(fā)式算法（Heuristic Algorithm）定義了節(jié)點(diǎn)分配的基本規(guī)則。Simple Placer算法默認(rèn)將起始點(diǎn)和終止點(diǎn)分配給CPU，其他節(jié)點(diǎn)中GPU的分配優(yōu)先級(jí)高于CPU，且默認(rèn)分配給GPU:0。啟發(fā)式規(guī)則適用于以下兩種場(chǎng)景：

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

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

5.4.2 代價(jià)模型

TF使用代價(jià)模型（Cost Model）會(huì)在計(jì)算流圖生成的時(shí)候模擬每個(gè)device上的負(fù)載，并利用啟發(fā)式策略估計(jì)device上的完成時(shí)間，最終找出預(yù)估時(shí)間較低的graph設(shè)備分配方案。[1]

Cost model預(yù)估時(shí)間的方法有兩種：

? ?使用啟發(fā)式的算法，通過把輸入和輸出的類型以及tensor的大小輸入進(jìn)去，得到時(shí)間的預(yù)估

? ?使用模擬的方法，對(duì)圖的計(jì)算進(jìn)行一個(gè)模擬，得到各個(gè)計(jì)算在其可用的設(shè)備上的時(shí)間。

啟發(fā)式策略會(huì)根據(jù)如下數(shù)據(jù)調(diào)整device的分配：節(jié)點(diǎn)任務(wù)執(zhí)行的總時(shí)間；單個(gè)節(jié)點(diǎn)任務(wù)執(zhí)行的累計(jì)時(shí)間；單個(gè)節(jié)點(diǎn)輸出數(shù)據(jù)的尺寸。

圖 5 9代價(jià)模型UML視圖

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

Cost model manager從graph創(chuàng)建cost model，再評(píng)估計(jì)算時(shí)間，如下。

? ?Function Inlining (函數(shù)內(nèi)聯(lián))

函數(shù)內(nèi)聯(lián)處理可減少方法調(diào)用的成本。在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節(jié)點(diǎn)。如n2=Identity(n1) + Identity(n1); ?優(yōu)化后: ?n2=n1 + n1;

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

? ?ExpandInlineFunctions(runtime, g)：展開內(nèi)聯(lián)函數(shù)的嵌套調(diào)用

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

Graph優(yōu)化相關(guān)測(cè)試文件在common_runtime/function_test.cc，調(diào)試方法：

作者簡介：

姚健，畢業(yè)于中科院計(jì)算所網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)室，畢業(yè)后就職于360天眼實(shí)驗(yàn)室，主要從事深度學(xué)習(xí)和增強(qiáng)學(xué)習(xí)相關(guān)研究工作。目前就職于騰訊MIG事業(yè)部，從事神經(jīng)機(jī)器翻譯工作。聯(lián)系方式： yao_62995@163.com