[發明專利]一種任務調度方法及裝置

在審

• 申請號: 201610715089.9
• 申請日: 2016-08-24
• 公開（公告）號: CN107783831A
• 公開（公告）日: 2018-03-09
• 發明（設計）人: 李航
• 申請（專利權）人: 深圳市中興微電子技術有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京派特恩知識產權代理有限公司11270
• 代理人: 張穎玲,蔣雅潔

技術領域

本發明涉及任務調度技術，尤其涉及一種任務調度方法及裝置。

背景技術

在嵌入式多處理器系統中，經常會出現這樣一種情況，即：一些處理器的負載很重，而另一些處理器的負載卻很輕，甚至空閑。然而，這種情況無疑會降低整體系統的工作效率。為了提高處理器的利用率以及整體系統并行計算的效率，應該把負載過重的處理器上的一部分負載即任務轉移到空閑的或負載較輕的處理器上，這就出現了關于處理器的負載分配問題的研究。

目前，解決處理器負載分配問題時，通常采用粒子群算法獲得最優解作為處理器調度的方案；所謂傳統粒子群算法是受鳥群覓食行為的啟發而提出的，其基本思想是通過群體中個體之間的協作和信息共享來尋找最優解。粒子群算法將粒子群體中的每個個體看作是搜索空間中的一個沒有體積的微粒，并且在搜索空間中從一個隨機初始位置根據隨機初始速度飛行。每個粒子代表解空間的一個候選解，粒子的飛行速度根據自身的飛行經驗和同伴的飛行經驗來進行動態調整。每個粒子在飛行過程中所經歷過的最好位置就是該粒子本身找到的個體最優解，整個粒子群體所經歷過的最好位置就是整個粒子群體目前所找到的整體最優解。每個粒子都通過個體最優解和整體最優解不斷地更新自己，從而產生新一代粒子群體，直到達到規定的迭代次數或者滿足規定的誤差標準為止。但是，現有的粒子群算法在求解調度問題時都存在早熟收斂、易陷入局部最優、進化后期算法收斂速度明顯下降等缺點。

顯然，現有技術中沒有合適、優化的算法能用于解決求解調度問題，基于算法求解來實現處理器的負載分配和任務優化調度尚沒有好的解決方案。

發明內容

有鑒于此，本發明實施例提供了一種任務調度方法及裝置，能基于合適的算法求解來優化、全面、有效地解決任務調度問題。

為達到上述目的，本發明的技術方案是這樣實現的：

本發明實施例提供了一種任務調度方法，所述方法包括：

重復執行任務隨機分配操作，獲得包含有Q種任務分配方式的初始處理器分配方案；所述任務隨機分配操作為將所有N個任務隨機分配于M個處理器中；M、N、Q為自然數且M<N；

重復執行下述操作，直至找到最終任務分配方式：

基于局部搜索和全局搜索更新處理器分配方案，計算更新后的處理器分配方案中每種任務分配方式下所有N個任務在M個處理器中完成所需的時間；

當所需時間最短的任務分配方式滿足要求時，將所述所需時間最短的任務分配方式作為任務調度的最終任務分配方式。

上述方案中，所述方法還包括：

當所需時間最短的任務分配方式不滿足要求時，對所述更新后的處理器分配方案中的任務分配方式執行變異操作。

上述方案中，所述將所有N個任務隨機分配于M個處理器中，包括：

隨機選擇[1,M]之間的一個整數隨機數m₁，并從所有N個任務中隨機選擇一個任務分配給第m₁個處理器；隨機選擇[1,M]之間的一個整數隨機數m₂，并從剩余的N-1個任務中隨機選擇一個任務分配給第m₂個處理器；以此循環，直至所有N個任務都被分配給M個處理器，獲得一種任務分配方式。

上述方案中，所述基于局部搜索和全局搜索更新處理器分配方案，包括：

利用粒子群算法對當前的處理器分配方案進行局部搜索，獲取所述當前的處理器分配方案中的局部最優任務分配方式；

將所述當前的處理器分配方案中的局部最優任務分配方式下所有N個任務在M個處理器中完成所需的時間作為第一時間；所述當前的處理器分配方案中的全局最優任務分配方式下所有N個任務在M個處理器中完成所需的時間作為第二時間；

確定所述第一時間小于或等于所述第二時間時，將所述當前的處理器分配方案中的全局最優任務分配方式替換為所述當前的處理器分配方案中的局部最優任務分配方式；

對所述當前的處理器分配方案中的任務分配方式執行交叉操作，獲得更新后的處理器分配方案。

上述方案中，所述利用粒子群算法對當前的處理器分配方案進行局部搜索，獲取所述當前的處理器分配方案中的局部最優任務分配方式，包括：

隨機生成一個包含有I個粒子且每個粒子為一種任務分配方式的初始粒子群，并將所述當前的處理器分配方案中的全局最優任務分配方式作為所述初始粒子群的初始最優粒子加入到所述初始粒子群中；