[發明專利]一種基于貪心模擬退火算法的軟硬件劃分的方法

無效

• 申請號: 201110391004.3
• 申請日: 2011-11-30
• 公開（公告）號: CN102508721A
• 公開（公告）日: 2012-06-20
• 發明（設計）人: 李蕊;楊志邦;王奕;徐成;劉彥;黃兵;駱偉;張婷;王輝
• 申請（專利權）人: 湖南大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 湖南兆弘專利事務所 43008
• 代理人: 趙洪;周長清

技術領域

本發明主要涉及到嵌入式系統設計領域，特指一種基于貪心模擬退火算法的軟硬件劃分的方法。

背景技術

軟硬件劃分是指在系統設計時確定各個模塊的實現方式，以解決系統功能模塊的映射問題。軟硬件劃分是嵌入式系統軟硬件協同設計的關鍵步驟，劃分結果直接決定系統設計的優劣。其基本目標是：在滿足設計約束的條件下，將任務合理地劃分到軟件或者硬件處理單元上執行，以實現系統目標最優化，具體包括硬件實現面積最小或功能模塊運行時間最小等。根據目標體系結構的不同，軟硬件劃分問題可分為雙路劃分和多路劃分。其中雙路劃分應用最廣泛，也是軟硬件劃分問題的基礎。

軟硬件劃分被證明是一個NP完全問題，隨著任務規模的增加，解空間成指數增長。現有的軟硬件劃分主要是基于啟發式算法，包括遺傳算法、模擬退火、禁忌搜索、免疫算法等。遺傳算法有較強的全局搜索性能，但它的爬山能力弱，在進化后期收斂速度較慢，在實際應用中容易出現早熟現象；模擬退火算法具有擺脫局部最優解的能力，能抑制遺傳算法的早熟現象，但它的進化速度慢，特別是前期的退火效率低，需要較長時間才能趨向于系統最優解；禁忌搜索法通過引入靈活的存儲結構和相應禁忌準則來避免迂回搜索，并通過赦免一些被禁忌的優良狀態，具有較好的爬山能力，但數據存取操作頻繁，影響了搜索速度；免疫算法是基于免疫系統的學習算法，具有良好的系統應答性和自平衡能力，但機理復雜、系統龐大，可以借鑒的研究成果不多，在算法理論基礎、建模方法等方面都存在問題。

國內外諸多學者也嘗試將不同劃分算法相結合，比較典型的是遺傳和禁忌搜索融合算法、遺傳和螞蟻算法融合算法以及遺傳粒子群優化算法等。這些算法在各自的領域都取得了一定的效果，但已有的方法大都結合兩種啟發式算法用于軟硬件劃分，難以避免啟發式算法所存在的初始化參數難以確定以及初始訓練過程漫長等問題。這些問題處理不當可能導致算法運行時間過長，并降低找到近似最優解的可能性。

發明內容

本發明要解決的技術問題就在于：針對現有技術存在的技術問題，本發明提供一種能夠減少算法運行時間、提高搜索質量、減少計算復雜度的基于貪心模擬退火算法的軟硬件劃分的方法。

為解決上述技術問題，本發明采用以下技術方案：

一種基于貪心模擬退火算法的軟硬件劃分的方法，其流程為：

(1)、將軟硬件劃分問題規約為0-1背包問題，使用時間復雜度較低的貪心算法對任務集進行初始劃分，然后將此劃分結果作為模擬退火算法的初始值；

(2)、模擬退火算法：主要由兩層循環構成，內層循環根據擾動模型產生新劃分并采用接收準則對其進行判斷接收；外層循環根據溫度閾值以及連續未接受新劃分的次數來判斷是否退出循環過程。

作為本發明的進一步改進：

所述步驟(1)中對任務集進行初始劃分的流程為：首先計算每個任務的收益質量比，然后按照非升序進行排序，將其壓入隊列Q；接下來進行初始化操作，將任務全部劃分到軟件上執行；每次循環尋找未劃分到硬件任務隊列Q中最大收益比任務v_j到硬件上實現，如果該任務v_j需要硬件A_j的大小小于剩余硬件A_res大小，就把任務v_j劃分到硬件上執行，剩余可用硬件A_res大小為A_res-A_j；否則，任務v_j不能劃分到硬件執行，只能劃分到軟件上執行；再把任務v_j從任務隊列Q中刪除，直到Q為空或硬件資源分配完成為止，最后輸出貪心算法的初始劃分結果，將該初始劃分結果作為模擬退火算法的初始值。

所述步驟(2)中，內層循環所采用接收準則的執行流程為：

(2.1.1)以當前劃分X為原點，系統時間的增量ΔT為橫軸，硬件面積的增量ΔA為縱軸，建立系統擾動示意圖；用直線l平分第二象限和第四象限，將第二象限分為Region1(區域1)和Region2(區域2)，將第四象限分為Region3(區域3)和Region4(區域4)；

(2.1.2)在第一象限中的新劃分不是理想的解，采用梅特羅波利斯(Metropolis)準則對其進行接收；對于第四象限中的Region4(區域4)中的劃分，采用梅特羅波利斯(Metropolis)準則對其進行接收；

(2.1.3)位于第三象限的新劃分是較理想的劃分，直接接收該解；第二象限中的Region2中的新劃分在增加較少硬件面積的同時降低了較多系統時間，直接接收該區域的解；