多選擇軟硬件劃分問(wèn)題的算法研究.pdf

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

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