[發明專利]一種基于遺傳算法的異構多核處理器任務分配與調度策略

有效

• 申請號: 201911315383.0
• 申請日: 2019-12-18
• 公開（公告）號: CN111061569B
• 公開（公告）日: 2023-05-09
• 發明（設計）人: 方娟;章佳興
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/126;G06F1/329
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 吳蔭芳

本發明提出了一種基于遺傳算法的異構多核處理器系統的任務分配與調度策略，異構多核處理器的任務分配與調度包括全局任務調度器中的任務分配和各個處理單元上的本地調度.主要過程可以分為以下幾個步驟：首先將全局任務調度器中的一個任務按照各個子任務的順序和通信信息轉換為一個有向無環圖，這個有向無環圖用一個DAG圖表示.然后將各個子任務發送到各個處理單元，每個處理單元按照本地任務序列進行處理.最后在運行過程中使用改進的遺傳算法對任務分配與調度方案進行優化.將遺傳算法求解的近似最優解作為分配與調度方案，此方案可以在該任務下一次執行時直接使用，提高異構多核處理器系統的效能、節約能耗。

技術領域

本發明屬于計算機系統結構領域，具體涉及一種基于遺傳算法的CPU-GPU?異構多核處理器任務分配與調度策略.

背景技術

伴隨著制造工藝的升級，特別是7納米技術的應用，處理器體系結構發生?了巨大的變革.傳統的單核結構被物理設計極限和能耗等一系列原因所制約，必?然導致摩爾定律重點由單純的晶體管數量轉移到可以被集成在芯片上的核心數?量.多核處理器在一個芯片上集成多個處理單元，相比于單核架構優勢明顯，可?以在相對較低的頻率下運行單個處理器需要很高的頻率才能提供的計算性能，?完善單核處理器散熱面積過小、高負載運行導致的散熱問題.多核處理器架構已?經得到了學術界和工業界的普遍認可.

根據處理器系統之間的內核差異，將多核處理器系統分為同構多核處理器?系統和異構多核處理器系統.同構多核處理器系統在提升系統整體性能時存在一?些不可避免且難以處理的問題.Kumar?R等人指出同構多核處理器只是簡單的核?堆砌，勢必會增加能耗和散熱的負擔.在接近系統性能瓶頸時，繼續通過簡單的?增加相同結構的處理器內核再也無法顯著提高多核處理器整體性能，這也是非?常著名的Amdahl定理，整個系統的性能受到軟件中必須串行部分的制約.異構?多核處理器在一定程度上彌補了同構多核處理器的不足，Rakesh?Kumar等人指?出異構多核處理器雖然不能完全解決這一問題，但是可以在很大程度上緩和?Amdahl定律，并且在提升系統吞吐量，節約能耗等方面也相對于同構處理器有?較大優勢.著眼未來，異構是處理器系統發展的必然趨勢.

雖然異構多核處理器在能耗方面優于同構多核處理器，但能耗問題仍然是?制約處理器發展的一大障礙。

多核處理器系統的任務分配與調度對系統運行能耗有很大影響，在早期研?究者致力于通過任務分配來降低同構多核處理器耗能，取得了出色的結果.隨著?異構多核處理器的興起，很多研究者將研究重點轉移到異構多核處理器系統的?任務分配領域.異構多核處理器內部結構設計更加復雜，任務調度的難度更大.?不少研究者將智能算法通過改進優化應用在異構多核處理器任務分配領域，取?得了豐碩的成果.

Baruah?S對任務分配模型進行線性規劃建模求解，通過解決線性規劃問題?處理任務分配，第一次論證了異構多核處理器的周期性任務分配是一個NP難?問題.雖然這是一個NP難問題，但是很多算法可以解決異構多核處理器環境?中實時任務分配問題，包括傳統的實時任務調度算法，如截止-單調(DM)算?法，速率-單調(RM)算法，最小松弛優先(LLF)算法，最早期限優先(EDF)?算法，以及基于線性規劃的(LP)算法和近年來非常熱門的群體智能算法，如?蟻群優化(ACO)，粒子群算法(PSO)，遺傳算法(GA)，蛙跳算法(SFLA)?等.