[發明專利]一種嵌入式異構多處理器系統的任務調度方法

有效

• 申請號: 200910100609.5
• 申請日: 2009-07-10
• 公開（公告）號: CN101604258A
• 公開（公告）日: 2009-12-16
• 發明（設計）人: 張禎;鄒青剛;鄭秋華;方美娥;吳國華
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06N3/00
• 代理公司: 杭州求是專利事務所有限公司
• 代理人: 杜 軍

1.一種嵌入式異構多處理器系統的任務調度方法，其特征在于該方法 的具體步驟是：

步驟(1).動態調整粒子速度V

調整粒子的飛行速度，在進化初期，粒子距離最優位置較遠，粒子的飛行 速度應快一些，這樣有利于盡快的移向最優位置；當粒子距離最優位置較近 時，粒子的飛行速度應慢一些，這樣可以避免因飛行速度過快而導致的粒子 “飛過”最優位置從而產生的來回運動現象；

粒子飛行速度的計算方程式如下所示：

Xij(t+1)=Xij(t)+Vij(t+1)×(1+k×sin[(iterImax+12)×π])---(1)]]>

X_ij(t+1)表示在時間點t+1的位移，V_ij(t+1)表示在時間點t+1的速度，iter 表示粒子當前的進化代數；I_max表示粒子的最大進化代數；K為比例系數，是 常量；

通過上述方程式對影響粒子飛行速度的因子進行動態調整，得到一個速 度的最優值；

步驟(2).調整慣性權重w

w仍然隨迭代次數線性遞減，當迭代次數到達某個閾值時，這時w的值為 w_min；然后w隨迭代次數線性遞增，這樣w隨迭代次數變化而變化，有助于 算法擺脫局部極值，增強粒子群優化算法的全局搜索能力，找出最優解；由 此提出慣性權重的調整策略；

慣性權重的粒子群優化算法的慣性權重計算公式如下：

w=wmax-wmax-wminiterT×iteriter≤iterT---(2)]]>

w=wmin+iter-iterTitermax-iterT×wmaxiter≥iterT---(3)]]>

iter為迭代次數；iter_max為設置的總的迭代次數；iter_T為迭代次數的閾值； w_max是慣性權重的最大值；w_min是慣性權重最小值；

步驟(3).模擬任務調度方法，具體步驟是：

步驟a.初始化一群粒子，確定群體規模m，給定算法的最大、最小權重 因子值，根據調度所需時間設定算法總的迭代次數iter_max和迭代次數的閾值 iter_T；

步驟b.根據所定義的適應度函數Sij=(Ti_execution_time)jΣj=1m(Ti_execution_time)j∈[0,1]]]>來 計算每個微粒的適應值；

步驟c.比較粒子的適應值和自身最優值pbest，如果當前粒子的適應值比 pbest更優則置pbest為當前粒子的適應值；比較粒子適應值與種群最優值 gbest；如果當前粒子的適應值比種群最優值gbest更優，則將種群最優值gbest 修改為當前粒子的適應值；

步驟d.判斷是否達到了閾值迭代，若沒有，則w值由公式(2)計算得出， 若有，w值則由公式(3)計算得出；

步驟e.根據以下式子對粒子速度進行更新；

v_ij(t+1)＝w×v_ij(t)+c₁r₁(pbest_ij-X_ij(t))+c₂r₂(gbest_j-X_ij(t))

X_ij(t+1)＝X_ij(t)+v_ij(t+1)

pbest為自身最優值，gbest種群最優值，c₁和c₂表示學習因子，r₁和r₂是0到1之 間的隨機數；

步驟f.根據調整粒子飛行速度來更新粒子的位置；計算方程式如下：

v_ij(t+1)＝w×v_ij(t)+c₁r₁(pbest_ij-X_ij(t))+c₂r₂(lbest_j-X_ij(t))

X_ij(t+1)＝X_ij(t)+v_ij(t+1)

pbest為自身最優值，lbest為局部極值，c₁和c₂表示學習因子，r₁和r₂是0到1之 間的隨機數；

步驟g.判斷是否達到最終迭代次數，如果沒有達到，執行步驟c；如果 達到了，則從最后一代中獲得個體最佳值。