引 言

　　隨著微電子技術(shù)的發(fā)展，芯片的集成度越來越高，片上系統(tǒng)( SOC)的發(fā)展已經(jīng)是必然趨勢(shì)。SOC系統(tǒng)是將原來由許多芯片完成的功能，集中到一塊芯片中完成。但SOC不是各個(gè)芯片功能的簡(jiǎn)單疊加，而是從整個(gè)系統(tǒng)的功能和性能出發(fā)，用軟硬協(xié)同設(shè)計(jì)和驗(yàn)證方法，利用IP復(fù)用及深亞微米技術(shù)，在一個(gè)芯片上實(shí)現(xiàn)復(fù)雜的功能。軟硬件協(xié)同設(shè)計(jì)是一個(gè)從高層抽象建模到低層硬件建模的過程。在從無時(shí)間概念的功能模型轉(zhuǎn)換為總線周期的功能模型過程中，軟硬件劃分和性能評(píng)估是軟硬件協(xié)同設(shè)計(jì)的難點(diǎn)和關(guān)鍵。 
      傳統(tǒng)的芯片設(shè)計(jì)中工程師一般都是憑經(jīng)驗(yàn)進(jìn)行軟硬件劃分，隨著系統(tǒng)結(jié)構(gòu)復(fù)雜度的增加，憑經(jīng)驗(yàn)已經(jīng)難以給出適當(dāng)?shù)膭澐纸Y(jié)果，而且系統(tǒng)的軟硬件劃分結(jié)果直接影響到后續(xù)的軟硬件協(xié)同設(shè)計(jì)和終的硬件實(shí)現(xiàn)，因此軟硬件自動(dòng)劃分技術(shù)成為當(dāng)前研究的熱點(diǎn)。為了實(shí)現(xiàn)軟硬件自動(dòng)劃分，并且評(píng)估軟硬件劃分的優(yōu)劣，評(píng)估因子的選擇以及性能評(píng)估算法的實(shí)現(xiàn)相當(dāng)重要，調(diào)度和分配一直是貫穿在軟硬件劃分性能評(píng)估的始末。目前，軟硬件劃分技術(shù)可以分為兩大類：①首先對(duì)系統(tǒng)初始化，然后在調(diào)度中分析系統(tǒng)特征并優(yōu)化分配。如YuaNXie 和WanyWolf提出的方法是將系統(tǒng)模塊初始化為硬件，然后根據(jù)時(shí)間約束條件改變分配方式將部分硬件由軟件替換減小系統(tǒng)
耗費(fèi)。②在固定分配方式下進(jìn)行調(diào)度，采用遺傳算法、模擬退火算法等進(jìn)行尋優(yōu)。如Dick首先初始化多種分配方案構(gòu)成種群，每個(gè)個(gè)體采用MD算法進(jìn)行調(diào)度，然后采用遺傳算法對(duì)種群進(jìn)行演化，直到搜索到解。 
　　本文研究的軟硬件劃分技術(shù)是基于第二類方法，即是在固定的分配方式下進(jìn)行調(diào)度。當(dāng)系統(tǒng)結(jié)構(gòu)中存在多個(gè)處理器時(shí)，系統(tǒng)的工作流程由多個(gè)并發(fā)的進(jìn)程構(gòu)成，單任務(wù)圖有時(shí)無法描述多個(gè)任務(wù)的并發(fā)性，本文采用多任務(wù)圖對(duì)系統(tǒng)抽象。針對(duì)MD (Mobility Directed)，HNF (Heavy Node First)，HLFET(HighLeveLFirsTwithEstimated Time)算法的缺陷，提出了MTLS(MultiTask LisTScheduling)性能評(píng)估方法。MTLS算法考慮了系統(tǒng)的關(guān)鍵路徑、任務(wù)的權(quán)重大小以及系統(tǒng)的時(shí)間約束，從全局把握。實(shí)驗(yàn)證明，MTLS算法比上述三種算法能夠更好地評(píng)估劃分性能。 
SOC軟硬件協(xié)同設(shè)計(jì) 

SOC軟硬件劃分平臺(tái) 
      軟硬件劃分是軟硬件協(xié)同設(shè)計(jì)首要問題，只有在系統(tǒng)各個(gè)模塊確定了實(shí)現(xiàn)方式之后才能保證軟件和硬件的設(shè)計(jì)可以同時(shí)進(jìn)行。系統(tǒng)實(shí)現(xiàn)的軟硬件劃分平臺(tái)如圖1所示，由六個(gè)模塊組成，分別為圖形用戶編輯接口、系統(tǒng)模型、分配模塊、IP特征庫(kù)、性能評(píng)估模塊、結(jié)果分析。 
      圖形用戶編輯接口是用戶輸入/輸出的接口。系統(tǒng)模型主要是對(duì)系統(tǒng)進(jìn)行形式化的定義，對(duì)系統(tǒng)進(jìn)行建模。IP特征數(shù)據(jù)庫(kù)中收集了很多現(xiàn)有IP核的性能參數(shù)，如IP核的尺寸、工作頻率、工作時(shí)的功耗、空閑時(shí)的功耗等。它是IP核復(fù)用技術(shù)的基礎(chǔ)。分配模塊主要是分析輸入的系統(tǒng)模型以及該系統(tǒng)模型與特征數(shù)據(jù)庫(kù)之間的關(guān)系，從IP庫(kù)中提取特征參數(shù)，完成對(duì)數(shù)據(jù)流圖的分配。性能評(píng)估模塊是，主要是對(duì)分配完成后的數(shù)據(jù)流圖進(jìn)行調(diào)度，評(píng)估出系統(tǒng)的運(yùn)行時(shí)間和功耗。結(jié)果分析模塊主要是分析可行的劃分解，比較得出較優(yōu)的劃分結(jié)果。 
SOC軟硬件劃分流程 
      本文采用速度、功耗和價(jià)格作為衡量的標(biāo)準(zhǔn)，這幾個(gè)參數(shù)也是生產(chǎn)者和消費(fèi)者共同關(guān)注的問題。要使劃分的結(jié)果，實(shí)際上是一個(gè)多目標(biāo)優(yōu)化的過程，遺傳算法可以很好地進(jìn)行多目標(biāo)尋優(yōu)。圖2是軟硬件劃分的流程圖，整個(gè)流程在外框架是一個(gè)多目標(biāo)尋優(yōu)的演化過程，而在每次的演化過程中采用MTLS算法對(duì)分配后的模型進(jìn)行調(diào)度和評(píng)估。 
      首先，在圖形接口輸入系統(tǒng)形式化定義后的數(shù)據(jù)流圖，從IP特征庫(kù)選擇合適的IP進(jìn)行初始化的分配。同時(shí)初始化種群，界定優(yōu)化算法的搜索空間，為多目標(biāo)優(yōu)化模塊指定相應(yīng)的優(yōu)化目標(biāo)。其次，調(diào)度種群中的個(gè)體，給出優(yōu)化目標(biāo)的評(píng)估結(jié)果，并將不滿足時(shí)間約束條件的解直接刪除。采用小生境技術(shù)選擇較優(yōu)的解構(gòu)成前沿，經(jīng)過演化，該前沿會(huì)逐漸靠近空間的前沿。，判斷逐步演化的前沿是否為前沿，如果是前沿，演化過程結(jié)束，并輸出一組非劣的劃分結(jié)果和相應(yīng)的目標(biāo)值。 
性能評(píng)估 

形式化定義 
      系統(tǒng)結(jié)構(gòu)是異步多處理器結(jié)構(gòu)，由多個(gè)RISC和多個(gè)ASIC組成，多個(gè)CPU共享一個(gè)存儲(chǔ)器。同一個(gè)CPU上可以執(zhí)行不同任務(wù)，而同一個(gè)ASIC只能執(zhí)行一種任務(wù)。為了較好地描述這樣的系統(tǒng)結(jié)構(gòu)，采用DAG (Directed Acyclic Graph)來對(duì)系統(tǒng)進(jìn)行抽象。DAG稱為有向無環(huán)圖，如圖4所示，DAG由節(jié)點(diǎn)和弧線構(gòu)成，N1→N2表示N2的執(zhí)行必須在N1完成之后。首先要把系統(tǒng)分解為若干個(gè)并行的流程。對(duì)于每個(gè)流程，按照一定的粒度對(duì)硬件描述代碼和軟件代碼進(jìn)行分析，分解為若干個(gè)任務(wù)。然后確定每個(gè)流程中任務(wù)間(包括硬件和軟件)的依賴關(guān)系。任務(wù)映射為DAG中的節(jié)點(diǎn)，任務(wù)之間的數(shù)據(jù)依賴映射為DAG中的弧線，因此系統(tǒng)的調(diào)度問題也就轉(zhuǎn)換成為對(duì)多任
務(wù)圖的調(diào)度。 
      對(duì)系統(tǒng)做如下定義：DAG = {D1，D2，. . . ，Di}，Di表示任務(wù)圖，Di= {N，E}，N= {N1，N2，. . . ，Ni}，Ni代表任務(wù)圖中的節(jié)點(diǎn)，NCi表示Ni的子節(jié)點(diǎn)，NPi表示Ni的父節(jié)點(diǎn)；E = { EN1→N2，EN1→N3 ，.，ENi→Nj}，ENi→Nj表示Ni到Nj的弧線。如果Ni和Nj都由硬件或者軟件實(shí)現(xiàn)，ENi→Nj代價(jià)為零，否則映射為總線。 
　　定義1　indegree表示流入任務(wù)節(jié)點(diǎn)弧線數(shù)，outdegree表示流出任務(wù)節(jié)點(diǎn)弧線的個(gè)數(shù)。src代表入度為零的任務(wù)節(jié)點(diǎn)，sink代表出度為零的任務(wù)節(jié)點(diǎn)。每個(gè)sink任務(wù)節(jié)點(diǎn)都會(huì)賦有截止時(shí)間deadline，表示對(duì)sink任務(wù)的時(shí)間約束。EXT表示任務(wù)的執(zhí)行時(shí)間。data定義為總線上傳輸?shù)臄?shù)據(jù)。ST表示系統(tǒng)調(diào)度所需的時(shí)間。 
      定義2　EFT( EarliesTFinishTime)表示任務(wù)節(jié)點(diǎn)早完成任務(wù)的時(shí)間，可以通過從src節(jié)點(diǎn)向下遍歷獲得。假設(shè)Ni有p個(gè)父節(jié)點(diǎn)，如果ENPik →Ni的代價(jià)為零，w= 0，如果ENPik →Nt由總線實(shí)現(xiàn)，w= 1(以后的w表示相同的含義)。EFT由如下的公式確定： 
        
      定義3　LFT(LatesTFinishTime)表示任務(wù)節(jié)點(diǎn)晚完成任務(wù)的時(shí)間，可以通過從樹的根節(jié)點(diǎn)向上遍歷獲得。假設(shè)Ni有p個(gè)子節(jié)點(diǎn)，LFT由如下公式確定： 

        如果Ni為sink節(jié)點(diǎn)，NLFTi= deadline。 
      定義4　mobility表示任務(wù)節(jié)點(diǎn)N和總線E執(zhí)行時(shí)間的靈活度。任務(wù)節(jié)點(diǎn)的mobility值定義為L(zhǎng)FT和EFT的差值：mobility =LFT-EFT任務(wù)節(jié)點(diǎn)N和總線E的mobility的屬性有如下關(guān)系：
　　 

      定義5　CP(CriticaLPath)定義為關(guān)鍵路徑，表示從src節(jié)點(diǎn)到sink節(jié)點(diǎn)執(zhí)行時(shí)間長(zhǎng)的路徑。Critical是一個(gè)布爾量，表示任務(wù)節(jié)點(diǎn)N和總線E是否位于關(guān)鍵路徑上。 
      定義6　BD (BottomDistance)表士任務(wù)節(jié)點(diǎn)到sink節(jié)點(diǎn)的長(zhǎng)的執(zhí)行路徑，由如下公式確定： 

        k如果Ni為sink節(jié)點(diǎn)，NBDi= NEXTi。

MTLS算法的思想與實(shí)現(xiàn) 
優(yōu)先級(jí)確定 
      優(yōu)先級(jí)的比較分為同一任務(wù)圖中節(jié)點(diǎn)之間的比較和不同任務(wù)圖中節(jié)點(diǎn)之間的比較。對(duì)于同一任務(wù)圖，關(guān)鍵路徑上的任務(wù)執(zhí)行時(shí)間長(zhǎng)，要使任務(wù)盡早完成，即要盡量使關(guān)鍵路徑上的任務(wù)盡早執(zhí)行，因此關(guān)鍵路徑上的任務(wù)優(yōu)先級(jí)。關(guān)鍵路徑上任務(wù)的父輩任務(wù)越早執(zhí)行使得關(guān)鍵路徑上的任務(wù)越早就緒，因此它們的優(yōu)先級(jí)次高。不屬于前兩類的任務(wù)節(jié)點(diǎn)通過BD來比較它們的優(yōu)先級(jí)。對(duì)于不同的任務(wù)圖，首先根據(jù)任務(wù)是否在關(guān)鍵路徑上來比較它們的優(yōu)先級(jí)，在關(guān)鍵路徑上的任務(wù)優(yōu)先調(diào)度。如果兩者都在關(guān)鍵路徑上或者都不在關(guān)鍵路徑上，就比較它們的mobility大小。mobility體現(xiàn)了任務(wù)圖的時(shí)間約束，約束條件緊迫的流程應(yīng)當(dāng)優(yōu)先考慮。 
速度和功耗的評(píng)估
　　算法實(shí)現(xiàn)的流程圖如圖3所示。輸入為配置好的多任務(wù)圖，根據(jù)上述定義計(jì)算出CP，以及每個(gè)任務(wù)節(jié)點(diǎn)和弧線的mo2bility和BD參數(shù)。根據(jù)優(yōu)先級(jí)確定計(jì)算出每個(gè)任務(wù)節(jié)點(diǎn)和弧線的優(yōu)先級(jí)大小，搜索就緒的任務(wù)節(jié)點(diǎn)和弧線，選擇并行執(zhí)行的節(jié)點(diǎn)，包括優(yōu)先級(jí)的硬件、優(yōu)先級(jí)的總線和優(yōu)先級(jí)的軟件。如果有多個(gè)CPU，則要根據(jù)CPU的個(gè)數(shù)確定多個(gè)軟件并行執(zhí)行的情況，并且在多CPU上進(jìn)行調(diào)度，保證CPU資源的充分利用。選擇每次調(diào)度中的執(zhí)行時(shí)間，判斷調(diào)度是否完成，如果沒有則繼續(xù)循環(huán)調(diào)度，如果結(jié)束就計(jì)算調(diào)度的累加時(shí)間。 
      假設(shè)Ni的實(shí)現(xiàn)IP為PE，Eij實(shí)現(xiàn)IP為B us，IPi= { PE1，PE2，. . . ，PEN，B us}，PE = PEh∪PEs，PEh代表軟件IP，PEs代表硬件IP。由IPi建立鏈表IPList，每個(gè)IPi需要執(zhí)行j個(gè)任務(wù)，用Tij表示，j個(gè)任務(wù)Tij建立鏈表TaskList，每個(gè)Tij對(duì)應(yīng)一個(gè)
任務(wù)節(jié)點(diǎn)Ni。
　　Tij= {Ni1，Ni2，. . . ，Nij}，IPi∈PE
　　Tij= { Ei1，Ei2，. . . ，Eij}，IPi為B us 
      調(diào)度前為每個(gè)任務(wù)圖建立鏈表Task Ready List和Task Compare List，Task Ready List用來比較同一任務(wù)圖中任務(wù)的優(yōu)先級(jí)，Task Compare List用來比較不同任務(wù)圖中任務(wù)之間的優(yōu)先級(jí)。實(shí)現(xiàn)MTLS性能評(píng)估算法的偽碼如下： 
        
        
      調(diào)度完成后，ST就是系統(tǒng)執(zhí)行的時(shí)間，也是系統(tǒng)速度的衡量標(biāo)準(zhǔn)。價(jià)格的評(píng)估比較簡(jiǎn)單，只需要簡(jiǎn)單的累加。在已知調(diào)度時(shí)間ST，每個(gè)任務(wù)執(zhí)行時(shí)間NEXT、單位時(shí)間的功耗Npow，總線的執(zhí)行時(shí)間EEXTij、總線工作功耗B uspow、總線空閑功耗B usidle下，系統(tǒng)功耗的評(píng)估由如下公式確定： 
        

實(shí)驗(yàn)結(jié)果與分析 
      MD算法的基本思想是根據(jù)任務(wù)執(zhí)行的靈活度來確定優(yōu)先級(jí)；HNF算法的基本思想是根據(jù)任務(wù)的權(quán)重大小來確定優(yōu)先級(jí)；HLFET算法的基本思想是根據(jù)任務(wù)執(zhí)行的路徑大小來確定優(yōu)先級(jí)。這三種算法都存在它們的不足，它們沒有從全局上考慮系統(tǒng)的整體信息，而是通過系統(tǒng)的局部信息來調(diào)度。MTLS算法考慮了系統(tǒng)的關(guān)鍵路徑、任務(wù)的權(quán)重大小以及系統(tǒng)的時(shí)間約束，是從全局上進(jìn)行把握的。 
      為了驗(yàn)證算法的有效性，采用包含兩個(gè)DAG的系統(tǒng)作為例子，如圖4所示，個(gè)DAG由七個(gè)任務(wù)節(jié)點(diǎn)組成，第二個(gè)DAG由10個(gè)任務(wù)節(jié)點(diǎn)組成。任務(wù)的執(zhí)行時(shí)間已經(jīng)在圖中注明，黑色節(jié)點(diǎn)代表任務(wù)由軟件實(shí)現(xiàn)，白色節(jié)點(diǎn)代表任務(wù)由硬件實(shí)現(xiàn)，每個(gè)sink節(jié)點(diǎn)的時(shí)間約束都為1400。采用MTLS算法，計(jì)算出了CP(CP為1表示節(jié)點(diǎn)在關(guān)鍵路徑上)，以及每個(gè)任務(wù)節(jié)點(diǎn)的參數(shù)mobility，BD，并得到了每個(gè)任務(wù)在相應(yīng)IP完成時(shí)間，如表1所示(mb表示mobility)。 
　　可見執(zhí)行的任務(wù)是DAG1中的N7，在1310時(shí)刻完成任務(wù)，因此采用MTLS算法需要1310個(gè)時(shí)間單位。同樣用MD，HNF，HLFET算法調(diào)度后，得到結(jié)果如下：MD算法需要1440個(gè)時(shí)間單位，HNF算法需要1390個(gè)時(shí)間單位，用HLFET算法需要1470個(gè)時(shí)間單位。采用MTLS算法執(zhí)行的時(shí)間短。實(shí)驗(yàn)數(shù)據(jù)如表1所示。 
       
　　為了更好地比較四種算法的優(yōu)劣，采用個(gè)數(shù)不同的任務(wù)圖來驗(yàn)證。分別輸入個(gè)數(shù)為2，4，6，8的任務(wù)圖，如圖5所示，可以發(fā)現(xiàn)隨著DAG個(gè)數(shù)的增多，四種算法的差距越大，MTLS算法比其他三種算法性能優(yōu)越。實(shí)驗(yàn)結(jié)果說明，MTLS算法適于并行進(jìn)程比較多的系統(tǒng)，它能夠很好地減少并行進(jìn)程的調(diào)度時(shí)間。MD算法雖然考慮到了關(guān)鍵路徑上任務(wù)，但沒有考慮到非關(guān)鍵路徑上的任務(wù)對(duì)調(diào)度的影響，而且會(huì)導(dǎo)致約束條件嚴(yán)格的任務(wù)一直保持高優(yōu)先級(jí)，使得其他任務(wù)無法搶占。HNF算法沒有考慮關(guān)鍵路徑，也沒有考慮時(shí)間約束，這種算法使用的任務(wù)特征太局部化。在兩個(gè)任務(wù)圖的關(guān)鍵路徑的長(zhǎng)度相差比較大的情況下，HLFET算法容易延遲路徑短的任務(wù)圖，雖然縮短了調(diào)度時(shí)間，卻無法滿足約束條件。MTLS算法既考慮了關(guān)鍵路徑，又考慮到了非關(guān)鍵路徑，同時(shí)也滿足了時(shí)間約束條件，從全局把握。同一任務(wù)圖中的就緒任務(wù)和不同任務(wù)圖中的就緒任務(wù)采用不同的策略調(diào)度，使得對(duì)軟硬件劃分的性能評(píng)估。 
結(jié)    論 

　　硬件集成度的飛速發(fā)展導(dǎo)致SOC產(chǎn)品的開發(fā)面臨著巨大的挑戰(zhàn)，SOC的設(shè)計(jì)方法學(xué)的研究還是任重而道遠(yuǎn)的。多任務(wù)圖比單任務(wù)圖能夠更好地描述包含多個(gè)處理器的系統(tǒng)結(jié)構(gòu)，因此提出用多任務(wù)圖建模。本文的軟硬件劃分平臺(tái)是在系統(tǒng)級(jí)進(jìn)行建模，提高了設(shè)計(jì)的層次，在高層對(duì)系統(tǒng)的速度、功耗、價(jià)格進(jìn)行評(píng)估，避免了底層設(shè)計(jì)帶來的不必要的損失。MTLS算法是本文提出的適合評(píng)估軟硬件劃分性能的評(píng)估算法，通過實(shí)驗(yàn)比較比其他三種算法優(yōu)越。在下一步的改進(jìn)方面，可以在目標(biāo)值的優(yōu)化方面改進(jìn)為優(yōu)化更多的目標(biāo)或是根據(jù)用戶的需求動(dòng)態(tài)選擇優(yōu)化目標(biāo)，以滿足不同用戶對(duì)產(chǎn)品的需求。