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

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

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

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