[發明專利]調度方案生成方法及裝置

有效

• 申請號: 201910057758.1
• 申請日: 2019-01-22
• 公開（公告）號: CN109871270B
• 公開（公告）日: 2021-04-02
• 發明（設計）人: 王毅;吳尚宇;陳家賢;雷潔彥;毛睿;廖好
• 申請（專利權）人: 深圳大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京三聚陽光知識產權代理有限公司 11250
• 代理人: 安志嬌

1.一種調度方案生成方法，其特征在于，所述方法包括：

終端獲取用戶輸入的初始操作信息，所述初始操作信息包括多個初始操作、各初始操作之間的傳輸數據和各初始操作的執行時間；

根據所述初始操作信息建立有向無環圖模型，所述有向無環圖模型的多個任務節點與多個所述初始操作一一對應，各所述任務節點之間的數據依賴關系與各所述初始操作之間的傳輸數據的數據依賴關系相同，各所述任務節點的執行時間與對應的初始操作的執行時間相等；

將所述有向無環圖模型重復執行不同次數作為不同的周期，并將各所述周期內的多個任務節點根據執行時間的長短進行排序，依次分配給所述終端的多個處理單元中完成時間最小的處理單元，得到對應各所述周期的調度方案，并從多個所述調度方案中確定初始調度方案，所述初始調度方案包括所述初始調度方案內的各任務節點與分配的處理單元的分配關系以及所述初始調度方案內的各任務節點的開始處理時間，其中，

所述將所述有向無環圖模型重復執行不同次數作為不同的周期，并將各所述周期內的多個任務節點根據執行時間的長短進行排序，依次分配給所述終端的多個處理單元中完成時間最小的處理單元，得到對應各所述周期的調度方案，并從多個所述調度方案中確定初始調度方案包括：

將所述有向無環圖模型執行一次作為一個周期，所述周期內的全部的任務節點為待分配任務節點，并將所述待分配任務節點按照所述執行時間的大小順序進行排序；

將排在首位的待分配任務節點分配給所述終端的多個處理單元中完成時間最小的處理單元，并根據所述排在首位的待分配任務節點的執行時間更新所述完成時間最小的處理單元的完成時間；

將排在第二位的待分配任務節點作為新的排在首位的待分配任務節點，并執行所述將排在首位的待分配任務節點分配給所述終端的多個處理單元中完成時間最小的處理單元的步驟，直至將全部的所述待分配任務節點分配完畢，得到對應所述周期的調度方案；

所述調度方案包括所述調度方案內的各任務節點的開始處理時間，根據所述調度方案內的各任務節點的開始處理時間和所述調度方案內的各任務節點的執行時間，確定所述調度方案內的各任務節點的結束處理時間的最大值；

根據所述終端的處理單元的數量、所述有向無環圖形模型的執行次數和所述調度方案內的各任務節點的結束處理時間的最大值，得到所述調度方案的利用率，并判斷所述調度方案的利用率是否大于預設利用率閾值；

若所述調度方案的利用率大于預設利用率閾值，則所述調度方案為初始調度方案；

若所述調度方案的利用率不大于預設利用率閾值，則增加所述有向無環圖模型的執行次數，將增加執行次數后的有向無環圖模型作為一個新的周期，執行所述周期內的全部的任務節點為待分配任務節點，并將所述待分配任務節點按照所述執行時間的大小順序進行排序的步驟，直至所述有向無環圖形模型的執行次數達到該預設次數，則各調度方案中利用率最大的調度方案為所述初始調度方案。

2.如權利要求1所述的調度方案生成方法，其特征在于，所述方法還包括：

根據所述初始調度方案確定所述初始調度方案內的各任務節點的重定時值；

根據所述初始調度方案內的各任務節點的執行時間和各所述任務節點之間的數據依賴關系，調整所述初始調度方案內的各任務節點的開始處理時間和重定時值，得到目標調度方案，所述目標調度方案包括所述初始調度方案內的各任務節點與分配的處理單元的分配關系、初始調度方案內的各任務節點調整后的開始處理時間以及初始調度方案內的各任務節點調整后的重定時值。

3.如權利要求1所述的調度方案生成方法，其特征在于，通過如下公式，根據所述終端的處理單元的數量、所述有向無環圖形模型的執行次數和所述調度方案內的各任務節點的結束處理時間的最大值，得到所述調度方案的利用率：

其中，V表示所述調度方案中任務節點T_i(i＝1,...,n)的集合，X_p表示所述有向無環圖形模型的執行次數，c_i表示任務節點T_i的執行時間，h表示所述終端的處理單元的數量，c_p表示所述調度方案內的各任務節點的結束處理時間的最大值。