多選擇軟硬件劃分問題的算法研究.pdf

1、軟硬件劃分是軟硬件協(xié)同設計的關鍵環(huán)節(jié)，劃分的結果直接影響目標系統(tǒng)的設計質量。由于單個任務具有多種不同的硬件實現(xiàn)方式，與傳統(tǒng)的單一硬件實現(xiàn)方式的軟硬件劃分問題相比，多選擇的軟硬件劃分更能客觀地反映現(xiàn)實應用。這導致問題的求解更具挑戰(zhàn)性，它們已被證明是NP完全問題。本文對于兩種不同任務圖模型上的多選擇軟硬件劃分問題分別做了算法方面的研究。
　　對于簡單任務圖模型上的多選擇軟硬件劃分問題，分別使用模擬退火算法和遺傳算法，提出了可行性的解決

2、方案。并與禁忌搜索算法進行比較，尋找多選擇軟硬件劃分問題的相對較好的啟發(fā)式算法。實驗結果表明，在求得的解的質量方面，禁忌搜索算法相比于其他兩種算法而言是最好的;在獲得較好解的速度方面，模擬退火算法和遺傳算法要比禁忌搜索算法快的多。
　　針對多核處理器片上系統(tǒng)上的多選擇軟硬件劃分問題，建立了任務圖為二叉樹的多選擇軟硬件劃分問題的計算模型，并分別提出了啟發(fā)式算法、禁忌搜索算法以及動態(tài)規(guī)劃算法來解決該問題。實驗結果表明，當問題規(guī)模較小時