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

有效

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

技術領域

本發明屬于計算機技術領域，特別涉及一種嵌入式異構多處理器系統的 任務調度方法。

背景技術

近年來，具有復雜功能的嵌入式多處理器系統越來越流行，其性能依靠 操作系統是否能夠提供高效的任務調度。因此，任務調度成為提高其性能的 關鍵因素。

在多處理系統中，任務調度一直是一個難題。傳統的方法，如分支定界 法，動態規劃等等，這些算法能夠獲得全局最優解，但是它們要么經常需要 花費大量的時間用于尋優，要么不能夠很好的用于解決實際問題。為了克服 傳統方法的缺陷，研究者提出了許多新的方法，如退火算法，基因算法，蟻 群算法等等。這些算法的共同特點是，雖然他們能夠在一定程度上降低了搜 尋最優解的時間。但是他們仍然不能完好的滿足嵌入式系統的實時要求。

標準的粒子群PSO算法沒有諸如繁殖、交叉和變異等遺傳操作，只通過簡 單的算術運算進行演化，非常容易實現。因此能大大的提高了尋找最優解的速 度。目前，作為一種重要的優化工具，粒子群PSO算法已經在許多優化問題中 得到了成功的應用。

發明內容

本發明的目的就是提供一種嵌入式異構多處理器系統的任務調度方法， 該方法基于調整飛行時間和慣性權重的粒子群優化算法(FIPSO)，用來解決異 構處理器間的任務調度問題，從而得到比較好的調度策略，提高處理器的效 率。

本發明方法的具體步驟是：

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

在標準的PSO算法迭代過程中，粒子的搜尋能力在迭代后期會逐漸下降， 為了克服這一困難，提高粒子群優化算法的收斂速度和精度，粒子的飛行速 度在FIPSO算法中動態的調整。

粒子群算法中粒子通過跟蹤兩個“極值”來更新自己的速度，算法結構 簡單，運行速度比較快。但是，標準的粒子群算法在搜索最優解時，有時會 出現粒子在最優解的附近來回運動現象，而且這個最優解可能就是局部最優 解。因此，我們提出了調整粒子的飛行速度，在進化初期，粒子距離最優位置 較遠，粒子的飛行速度應快一些，這樣有利于盡快的移向最優位置；當粒子距 離最優位置較近時，粒子的飛行速度應慢一些，這樣可以避免因飛行速度過 快而導致的粒子“飛過”最優位置從而產生的來回運動現象。標準的粒子群 算法在進化初期和后期都固定飛行速度系數設置為1，這將將導致粒子群在進 化后期搜索性能下降。

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

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為比例系數，是常量