基于EDA 的嵌入式系統(tǒng)軟硬件劃分方法

摘要：針對嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計(jì)中的軟硬件劃分問題，提出了一種基于分布估計(jì)算法的解決方案，通過將算法映射到一般結(jié)構(gòu)Gauss 網(wǎng)絡(luò)上，提高了算法的穩(wěn)定性和搜索效率。結(jié)果表明，該算法有效地解決了軟硬件劃分問題。

1 引言

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

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

2 劃分模型

系統(tǒng)功能的軟件通常采用 C/C++語言等高級(jí)程序設(shè)計(jì)語言實(shí)現(xiàn)，然后根據(jù)不同顆粒度的要求提取系統(tǒng)控制數(shù)據(jù)流圖CDFG。控制數(shù)據(jù)流圖是系統(tǒng)的行為級(jí)描述，通常使用有向無環(huán)圖表示，主要描述系統(tǒng)中任務(wù)間的控制、數(shù)據(jù)關(guān)系及每個(gè)任務(wù)的代價(jià)信息，而與系統(tǒng)實(shí)現(xiàn)時(shí)采用什么樣的體系結(jié)構(gòu)無關(guān)。

3 劃分算法

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

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

4 仿真試驗(yàn)

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

表 1 為60 節(jié)點(diǎn)系統(tǒng)隨機(jī)運(yùn)行10 次的統(tǒng)計(jì)結(jié)果。從表中數(shù)據(jù)可以看出，與遺傳算法相比，本文提出的GN-EDA 算法在算法的執(zhí)行速度和搜索目標(biāo)函數(shù)最優(yōu)值方面都有很大的優(yōu)勢。

對于各節(jié)點(diǎn)數(shù)系統(tǒng)，尤其是對于較多節(jié)點(diǎn)數(shù)系統(tǒng)，GN-EDA 算法有更為優(yōu)化的結(jié)果，且劃分結(jié)果較為穩(wěn)定。

圖 2 為 60 節(jié)點(diǎn)系統(tǒng)隨機(jī)運(yùn)行30 次，劃分過程中平均每代最佳有效個(gè)體對應(yīng)的系統(tǒng)性能，從圖中可以看出GN-EDA 算法有很好的收斂性。

5 結(jié)論

本文作者創(chuàng)新點(diǎn)：運(yùn)用一種建立在一般結(jié)構(gòu)Gauss 網(wǎng)絡(luò)上的分布估計(jì)算法對嵌入式系統(tǒng)軟硬件劃分問題進(jìn)行了研究，該算法無需進(jìn)行Gauss 網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)，大大減少了計(jì)算量，適用于處理日趨復(fù)雜的嵌入式系統(tǒng)軟硬件劃分問題。實(shí)驗(yàn)結(jié)果表明，GN-EDA 算法能有效地完成軟硬件劃分，并具有較好的計(jì)算穩(wěn)定性。