軟硬件劃分的啟發(fā)式算法.pdf

1、在實(shí)現(xiàn)嵌入式系統(tǒng)的過(guò)程中，軟硬件協(xié)同設(shè)計(jì)技術(shù)通常需要考慮在縮短上市時(shí)間的基礎(chǔ)上滿足各種設(shè)計(jì)約束。協(xié)同設(shè)計(jì)的一個(gè)關(guān)鍵要求是對(duì)系統(tǒng)模塊進(jìn)行一個(gè)有效的軟硬件劃分，在滿足功耗，延遲，硬件面積等因素的約束下，使得系統(tǒng)的某個(gè)屬性，比如通訊代價(jià)，硬件資源開(kāi)銷(xiāo)等達(dá)到最優(yōu)。
　　 作為軟硬件系統(tǒng)設(shè)計(jì)的關(guān)鍵步驟之一，軟硬件劃分技術(shù)對(duì)于系統(tǒng)的整體性能有顯著的影響。而該劃分問(wèn)題本身已經(jīng)被證明是NP完全問(wèn)題，所以通常通過(guò)設(shè)計(jì)一些近似算法來(lái)對(duì)此類(lèi)問(wèn)題進(jìn)行求

2、解。本文將一類(lèi)軟硬件劃分問(wèn)題轉(zhuǎn)化成擴(kuò)展的0-1背包問(wèn)題，然后設(shè)計(jì)了一個(gè)啟發(fā)式算法來(lái)解決這個(gè)問(wèn)題，并使用了禁忌搜索這種智能優(yōu)化方法對(duì)該啟發(fā)解進(jìn)行提升，從而達(dá)到在滿足系統(tǒng)軟件代價(jià)和通訊代價(jià)的前提下，使得系統(tǒng)的硬件代價(jià)最小的優(yōu)化目標(biāo)。充分的實(shí)驗(yàn)數(shù)據(jù)表明，本文提出的算法和國(guó)內(nèi)外最新的工作相比，能產(chǎn)生質(zhì)量更好的解，本文算法最高能提升百分之二十八。
　　 本文還將軟硬件劃分問(wèn)題抽象成一個(gè)圖平衡劃分問(wèn)題，在這個(gè)新的計(jì)算模型下，本文運(yùn)用了同樣的

3、策略來(lái)解決這一類(lèi)問(wèn)題。除了在軟硬件劃分領(lǐng)域，該問(wèn)題還被證明是一類(lèi)廣泛應(yīng)用在大規(guī)模集成電路設(shè)計(jì)，圖像分割，數(shù)據(jù)挖掘等領(lǐng)域的NP完全問(wèn)題，所謂平衡劃分問(wèn)題，就是對(duì)于給定的圖，尋求一個(gè)可行劃分，將頂點(diǎn)集合劃分到兩個(gè)互不相交的集合中，使得系統(tǒng)的割邊數(shù)最少，并且要求劃分結(jié)果要保持兩個(gè)集合中的頂點(diǎn)數(shù)目大致相等。本文提出了一個(gè)簡(jiǎn)單高效的多啟動(dòng)(Multi-start)的啟發(fā)式算法來(lái)解決這個(gè)平衡劃分問(wèn)題，并采用禁忌搜索對(duì)該啟發(fā)解進(jìn)行提升。實(shí)驗(yàn)數(shù)據(jù)表明，