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

無效

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

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

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

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

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

3.根據(jù)權利要求1所述的基于貪心模擬退火算法的軟硬件劃分的方法，其特征在于，所述步驟(2)中，內(nèi)層循環(huán)所采用接收準則的執(zhí)行流程為：

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

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

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

(2.1.4)對于第二象限中的Region1，采用傳統(tǒng)接收準則將直接接收該解；

(2.1.5)對于第四象限中的Region3，采用傳統(tǒng)接收準則接收該解。

4.根據(jù)權利要求1所述的基于貪心模擬退火算法的軟硬件劃分的方法，其特征在于，所述步驟(2)中，外層循環(huán)的執(zhí)行流程為：首先采用貪心算法的求解結果對模擬退火進行初始化，然后進行模擬退火操作；對每個溫度進行K次循環(huán)，每次循環(huán)根據(jù)擾動模型產(chǎn)生新的軟硬件劃分，采用改進的模擬退火接收準則對新劃分進行判斷，決定是否接受新解；如果X_best未更新，則連續(xù)未接受新的劃分次數(shù)N_useless加1，否則，連續(xù)未接受新的劃分次數(shù)N_useless重新賦值0；再降低當前溫度值，直循環(huán)直至算法滿足退出條件，即當前溫度T_cur小于等于閾值T_trd或連續(xù)未接受新劃分的次數(shù)N_useless大于等于M；最后輸出劃分結果，算法結束。