軟硬件劃分中的圖歸約技術(shù).pdf

1、嵌入式系統(tǒng)設(shè)計(jì)中的一個關(guān)鍵步驟是軟硬件劃分問題，即確定哪些部分由硬件實(shí)現(xiàn)及哪些部分由軟件實(shí)現(xiàn)。軟硬件劃分與調(diào)度問題已經(jīng)被證明是NP難題，所以大多數(shù)關(guān)于軟硬件劃分與調(diào)度問題的研究都集中在尋找一種有效的啟發(fā)式的解決方案。隨著近幾年對軟硬件劃分與調(diào)度算法的不斷改進(jìn)，劃分與調(diào)度算法已經(jīng)達(dá)到了一個較高的水平，軟硬件劃分與調(diào)度算法上的優(yōu)化效果已經(jīng)非常有限，若再改進(jìn)其算法難度比較大。
　　 現(xiàn)代的嵌入式系統(tǒng)在功能上越來越齊全，其規(guī)模也越來越大

2、，隨著任務(wù)數(shù)的不斷增多其系統(tǒng)的任務(wù)圖也愈加復(fù)雜。鑒于軟硬件劃分與調(diào)度算法的效率已很難大幅提高，本文提出了任務(wù)圖歸約技術(shù)的新觀點(diǎn)。在軟硬件劃分與調(diào)度之前對整個系統(tǒng)的任務(wù)圖作一個預(yù)處理，找出所有滿足要求的可歸約子圖，并按貪心思想找出一組不存在交叉的子圖，把每個子圖簡化成一個任務(wù)結(jié)點(diǎn)，從而有效簡化原始任務(wù)圖。
　　 本文主要提出了四個新的算法：隨機(jī)任務(wù)圖生成算法、基于BFS的算法、路徑流(PFA)算法和選擇無交叉子圖算法，其核心是兩個

3、尋找可歸約子圖算法，即基于BFS的算法和路徑流(PFA)算法。這兩個算法都能找出任務(wù)圖中所有符合要求的可歸約子圖，基于BFS的算法受廣度優(yōu)先搜索思想的啟發(fā)，逐點(diǎn)遍歷、核查，算法的時間復(fù)雜度較高，效率低。而路徑流(PFA)算法則基于路徑的思想，效率較高。其找出所有子圖所花費(fèi)的時間大概是前者的30％～80％。平均實(shí)驗(yàn)數(shù)據(jù)表明，該歸約技術(shù)最壞情況下可以使任務(wù)圖簡化為原來的67％，最好情況下可簡化為原來的58％。歸約后的任務(wù)圖能夠有效降低劃分與