Baidu Astar 2019 Onsite

題目背景

深度學習模型訓練可以被描述為一個有向無環的計算圖的執行。計算圖中的節點叫做 Operator。節點之間有方向的邊代表 Operator 之間的依賴關係,這個依賴關係是由深度學習模型確定的,即一個 Operator 的輸出(Tensor)是另一個 Operator 的輸入,那麼在計算圖中就需要有一條射線連接兩個 Operator。

一個 Operator 可以有多個 Tensor 輸入或者多個 Tensor 輸出。Operator 本身有計算代價,通常是計算 Operator 所需要的時間。Operator 可以運行在多種設備上。同一個設備下在任意時間點只能最多 N 個 Operator 並發執行,如果 N=1,意味著這個設備下執行Operator 只能串列。

執行在不同設備下的 Operator,可以並發執行。

計算圖的起始節點可以有多個,結算圖的終止節點也可以有多個,整個計算圖的節點都執行完算作深度學習模型的一次迭代(Iteration)。

此處用一張 DAG 解釋以上概念

此處用一張 DAG 解釋以上概念

圖中有兩個顏色的節點,代表在不同設備上執行的 Operator,節點中的數字代表 Operator 的計算代價。假設每個設備只允許一個並發,那麼可以給出若干個符合拓撲序的執行順序,例如 ABCFGDEHI,執行代價為 16,也可以是 DEACBFGHI,執行代價為 19。

題目

本題假定計算圖中的 Operator 有兩種類型,一種是計算 Operator,一種是通信 Operator。計算 Operator 在 AI 晶元上執行,通信 Operator 主要在網路通信設備上執行。

通信 Operator 最多有 3 個並發,計算 Operator 最多有 1 個並發。計算圖的總節點數不超過十萬。要求實現一個函數,給定任意計算圖,返回一個符合計算圖拓撲排序的 Operator 執行順序,使得整體計算代價盡量小。

數據

計算圖來源:基於一些計算圖生成規則(規則不公開)隨機生成的計算圖。

比賽開始時,會提供 100 個根據賽題系統生成規則隨機生成的計算圖,以及 10 個真實深度學習模型轉換得到的計算圖,方便選手進行調試和觀察規律。

賽制

三階段綜合排名制,第一階段為熱身階段,主要目的是熟悉基本工具,不計分。第二階段選手的平均計算代價占最終得分 10%,第三階段選手的平均計算代價占最終得分的 90%。

第一階段:選手能夠根據比賽平台提供的幾個計算圖示例,通過程序或者肉眼觀察的方式給出計算圖的執行順序,並提交到 Timeline 系統生成 Timeline 文件。Timeline 文件可以用於在 Chrome 瀏覽器進行可視化,代表計算圖的執行時間線。Timeline 在整個比賽都可以提交,推薦選手在 30 分鐘內完成。

第二階段:計算圖數目 100,由賽題系統生成,提交截止時間是比賽開始後 2.5 小時,到提交時間截止後,系統會運行選手最後一次提交的 CPP 文件作為選手的演算法,10 分鐘內給出榜單。

第三階段:計算圖數目 10000,由賽題系統生成,提交截止時間是比賽開始後 6 小時,隨後半小時內系統會給出選手最終排名,比賽結束。

評分規則

評估系統會對選手提交的演算法進行綜合評估,在賽題系統隨機生成的題目上進行打分。賽題系統生成題目的方式會參考真實深度學習模型的一些統計指標,通過系統規則生成,這部分規則對選手不公開。

得分計算方法:賽題系統會提供基線演算法對賽題進行打分,基線演算法來源於百度開源深度學習框架飛槳中的圖調度引擎的基礎演算法。選手提交的演算法,相對於基線演算法的提升會作為選手的最終得分,得分計算公式如下:

其中,baseline_cost
為飛槳的基礎調度演算法得到計算代價,total_cost 為計算圖所有節點的計算代價總和,user_cost 為選手的演算法得到的計算代價。

關於計算代價:選手提交的程序會被編譯為動態庫與系統聯編,並在集群環境中進行大規模分散式計算,並得到每張圖的計算代價值。

運行超時的計算代價:在集群環境中,我們會為每次運行設置一個超時時間,長度為 10s。如果選手提交的程序在同一張計算圖下超時達到3次,我們認為選手提交的程序運行速度過慢,並給超時的計算圖一個超時代價。超時代價為當前計算圖所有計算節點計算代價總和。

內存超過系統限制的計算代價:系統限制選手的演算法在賽題運行過程中,單個計算圖執行不能超過 16GB 內存,如果內存超限,系統會給出以內存超限代價返回,內存超限代價為當前計算圖所有計算節點計算代價總和。

其他系統類錯誤:運行過程中遇到程序異常退出,視為選手代碼有 Bug,給出異常錯誤的計算代價,異常錯誤的計算代價為當前計算圖所有計算節點計算代價總和。

排名計算方法:選手的演算法打分會根據上述給定的公式進行計算,系統會根據選手的打分進行排名,評分越高排名越靠前。如果評分相同,則根據演算法的執行時間進行排序。演算法的執行時間會在選手得分相同的情況下,在公平環境下重新運行得到。

程序介面

編程語言採用 C++11 標準,編譯器為 gcc 5.4,不允許使用 C++ 基礎庫以外的庫,編譯命令g++ -O3 -lpthread

計算圖的表示格式:計算圖通過一組表達式構成,例如在題目介紹部分展示的計算圖是通過下面這組表達式構成:

                    B=A
                    C=A
                    G=B
                    F=B
                    E=D
                    H=C#E#G
                    I=H

比賽中,每個計算圖相關的表達式以及節點的詳細信息存放在單獨的文件夾下。比如在 task_example 中,這些表達式存放在 expressions.txt 文件中, 同時,每個節點的詳細信息(比如權重,顏色等)存放在 nodes 文件夾下,節點所在文件的名字為 node_x.txt, 其中 x 表示顏色信息。在 task_example 中,計算圖中的節點有兩種顏色,這兩種顏色所對應的節點信息分別存放在 node_0.txt 和 node_1.txt 中。

                    ├── task_example
                    │   ├── expressions.txt
                    │   └── nodes
                    │       ├── node_0.txt
                    │       └── node_1.txt

選手需要實現的介面:std::vector<std::string> execution_order(const std::string& node_path);

execution_order 的輸入為計算圖表達式和節點所在的路徑,輸出為執行所有節點的 topo.txt 序列,輸出的形式為節點的 name。

Timeline