軟硬件劃分中的圖歸約技術.pdf

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

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

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