[發明專利]一種數據流體系結構中動態節點分配方法和系統

有效

• 申請號: 201710681320.1
• 申請日: 2017-08-10
• 公開（公告）號: CN107632890B
• 公開（公告）日: 2021-03-02
• 發明（設計）人: 歐焱;張浩;李易;譚旭;葉笑春
• 申請（專利權）人: 北京中科睿芯科技集團有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/52
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司 11139
• 代理人: 孫皓晨

本發明公開了一種數據流體系結構中動態節點分配方法，該方法將數據流圖中的節點一一映射到物理執行單元上，被映射的節點稱為死節點，在數據流圖中設置一管理節點，管理節點與每一節點之間均具有一數據傳輸通路；在管理節點設置信息表，將活節點統計在信息表中；為每一死節點分別設置一擁塞閾值；檢測死節點是否擁塞，如果死節點檢測上游節點已執行完畢但是其自身的指令仍正在執行，并且執行時間超過其對應的擁塞閾值，則判定死節點已發生擁塞；當一死節點A發生擁塞時，死節點A則向管理節點發送請求消息；管理節點收到請求消息后根據實際情況將請求消息映射至一活節點上；當該活節點B的租用時間達到租用期限時，管理節點向活節點發出回收請求。

技術領域

本發明涉及數據流體系結構技術領域，具體而言，涉及一種數據流體系結構中動態節點分配方法和系統。

背景技術

隨著大數據計算時代的來臨，數據集的數量和規模對處理器的處理能力的要求也越來越高。數據流體系結構具有大量指令級并行以及存儲器訪問功耗低的特點，因而得到了社會的廣泛關注。在數據流圖的體系結構當中，程序代碼可以轉化為數據流圖。數據流圖是有向圖，其中每個節點表示程序中的一段代碼，有向線段代表節點間的數據流向。傳統的馮諾依曼結構中，指令的之間的數據傳遞是通過存儲器進行交互的，上一條指令將數據存入存儲器當中后，下一條指令從存儲器中將數據讀取出來。在馮諾依曼結構中，共享數據的處理單元之間會因為鎖機制降低性能，頻繁地訪問存儲器也會帶來功耗的提升；而數據流體系結構中的數據直接在指令之間進行傳遞，減少了訪問存儲器的功耗，并且消除了鎖機制造成的性能降低。另外，在數據流體系結構中，指令的并行度高，從而能夠提高執行效率。在數據流圖中，不同的節點的執行速率是不同的，導致下游節點接收源操作數的時間也不相同，節點需要所有源數據到達之后才能夠執行。因此，節點的執行的開始時間取決于最晚到達節點的源數據的時間，而數據流動慢、相互間存在依賴的節點集被稱為關鍵路徑，本發明中，將數據流圖中執行效率低的節點稱為關鍵節點。

為了能夠緩解數據流圖中關鍵操作(關鍵路徑上的低效率的操作)給程序帶來的長延遲的影響，提高數據流圖中節點中功能部件的執行效率，通常采用靜態優化方法進行加速，具體的，在數據流圖中，找出關鍵節點，復制該節點為多個相同的節點，增加執行相同代碼的節點，從而使數據流圖的執行效率能夠提高，如圖1所示為靜態優化方法的示意圖，其中map節點為數據分配節點，用于將前驅節點的數據分配給后繼節點；merge節點是匯聚節點，也是用于將前驅節點的數據分發給后繼節點。這種方法存在的問題是，雖然能夠解決某些關鍵節點執行較慢的問題，但是需要大量的實驗測試和經驗才能判斷出哪些節點是關鍵節點，這會增加預處理的時間。另外，即使是對于同一個應用的數據流圖而言，在程序執行的不同時期，造成數據流圖擁塞的節點片段也不一樣。因此，即使是對同一個數據流圖進行靜態優化，還是很難在程序執行的全部時間段都達到很好的加速效果。

基于以上問題，靜態優化方法需要的預處理時間較長，并且對于同樣一個應用而言，使用靜態優化方法也很難使得全時間段的效率均能夠提升，導致在不同的時間造成計算資源的浪費。因此，需要一種能夠對數據流圖中的節點進行動態分配的方法，以將節點按需分配，并且靈活地對數據流圖進行加速。

發明內容

本發明提供一種數據流體系結構中動態節點分配方法以及系統，用以按照實際需要對數據流圖中的節點進行動態分配，并且靈活地對數據流圖進行加速。

為達到上述目的，本發明提供了一種數據流體系結構中動態節點分配方法，其包括以下步驟：

將數據流圖中的節點一一映射到物理執行單元上，其中，該步驟中被映射的節點稱為死節點，活節點包括未映射的節點和沒有被完全利用的節點，其中，沒有被完全利用的節點指節點對應的物理執行單元的計算資源沒有被完全利用，每一活節點均預設有一租用期限；

在數據流圖中設置一管理節點，管理節點與每一節點之間均具有一數據傳輸通路；