[發明專利]一種數據流架構中基于網絡負載特征進行指令調度的方法

在審

• 申請號: 201710787808.2
• 申請日: 2017-09-04
• 公開（公告）號: CN107665127A
• 公開（公告）日: 2018-02-06
• 發明（設計）人: 馮煜晶;張浩;吳冬冬;葉笑春
• 申請（專利權）人: 北京中科睿芯智能計算產業研究院有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司11139
• 代理人: 孫皓晨

技術領域

本發明涉及數據流架構中的指令調度方法，具體而言，涉及一種數據流架構中基于網絡負載特征進行指令調度的方法。

背景技術

隨著計算機體系結構的發展，領域專用的計算機體系結構成為主要發展趨勢。在面向特定應用時，專用型結構利用應用特征對結構進行相應的優化，從而更好地發揮出硬件的計算性能。在高性能計算領域，數據流計算是領域專用計算結構的一個重要分支，數據流計算表現出了較好的性能和適用性。數據流架構通常都包括若干個或者十幾個計算節點(計算節點稱為processing element，簡稱PE)，每個計算節點都是運算能力較強但是控制能力較弱、復雜度較小的核心。每個計算節點內設置N個指令槽，每個指令槽內保存這條指令執行所需的操作數信息，當指令對應的所有源操作數都已經準備好同時該指令的下游也準備好接收結果數據時，這條指令就可以被指令調度邏輯選擇進入到該計算節點的執行流水線當中。每個計算節點內的指令調度邏輯在每個時鐘周期都會從那些準備好的指令當中進行選擇然后發射到執行流水線當中。一般的指令調度邏輯都是選擇根據指令標號順序采用輪詢(round-robin)的方式進行選擇。如圖1所示為輪詢方式選擇指令的示意圖，一計算節點一共設置16個指令槽(編號分別為0～15)，Cycle1、Cycle2和Cycle3為時間軸上3個連續的時間點。在時間點Cycle1時，16個指令槽當中一共存在4條指令是“Ready”的，可以被調度邏輯選擇發射，此時，在時間點Cycle1選擇2號指令槽。之后，在時間點Cycle2的時候，指令槽當中的2號指令槽由于前一個時間點Cycle1被選中發射到流水線當中，所以在當前時間點Cycle2處于發射狀態，此時，6號、9號、13號和14號指令槽都處于“Ready”狀態，可以被調度邏輯選擇。輪詢的原則是按照指令標號的順序從所有處于“Ready”狀態的指令當中進行選擇，所以在時間點Cycle2時選擇的是6號指令槽。在時間點Cycle3時，采用類似的原理，選擇的是9號指令槽。總結起來，傳統的輪詢方式有2個要素：(1)按照指令的順序進行選擇；(2)從所有“Ready”的指令當中選擇。

可見，傳統的數據流架構當中，一般都是根據指令的源操作數是否完備作為先決條件，然后從這些滿足先決條件的指令當中根據指令的順序進行輪詢選擇，被選出的指令被調度到計算流水線當中執行。如果在數據流架構下，指令被映射到數據流陣列的映射算法和指令的排序同時都能夠較好地考慮到各方面的均衡，這種普通的輪詢調度方式也能夠較好地保持計算資源和網絡負載的均衡；但是如果指令在映射到數據流陣列的時候沒有全面考慮到各方面均衡，可能導致連接數據流陣列的網絡出現局部性繁忙，此時如果仍然采用普通的輪詢策略，執行節點內部的計算流水線會出現停頓等待，計算單元的局部性利用率降低。

一般在數據流架構當中，多個計算節點采用2D mesh結構進行連接，由片上路由(Router)負責在計算單元(PE)之間傳遞操作數。圖2為一片上網絡示意圖，圖3為圖2中一個片上路由201的出口和入口示意圖，如圖2所示，片上網絡由多個計算單元、多個片上路由構成2D mesh結構，SPM為片上路由發送的系統參數報文，如圖3所示，片上路由201內部有5個入口和5個出口。5個入口分別對應東、南、西、北方向和本地PE202，5個出口分別對應東、南、西、北方向和本地PE202。在片上路由201內部，來自不同入口的數據包先分別被放入到各個方向對應的輸入緩存(input buffer)當中，然后對數據包信息進行解析，根據數據包的目的方向從對應的出口發送到下一級節點當中。每個時鐘周期，每個出口可以處理1個數據包。

以上分析了傳統數據流架構中的指令調度策略即輪詢方式的基本過程，以及數據流架構中片上路由的工作原理。可以看出，兩者并沒有緊密的配合，指令調度邏輯在調度指令執行的時候并沒有考慮指令執行結果的發送方向，而是僅僅考慮指令的順序和指令的操作數是否準備好。如果指令映射的時候，在某個方向局部密集，按照原本片上路由的處理速度，該方向會導致執行速度出現瓶頸。另外，如果仍然按照原來的輪詢策略調度指令，則會導致計算節點內部出現流水線的停頓和空閑。

可見，如果計算節點在調度指令的同時考慮網絡擁堵狀況，那么指令調度邏輯可以選擇不擁堵方向上的指令進行調度，從而有助于提高計算節點內部的部件利用率和網絡資源的利用率和吞吐率，這也是本領域技術人員的一個重要目標。

發明內容

本發明提供一種數據流架構中基于網絡負載特征進行指令調度的方法，該方法在指令調度的同時考慮網絡擁堵狀況，以提高計算節點內部的部件利用率和網絡資源的利用率和吞吐率。