[發明專利]一種基于MILP的周期關聯任務異構多核映射調度方法

有效

• 申請號: 201711448660.6
• 申請日: 2017-12-27
• 公開（公告）號: CN108108237B
• 公開（公告）日: 2021-09-28
• 發明（設計）人: 高溦;凌翔;陳亦歐;鄭宏亮;陳朱疊
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 四川力久律師事務所 51221
• 代理人: 王蕓;熊曉果

本發明公開了一種基于MILP的周期關聯任務異構多核映射調度方法，在保證關聯任務的先后約束與通信，以及任務周期性的不交疊執行的前提下，基于混合整數線性規劃來最小化所使用的處理器核數目或者最小化調度延時，求解得到最優調度方案。因此，本發明能夠有效地解決架構為全連接的異構多核系統中有先后約束的周期任務的映射調度問題。

技術領域

本發明涉及異構多核系統的映射調度方法，特別涉及一種基于MILP的周期關聯任務異構多核映射調度方法。

背景技術

在實時通信系統中，通信處理過程可以被模型化為周期關聯任務集，其中每一個通信模塊被視為一個子任務，數據的依賴關系被視為任務與任務間的先后關系，而每一個通信模塊都是周期性的到來，而且每個模塊的數據幀呈倍數關系。為了處理連續不斷的數據流，任務模塊通常都是計算密集型和高度并行化的，因此它們非常適合在多核系統中執行。對于當下發展迅速的移動通信應用來講，多核處理器具有極大的優勢，在通信領域具有極其廣泛的應用。在眾多的多核系統中，異構多核變得越來越受關注，通過將多個計算能力不同的處理器集成在一起，能夠提供更有效的處理能力。而如何應用異構多核處理器來實現多種多樣的通信系統以及完成多標準的解決方案，首要考慮的是周期關聯任務在異構多核系統中的映射調度問題。

周期關聯任務在異構多核系統中的映射調度問題即是如何把N個周期任務分配到合適的處理器上以及安排每個處理器上任務的執行順序。每個任務由執行時間以及任務周期進行表征，任務的任意兩個連續實例間的時間間隔等于其周期，一旦任務的開始時間以及執行的處理器被指定以后，任務將會在確定的時間點上周期性的執行，且與其他的任務不發生沖突，即執行時間不交疊。

雖然周期關聯任務在異構多核系統中的映射調度問題已經被證明是NP難問題，同時研究者們也針對不同的問題背景做出了大量的研究。但由于在實際應用中，存在通用處理器以及專用處理器(如DSP、FPGA等)協同處理任務的應用場景，而該應用場景下的多處理器架構是包含多個異構的處理器池，每個處理器池中包含的處理器是同構的，處理器之間是全連接的。而目前還沒有針對周期關聯任務在該異構多核處理器架構中的映射調度的研究。

發明內容

本發明的目的在于克服現有技術中所存在的上述不足，提供一種能夠將有先后約束的周期任務映射調度到異構多處理器中的映射調度算法，并使得所用的處理器數目最少或者調度延時最短。

為了實現上述發明目的，本發明提供了以下技術方案：

一種基于MILP的周期關聯任務異構多核映射調度方法，其特征在于，包括，

任務定義；其中，給定N個任務，任務集表示為T＝{τ₁，τ₂，…，τ_N}，每個任務的周期為T_i，任務的第一次執行時間為s_i，任務的執行時長為b_mi；當兩任務τ_i，τ_j相關聯時表示為τ_i→τ_j，且任務τ_i與任務τ_j之間的通信時長為e_ij；給定M個處理器池，處理器池集表示為Φ＝{ψ₁，ψ₂，…，ψ_M}，每個處理器池中包含P個處理器，處理器池中的處理器集定義為P＝{p₁，p₂，…，p_P}；

設定約束條件；其中，設定的約束條件包括：

任務執行約束條件：

任務映射約束條件：其中二元變量map_imp＝{0，1}，當map_imp為1時表示任務τ_i被映射到第m個處理器池的第p個處理器上；