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

有效

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

1.一種基于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個處理器上；

處理器映射約束條件：

其中二元變量pro_mp＝{0，1}，當pro_mp為1時表示至少有一個任務被映射到第m個處理器池的第p個處理器上；

兩任務執行約束條件：

s.t.)i≠j，sep_ij+map_imp+map_jmp≤2

s.t.)i≠j，k≠m or p≠l，sep_ij-map_imp-map_jkl≥-1

b_mi-sep_ijZ≤(s_j-s_i) mod g_i，j≤g_i，j-b_mj+sep_ijZ

其中，二元變量sep_ij＝{0，1}，當sep_ij為1時表示任務τ_i，τ_j被映射到不同的處理器上，而當sep_ij為0時表示任務τ_i，τ_j被映射到同一處理器上；g_i，j為兩任務τ_i，τ_j周期的最大公約數，即g_i，j＝gcd(T_i，T_j)；Z為常量整數；

而且，由于線性規劃需要處理線性的約束條件，而(s_j-s_i)mod g_i，j是非線性的，因此令(s_j-s_i)mod g_i,j＝(s_j-s_i)-q_j，ig_i，j，將(s_j-s_i)mod g_i，j線性化，其中q_j，i為整數變量且q_j，i的取值范圍為

關聯任務約束條件：

情況1，當τ_i→τ_j，T_i＝T_j時，則關聯任務約束條件為：

b_mi-sep_ijZ≤(s_j-s_i)-q_j，ig_i，j≤g_i，j-b_mj+sep_ijZ

其中，c_ij表示任務τ_i與任務τ_j之間的通信開銷；

情況2，當τ_i→τ_j，aT_i＝T_j，a∈N⁺，則關聯任務約束條件為：

情況3，當τ_i→τ_j，T_i＝aT_j，a∈N⁺時，關聯任務約束條件與情況1的關聯任務約束條件一致；

設定目標函數；其中，目標函數為：

或者min max(s_i+b_mi)。