（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）動態(tài)可重構(gòu)系統(tǒng)任務(wù)劃分方法研究.pdf

南京郵l 【1 人學(xué)顧一 ：研究生學(xué)位論義摘愛 摘要 軟硬件協(xié)同設(shè)計(jì)使嵌入式系統(tǒng)的軟件和硬件設(shè)計(jì)互相協(xié)同、并行實(shí)現(xiàn)，有利于盡早發(fā) 現(xiàn)錯誤、降低成本和提高系統(tǒng)性能，而軟硬件任務(wù)劃分是嵌入式協(xié)同設(shè)計(jì)的重要環(huán)節(jié)，對 系統(tǒng)的后續(xù)設(shè)計(jì)實(shí)現(xiàn)及系統(tǒng)整體性能都有較大的影響。軟硬件劃分是在滿足系統(tǒng)各項(xiàng)約束 條件的前提下，為目標(biāo)系統(tǒng)各個功能任務(wù)確定具體的實(shí)現(xiàn)方式，以達(dá)到各項(xiàng)約束最佳的軟 硬件分配方案。 可重構(gòu)計(jì)算以其較高的靈活性和系統(tǒng)性能目前廣泛應(yīng)用于多個領(lǐng)域。隨著以f p g a 為代 表的可重構(gòu)硬件的發(fā)展，動態(tài)可重構(gòu)系統(tǒng)已經(jīng)成為了嵌入式系統(tǒng)的一個發(fā)展趨勢。動態(tài)可 重構(gòu)系統(tǒng)不僅在系統(tǒng)結(jié)構(gòu)上有別于傳統(tǒng)的嵌入式系統(tǒng)，而且其任務(wù)執(zhí)行方式也發(fā)生了根本 性的變化，最大的特點(diǎn)是可以時分復(fù)用的使用可重構(gòu)單元以硬件方式執(zhí)行任務(wù)，極大的提 高了系統(tǒng)性能。但是同時也帶來了一些新的問題，如重構(gòu)時間過長、可重構(gòu)硬件資源布局 和配置文件如何預(yù)讀取等。由于動態(tài)可重構(gòu)系統(tǒng)的諸多新特點(diǎn)新問題，傳統(tǒng)的軟硬件劃分 方法已經(jīng)不再適用。因此本文在對軟硬件劃分和動態(tài)可重構(gòu)系統(tǒng)特點(diǎn)研究的基礎(chǔ)上，提出 了基于權(quán)重動態(tài)可變的免疫算法的軟硬件劃分方法，并結(jié)合調(diào)度算法進(jìn)行評估。這種算法 能較好的適應(yīng)動態(tài)可重構(gòu)環(huán)境，使動態(tài)可重構(gòu)系統(tǒng)的軟硬件任務(wù)劃分更加合理，能夠充分 發(fā)揮可重構(gòu)單元的高速性，達(dá)到系統(tǒng)性能的最優(yōu)化。 關(guān)鍵詞：動態(tài)可重構(gòu)系統(tǒng)，軟硬件劃分，免疫算法，任務(wù)調(diào)度 南京郵i 乜人學(xué)頌l ：研究生學(xué)位論文a b s t r a c t a b s t r a c t h a r d w a r e s o f t w a r ec o d e s i g ne n a b l ep a r a l l e li m p l e m e n t a t i o nf o rt h es o f t w a r ea n dh a r d w a r e d e s i g no fe m b e d d e ds y s t e ma n d i ta l s oc o n d u c e st oe a r l yd e t e c t i o no fe r r o r s ，c o s t sr e d u c t i o na n d s y s t e mp e r f o r m a n c ei m p r o v e m e n t a n dh a r d w a r e s o f t w a r ep a r t i t i o n i n g i so n eo ft h em o s t i m p o r t a n ta s p e c t so fe m b e d d e ds y s t e mc o d e s i g n t h er e s u l to fh w s wp o r t i o n i n gh a sag r e a t e r i m p a c tt of o l l o w - u pd e s i g na n do v e r a l ls y s t e mp e r f o r m a n c e h w s wp o r t i o n i n ga l g o r i t h mf i r s t l y m u s tm e e tt h ed e m a n d so ft h et a r g e ts y s t e m ，t h e ni ta s s i g n se a c ht a s ko ft a r g e ts y s t e mt 6s o f t w a r e o rh a r d w a r ec o m p u t i n gu n i ti no r d e rt oa c h i e v et h eb e s ts y s t e mp e r f o r m a n c e b e c a u s eo fi t sh i g h f l e x i b i l i t ya n ds y s t e mp e r f o r m a n c e ，r e c o n f i g u r a b l ec o m p u t i n g c u r r e n t l yi sw i d e l yu s e di nm a n yf i e l d s w i t ht h ed e v e l o p m e n to fr e c o n f i g u r a b l eh a r d w a r e ，s u c h a sf p g a ，d y n a m i c a l l yr e c o n f i g u r a b l es y s t e mh a sb e c o m ead e v e l o p i n gt r e n do fe m b e d d e d s y s t e m d y n a m i cr e c o n f i g u r a b l es y s t e mi sn o to n l yd i f f e r e n tf r o mt h et r a d i t i o n a le m b e d d e d s y s t e m si ns y s t e ms t r u c t u r e ，b u ta l s oi t sp a t t e r n so ft h et a s kp e r f o r m a n c eh a v eu n d e r g o n ea f u n d a m e n t a lc h a n g e i tc a nu s et h er e c o n f i g u r a b l eh a r d w a r et or u nt h et a s k si nt d mw a yt o s p e e du pt h es y s t e m m e a n w h i l e ，i tb r i n g ss o m en e wp r o b l e m s ，s u c ha sr e c o n f i g u r a t i o nl a t e n c y , t h el a y o u tm o d eo fr e c o n f i g u r a b l eh a r d w a r er e s o u r c e s ，h o wt op r e f e t c ht h ec o n f i g u r a t i o nf i l e s a n ds oo n f o rt h es a k eo ft h en e wf e a t u r e sa n dp r o b l e m so fd y n a m i c a l l yr e c o n f i g u r a b l es y s t e m ， t h et r a d i t i o n a lm e t h o d so fh w s wp a r t i t i o n i n ga r en ol o n g e ra d a p t a b l e t h e r e f o r e ，i nt h i sp a p e r , b a s e do nt h es u f f i c i e n tc o n s i d e ro ft h ec h a r a c t e r i s t i co fd y n a m i c a l l yr e c o n f i g u r a t i o na n dh w s w p a r t i t i o n i n g ，a l li m m u n ea l g o r i t h mo fa l t e r a b l ec o e f f i c i e n to fp a r a m e t e r sd r i v e nh w s w p a r t i t i o n i n gm e t h o dc o m b i n e d 、析t l ls c h e d u l i n ga l g o r i t h mi sp r e s e n t e dt ot r yt op a r t i t i o nt h et a s k s o fa p p l i c a t i o n t h i sa l g o r i t h mi sb e t t e rt h a nt r a d i t i o n a lh w s wp a r t i t i o n i n gm e t h o d st oa d a p tt o t h ee n v i r o n m e n to fd y n a m i cr e c o n f i g u r a b l es y s t e m i ti sm o r er a t i o n a la n de f f i c i e n t ，a n di tc a n a c h i e v et h eo p t i m i z a t i o no fs y s t e mp e r f o r m a n c e k e yw o r d s ：d y n a m i c a l l yr e c o n f i g u r a b l es y s t e m ，h w s wp a r t i t i o n i n g ，i n l l t l u n ea l g o r i t h m ， t a s ks c h e d u l i n g i i 南京郵電大學(xué)學(xué)位論文原創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得 的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包 含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得南京郵電大學(xué)或其它 教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的 任何貢獻(xiàn)均己在論文中作了明確的說明并表示了謝意。 研究生始砂吼型 南京郵電大學(xué)學(xué)位論文使用授權(quán)聲明 南京郵電大學(xué)、中國科學(xué)技術(shù)信息研究所、國家圖書館有權(quán)保留本人所送 交學(xué)位論文的復(fù)印件和電子文檔，可以采用影印、縮印或其它復(fù)制手段保存論 文。本文電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。除在保密期內(nèi)的保密論文 外，允許論文被查閱和借閱，可以公布( 包括刊登) 論文的全部或部分內(nèi)容。 論文的公布( 包括刊登) 授權(quán)南京郵電大學(xué)研究生部辦理。 研究生簽名：步目馬毒寸 導(dǎo)師簽名：期：少c ) 需罾o 南京郵l u 人學(xué)顧i j 研究生學(xué)位論義第一章引言 1 1 課題背景 1 1 1 嵌入式系統(tǒng)的特點(diǎn) 第一章引言 隨著嵌入式技術(shù)的發(fā)展，嵌入式系統(tǒng)被廣泛應(yīng)用于國防電子、數(shù)字家庭、工業(yè)自動化、 汽車電子、醫(yī)學(xué)科技、消費(fèi)電子、無線通訊、電力系統(tǒng)等國民經(jīng)濟(jì)的主要行業(yè)。嵌入式系 統(tǒng)被定義為【1 1 ：以應(yīng)用為中心、以計(jì)算機(jī)技術(shù)為基礎(chǔ)、軟件硬件可裁剪、適應(yīng)應(yīng)用系統(tǒng)， 對功能、可靠性、成本、體積、功耗嚴(yán)格要求的專用計(jì)算機(jī)系統(tǒng)。一個嵌入式系統(tǒng)就是一 個硬件和軟件的集合體，它包括硬件和軟件兩部分。硬件包括嵌入式處理器、存儲系統(tǒng)及 外部接口。嵌入式軟件主要包括兩大部分，嵌入式操作系統(tǒng)和應(yīng)用軟件。相對于通用計(jì)算 機(jī)系統(tǒng)，嵌入式系統(tǒng)具有許多自身的特點(diǎn)【1 2 1 ，主要有以下幾個方面： ( 1 ) 專用性強(qiáng)：通常用在特定的領(lǐng)域，為特定的用戶群設(shè)計(jì)。軟件系統(tǒng)和硬件緊密結(jié) 合，針對不同的應(yīng)用常常要做很大的改動，甚至廢棄整個系統(tǒng)并重新進(jìn)行設(shè)計(jì)。 ( 2 ) 有實(shí)時性約束：嵌入式系統(tǒng)往往對時間的要求非常嚴(yán)格，能快速響應(yīng)外部事件， 常用在一些對實(shí)時性要求很高的場合，如果不能及時響應(yīng)，系統(tǒng)將出現(xiàn)重大錯誤。雖然現(xiàn) 在有些嵌入式系統(tǒng)的應(yīng)用對實(shí)時性的要求不是很高，但實(shí)時性的要求也始終是衡量系統(tǒng)性 能的_ 個重要指標(biāo)。 ( 3 ) 成本要求嚴(yán)格：成本指的是系統(tǒng)成本，包括軟硬件成本，設(shè)計(jì)開發(fā)成本和開發(fā)周 期成本等多個方面，要求設(shè)計(jì)者在進(jìn)行開發(fā)時必須綜合考慮，在各種約束中找到滿足系統(tǒng) 需求描述的折中方案。 ( 4 ) 要求低功耗：由于許多嵌入式系統(tǒng)用在小型應(yīng)用系統(tǒng)中，且要求長時間不間斷工 作，因此功耗也是衡量嵌入式系統(tǒng)性能的一項(xiàng)重要指標(biāo)。功耗約束影響了系統(tǒng)設(shè)計(jì)決策的 許多方面，包括處理器選擇、內(nèi)存體系結(jié)構(gòu)的設(shè)計(jì)等j 還有可能決定軟件是用匯編語言編 寫還是c 語言編寫。 ( 5 ) 可靠性要求：由于些嵌入式系統(tǒng)用于關(guān)鍵性產(chǎn)品，承擔(dān)高危險及高保密要求的 應(yīng)用，所以可靠性的要求也是設(shè)計(jì)者必須考慮的因素。嵌入式c p u 大多工作在為特定用戶 群設(shè)計(jì)的系統(tǒng)中，通常具有功耗低、體積小、集成度高等特點(diǎn)，要求嵌入式系統(tǒng)設(shè)計(jì)的小 型化，高可靠性。 ( 6 ) 需要專門的開發(fā)工具和方法：由于嵌入式系統(tǒng)包括了硬件和軟件，其開發(fā)的方法 1 墮皇唑皇叁蘭堡! ：至! 窒竺蘭篁絲苧笙二里! ! 童 也不同于普通的p c 機(jī)。針對嵌入式系統(tǒng)已經(jīng)出現(xiàn)了很多設(shè)計(jì)方法，如先硬件后軟件、先 軟件后硬件和軟硬件協(xié)同設(shè)計(jì)等。嵌入式調(diào)試已發(fā)展出了很多支持嵌入式系統(tǒng)開發(fā)過程的 專用工具套件。 廣泛的應(yīng)用范圍以及上述這些特點(diǎn)，使嵌入式系統(tǒng)的復(fù)雜度日益增加，設(shè)計(jì)的難度也 越來越大。針對這些問題，前人做了很多探索，并提出了一些有效的解決方法，如在設(shè)計(jì) 中使用軟硬件協(xié)同設(shè)計(jì)，采用基于f p g a 的可重構(gòu)系統(tǒng)滿足系統(tǒng)性能的各項(xiàng)要求等。 1 1 2 軟硬件協(xié)同設(shè)計(jì)技術(shù)的發(fā)展?fàn)顩r 在傳統(tǒng)的嵌入式系統(tǒng)設(shè)計(jì)方法中，將硬件和軟件劃分為兩個獨(dú)立的部分，先硬件后軟 件，分別按照各自的設(shè)計(jì)流程來完成。這導(dǎo)致了軟硬件開發(fā)工作被割裂開，工程師之間缺 乏有效的溝通。如果在軟硬件集成時，系統(tǒng)實(shí)現(xiàn)不能滿足開發(fā)性能指標(biāo)，將需要對軟件與 硬件反復(fù)修改、反復(fù)試驗(yàn)。而硬件功能的調(diào)整會導(dǎo)致成本的增加和開發(fā)周期的延長。在實(shí) 際設(shè)計(jì)中，這種開發(fā)方法不能對整個系統(tǒng)性能做出較好的優(yōu)化，已經(jīng)不能適應(yīng)如今規(guī)模和 復(fù)雜度都越來越大的應(yīng)用。 針對傳統(tǒng)設(shè)計(jì)方法缺陷，人們提出了軟硬件協(xié)同設(shè)計(jì)的思想。軟硬件協(xié)同設(shè)計(jì)方法學(xué) 的研究始于2 0 世紀(jì)9 0 年代初期，第一屆i n t e r n a t i o n a lw o r k s h o po nh a r d w a r e s o f t w a r e c o d e s i g n 會議于1 9 9 3 年召開，它標(biāo)志著軟硬件協(xié)同設(shè)計(jì)方法學(xué)的研究正式展開，軟硬件 協(xié)同設(shè)計(jì)領(lǐng)域正式確立。與傳統(tǒng)的嵌入式系統(tǒng)設(shè)計(jì)方法不同，它把軟件設(shè)計(jì)和硬件設(shè)計(jì)工 作作為一個整體而不是把軟件和硬件分開。軟硬件協(xié)同設(shè)計(jì)強(qiáng)調(diào)軟件和硬件設(shè)計(jì)開發(fā)的并 行性和相互反饋，克服了傳統(tǒng)方法中把軟件和硬件分開設(shè)計(jì)所帶來的種種弊端，協(xié)調(diào)軟件 和硬件之間的制約關(guān)系，為硬件和軟件的協(xié)同描述、驗(yàn)證和綜合提供一種集成環(huán)境，達(dá)到 了系統(tǒng)高效工作的目的，是目前嵌入式系統(tǒng)設(shè)計(jì)中廣泛采用的一種方法。軟硬件協(xié)同設(shè)計(jì) 的設(shè)計(jì)流程如圖1 1 ： 2 南京郵i 乜人學(xué)碩 ：研究生學(xué)位論文第一章引言 圖1 1 軟硬件協(xié)同設(shè)計(jì)流程圖 軟硬件協(xié)同設(shè)計(jì)在軟件及硬件實(shí)現(xiàn)之前，就從統(tǒng)一描述的系統(tǒng)功能開始，將硬件完成 的功能作全盤考慮并均衡，在設(shè)計(jì)空間搜索技術(shù)的支持下，設(shè)計(jì)出不同的軟硬件體系結(jié)構(gòu) 并進(jìn)行評估，最終找到較理想的目標(biāo)系統(tǒng)軟硬件體系結(jié)構(gòu)，然后使用軟硬件劃分技術(shù)進(jìn)行 劃分，產(chǎn)生一個最佳的軟件、硬件劃分方案來滿足性能、成本、功耗、開發(fā)周期等一系列 設(shè)計(jì)約束限制。其核心問題是溝通軟件設(shè)計(jì)和硬件設(shè)計(jì)，避免系統(tǒng)設(shè)計(jì)中相互依賴、互相 影響的這兩部分過早獨(dú)立。在開發(fā)過程中強(qiáng)調(diào)硬件設(shè)計(jì)師和軟件設(shè)計(jì)師相互協(xié)作，并行地 設(shè)計(jì)系統(tǒng)的硬件和軟件。其設(shè)計(jì)過程充分體現(xiàn)了軟硬件的協(xié)同性，在功能劃分時就對現(xiàn)有 的軟硬件資源進(jìn)行充分的考慮，在軟硬件功能的設(shè)計(jì)和仿真驗(yàn)證過程中，軟件和硬件相互 支持，這就使得軟硬件功能模塊能夠在設(shè)計(jì)開發(fā)的早期互相結(jié)合協(xié)調(diào)，從而及早發(fā)現(xiàn)問題 解決問題【3 l ，避免了開發(fā)后期對系統(tǒng)的反復(fù)修改。通過軟硬件協(xié)同設(shè)計(jì)可以有效的縮短開 發(fā)周期，降低成本，實(shí)現(xiàn)軟硬件系統(tǒng)性能的優(yōu)化，更好的滿足設(shè)計(jì)要求。 軟硬件協(xié)同設(shè)計(jì)具有以下幾個特征 4 5 l ： ( 1 ) 在系統(tǒng)層設(shè)計(jì)中，使用統(tǒng)一的描述和工具對軟件和硬件進(jìn)行集成開發(fā)，并具有跨 越軟硬件界面進(jìn)行系統(tǒng)優(yōu)化的能力； ( 2 ) 提供軟硬件協(xié)同仿真的能力，可進(jìn)行全系統(tǒng)設(shè)計(jì)驗(yàn)證； ( 3 ) 支持多領(lǐng)域?qū)＜疫M(jìn)行合作開發(fā)與研究。 軟硬件協(xié)同設(shè)計(jì)從軟件和硬件設(shè)計(jì)工作緊密結(jié)合的需要中演化而來。目前軟硬件協(xié)同 3 南京郵電人學(xué)壩 j 研究生學(xué)位論文第一章引言 設(shè)計(jì)方法學(xué)研究還處于發(fā)展階段，許多技術(shù)仍未成熟和實(shí)用化，是目前一個十分活躍的研 究領(lǐng)域，加強(qiáng)對軟硬件協(xié)同設(shè)計(jì)的研究具有重大的現(xiàn)實(shí)意義，將能夠?yàn)榍度胧较到y(tǒng)設(shè)計(jì)帶 來革命性的變化。 軟硬件協(xié)同設(shè)計(jì)方法主要有下面幾個關(guān)鍵技術(shù)【6 - 7 】： ( 1 ) 系統(tǒng)描述 包括功能和非功能性的需求描述。用一種或多種系統(tǒng)級描述語言對所要設(shè)計(jì)的嵌入式 系統(tǒng)的功能和性能進(jìn)行全面描述，建立系統(tǒng)軟硬件模型。模型可以用非正式語言，或是自 然語言來手工完成，也可以用e d a 工具實(shí)現(xiàn)。手工描述不具體也不夠準(zhǔn)確，雖然簡單但卻 會使設(shè)計(jì)復(fù)雜化，在設(shè)計(jì)時一定要考慮充分，而用e d a 實(shí)現(xiàn)則會好一點(diǎn)。 ( 2 ) 軟硬件劃分 把系統(tǒng)劃分成為軟件模塊和硬件模塊。軟硬件劃分是協(xié)同設(shè)計(jì)方法中的一個關(guān)鍵組成 部分。隨著嵌入式系統(tǒng)的復(fù)雜程度和規(guī)模的不斷擴(kuò)大，手工的劃分方法已不能勝任，為此 人們提出了很多劃分算法如g a ，s a ，t s ，p a c e ，k e m i g h a n l i n ，m i b s ，雙向約束搜索 法，分級群聚法，基于簇的規(guī)劃法，整數(shù)規(guī)劃法等 8 , 9 1 0 , 1 1 1 ，以解決軟硬件劃分的問題。軟 硬件劃分的內(nèi)容在下面的章節(jié)中將具體展開敘述，它是開展動態(tài)可重構(gòu)系統(tǒng)軟硬件劃分研 究的重要基礎(chǔ)。 ( 3 ) 軟硬件綜合 包括硬件綜合，軟件代碼的生成和接口的生成。硬件綜合由硬件高層綜合、邏輯綜合、 版圖綜合等幾個不同的階段構(gòu)成?，F(xiàn)在，中低層的邏輯綜合和版圖綜合已較成熟，硬件高 層綜合雖然技術(shù)成熟度不如前兩者，但是目前也已經(jīng)有成果投入使用。軟件綜合包括軟件 高級綜合、編譯、匯編等幾個階段即代碼的生成。由于傳統(tǒng)的軟件綜合技術(shù)尚不成熟，所 以嵌入式系統(tǒng)的軟件綜合技術(shù)還處于發(fā)展階段。但是嵌入式軟件綜合較之傳統(tǒng)的軟件綜合 有更多的限制，可以引入更多領(lǐng)域的知識，因此軟件綜合技術(shù)有著廣大的發(fā)展前景。接口 綜合包括硬件構(gòu)件添加鎖存器、f i f o 、地址譯碼器、為軟件構(gòu)件添加輸入輸出、同步操 作等。 ( 4 ) 軟硬件協(xié)同仿真和驗(yàn)證 對系統(tǒng)的功能和限制進(jìn)行協(xié)同仿真和驗(yàn)證。仿真和驗(yàn)證是檢驗(yàn)系統(tǒng)設(shè)計(jì)正確性的過程， 用來對設(shè)計(jì)結(jié)果的正確性和優(yōu)化程度進(jìn)行評估，以達(dá)到避免在系統(tǒng)實(shí)現(xiàn)過程中發(fā)現(xiàn)問題再 進(jìn)行反復(fù)修改的目的。軟硬件協(xié)同仿真可以分為系統(tǒng)級協(xié)同仿真、行為級協(xié)同仿真、 r t l ( r e g i s t e rt r a n s f e rl e v e l ) 級協(xié)同仿真和門級協(xié)同仿真。系統(tǒng)級協(xié)同仿真用于驗(yàn)證算法的 正確性和評估系統(tǒng)的整體性能，它往往側(cè)重于對總線操作進(jìn)行模擬。門級協(xié)同仿真完整的 4 南京郵i 乜人學(xué)頤1 ：研究生學(xué)位論文第一章引言 模擬軟硬件實(shí)際運(yùn)行過程，但是仿真的速度會隨著設(shè)計(jì)規(guī)模的增大急劇下降。一般來說， 抽象層次越高，反映的細(xì)節(jié)越少，模擬的速度越快。軟硬件協(xié)同仿真通常是直接在模擬的 硬件上運(yùn)行軟件，即微處理器通常與別的硬件在同層次上被模擬。軟硬件協(xié)同驗(yàn)證技術(shù) 把軟件和硬件的模擬聯(lián)系起來協(xié)同進(jìn)行，軟件的集成與調(diào)試在設(shè)計(jì)循環(huán)初期通過一個虛擬 樣機(jī)進(jìn)行，不需要等待硬件完成。應(yīng)該注意的是，在系統(tǒng)仿真驗(yàn)證過程中，雖然模擬可以 改進(jìn)和加速設(shè)計(jì)工作，但是軟硬件工作的環(huán)境很難和實(shí)際目標(biāo)系統(tǒng)完全一樣，軟硬件交互 的方式和效果也有很大不同，因此仿真驗(yàn)證的有效性是有限的。 1 1 。3 軟硬件劃分 在整個軟硬件協(xié)同設(shè)計(jì)流程中，軟硬件劃分算法是其中的一個關(guān)鍵技術(shù)。其主要任務(wù) 是在滿足各項(xiàng)設(shè)計(jì)約束指標(biāo)的條件下，把系統(tǒng)功能劃分到目標(biāo)結(jié)構(gòu)中的軟件和硬件部分 上，是確定系統(tǒng)的哪部分功能用軟件實(shí)現(xiàn)，哪部分功能用硬件實(shí)現(xiàn)的過程，己成為軟硬件 協(xié)同設(shè)計(jì)的重要研究內(nèi)容之一【1 2 l 。統(tǒng)計(jì)數(shù)據(jù)表明，包括軟硬件劃分在內(nèi)的最初1 0 的系統(tǒng) 級設(shè)計(jì)過程對于最終的設(shè)計(jì)質(zhì)量和成本有8 0 的影響，因此系統(tǒng)設(shè)計(jì)對軟硬件劃分的質(zhì)量 要求十分嚴(yán)格。 軟硬件劃分主要包括以下三個方面，這三個方面既相互獨(dú)立，又相互依賴： ( 1 ) 處理單元的確定 確定要用到的軟件和硬件處理單元的類型和數(shù)量，如c p u 類型和f p g a 的型號等，它也 是設(shè)計(jì)約束之一： ( 2 ) 任務(wù)分配 把系統(tǒng)中的任務(wù)分配到目標(biāo)結(jié)構(gòu)中的處理單元和資源上執(zhí)行，并滿足系統(tǒng)在性能和成 本方面的約束。這是軟硬件劃分中最關(guān)鍵的一步，有了劃分結(jié)果后才能對劃分方案進(jìn)行調(diào) 度和評估。 ( 3 ) 任務(wù)調(diào)度 確定指派在各個處理單元上任務(wù)的執(zhí)行順序和開始時間，以滿足系統(tǒng)任務(wù)之間的控制 和數(shù)據(jù)依賴關(guān)系，并優(yōu)化系統(tǒng)性能。任務(wù)調(diào)度不僅是評估軟硬件劃分方案優(yōu)劣的必要步驟， 也是進(jìn)一步提升系統(tǒng)性能的有效手段。 軟件實(shí)現(xiàn)的特點(diǎn)是靈活、成本低；而硬件實(shí)現(xiàn)的特點(diǎn)速度快，但是成本高。在滿足系 統(tǒng)設(shè)計(jì)要求的同時，如何兼顧系統(tǒng)的性能和成本，達(dá)到性能和成本的最佳結(jié)合，是軟硬件 劃分要解決的問題。劃分結(jié)果的好壞直接影響著系統(tǒng)的性能。從理論上來說，每一個應(yīng)用 南京郵 u 人學(xué)頌1 ：彬f 究生學(xué)位論義第一章引言 系統(tǒng)，都存在一個適合于該系統(tǒng)的硬件和軟件功能的最佳組合。應(yīng)該從應(yīng)用系統(tǒng)的需求出 發(fā)，依據(jù)定的指導(dǎo)原則對硬件和軟件的功能進(jìn)行分析和合理的劃分，從而使系統(tǒng)的整體 性能、運(yùn)行時間、功耗、存儲容量等達(dá)到最佳狀態(tài)。 傳統(tǒng)的軟硬件劃分是手工進(jìn)行的，隨著嵌入式系統(tǒng)結(jié)構(gòu)變的更加復(fù)雜，系統(tǒng)規(guī)模的不 斷擴(kuò)大，開發(fā)時問要求更加緊迫，傳統(tǒng)的方法已不再可行，單憑設(shè)計(jì)人員的經(jīng)驗(yàn)進(jìn)行劃分 很難保證滿足設(shè)計(jì)約束指標(biāo)，并得到最優(yōu)或近似最優(yōu)的結(jié)果。這種情況下，對系統(tǒng)級自動 化設(shè)計(jì)工具的需求同益緊迫，近年來自動劃分算法得到了長足的發(fā)展。軟硬件劃分問題的 求解，就是在一定的系統(tǒng)模型基礎(chǔ)上，對于解空間進(jìn)行搜索的過程，為系統(tǒng)的每個功能模 塊( 節(jié)點(diǎn)) 選擇一種合適的實(shí)現(xiàn)方式( 軟件或硬件) ，在最大化系統(tǒng)性能的條件下，使系統(tǒng)成 本達(dá)到最小。一個好的劃分算法可以在較快的時間內(nèi)得出較優(yōu)的劃分方案。一個優(yōu)秀的劃 分方案必須考慮系統(tǒng)的整體性能、運(yùn)行時間、功耗、存儲容量等，屬于多約束條件下的優(yōu) 化組合問題。 1 1 4 可重構(gòu)計(jì)算的發(fā)展 可重構(gòu)是在軟件的控制下，利用可重用的資源重構(gòu)或重組成另一個計(jì)算平臺以適應(yīng)不 同的應(yīng)用需求?？芍貥?gòu)計(jì)算系統(tǒng)提供了一種介于通用計(jì)算機(jī)和專用計(jì)算系統(tǒng)之間的計(jì)算手 段。通用計(jì)算機(jī)是面向通用應(yīng)用領(lǐng)域進(jìn)行設(shè)計(jì)的，其設(shè)計(jì)目標(biāo)主要是能夠靈活地處理不同 的計(jì)算任務(wù)，這使得通用計(jì)算機(jī)具有很大的靈活性和應(yīng)用范圍，但對某些特殊的應(yīng)用領(lǐng)域 卻難以取得高性能。專用集成電路是針對某種特殊應(yīng)用設(shè)計(jì)的計(jì)算系統(tǒng)，對于特定的計(jì)算 任務(wù)，專用計(jì)算系統(tǒng)表現(xiàn)出極高的性能，但無法處理特定計(jì)算任務(wù)之外的其它任務(wù)。通用 計(jì)算機(jī)和專用計(jì)算系統(tǒng)代表了兩種極端的計(jì)算手段，通用計(jì)算機(jī)具有最大的靈活性和低性 能，專用計(jì)算系統(tǒng)具有最高的性能和最差的靈活性。而現(xiàn)在有許多應(yīng)用需求既要求較高的 性能，又需要一定的靈活性。這些應(yīng)用需求導(dǎo)致了可重構(gòu)計(jì)算的產(chǎn)生。可重構(gòu)計(jì)算的主要 目標(biāo)是希望通過硬件可編程，來適應(yīng)計(jì)算任務(wù)的需求，以期達(dá)到最佳性能。可重構(gòu)計(jì)算的 概念最早可以追溯到上世紀(jì)6 0 年代?？芍貥?gòu)計(jì)算大致經(jīng)過了三個發(fā)展時期【j ： ( 1 ) 早期的可編程模擬計(jì)算機(jī)，大量運(yùn)算放大器、比較器、乘法器和無源元件通過一 塊塊插線板和接插線連接起來，使用者可以實(shí)現(xiàn)一種網(wǎng)絡(luò)，該網(wǎng)絡(luò)的所有節(jié)點(diǎn)電壓遵從一 組微分方程。這樣模擬計(jì)算機(jī)就變成了微分方程求解器，并具有可重構(gòu)性。這是可重構(gòu)計(jì) 算系統(tǒng)的雛形。 ( 2 ) 可重構(gòu)計(jì)算真正向靈活流暢邁出的第步是嵌入式數(shù)字計(jì)算機(jī)的出現(xiàn)。系統(tǒng)特性 由r a m 中的軟件來定義，實(shí)現(xiàn)起來非常簡單方便。在安裝時甚至是工作時，可以通過改變 6 雨泉郵電人掌壩i j 研究生學(xué)位論義第一牽0 i 言 系統(tǒng)的操作來響應(yīng)數(shù)據(jù)改變，此過程實(shí)際上只是加載不同應(yīng)用程序的過程。 ( 3 ) 基于靜態(tài)存貯器( s r a m ) 的大規(guī)?，F(xiàn)場可編程門陣列( f p g a ) 出現(xiàn)以后，才真正對 可重構(gòu)計(jì)算展開深入研究。研究人員發(fā)現(xiàn)通過對這種器件所擁有的邏輯單元與互連結(jié)構(gòu)進(jìn) 行改變，可以創(chuàng)建出適合芯片要求的任意邏輯網(wǎng)表，很快選定f p g a 實(shí)驗(yàn)時間配置的可重 構(gòu)性，創(chuàng)建用于特殊算法的硬線連接數(shù)字網(wǎng)絡(luò)。 可重構(gòu)的目的是為了解決硬件結(jié)構(gòu)與應(yīng)用的不匹配，可重構(gòu)的基礎(chǔ)是可重用資源?？?重構(gòu)計(jì)算具有以下一些優(yōu)點(diǎn)1 1 3 , 3 0 ! ： ( 1 ) 可重構(gòu)計(jì)算能夠有效的提高系統(tǒng)性能?？芍貥?gòu)系統(tǒng)本質(zhì)上是用硬件來實(shí)現(xiàn)系統(tǒng)功 能，因此可以顯著提高系統(tǒng)運(yùn)行速度； ( 2 ) 可重構(gòu)計(jì)算技術(shù)能夠通過動態(tài)改變可重構(gòu)硬件的配置來靈活滿足多種功能需求。 可重構(gòu)的特性使得同一可重構(gòu)邏輯器件能夠滿足不同的設(shè)計(jì)需求，這一點(diǎn)是傳統(tǒng)的專用集 成電路計(jì)算模式不能夠達(dá)到的。 ( 3 ) 可重構(gòu)計(jì)算可以有效的加速產(chǎn)品開發(fā)?？芍貥?gòu)器件廠商會配合不同的可重構(gòu)邏輯 器件提供相應(yīng)的開發(fā)工具和流程，同時還會提供大量參考設(shè)計(jì)和i p 核以減少設(shè)計(jì)者的重復(fù) 勞動并提高設(shè)計(jì)的可靠性。 ( 4 ) 使用可重構(gòu)計(jì)算技術(shù)能夠極大的降低系統(tǒng)成本。在開發(fā)中利用可重構(gòu)硬件比使用 專用硬件電路更能節(jié)省成本。另外，通過在運(yùn)行時使用時域劃分的概念復(fù)用可重構(gòu)硬件可 以進(jìn)一步降低系統(tǒng)的成本。 可重構(gòu)系統(tǒng)就是指用可重構(gòu)的硬件實(shí)現(xiàn)可重構(gòu)計(jì)算的系統(tǒng)。由于可重構(gòu)系統(tǒng)的這些優(yōu) 點(diǎn)，目前可重構(gòu)技術(shù)被廣泛的應(yīng)用于高速數(shù)字濾波器、硬件演化計(jì)算、多媒體計(jì)算、圖象 處理、數(shù)據(jù)加密、容錯系統(tǒng)等領(lǐng)域。動態(tài)可重構(gòu)系統(tǒng)已經(jīng)被廣泛應(yīng)用于實(shí)際生產(chǎn)和生活中， 如何提高動態(tài)可重構(gòu)系統(tǒng)性能已經(jīng)成為了目前研究的一大熱點(diǎn)。現(xiàn)在專門用于動態(tài)可重構(gòu) 系統(tǒng)任務(wù)劃分的方法還不多，軟硬件任務(wù)的劃分問題又是影響整個系統(tǒng)性能的關(guān)鍵。所以 改進(jìn)優(yōu)化任務(wù)劃分的算法不僅可以使動態(tài)可重構(gòu)技術(shù)不斷發(fā)展和完善，更能使動態(tài)可重構(gòu) 計(jì)算系統(tǒng)的應(yīng)用越來越廣泛。 1 1 5f p g a 技術(shù)的發(fā)展 隨著微電子技術(shù)的發(fā)展，系統(tǒng)設(shè)計(jì)師希望專用集成電路( a s i c ) 的設(shè)計(jì)周期盡可能短， 最好是在實(shí)驗(yàn)室里就能設(shè)計(jì)出合適的a s i c 芯片，并且立即投入實(shí)際應(yīng)用之中，因而出現(xiàn)了 現(xiàn)場可編程邏輯器件( f p l d ) ，其中應(yīng)用最廣泛的當(dāng)屬現(xiàn)場可編程門陣列( f p g a ) 和復(fù)雜可 南京郵電大學(xué)碩士研究生學(xué)位論文第一章引言 編程邏輯器件( c p l d ) ?，F(xiàn)場可編程門陣列( f p g a ) 是在p a l 、g a l 、e p l d 等可編程器件的 基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物，它是作為a s i c 領(lǐng)域中的一種半定制電路而出現(xiàn)的，既解決了定 制電路的不足，又克服了原有可編程器件門電路數(shù)有限的缺點(diǎn)。 f p g a i 為部包括可配置邏輯模塊( c l b ，c o n f i g u r a b l el o g i cb l o c k ) 、輸入輸出模塊( i o b ， i n p u to u t p u tb l o c k ) 和內(nèi)部連線( i n t e r c o n n e c t ) 三個部分1 1 4 , 1 5 1 。當(dāng)今的f p g a 支持很多i o 標(biāo)準(zhǔn)， 實(shí)現(xiàn)了i o 支持的靈活性。可配置邏輯塊是f p g a 內(nèi)的基本邏輯單元。實(shí)際數(shù)量和特性會依 器件的不同而不同，但是每個c l b 都包含一個由4 或6 個輸入、一些選型電路( 多路復(fù)用器等) 和觸發(fā)器組成的可配置開關(guān)矩陣。開關(guān)矩陣是高度靈活的，可以進(jìn)行配置以便處理組合邏 輯、移位寄存器或r a m 。c l b 提供了邏輯性能，內(nèi)部連線在c l b 和i o 之間發(fā)送信號。目 前有幾種布線方法，從專門實(shí)現(xiàn)c l b 互連到快速水平和垂直長線，再到實(shí)現(xiàn)時鐘與其它全 局信號的低歪斜發(fā)送的器件。隨著技術(shù)的發(fā)展，目前已經(jīng)可以使用設(shè)計(jì)軟件自動進(jìn)行內(nèi)部 連線，這樣就極大地降低了設(shè)計(jì)復(fù)雜度。在系統(tǒng)存儲方面，大多數(shù)f p g a 均提供嵌入式b l o c k r a m 存儲器，這可以在設(shè)計(jì)中實(shí)現(xiàn)片上存儲器。對于高密度的器件，時鐘分配是一個大問 題。在系統(tǒng)級設(shè)計(jì)中，時鐘脈沖相位差過大，就會限制系統(tǒng)的性能，在每個時鐘周期內(nèi)損 失若干納秒。新一代的f p g a 中有獨(dú)立的延時鎖相環(huán)，允許內(nèi)、外時鐘進(jìn)行同步來解決這 個問題和消除系統(tǒng)時鐘脈沖相位差。 f p g a 的具體結(jié)構(gòu)為c l b 排成陣列位于芯片內(nèi)部，在芯片四周是可編程的i o ，連接功 能塊和i o 的可編程互連線均勻分布于陣列的行與列之間。按照編程的方式和功能塊的結(jié)構(gòu) 可分為s r a m 查找表型和反熔絲多路開關(guān)型兩類。前者在掉電后配置丟失，但可以實(shí)現(xiàn)系統(tǒng) 內(nèi)再編程、系統(tǒng)運(yùn)行器件再編程和網(wǎng)絡(luò)遠(yuǎn)程配置等特性，后者一次編程后不可再編程，掉 電后配置不丟失。 f p g a 具有編程方式簡便、可靠性高、功能強(qiáng)大、開發(fā)便捷和開發(fā)周期短的優(yōu)點(diǎn)。它的 迅速發(fā)展為可重構(gòu)計(jì)算技術(shù)的發(fā)展提供了必要的硬件支持。作為實(shí)現(xiàn)可重構(gòu)計(jì)算技術(shù)的關(guān) 鍵器件，f p g a 在過去很長一段時間內(nèi)存在計(jì)算密度低、配置時間長、封裝復(fù)雜、高密度 芯片的靜態(tài)功耗和尺寸大等問題，在性能上不及a s i c ，靈活性不如處理器。如今，f p g a 經(jīng)過十幾年的發(fā)展，現(xiàn)場可編輯邏輯器件從最初的1 2 0 0 個可用門，發(fā)展到現(xiàn)在數(shù)百萬可用 門，并能嵌入處理器軟核、乘法器以及大量的片上存儲器，i o 管腳數(shù)也得到很大程度的增 加。性能和靈活性的不斷提升與價格和功耗的不斷降低，已經(jīng)使f p g a 能夠滿足可重構(gòu)計(jì) 算對硬件的要求，這也是最近幾年可重構(gòu)計(jì)算得到長足發(fā)展的一個重要原因。 8 南京郵電人學(xué)碩l ：研究生學(xué)位論文第一章引言 1 2 論文的組織結(jié)構(gòu) 論文對可重構(gòu)系統(tǒng)以及軟硬件劃分方法進(jìn)行了研究，并在此基礎(chǔ)上提出了一種針對可 重構(gòu)系統(tǒng)的軟硬件劃分算法，并進(jìn)行了仿真實(shí)驗(yàn)與比較。論文中的各章節(jié)安排如下： 第一章：引言。介紹了嵌入式系統(tǒng)的特點(diǎn)，分析了軟硬件協(xié)同設(shè)計(jì)技術(shù)目前的發(fā)展?fàn)?況，軟硬件劃分的基本概念和要求等，最后介紹了可重構(gòu)系統(tǒng)的發(fā)展?fàn)顩r以及論文的組織 結(jié)構(gòu)。 第二章：軟硬件劃分的相關(guān)技術(shù)。介紹軟硬件劃分中的一些基本概念，闡述了劃分過 程中的一些問題。 第三章：可重構(gòu)嵌入式系統(tǒng)的研究。介紹可重構(gòu)系統(tǒng)的關(guān)鍵技術(shù)，分析了影響系統(tǒng)性 能的各個問題，以及應(yīng)該在軟硬件劃分時需要注意的因素等。 第四章：基于權(quán)重動態(tài)可變免疫算法的軟硬件劃分算法和動態(tài)可重構(gòu)系統(tǒng)調(diào)度。提出 了針對動態(tài)可重構(gòu)系統(tǒng)的軟硬件劃分算法和與評估劃分結(jié)果相結(jié)合的任務(wù)調(diào)度方法，并用 實(shí)驗(yàn)驗(yàn)證了算法的優(yōu)越性。 第五章：總結(jié)與展望。主要對全文進(jìn)行了總結(jié)，并提出了未來需要進(jìn)一步深入研究的 工作。 9 南京郵電人學(xué)頌17 研究生學(xué)位論文 第二章嵌入式系統(tǒng)軟硬件劃分技術(shù) 第二章嵌入式系統(tǒng)軟硬件劃分技術(shù) 2 1 軟硬件劃分的概念、意義和基本原則 系統(tǒng)劃分主要有兩種方法：結(jié)構(gòu)劃分和功能劃分1 1 6 】。結(jié)構(gòu)劃分先從結(jié)構(gòu)上來實(shí)現(xiàn)目標(biāo) 系統(tǒng)，然后再對其進(jìn)行劃分，只能應(yīng)用于硬件設(shè)計(jì)。功能劃分先將系統(tǒng)功能分為若干個不 可再分的塊，再把這些功能塊劃分到系統(tǒng)組件上，通過軟件或硬件來實(shí)現(xiàn)每個組件的功能。 隨著系統(tǒng)組件的數(shù)量越來越多，結(jié)構(gòu)劃分已不能適應(yīng)實(shí)際的要求，因此功能劃分更適合于 用來劃分復(fù)雜的目標(biāo)系統(tǒng)，本文所指的軟硬件劃分即為軟硬件功能的劃分。 嵌入式系統(tǒng)中的功能任務(wù)模塊大多都有兩種基本的實(shí)現(xiàn)方法：軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)。 一般來說，硬件比軟件能提供更好的性能，而軟件更容易開發(fā)和修改，靈活性更強(qiáng)、成本 比硬件更低。軟硬件任務(wù)劃分是將系統(tǒng)任務(wù)描述分解成為與實(shí)現(xiàn)有關(guān)的軟件部分和硬件部 分，確定系統(tǒng)的軟硬件界面，并分配到相應(yīng)的軟件和硬件上，決定如何在軟硬件各部件之 間優(yōu)化系統(tǒng)配置的過程。 圖2 1 軟硬件劃分流程圖 軟硬件劃分的基本流程如圖2 1 所示。嵌入式系統(tǒng)的硬件和軟件之間有著相互聯(lián)系、 1 0 南京郵電人學(xué)壩l j 佃f 究生學(xué)位論文第二章嵌入式系統(tǒng)軟硬件劃分技術(shù) 相互影響和制約的密切關(guān)系。雖然很多時候，計(jì)算機(jī)中的大部分功能既可以用硬件實(shí)現(xiàn)， 也可以用軟件實(shí)現(xiàn)，軟硬件之間的界限并不十分清晰，但是它們之間的性能差異很大。因 而有的功能適合用硬件實(shí)現(xiàn)，另外一些則適合用軟件實(shí)現(xiàn)。這就需要對目標(biāo)系統(tǒng)進(jìn)行分析， 綜合考慮各種功能性和非功能性約束，找到目標(biāo)系統(tǒng)軟硬件設(shè)計(jì)最佳平衡點(diǎn)。 在多數(shù)情況下，采用硬件特別是大規(guī)模集成電路，往往可以簡化設(shè)計(jì)工作，通過操作 的并行性和硬件本身較快的速度使系統(tǒng)性能得到顯著提高，但使用硬件的成本較高，缺乏 靈活性，而且硬件使用得越多開發(fā)風(fēng)險越大，這是因?yàn)樾薷挠布^之修改軟件的成本和時 間都要大得多。用軟件來實(shí)現(xiàn)部分硬件功能的優(yōu)點(diǎn)是可以降低系統(tǒng)成本，減小體積和功耗， 提高系統(tǒng)靈活性等，但缺點(diǎn)是運(yùn)行速度較低，另外復(fù)雜的軟件其開發(fā)和維護(hù)成本也相對較 高。所以在嵌入式系統(tǒng)的設(shè)計(jì)中必須從系統(tǒng)的各項(xiàng)約束出發(fā)來對軟硬件功能進(jìn)行劃分。基 本原則是：對實(shí)時性有要求且成本不敏感的系統(tǒng)盡量用硬件實(shí)現(xiàn)；關(guān)注成本且產(chǎn)量較大的 系統(tǒng)盡量通過軟件實(shí)現(xiàn)；在軟件實(shí)現(xiàn)無法滿足系統(tǒng)性能要求時采用硬件實(shí)現(xiàn)；處理器和專 用硬件或可重構(gòu)硬件并用，可以同時提高處理速度和系統(tǒng)的靈活性。 2 2 軟硬件劃分的步驟和方法 軟硬件劃分是嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計(jì)的最重要的問題之一，一般有以下六個步驟 【1 6 】，劃分結(jié)果的好壞將直接影響著后續(xù)的開發(fā)進(jìn)程和整個系統(tǒng)的成本及性能，是協(xié)同設(shè)計(jì) 中必須解決好的一個重要問題。 南京郵r u 人學(xué)頌i 二研究生學(xué)位論文第一二章嵌入式系統(tǒng)軟硬件劃分技術(shù) 圖2 2 軟硬件劃分步驟 ( 1 ) 根據(jù)系統(tǒng)需求，建立一個可以用來表達(dá)整個系統(tǒng)的模型。該模型從用戶的角度對 系統(tǒng)進(jìn)行描述，包括系統(tǒng)要實(shí)現(xiàn)的功能以及性能、功耗、成本等非功能性的指標(biāo)，是系統(tǒng) 整體的功能分配圖，在這一步還沒有確定系統(tǒng)功能的哪些部分由軟件實(shí)現(xiàn)，哪些由硬件實(shí) 現(xiàn)。 ( 2 ) 根據(jù)系統(tǒng)模型，確定目標(biāo)系統(tǒng)架構(gòu)，包括軟硬件子系統(tǒng)的劃分和通信機(jī)制，定義 系統(tǒng)實(shí)現(xiàn)的目標(biāo)平臺的軟硬件映射，如所使用的c p u 、內(nèi)存容量、總線、操作系統(tǒng)等，得 到初步的軟硬件劃分結(jié)果，但這還不是最終的輸出。 ( 3 ) 根據(jù)系統(tǒng)需求，明確系統(tǒng)設(shè)計(jì)所必須滿足的各項(xiàng)約束指標(biāo)，確定對系統(tǒng)設(shè)計(jì)進(jìn)行 評估的辦法和準(zhǔn)則，為評價第二步得到的初步劃分結(jié)果做準(zhǔn)備。 ( 4 ) 根據(jù)系統(tǒng)各項(xiàng)約束和評估準(zhǔn)則選擇合適的目標(biāo)函數(shù)。目標(biāo)函數(shù)的選擇對劃分結(jié)果 的評價具有極大的影響，因此在選擇時必須綜合各種因素進(jìn)行考慮。 ( 5 ) 迭代求解，確定是否是最優(yōu)或次優(yōu)的劃分方案。在這個過程中不斷改進(jìn)系統(tǒng)的軟 硬件劃分，直到滿足終止條件。也可以在過程中改變系統(tǒng)的評估標(biāo)準(zhǔn)、約束指標(biāo)和目標(biāo)函 數(shù)，但一定要滿足目標(biāo)系統(tǒng)的需求。 ( 6 ) 根據(jù)輸出的軟硬件劃分方案進(jìn)行設(shè)計(jì)并實(shí)現(xiàn)。 按軟硬件功能劃分的方法有很多種，如一種常用的4 層分割法。它按每項(xiàng)功能把一個系 1 2 塑室墮! 墊盔蘭竺! 型! 莖生蘭垡笙蘭墨三至壁全壟墨竺鏊堡竺型坌墊壟 統(tǒng)分成4 個等級，從上到下依次是功能程序?qū)?、流程控制層、基本塊層和指令層。對于一 個結(jié)構(gòu)和功能比較簡單的系統(tǒng)來說，軟硬件劃分的方案數(shù)量較少，可以根據(jù)設(shè)計(jì)者的經(jīng)驗(yàn)， 手工把系統(tǒng)功能劃分為軟件實(shí)現(xiàn)或硬件實(shí)現(xiàn)。但是隨著嵌入式系統(tǒng)規(guī)模的增大，軟硬件模 塊的數(shù)量也隨之增多，軟硬件劃分問題的求解規(guī)模也不斷擴(kuò)大，這時再僅僅依靠設(shè)計(jì)者的 經(jīng)驗(yàn)已經(jīng)很難得到一個合理的軟硬件劃分方案。因此，研究自動的軟硬件劃分方法，在嵌 入式軟硬件協(xié)同設(shè)計(jì)中的重要性日益突出。r o l f e m s d j 等人提出了面向軟件的劃分方法， 主要思想是把系統(tǒng)所有可以用軟件實(shí)現(xiàn)的功能都以軟件方式實(shí)現(xiàn)，然后再逐步把操作從軟 件轉(zhuǎn)移到硬件實(shí)現(xiàn)，直到滿足目標(biāo)系統(tǒng)要求。g u p 泖d em i c h e l i t l 8 】在1 9 9 3 年提出了面向硬 件的劃分方法，思想是把系統(tǒng)的功能盡量都以硬件的方式實(shí)現(xiàn)，然后再逐步把操作從軟件 轉(zhuǎn)移到硬件實(shí)現(xiàn)。f r a n kv a h i d t l 9 l 等人1 9 9 6 年提出了一種適于對軟硬件功能部件進(jìn)行進(jìn)程級 描述的劃分模型s l i f ( s p e c i f i c a t i o nl e v e li n t e r m e d i a t ef o r m a t ) 。 i r a c h e nl i n 2 0 】等人1 9 9 8 年提 出了基于緩沖區(qū)大小的劃分方法。他們的劃分算法考慮了以往算法所忽略的兩個方面：數(shù) 據(jù)依賴和系統(tǒng)延遲。x h u l 2 1 1 在1 9 9 9 年提出了人工干預(yù)下的自動劃分方法。這種劃分方法 的核心是設(shè)計(jì)空間的可視化( 不是枚舉所有可能的設(shè)計(jì)配置) 。這種設(shè)計(jì)空間的表示方法為 設(shè)計(jì)者提供了一個很直觀的形式來標(biāo)明那些劃分更好。j o r gh e n k e l t 2 2 j 于1 9 9 9 年提出一種面 向低功耗的軟硬件劃分方法。m m e e r w e i n t 2 3 i 于2 0 0 0 年提出基于i p 重用的軟硬件劃分方法。 這些劃分方法在其使用環(huán)境和目標(biāo)系統(tǒng)應(yīng)用領(lǐng)域內(nèi)都取得了較好的試驗(yàn)結(jié)果，但它們 都不是通用的自動化軟硬件任務(wù)劃分方法，只適用于某個具體領(lǐng)域和環(huán)境。因此，在目標(biāo) 系統(tǒng)做軟硬件劃分時，還應(yīng)該根據(jù)系統(tǒng)的具體情況選擇劃分算法。本文就是在對動態(tài)可重 構(gòu)系統(tǒng)功能實(shí)現(xiàn)特點(diǎn)和應(yīng)用環(huán)境研究的基礎(chǔ)上，改進(jìn)并優(yōu)化免疫算法，并提出一種調(diào)度策 略以更好更客觀的評估算法的優(yōu)劣，最后找到一種能夠有效提高動態(tài)可重構(gòu)系統(tǒng)性能的任 務(wù)劃分方法，可以很好地應(yīng)用于嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計(jì)中。 2 3 軟硬件劃分中的問題 為了便于理解和對比各種不同的劃分技術(shù)，可以將整個劃分問題分為【2 4 l ：系統(tǒng)描述抽 象級別、粒度、系統(tǒng)組件的分配、度量和評估、目標(biāo)和接近函數(shù)、劃分算法、輸出，以及 控制流程和設(shè)計(jì)者的參與等八個基本問題。 2 3 1 系統(tǒng)描述 軟硬件劃分是在系統(tǒng)描述基礎(chǔ)上進(jìn)行的，系統(tǒng)描述是軟硬件劃分六個步驟中的第一 1 3 甬京m 6 電人掌壩 j 矽 生學(xué)位論文 第一二犖嵌入式系統(tǒng)軟硬件劃分技術(shù) 步。在系統(tǒng)功能軟硬件劃分之前，嵌入式系統(tǒng)的功能描述是一種有利于劃分的統(tǒng)一的中間 表示格式。利用系統(tǒng)描述，軟硬件功能的折衷及系統(tǒng)功能在軟件與硬件之間的轉(zhuǎn)換可以很 方便地進(jìn)行。系統(tǒng)描述的最終結(jié)果是生成軟硬件劃分所需要的節(jié)點(diǎn)相關(guān)信息，包括元件庫、 節(jié)點(diǎn)映射和設(shè)計(jì)約束等。各種嵌入式系統(tǒng)的結(jié)構(gòu)和功能干差萬別，要抽象出一個通用的系 統(tǒng)描述模型，是非常困難也是不可能的。 在進(jìn)行系統(tǒng)描述時，首先應(yīng)給出系統(tǒng)所要實(shí)現(xiàn)功能的規(guī)格描述。建立的系統(tǒng)功能描述 應(yīng)該與該功能的實(shí)現(xiàn)方式無關(guān)，即不能偏向于特定的結(jié)構(gòu)，也不能傾向于用軟件或是硬件 來實(shí)現(xiàn)。同時這種系統(tǒng)功能概念級的描述應(yīng)是可執(zhí)行的，以便對系統(tǒng)功能進(jìn)行模擬驗(yàn)證。 此描述根據(jù)系統(tǒng)需求和系統(tǒng)定義描述出系統(tǒng)要實(shí)現(xiàn)的功能以及性能、功耗、芯片面積等非 功能性的指標(biāo)。系統(tǒng)描述把系統(tǒng)功能分解成各個子功能，描述出實(shí)現(xiàn)這些功能的算法，然 后建立起可執(zhí)行的系統(tǒng)功能模型。通過系統(tǒng)功能模型的仿真，分析完善系統(tǒng)的功能設(shè)計(jì)。 在對實(shí)際系統(tǒng)進(jìn)行描述的時候，沒有必要也不可能把所有的有關(guān)因素都考慮進(jìn)去，應(yīng)該根 據(jù)問題的特征選擇目標(biāo)系統(tǒng)各項(xiàng)主要指標(biāo)，力求在滿足一定準(zhǔn)確度的前提下，盡可能采用 簡潔的模型描述系統(tǒng)。 各種劃分技術(shù)一般通過概念模型的抽象級別來定義劃分的輸入。比較粗略的可以將抽 象級別定義為系統(tǒng)描述中低復(fù)雜度結(jié)構(gòu)對象數(shù)量的度量，抽象級別越低，說明低復(fù)雜度結(jié) 構(gòu)對象越多。多種抽象級別的描述，由高到低大致有如下幾種：任務(wù)數(shù)據(jù)流圖、任務(wù)級、 算法級數(shù)據(jù)流圖、帶數(shù)據(jù)通道的有限狀態(tài)機(jī)、寄存器傳輸級、結(jié)構(gòu)級等。不同的抽象級別 代表了設(shè)計(jì)中不同的中間實(shí)現(xiàn)體。由于通常的設(shè)計(jì)都從較高的抽象級別開始，再往里加入 結(jié)構(gòu)細(xì)節(jié)信息形成較低的抽象層次。因此，劃分輸入的抽象級別的不同也能代表劃分之間 已完成設(shè)計(jì)的多少。 目前常用于描述系統(tǒng)的模型有控制數(shù)據(jù)流圖( c d f g ) ，v h d l ，無環(huán)數(shù)據(jù)流圖( a c y c l i c d f g ) ，帶數(shù)據(jù)通道的有限狀態(tài)機(jī)( d f s m ) 等。其中c d f g 是一種異構(gòu)模型，結(jié)合了流程圖 c f g 和數(shù)據(jù)流圖d f g 兩種模型的優(yōu)點(diǎn)，可以在一個表示中既可以顯式表示數(shù)據(jù)相關(guān)性，又 可以顯式表示系統(tǒng)的控制順序。由于嵌入式系統(tǒng)的實(shí)現(xiàn)流程是一個數(shù)據(jù)流的輸入輸出過 程，整個系統(tǒng)可以分為一定粒度大小的多個任務(wù)來完成。系統(tǒng)的控制數(shù)據(jù)流圖( c d f g ) 是 一個有向無環(huán)圖，它能夠很好地表示這一過程，所以本文就以這種模型作系統(tǒng)描述。 2 3 2 劃分粒度 劃分的粒度也是軟硬件劃分中的一個重要問題。所謂粒度，就是每個對象中所含描述 1 4 墮室些皇盔蘭堡圭竺窒竺蘭垡堡苧差三雯璧全莖墨塹鏊堡堡型坌墊查 規(guī)模的度量。粗度量意味著每個對象中含有大量描述，而細(xì)粒度則表示對象中僅含有少量 描述。劃分的粒度主要有任務(wù)( t a s k ) ，操作( o p e r a t i o n ) ，實(shí)體( e n t i t y ) ，基本調(diào)度單元( b a s i c s c h e d u l i n gb l o c k s ) 以及分層等。劃分時可以使用固定的粒度也可以使用動態(tài)變化的粒度。 顯然，對輸入分解的粒度越細(xì)，就能獲得越多的對象和越多的劃分方案，也就更有可能獲 得較優(yōu)的結(jié)果。但是如果劃分的粒度過小也會遇到一些問題。首先細(xì)粒度分解不可避免的 會導(dǎo)致劃分對象增多，劃分算法將需要更多的時間進(jìn)行計(jì)算，在廣泛使用自動劃分算法和 計(jì)算機(jī)速度不斷增加的今天，這已經(jīng)不是很大的問題。其次，設(shè)計(jì)者不容易辨識細(xì)粒度對 象，因此也就難于支持手動交互。再次，細(xì)粒度劃分的結(jié)果對設(shè)計(jì)者來說不易于理解，對 其進(jìn)行手動設(shè)計(jì)或修改都較困難，對系統(tǒng)的評估也較困難。 2 3 3 系統(tǒng)組件分配 系統(tǒng)組件分配是軟硬件劃分步驟中的第二步。所謂系統(tǒng)組件分配就是從系統(tǒng)實(shí)現(xiàn)允許 的軟硬件組件中選擇部分組件來構(gòu)造系統(tǒng)，以滿足目標(biāo)系統(tǒng)需求的過程?？梢杂酶鞣N不同 的組件分配組合來實(shí)現(xiàn)目標(biāo)系統(tǒng)，各種組合之間的不同在于實(shí)現(xiàn)系統(tǒng)的性能和開銷各不相 同。分配可以手工或使用自動劃分算法來完成，它必須指定功能對象分配到的系