軟硬件協(xié)同設(shè)計中的軟硬件劃分方法綜述*

李巖，屈媛，陳儀香

(1.華東師范大學(xué) 計算機科學(xué)與軟件工程學(xué)院 嵌入式軟件與系統(tǒng)系，上海 200062；2.華東師范大學(xué) 教育部軟硬件協(xié)同設(shè)計技術(shù)與應(yīng)用工程研究中心)

軟硬件協(xié)同設(shè)計中的軟硬件劃分方法綜述*

李巖1,2，屈媛1,2，陳儀香1,2

(1.華東師范大學(xué) 計算機科學(xué)與軟件工程學(xué)院 嵌入式軟件與系統(tǒng)系，上海 200062；2.華東師范大學(xué) 教育部軟硬件協(xié)同設(shè)計技術(shù)與應(yīng)用工程研究中心)

近年來，隨著信息領(lǐng)域的物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、機器人等研究熱點發(fā)展，嵌入式系統(tǒng)技術(shù)再次得到科技工作者和工程師的廣泛關(guān)注和重視，同時嵌入式系統(tǒng)產(chǎn)品的集成度和性能要求越來越高。軟硬件協(xié)同設(shè)計是開發(fā)嵌入式系統(tǒng)產(chǎn)品的重要方法之一，而軟硬件劃分是軟硬件協(xié)同設(shè)計中的關(guān)鍵技術(shù)。本文對現(xiàn)有軟硬件劃分方法從不同層面進行梳理和分類，重點介紹幾種常用的軟硬件劃分方法，并結(jié)合實例進行了詳細闡述，最后對這幾種方法進行綜合比較，供嵌入式系統(tǒng)開發(fā)科技工作者和工程師參考。

嵌入式系統(tǒng)；軟硬件協(xié)同設(shè)計；軟硬件劃分

引 言

隨著物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)和機器人的發(fā)展，高科技產(chǎn)品逐漸滲透到人們的學(xué)習(xí)、生活中，人們對高科技產(chǎn)品的集成度和功能要求越來越高，嵌入式系統(tǒng)設(shè)計面臨著許多矛盾和問題，主要有兩個方面，一方面是低成本和高性能之間的矛盾，另一方面是更迭周期與復(fù)雜性之間的矛盾。針對上述矛盾，設(shè)計者的解決方案是采用軟硬件協(xié)同設(shè)計方法進行嵌入式系統(tǒng)設(shè)計。軟硬件協(xié)同設(shè)計是在系統(tǒng)目標(biāo)要求的指導(dǎo)下，通過綜合分析系統(tǒng)軟硬件功能及現(xiàn)有資源，最大限度地挖掘系統(tǒng)軟硬件之間的并發(fā)性，協(xié)同設(shè)計軟硬件體系結(jié)構(gòu)，使得系統(tǒng)能夠工作在最佳狀態(tài)，達到性能最優(yōu)[1]。

軟硬件協(xié)同設(shè)計的過程通常包括選擇、劃分、規(guī)劃、通信這4個主要任務(wù)[2]?！斑x擇”的目的是分析系統(tǒng)實現(xiàn)需要哪些功能模塊；“劃分”的目的是將選擇出的功能模塊一部分交由軟件實現(xiàn)，另一部分交由硬件實現(xiàn)，從而達到系統(tǒng)的性能要求；“規(guī)劃”的目的是避免系統(tǒng)出現(xiàn)時間響應(yīng)沖突或硬件資源使用沖突等；“通信”的目的則是保證各個軟硬件模塊之間良好的交互通信。

其中，“劃分”即軟硬件劃分，是軟硬件協(xié)同設(shè)計的關(guān)鍵技術(shù)，對提高系統(tǒng)性能至關(guān)重要。軟件的特點是靈活、成本低，但運行慢，而且并行處理不穩(wěn)定；而硬件的特點是速度快，并行處理穩(wěn)定但實現(xiàn)成本高。因此，如何充分利用軟件和硬件的優(yōu)勢，使得系統(tǒng)兼顧時間、成本、功耗、硬件面積等方面的性能，是劃分的關(guān)鍵。

軟硬件劃分是一個典型的組合優(yōu)化問題。本文首先將軟硬件劃分方法依據(jù)求解組合優(yōu)化問題的常用算法進行分類，然后圍繞這幾種分類結(jié)合實例重點闡述了近年來軟硬件協(xié)同設(shè)計中幾種常用的軟硬件劃分方法，并針對這幾種方法進行了綜合比較，最后做出總結(jié)。

1 研究現(xiàn)狀

1.1 國外軟硬件劃分

嵌入式系統(tǒng)設(shè)計者最初是通過手工方式對系統(tǒng)進行軟硬件劃分，而自動劃分方法最早出現(xiàn)在20世紀90年代初期[3]。通過研究，國外學(xué)術(shù)界相繼出現(xiàn)了采用抽象估計可調(diào)度系統(tǒng)結(jié)構(gòu)概率[4]的方法，改進迭代算法、模擬退火算法、禁忌搜索算法以及遺傳算法等來實現(xiàn)軟硬件劃分。之后國外眾多研究學(xué)者先后提出多種基于經(jīng)典優(yōu)化算法的改進算法，從而提高軟硬件劃分效率。Bender和 Schwiegershausen等人[6]提出采用混合整數(shù)線性規(guī)劃方法(MILP)來解決軟硬件劃分問題。Chonlameth等人[8]提出在基于約束(constrain-based Co-Design)的軟硬件協(xié)同設(shè)計方法中引入Unified Modeling Language來進行軟硬件劃分，在軟硬件協(xié)同設(shè)計中引入模型分析，將軟硬件劃分上升到一個新的層面。

1.2 國內(nèi)軟硬件劃分

2003年，中國科學(xué)院軟件研究所陳思功等人在Chonlameth等人[8]提出的CBC/UML方法的基礎(chǔ)上，提出改進的基于UML模型分析的軟硬件劃分方法。2005年，中國科學(xué)院院士、華東師范大學(xué)何積豐教授[9]，以矩陣乘法運算為例，提出關(guān)于同步模型使用UPPAAL工具的最優(yōu)軟硬件劃分方法。2008年，黃源等人[17]提出采用基于時間Petri網(wǎng)來進行軟硬件劃分[8]，開辟了軟硬件劃分技術(shù)新局面。2010年，國防科技大學(xué)羅莉、夏軍等人[10]提出一種有效的面向多目標(biāo)軟硬件劃分的遺傳算法。2011年，天津工業(yè)大學(xué)韓紅蕾等人[11]針對調(diào)度與軟硬件劃分問題提出一種高效的啟發(fā)式算法，即多核片上系統(tǒng)的高效軟硬件劃分及調(diào)度算法。2014年，謝曉娜等人提出了支持多屬性決策的軟硬件劃分方法。2015年，陳瑋等人提出基于組合算法的軟硬件劃分方法，即先利用遺傳算法找到問題的可行解，再利用粒子群算法找到最優(yōu)的方案。2015年，鐘麗等人[22]提出基于ESL方法的SM2加密算法的軟硬件協(xié)同設(shè)計方案。該方案通過分析SM2算法的原理，研究不同的軟硬件劃分方案，采用SystemC語言對硬件模塊進行周期精確級建模。通過比較軟、硬件模塊周期數(shù)，得到最佳的性能劃分方法。最終通過將ESL模型轉(zhuǎn)化為RTL級模型實現(xiàn)邏輯綜合與比較，進而對資源和開銷進行平衡。

2 軟硬件劃分方法介紹

2.1 基于規(guī)劃類算法的軟硬件劃分方法

2.1.1 線性規(guī)劃方法

對系統(tǒng)進行設(shè)計，尤其是在對系統(tǒng)級芯片(SoC)進行設(shè)計時，必須考慮到系統(tǒng)的集成度、體積、功耗、可靠性等問題。多目標(biāo)的系統(tǒng)設(shè)計通常會明確給出要達到什么樣的目標(biāo)，系統(tǒng)最終要求綜合考慮所有目標(biāo)，在滿足所有目標(biāo)約束的條件下達到系統(tǒng)性能最優(yōu)。該問題類似于對多個不等式進行線性規(guī)劃求目標(biāo)函數(shù)的最優(yōu)解問題。將線性規(guī)劃方法應(yīng)用到系統(tǒng)軟硬件劃分上，借助參數(shù)表示將問題抽象成一個目標(biāo)函數(shù)和幾個約束不等式，利用現(xiàn)有的線性規(guī)劃軟件對該目標(biāo)函數(shù)進行求解。

本文以一個PDA手機平臺的視頻、音頻發(fā)送系統(tǒng)[10]為實例來介紹該方法。參數(shù)如表1所列，系統(tǒng)的每一個模塊都有其相應(yīng)的IP核和軟件構(gòu)件可以實現(xiàn)其功能。此外，還要求系統(tǒng)成本不得超過1100元人民幣，系統(tǒng)硬件面積不得超過3 900 mm2，系統(tǒng)功耗不能超過1.9 W，響應(yīng)延遲時間不得超過600 ms。軟硬件劃分的目的是在滿足各項約束的條件下，尋找所有可能滿足約束條件的構(gòu)建組合。

表1 各功能模塊對應(yīng)IP核及軟件構(gòu)件參數(shù)列表[10]

通過系統(tǒng)問題描述，設(shè)一組參數(shù)Xij，表示第i個功能單元的第j個構(gòu)件或IP核，其值為1表示啟用該構(gòu)件，為0表示不啟用該構(gòu)件；Cij表示構(gòu)件或IP核的成本；Aij表示構(gòu)件或IP核的硬件面積；Eij表示構(gòu)件或IP核的功耗；Tij表示構(gòu)件或IP核的時間特性。則目標(biāo)函數(shù)為求所有性能參數(shù)之和的最小值MIN，即

(1)

功耗對系統(tǒng)開銷影響較大，但其值很小，為了突出功耗在劃分中所起的作用，使用一組影響因子α，β，γ，δ。其中α為系統(tǒng)成本的影響因子，β為系統(tǒng)硬件面積的影響因子，γ為系統(tǒng)功耗的影響因子，δ為系統(tǒng)時間特性的影響因子。經(jīng)過不斷試驗，得到這組影響因子的常數(shù)分別是3、1、2 000、6.5。因此，目標(biāo)函數(shù)為:

(2)

系統(tǒng)約束模型可以表示為：

(3)

此外，系統(tǒng)隱含的約束為每個功能單元只能選擇一個軟件構(gòu)件或者IP核，因此，有∑X1j=1，∑X2j=1，∑X3j=1，∑X4j=1，∑X5j=1，∑X6j=1。

通過以上定義及分析，對目標(biāo)函數(shù)和約束函數(shù)使用LINGO線性規(guī)劃軟件進行求解，得到的劃分結(jié)果為111 432，即該系統(tǒng)的各個模塊的軟件構(gòu)件及IP核構(gòu)成為Core11Core21Core31Core44Core53Core62，即音頻數(shù)據(jù)采集模塊用軟件構(gòu)件Core11實現(xiàn)，視頻數(shù)據(jù)采集模塊用軟件構(gòu)件Core21實現(xiàn)，用戶界面用Core31實現(xiàn)，MP3編碼模塊用IP核Core44實現(xiàn)，MPEG4編碼模塊用IP核Core53實現(xiàn)，音頻與視頻同步模塊用軟件構(gòu)件Core62實現(xiàn)。但是，此解只能作為滿足系統(tǒng)約束條件下的解空間中某一方面性能的最優(yōu)解，是局部最優(yōu)解。

許多學(xué)者[12]對線性規(guī)劃方法作出了改進，提出了如整數(shù)規(guī)劃、混合整數(shù)規(guī)劃等方法，使系統(tǒng)模型更加精確，得到劃分的最優(yōu)解。但線性規(guī)劃作為優(yōu)化問題的經(jīng)典求解方式，對于規(guī)模較小的問題，求解效率較高。

2.1.2 基于UML模型的分析方法

在進行軟硬件協(xié)同設(shè)計時，開發(fā)者會留下許多文檔，如設(shè)計說明文字、圖表等，通過對文檔的分析得到系統(tǒng)約束。這些文檔通常是使用自然語言書寫，不足以體現(xiàn)軟硬件協(xié)同的設(shè)計環(huán)境，對系統(tǒng)模型分析有一定的局限性。Chonlameth等人[8]提出的基于約束的協(xié)同設(shè)計方法，首先從需求文檔中提煉出設(shè)計約束模型，從而明確系統(tǒng)設(shè)計中各個組件的界限?；诩s束的軟硬件協(xié)同設(shè)計過程對每個階段(選擇、劃分、規(guī)劃、通信)進行迭代，每次迭代會產(chǎn)生新的約束模型，根據(jù)新的約束再進行設(shè)計。當(dāng)不再有新的約束產(chǎn)生時，意味著系統(tǒng)滿足了所有的約束，是可行的。

Chonlameth在基于約束的設(shè)計方法里引入UML，給協(xié)同設(shè)計提供了一個良好的設(shè)計方法。UML具有強大的需求分析功能，可以從不同角度明確系統(tǒng)需求，加上它使用圖形化語言對需求進行建模，更加正規(guī)、直觀。對象約束語言是UML中一個重要組成部分，它是一種形式化語言，能利用文字標(biāo)記清晰準確地描述出UML基礎(chǔ)機制不能表示的狀態(tài)屬性。CBC/UML方法的核心是通過UML建立系統(tǒng)模型并給出不同模型中的系統(tǒng)約束，當(dāng)所有約束都用軟件或硬件實現(xiàn)，系統(tǒng)協(xié)同設(shè)計就完成了。

針對CBC/UML方法對系統(tǒng)模型方面提煉不足的缺點，中國科學(xué)院陳思功等人對該方法中只使用UML用例圖和活動圖進行了拓展，增加了順序圖和協(xié)作圖，利用權(quán)值約束的數(shù)學(xué)方法。具體做法是以智能電話為例，通過用例圖進行用例分析，明確資源需求。從已有技術(shù)出發(fā)，提出了解決模型，最后從系統(tǒng)實現(xiàn)可行以及系統(tǒng)約束權(quán)值最小角度出發(fā)完成軟硬件劃分，并能得到系統(tǒng)開銷小的模型。改進的基于UML的劃分方法更適用于較為復(fù)雜的嵌入式系統(tǒng)，并且能為系統(tǒng)模型提供重要的參考[2]。

2.2 基于構(gòu)造式的軟硬件劃分方法

在多核片上系統(tǒng)軟硬件協(xié)同設(shè)計中，軟硬件劃分與調(diào)度是設(shè)計的關(guān)鍵，韓紅蕾等人[11]針對這一關(guān)鍵問題提出一種高效的啟發(fā)式算法。該算法包括兩部分：一部分是多處理器上的調(diào)度問題，根據(jù)任務(wù)圖中各個任務(wù)節(jié)點的出度，即任務(wù)間的通信費用，給出各個任務(wù)節(jié)點的優(yōu)先級，出度高的節(jié)點優(yōu)先級高，出度相同的節(jié)點，比較其軟件計算時間，軟件計算時間越長，優(yōu)先級越高。出度較大或軟件執(zhí)行時間越長的任務(wù)優(yōu)先被執(zhí)行，保證了后續(xù)任務(wù)的等待時間較短，從而使得總執(zhí)行時間較短。另一部分是軟硬件劃分問題，在滿足硬件約束的前提下，每次迭代將關(guān)鍵路徑上受益面積比[11]最大的任務(wù)交給硬件實現(xiàn)，然后更新關(guān)鍵路徑與剩余的硬件面積，循環(huán)結(jié)束的標(biāo)志是剩余硬件資源不再滿足選擇的關(guān)鍵路徑上的任意任務(wù)所需。該算法在已有算法[16]基礎(chǔ)上改進了38%。結(jié)合該算法與線性規(guī)劃方法，提出在使用該算法進行軟硬件劃分之后使用線性規(guī)劃方法驗證劃分結(jié)果是否最優(yōu)，若結(jié)果不是最優(yōu)，則需要重新使用該算法進行劃分。

圖1 任務(wù)圖模型

首先，為了使系統(tǒng)的執(zhí)行時間最短，將多處理器嵌入式系統(tǒng)的軟硬件劃分問題和多任務(wù)在多處理上的調(diào)度問題結(jié)合起來。給出問題描述：以任務(wù)T1、T2、…、T10分配到5個處理器P1、P2、P3、P4、P5上為例，任務(wù)之間存在通信，通信會產(chǎn)生通信費用。如何在5個處理器上調(diào)度10個任務(wù)，使得通信費用與執(zhí)行時間達到最優(yōu)？

通過由任務(wù)圖模型刻畫軟硬件劃分問題的常用方法，這里給出一個任務(wù)圖模型，如圖1所示,每個節(jié)點代表一個任務(wù),每條有向邊表示相應(yīng)兩節(jié)點之間存在通信,有向邊的權(quán)值表示通信費用。

任務(wù)圖模型給出后，根據(jù)節(jié)點之間的通信次數(shù)將任務(wù)節(jié)點集合V劃分成p個子集Vi，一個通用的劃分規(guī)則如下所示：

圖2 調(diào)度后的任務(wù)圖模型

d(Ti,Tj)表示Ti與Tj之間的通信次數(shù)；0代表兩個任務(wù)之間沒有通信關(guān)系。給出邊界值ε、ζ、η按照δij≤ε，ε<δij≤ζ，ζ<δij≤η，η<δij以及d(Ti,Tj)=0，將全部任務(wù)劃分成5個等價類。等價類劃分即任務(wù)調(diào)度，調(diào)度后的任務(wù)圖如圖2所示。其中，Ts表示任務(wù)實際執(zhí)行時間，Cs表示具有通信關(guān)系的兩個任務(wù)集之間實際的通信時間。由調(diào)度后的任務(wù)模型進行軟硬件劃分，選出調(diào)度長度最長的路徑，從中選出受益面積比最大的任務(wù)交給硬件實現(xiàn)，循環(huán)執(zhí)行該算法，直到剩余的硬件資源不能滿足下一個選出任務(wù)需要的硬件資源。

根據(jù)韓紅蕾等人提出的劃分方法，產(chǎn)生的結(jié)果不一定是最優(yōu)的，也存在可能不滿足系統(tǒng)約束的劃分結(jié)果。因此，需要在每次軟硬件劃分結(jié)束之后，對劃分結(jié)果使用線性規(guī)劃方法驗證，觀察是否滿足系統(tǒng)所有約束條件，并且達到性能最優(yōu)，如果不滿足上述條件，則追溯到任務(wù)調(diào)度規(guī)則，重新對系統(tǒng)任務(wù)進行劃分。構(gòu)造式方法依賴于有效的啟發(fā)式規(guī)則，啟發(fā)式策略雖然不能保證得到最優(yōu)解，但可以在一定時間內(nèi)找到近似最優(yōu)解。

2.3 基于搜索式的軟硬件劃分方法

2.3.1 蟻群算法

搜索式算法原理是從解空間中的任意解出發(fā)，搜索其鄰域中更優(yōu)的解來替代當(dāng)前解。蟻群算法初始將m只螞蟻放在起始節(jié)點上，每條邊上賦予初始信息素濃度。當(dāng)蟻群一次完整的尋優(yōu)過程完成之后，對每條邊上的信息素濃度計算并更新,然后又進行新一輪的循環(huán)。循環(huán)結(jié)束的標(biāo)志是蟻群選擇了同一條路徑或達到預(yù)定義的循環(huán)次數(shù)。以第2.1.1小節(jié)提到的PDA手機平臺的視頻、音頻發(fā)送系統(tǒng)為例，任務(wù)圖模型定義如下：節(jié)點V(vt,v1,v2,…,vs)代表任務(wù)模塊，音頻數(shù)據(jù)采集模塊記做v1，視頻數(shù)據(jù)采集模塊記做v2，用戶界面記做v3，MP3編碼模塊記做v4，MPEG4編碼模塊記做v5，音頻與視頻模塊記做v6。

系統(tǒng)的任務(wù)節(jié)點數(shù)為N，則第i(i=1,2，…，N)個節(jié)點采用第j(j=0或1,0表示軟件實現(xiàn),1表示硬件實現(xiàn))種開發(fā)方式。得到的任務(wù)圖模型如圖3所示。

圖3 PDA手機平臺 任務(wù)圖模型

利用基本蟻群算法來求解嵌入式系統(tǒng)軟硬件劃分問題，當(dāng)搜索循環(huán)到一定次數(shù)時，由于搜索過程中的概率性和正反饋作用，產(chǎn)生的局部最優(yōu)解上信息素濃度不斷增加，最終導(dǎo)致所有的搜索結(jié)果都趨于一個局部最優(yōu)解。李正民等人[13]在進行軟硬件劃分時對蟻群算法做出了改進，在信息更新過程中引入局部和全局更新規(guī)則。即當(dāng)一只螞蟻完成一條搜索路徑后，路段信息素濃度按照局部更新規(guī)則更新；當(dāng)全部螞蟻都完成一次路徑搜索后，若在本輪搜索過程中產(chǎn)生了比以前更優(yōu)的路徑，則將當(dāng)前路徑作為全局最優(yōu)路徑，并采用全局更新規(guī)則對與最優(yōu)路徑各節(jié)點相連的路段信息素濃度進行更新。局部和全局更新規(guī)則的使用，有效防止了一條路徑上信息素濃度的過度積累，通過在更新規(guī)則中引入調(diào)整參數(shù)來調(diào)節(jié)同一條路徑被其他螞蟻搜索的概率，盡量使得更多的路徑得到遍歷，降低陷入局部最優(yōu)解的概率。

基于蟻群算法的嵌入式系統(tǒng)軟硬件劃分，首先對系統(tǒng)任務(wù)進行建模，將劃分問題轉(zhuǎn)換成多條件約束問題。采用二進制形式表示最優(yōu)劃分方案，則某任務(wù)節(jié)點的軟件和硬件劃分狀態(tài)通過0或1表示，蟻群對最優(yōu)劃分方案進行局部和全局搜索，搜索過程中不斷對信息素進行更新，每次搜索完成后保存全局最優(yōu)解。對當(dāng)前全局最優(yōu)解進行條件判斷，若滿足條件則結(jié)束搜索；若不滿足，則繼續(xù)搜索。將PDA手機平臺的視頻與音頻系統(tǒng)通過改進的遺傳算法進行軟硬件劃分，得到的劃分結(jié)果如下：

v1為0，采用軟件構(gòu)件實現(xiàn)，v2采用軟件構(gòu)件實現(xiàn)，v3采用軟件構(gòu)件實現(xiàn)，v4采用硬件構(gòu)件實現(xiàn)，v5采用硬件構(gòu)件實現(xiàn)，v6采用軟件構(gòu)件實現(xiàn)。

使用蟻群算法進行軟硬件劃分的關(guān)鍵是保證每次搜索都盡可能多的遍歷路徑，使得每次全局搜索完畢后得到的是全局最優(yōu)解而非局部最優(yōu)解[13]。

2.3.2 改進的遺傳算法

多目標(biāo)劃分求解的關(guān)鍵是求出問題的最優(yōu)解集，然后由設(shè)計者根據(jù)需要選擇合適的解。遺傳算法具有并行、群體搜索的特點，通過多次迭代篩選出適應(yīng)性最強的一組解或多組解，非常適用于求解多目標(biāo)優(yōu)化問題。

多目標(biāo)優(yōu)化問題一般可以描述為下面的數(shù)學(xué)模型[10]：

(5)

式中，x=(x1,x2, … ,xn)T是Rn空間中帶有n個決策變量的向量；f(x)是目標(biāo)函數(shù)，包含p個子目標(biāo)函數(shù)；gi(x)是m個不等式的約束函數(shù)，構(gòu)成多目標(biāo)優(yōu)化的約束集。

針對第2.1.1小節(jié)中的實例，國防科技大學(xué)羅莉等人[10]改進傳統(tǒng)的遺傳算法，在算法實現(xiàn)中，遺傳編碼采用簡單易行的符號編碼方式，每一位代表一個功能模塊，其值為對應(yīng)的IP核或軟件構(gòu)件；變異操作采用基于隨機概率的單點變異，發(fā)生變異的數(shù)目為種群規(guī)模的0.2倍；選擇操作采用父子選擇策略，即子代全部進入下一代，不足的部分用父代個體中適應(yīng)度大的補充。遺傳算法模擬自然界的“優(yōu)勝劣汰”，羅莉等人用適應(yīng)度大小來模擬個體對環(huán)境的適應(yīng)能力，以此表示解點的好壞。設(shè)置的適應(yīng)度函數(shù)計算每組解的適應(yīng)能力，將適應(yīng)能力低的個體淘汰。為了加快求解速度，避免產(chǎn)生違反約束的無效解，對適應(yīng)度函數(shù)中的參數(shù)進行自適應(yīng)調(diào)整，增加有效解，并基于懲罰函數(shù)選擇保留精英。

使用這種改進的遺傳算法進行軟硬件劃分可以得到多組滿足約束條件的解，其中包含使用線性規(guī)劃方法得到的解，這些解都是在某一方面性能最優(yōu)的情況下兼顧滿足其他方面的約束條件，設(shè)計者可以根據(jù)需要選擇其中一個。

2.4 基于任務(wù)級的軟硬件劃分方法

2.4.1Primal-Dual劃分策略

傳統(tǒng)的軟硬件劃分方法分為面向軟件和面向硬件兩種。面向硬件即從硬件開始，根據(jù)系統(tǒng)性能的約束條件，將部分任務(wù)移至軟件實現(xiàn)的方法；面向軟件即從軟件開始，根據(jù)系統(tǒng)對時間的約束，將部分任務(wù)移至硬件實現(xiàn)的方法，該方法具有實現(xiàn)簡單、易用的特點。

原始-對偶(primal-dual)策略[14]是一種經(jīng)典的組合優(yōu)化策略。Vulcan和Cosyma是最早的軟硬件協(xié)同綜合系統(tǒng)(co-synthesissystems)，它們均采用primal-dual策略進行軟硬件劃分。其中，Vulcan采用primal策略，即在劃分之前將所有功能模塊由硬件實現(xiàn)，然后根據(jù)程序中線程之間的并發(fā)性以及依賴關(guān)系，將某些模塊交由軟件實現(xiàn)，觀察這些模塊移植到CPU后系統(tǒng)是否可行，若可行則更新系統(tǒng)開銷，繼續(xù)劃分。Cosyma與Vulcan截然相反，Cosyma采用dual策略，即在劃分之前將所有功能由軟件實現(xiàn)，然后使用Cx編譯器將程序源碼轉(zhuǎn)換為ES圖，對系統(tǒng)進行軟硬件劃分，即對該ES圖進行模塊劃分，將一部分模塊交由硬件實現(xiàn)。Cosyma系統(tǒng)在進行功能分配時以程序塊為原子，即將一部分程序塊交由硬件實現(xiàn)，程序塊不可分割。

類似于使用dual策略，一個簡單的嵌入式系統(tǒng)案例：在道路監(jiān)控中實現(xiàn)降雨實時監(jiān)測功能[15]。該系統(tǒng)主要利用攝像頭的實時拍照功能，將每次采集到的照片進行灰度處理，之后與晴天時同一場景下的灰度圖進行對比，觀察其中是否有雨滴出現(xiàn)后產(chǎn)生的光強差，從而得出是否有降雨的結(jié)論。由于系統(tǒng)實現(xiàn)過程簡單，首先將所有功能模塊使用軟件實現(xiàn)，然后將整個程序分成讀入幀圖像、圖像預(yù)處理、轉(zhuǎn)灰度圖、灰度圖相減、劃分子塊、統(tǒng)計子塊、做出決策子模塊，通過在MATLAB中仿真運行程序，記錄每個子模塊的運行時間，取10次仿真結(jié)果的平均值，得到如表2所列的運行結(jié)果。比較各模塊的平均運行時間，最終決定將比較耗時的讀入圖像和轉(zhuǎn)灰度圖模塊交由硬件實現(xiàn)，其他模塊使用軟件實現(xiàn)。

表2 各模塊平均運行時間

2.4.2 基于ESL的劃分策略

基于電子系統(tǒng)級(Electronic System Level，ESL)的設(shè)計與驗證方式是從系統(tǒng)級到時序級對芯片整體架構(gòu)進行軟硬件劃分和仿真，主要流程分為：高層次建模、系統(tǒng)集成、驗證調(diào)試、架構(gòu)探索、系統(tǒng)綜合等[20]。

SM2算法是國家密碼管理局于2010年12月發(fā)布的橢圓曲線公鑰密碼算法，橢圓曲線密碼學(xué)算法的密鑰長度是可變的，SM2標(biāo)準規(guī)定使用256位，這對算法的性能優(yōu)化提出了很高的要求。SM2屬于計算密集型算法，且其層次性較強，實現(xiàn)結(jié)構(gòu)從頂層到底層分為：模運算層、點運算層、多倍點運算層和應(yīng)用層[21]，其中多倍點運算層包括點乘運算。針對每一級運算復(fù)雜度的不同選擇使用軟件或硬件方式實現(xiàn)，共組合產(chǎn)生6種劃分方式。

基于不同的劃分方案，使用SystemC語言對SM2算法硬件實現(xiàn)部分進行周期精確(Cycle Accurate)建模[20]。接著通過系統(tǒng)級與模塊及兩層驗證比較軟硬件模塊執(zhí)行周期數(shù)，以模乘運算為例[22]，如：對于點乘運算，硬件實現(xiàn)相較于軟件實現(xiàn)所需周期數(shù)，其倍數(shù)能提高500倍，性能得到大幅度提高，可將該部分劃分為硬件實現(xiàn)。當(dāng)時鐘頻率為 50 MHz時，用軟件完成一次加密算法超過10 s，若采用點乘部分作為硬件加速模塊，點乘時間為20 ms，完成一次加密需要40 ms。此時優(yōu)選硬件實現(xiàn)點乘及其以下的運算模塊，其他模塊采用軟件實現(xiàn)。此劃分方式可提高系統(tǒng)實時性。

硬件加速模塊提高系統(tǒng)實時性的同時，還會提高系統(tǒng)的硬件面積和功耗。同時將RTL級模型在硬件平臺上實現(xiàn)，通過比較面積和功耗得到性能和資源的平衡。用戶可根據(jù)系統(tǒng)需求，對6種劃分方式進行分析與選擇。

結(jié) 語

本文主要介紹了常用的3種軟硬件劃分求解方法和一種任務(wù)級的軟硬件劃分方法。

規(guī)劃類方法主要介紹了最常用的線性規(guī)劃法和基于UML模型分析的軟硬件劃分方法，線性規(guī)劃、動態(tài)規(guī)劃、混合整數(shù)規(guī)劃等計算復(fù)雜度高，內(nèi)存開銷大，只適合于求解小規(guī)模的嵌入式系統(tǒng)劃分問題，隨著劃分問題擴大，計算時間復(fù)雜度呈指數(shù)上升。構(gòu)造式方法關(guān)鍵在于構(gòu)造正確的啟發(fā)式規(guī)則，求解效率較高，可以得到次優(yōu)解，但針對復(fù)雜度高的劃分問題難以構(gòu)造出合適的啟發(fā)式規(guī)則。搜索式算法求解效率高，可以得到最優(yōu)解，但也容易陷入局部最優(yōu)?；谌蝿?wù)級的劃分方法在實踐中應(yīng)用廣泛，但多是根據(jù)經(jīng)驗進行劃分，缺乏科學(xué)的分析方法。

[1] 杜敏.嵌入式系統(tǒng)軟硬件劃分方法的研究[D].哈爾濱:哈爾濱理工大學(xué),2008.

[2] 陳思功,秦曉,章恒翀.基于UML的軟硬件協(xié)同設(shè)計的模型分析方法[J].軟件學(xué)報,2003(1):103-109.

[3] CHATHA K S,VEMURI R.An Iterative Algorithm for Hardware-Software Partitioning,Hardware Design Space Exploration and Scheduling[J].Design Automation for Embedded Systems,2000,5(2):281-293.

[4] D’AMBROSIO J G,HU X.Configuration-level Hardware/Software Partitioning for Real-time Embedded Systems[C]//Proceedings of the Third International Workshop on Hardware/Software Co-Design,1994:34-41.

[5] Kalavade A,Lee E A.The Extended Partitioning Problem:Hardware/Software Mapping,Scheduling,and Implementation-bin Selection[J].Design Automation for Embedded Systems,1997,2(2):125-163.

[6] Bender,Armin.Design of an Optimal Loosely Coupled Heterogeneous Multiprocessor System[J].European Design&Test Conference,1997:275-281.

[7] Dick R P,Jha N K.MOCSYN:multiobjective core-based single-chip system synthesis[C]//Design,Automation and Test in Europe Conference and Exhibition,1999.

[8] Chonlameth Arpnikanondt,Vijay K Madisetti.Constraint-Based Codesign(CBC) of Embedded Systems:The UML Approach[C]//Center for Signal&Image Processing(CSIP) Electrical&Computer Engineering Georgia Tech,Atlanta,GA 30332-0250.

[9] Jifeng He,Dang Van Hung,Geguang Pu,et al.Exploring optimal solution to hardware/software partitioning for synchronous model[J].Formal Aspects of Computing,2005,17(4):443-460.

[10] 羅莉,夏軍,何鴻君,等.一種有效的面向多目標(biāo)軟硬件劃分的遺傳算法[J].計算機科學(xué),2010,37(12):275-279.

[11] 韓紅蕾,劉文菊,武繼剛,等.多核片上系統(tǒng)的高效軟硬件劃分及調(diào)度算法[J].計算機工程與科學(xué),2011,33(9):57-62.

[12] 郭天天.嵌入式系統(tǒng)軟硬件劃分技術(shù)研究[D].長沙:國防科技大學(xué),2006.

[13] 李正民,郭金金,呂瑩瑩.一種嵌入式系統(tǒng)軟硬件劃分算法[J].計算機仿真,2011,28(10):204-207.

[14] Jorgen Staunstrup,Wayne Wolf.Hardware/Software Co-Design Principles and Practice[M].The Hague:Kluwer Academic Publishers,1997.

[15] 楊志華.攝像頭降雨監(jiān)測系統(tǒng)的軟硬件協(xié)同設(shè)計[D].上海:華東師范大學(xué),2013.

[16] Youness H,Hassen M,Sakanushi K,et al.A High Performance Algorithm for Scheduling and Hardware-Software Partitioning on MPSoCs[C]//Proc of the 4th Int’l Conf on Design&Technology of Integrated System in Nanoscal Era,2009.

[17] 黃源,鐘艷如,陳洺均.基于時間Petri網(wǎng)的嵌入式系統(tǒng)軟硬件劃分方法[J].微計算機信息,2008,24(8):33-35.

[18] 陳瑋,顧思思.基于組合算法的嵌入式系統(tǒng)軟硬件劃分方法[J].計算機應(yīng)用與軟件,2015(10):240-243.

[19] 謝曉娜,朱清新.支持多屬性決策的嵌入式系統(tǒng)軟硬件劃分[J].計算機應(yīng)用研究,2014,31(5):1445-1448.

[20] 游余新.基于ESL設(shè)計方法學(xué)的So設(shè)計[J].中國集成電路,2011(9):29-35.

[21] 國家密碼管理局.SM2橢圓曲線公鑰密碼算法總則[EB/OL].[2017-04] .http//www.oscca.gow.cn/.

[22] 鐘麗,劉彥,余思洋,等.嵌入式系統(tǒng)芯片中SM2算法軟硬件協(xié)同設(shè)計與實現(xiàn)[J].計算機應(yīng)用,2015,35(5):1412-1416.

李巖(碩士研究生)，主要研究領(lǐng)域為嵌入式軟件與系統(tǒng)設(shè)計與建模；屈媛(碩士研究生)，主要研究領(lǐng)域為嵌入式軟硬件協(xié)同設(shè)計;陳儀香(教授)，主要研究方向為嵌入式軟件與系統(tǒng)設(shè)計與建模、嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計、軟件可信性度量以及形式化方法。

Review of Hardware/Software Partitioning Method in Hardware-software Co-design

Li Yan1,2,Qu Yuan1,2,Chen Yixiang1,2

(1.Department of Embedded Software and Systems,School of Computer Science and Software Engineering,East China Normal University,Shanghai 200062，China;2.MOE Engineering Research Center for Software/hardware Co-design Technology and Application,East China Normal University)

With the development of internet of things,industrial internet,robot technology in the field of information,the embedded system technology attracts scientists and engineers attention broadly again.Meanwhile,high integration and performance of embedded products are required.One of important approach to develop embedded products is hardware-software co-design and the key point is hardware/software partitioning.According to various scenes,we classify the methods in hardware/software partitioning proposed recently and elaborate each partitioning method combined with real cases.Then a comprehensive comparison is made between these methods,which provides reference to scientists and engineers in the field of embedded system development.

embedded system;hardware-software co-design;hardware/software partitioning

上海市高校物聯(lián)網(wǎng)知識服務(wù)平臺計劃(ZF1213)。

TP31

A

?士然

2017-04-17)