基于EDA 的嵌入式系統軟硬件劃分方法

摘要：針對嵌入式系統軟硬件協同設計中的軟硬件劃分問題，提出了一種基于分布估計算法的解決方案，通過將算法映射到一般結構Gauss 網絡上，提高了算法的穩定性和搜索效率。結果表明，該算法有效地解決了軟硬件劃分問題。

1 引言

嵌入式系統是由一個或若干個微處理器、ASICs、存儲器和總線構成的，在一定時間內響應輸人的系統。傳統的嵌入式系統的設計方法將硬件和軟件劃分為兩個獨立的部分，由硬件工程師和軟件工程師按照擬定的設計流程分別完成。這種設計方法只能改善硬件和軟件各自的性能，而在有限的設計空間中不可能對整個系統做出較好的性能綜合優化。隨著嵌入式系統的功能越來越強，其結構變得越來越復雜，系統的集成度越來越高，調試越來越困難，傳統的設計方法是已經不能滿足現代嵌入式系統的設計要求，取而代之的是以軟硬件協同設計為主要特征的系統設計方法，其主要思想是用自動、優化的系統體系結構開發替代人工的軟硬件子系統分割，在系統設計的高層階段實現系統原型的快速開發并預估系統實現的性能，實現系統在性能、成本等方面的優化。

軟硬件劃分是嵌入式系統軟硬件協同設計中的一個關鍵問題，其作用是從軟硬件系統設計空間中，根據系統功能定義，獲得一個滿足系統時間、成本、功耗等方面要求的趨于最優的實現，其結果直接決定系統設計的優劣。近年來，人們將各類啟發式算法應用于軟硬件劃分的研究中，取得了較好的方案。Eles 等[1]利用模擬退火算法，Ernst 等[2]采用模擬退火算法和禁忌搜索算法，Saha 等[3]運用遺傳算法實現軟/硬件劃分。軟硬件劃分問題本質上是一類組合優化問題，分布估計算法(Estimation of Distribution Algorithms，EDAs)是一種新的基于種群進化的算法，具有收斂速度快，避免陷入局部最優的特點。本文提出了一個基于分布估計算法的軟硬件劃分算法，較好地應用于軟硬件協同設計中。

2 劃分模型

系統功能的軟件通常采用 C/C++語言等高級程序設計語言實現，然后根據不同顆粒度的要求提取系統控制數據流圖CDFG。控制數據流圖是系統的行為級描述，通常使用有向無環圖表示，主要描述系統中任務間的控制、數據關系及每個任務的代價信息，而與系統實現時采用什么樣的體系結構無關。

3 劃分算法

分布估計算法是一類基于概率模型的進化算法, 與傳統的進化方法不同, 它不使用交叉、變異等算子，而是以群體中適應度較高的個體的概率分布作為進化模型，并由該模型產生下一代子群，利用跟先進的方法取代了遺傳算法再結合操作方式，拓展了算法的應用空間。由于進化模型是由統計的概率分布信息推導而來， 因而能最大限度地利用已有信息，更準確地反映變量間的相互關系，顯現出群體的主要特征。理論研究表明，EDAs 在迭代過程中有可能獲取群體中的個體之間及個體中不同位之間的交互信息，辨識并且操縱重要的模式塊，從而能夠有效求解決策變量之間有相互作用的優化問題[4]。

根據概率估計算法的不同，EDAs 分為一階EDAs 和高階EDAs 兩大類，其中，二階EDAs中的建立在一般結構Gauss 網絡上的分布估計算法(GN-EDA)采用一種不使用條件概率密度函數來產生樣本的方法，無需進行Gauss 網絡結構的學習，大大減少了計算量，而且可以獲得高精度的聯合密度函數[5]。

4 仿真試驗

算法采用 C++在m IntelP41.6GHz 256MRam 環境下實現，CDFG 的結點數、時間約束、每個節點的信息、結點之間的連接關系都是隨機生成的。首先，隨機生成了 30、60、100、200 個節點的 CDFG，并隨機生成了各個節點的性能參數，同時根據對節點的性能參數的分析，確定了系統的約束條件以及這些約束條件各自的權重。CDFG 硬件執行時間為軟件執行時間的20%~50%，硬件代價約束取值為總硬件代價之和的50%。對每個 CDFG 都進行 100次的測試，并將最終求出的最優解的代價函數值的平均值同遺傳算法求出的值進行了比較，實驗數據如表 1 所示。

表 1 為60 節點系統隨機運行10 次的統計結果。從表中數據可以看出，與遺傳算法相比，本文提出的GN-EDA 算法在算法的執行速度和搜索目標函數最優值方面都有很大的優勢。

對于各節點數系統，尤其是對于較多節點數系統，GN-EDA 算法有更為優化的結果，且劃分結果較為穩定。

圖 2 為 60 節點系統隨機運行30 次，劃分過程中平均每代最佳有效個體對應的系統性能，從圖中可以看出GN-EDA 算法有很好的收斂性。

5 結論

本文作者創新點：運用一種建立在一般結構Gauss 網絡上的分布估計算法對嵌入式系統軟硬件劃分問題進行了研究，該算法無需進行Gauss 網絡結構的學習，大大減少了計算量，適用于處理日趨復雜的嵌入式系統軟硬件劃分問題。實驗結果表明，GN-EDA 算法能有效地完成軟硬件劃分，并具有較好的計算穩定性。