（微電子學(xué)與固體電子學(xué)專(zhuān)業(yè)論文）可重構(gòu)系統(tǒng)任務(wù)調(diào)度與系統(tǒng)級(jí)fpga抗輻照設(shè)計(jì).pdf

摘要 摘要 可重構(gòu)計(jì)算作為一種新型的計(jì)算技術(shù)已成為國(guó)際上計(jì)算體系結(jié)構(gòu)的熱門(mén)研 究方向之一?？芍貥?gòu)計(jì)算利用可重構(gòu)器件，將軟件實(shí)現(xiàn)的算法映射到硬件電路上 以提高計(jì)算性能。它兼有軟件的靈活性和硬件的高性能。 首先，本文研究了可重構(gòu)計(jì)算系統(tǒng)應(yīng)用的設(shè)計(jì)流程，從最初的應(yīng)用描述到最 后生成編程點(diǎn)之間的關(guān)鍵步驟。然后介紹了幾種常見(jiàn)的可重構(gòu)計(jì)算平臺(tái)，以及可 重構(gòu)計(jì)算在信號(hào)處理、網(wǎng)絡(luò)安全等領(lǐng)域的應(yīng)用模型。 第二，本文研究了可重構(gòu)計(jì)算任務(wù)調(diào)度和放置問(wèn)題。在此研究基礎(chǔ)上，本文 提出了在線(xiàn)任務(wù)預(yù)約重調(diào)度算法。仿真結(jié)果顯示，在正常負(fù)載率區(qū)間下，新的調(diào) 度策略有效的降低了任務(wù)拒絕率，而運(yùn)行開(kāi)銷(xiāo)在可接受范圍內(nèi)。 本文另一研究重點(diǎn)是系統(tǒng)級(jí)f p g a 抗輻照設(shè)計(jì)。通過(guò)將任務(wù)的檢錯(cuò)和重配置 交給操作系統(tǒng)管理，可以利用統(tǒng)一任務(wù)接口并提高系統(tǒng)的靈活性。為此，本文利 用a r m 開(kāi)發(fā)板和f d p 3 0 0 0 k 組成原型系統(tǒng)，并通過(guò)功能仿真。 關(guān)鍵詞：可重構(gòu)計(jì)算，任務(wù)調(diào)度，s e u ，抗輻照 a b s t r a c l a b s t r a c t a san e wc o m p u t i n gt e c 晡q u e ，r e c o n f i 舒l r a b i ec o m p u t i i 塔i sb e c o m i n go n eo ft h e m o s tp o p u l a l fd i r e c t i o l l so fr e s e a r c ho nc o m p u t m ga r c l l i t e c t u r ei m e m a t i o n a l l y r e c o 娟g u r a b l ec o m l ) u t i n gi st ou t i l i z et h er e c o l l f i g u r a b l ed e v i c e sa n dm 印s o f t w a r e i i i l p l e m e n t e da l g o r i t h mo n t oh a r d w a f et oa c c e l e r a t ec o m p u t i n gp e r f o n n a n c e 1 th a st h e m e r i t so f b o ms o r w a r e sf l e x i b i l 時(shí)a i l d h a r d w a r e sh i 曲p e r f o 徹a n c c f i r s t l y ，“sp a p e rs t u d i e dm ed e s i g i lf l o wo f 柚a p p l i c 蕊o no nr e c o 曲g u r a b l e c o m p u t i n gs y g t e m ，c o v e r i n gk e ys t e p s 丘o mm ed e s c r i p t i o no f 粗a p p l i c a t i o na tt h e v e f yb e 西徹i n gt 0p r o 鱸砌n gb i t sg e n e r a t i o na tl a s t t h e nc o m m o nr e c o n f i g m b l e c o m p u t i n gp l a t f 0 舳sa r ei n 臼d d u c e da i 】da l s ot h ea p p l i c a t i o nm o d e l s0 fr e c o n f i g u ra _ b l e c o i n p u t i n gi na r e a ss u c h 硒s i 印a lp r o c e s s i n g 觚dn e t 、0 r ks e c u r 戤 s e c o n d l y ，t l l i sp a p e rs t i l d i c d 也er e s e a r c ho nt a s l ( s s c h e d u l i n g 雒dp l a c e m e n t p f o b l e mi nr e c o i g u r a b l ec o m p u t m gs y s t e m s b a s e do nt h i sr e s e a r c i l ，t h i sp a p e r p r o p o s e dt l l e o n l i n et a s l ( sr e s e r v a t i o nr e s c h e d u l i n ga l g o r i t l l m s i n l u l a t i o nr e s u l t s h 0 、v st l l a tu n d e rn o n n a ls y s t e ml o a dr a n g e ，m ep r o p o s e ds t r a l e g yr e d u c e st 1 1 et a s k r c j e c t i o nr a t ee 艉c t i v e l yw h i l ck e e p i n gm 】吐i m eo v e r h e a dm a n a g e a b l e a n o t h e rf o c u so fn l i sp a p e ri s t l l es e um i t i g a t i o nt e c h l l i q u e sa ts y s t e ml e v e l t h r o u g hm a n a g i n gn l ee r r o rc h e c ka 1 1 dr e c o i 刪i o no ft a s k sb y0 p e r a t i n gs y s t e m ， w ec 觚b e n e f i ti 如mu s i n g 廿l eu i l i f o 冊(cè)t a s ki n t e 而c e 觚di n c r e a s em es y s t e m s n e x i b i l i 哆t 0 沁m e v et h a t ，也i sp a p e ru s e s 刪d e v e l o p m e n tb o a r d 鋤df d p 3 0 0 0 k t 0m a l ( ea p r o t o t ) ，i ) es y s t e m 觚ds 咖l a t i o nh a db e e nm n 0 ni ts u c c e s s m l l y k e y o r d ：r e c o n f i g u m b l ee o m p u t i n g ，t a s ks c h e d u l i n g ，s e u ，a n t i 一謝i a t i o n 第1 章引言 第1 章引言 1 1 研究背景 在傳統(tǒng)的計(jì)算系統(tǒng)中，算法可以采用兩種不同的方法來(lái)實(shí)現(xiàn)。一是用軟件編 程實(shí)現(xiàn)，并在通用處理器上運(yùn)行。該方法靈活性高，通過(guò)編寫(xiě)軟件指令就可改變 系統(tǒng)的功能，但指令的串行執(zhí)行以及指令集的有限性使得通用處理器的性能往往 不能滿(mǎn)足要求；二是采用硬件功能模塊如專(zhuān)用集成電路( a p p l i c a t i o ns p e c i f i c i n t e g r a t e dc i r c l l i t s ，a s i c s ) 實(shí)現(xiàn)。這種方法具有很高的執(zhí)行速度和運(yùn)算精度， 但功能單一、靈活性差，要想實(shí)現(xiàn)不同的算法必須重新設(shè)計(jì)集成電路，開(kāi)發(fā)成本 和周期都很高。 可重構(gòu)計(jì)算作為一種新的體系結(jié)構(gòu)，采用可編程的硬件模塊來(lái)實(shí)現(xiàn)計(jì)算，填 補(bǔ)了軟硬件之間的鴻溝，既保證了系統(tǒng)的性能，又保證了靈活性【l 】。以現(xiàn)場(chǎng)可 編程門(mén)陣列( f i e l dp r o g r a m m a b l eg a t ea m 叮s ，f p g a s ) 為代表的可重構(gòu)邏輯器件 可以被任意次地重新配置，使得一片可重構(gòu)器件能夠在不同時(shí)間運(yùn)行不同的硬件 算法，就像不同的算法運(yùn)行在傳統(tǒng)的處理器上一樣。 可重構(gòu)計(jì)算通過(guò)在時(shí)域上重用硬件資源來(lái)完成對(duì)計(jì)算任務(wù)并行性的利用，可 簡(jiǎn)單定義為至少包含一個(gè)可變硬件模塊的計(jì)算系統(tǒng)，此模塊的功能應(yīng)能夠被最終 用戶(hù)修改。修改過(guò)程主要是通過(guò)對(duì)系統(tǒng)中的可編程器件進(jìn)行重構(gòu)或部分重構(gòu)來(lái)實(shí) 現(xiàn)的。利用這一技術(shù)設(shè)計(jì)的可重構(gòu)系統(tǒng)，能在只增加少量硬件資源的情況下，將 軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)的優(yōu)點(diǎn)合二為一。它的出現(xiàn)使得過(guò)去傳統(tǒng)意義上硬件和軟件 的界限變得模糊，硬件系統(tǒng)得以軟件化【2 】。 從可重構(gòu)系統(tǒng)被提出的一開(kāi)始，它就以在各種應(yīng)用場(chǎng)合表現(xiàn)出的優(yōu)越性能而 倍受矚目。早期最成功的例子是s p l a l s h2 。在基因組分析的應(yīng)用中，它比當(dāng)時(shí)的 s p a r c1 0 工作站的運(yùn)算速度整整快了2 5 0 0 倍；若做灰度圖像的中值濾波器，則 比s p a r c1 0 快了幾乎1 4 0 倍【3 】【4 】。需要指出的是，s p l a s h2 使用了1 7 塊f p g a 而s p a r c1 0 只有1 個(gè)c p u ，按芯片數(shù)平均，在以上兩個(gè)應(yīng)用中每塊f p g a 分別 使性能提高了1 4 7 倍和8 倍，這一結(jié)果是相當(dāng)驚人的，并引發(fā)了學(xué)術(shù)界對(duì)可重構(gòu) 計(jì)算的巨大興趣。 隨著應(yīng)用場(chǎng)合的不同，可重構(gòu)計(jì)算系統(tǒng)對(duì)性能的提高程度也不大相同。一般 情況下，按系統(tǒng)中f p g a 的芯片數(shù)量進(jìn)行平均，每塊f p g a 能使運(yùn)算速度提高 7 3 0 倍左右。少量特別的例子能使速度提得更高【5 】。一般系統(tǒng)內(nèi)f p g a 數(shù)量越 第1 章引言 多，總體的性能就越高，而平均每塊芯片提高的速度倍數(shù)越低。 可重構(gòu)計(jì)算系統(tǒng)已被廣泛地應(yīng)用于從嵌入式系統(tǒng)到高性能計(jì)算的許多領(lǐng)域 6 】，包括數(shù)字圖像處理、網(wǎng)絡(luò)安全、生物信息學(xué)和超級(jí)計(jì)算等。 ， 1 1 1 可重構(gòu)計(jì)算的概念 人們從不同的研究角度出發(fā)，對(duì)可重構(gòu)計(jì)算的理解也不盡相同。目前比較公 認(rèn)的定義由加州大學(xué)伯克利分校可重構(gòu)技術(shù)研究中心的a n 出ed e h o n 和j o h n w a 岍z y n e k 于1 9 9 9 年a c m 設(shè)計(jì)自動(dòng)化國(guó)際會(huì)議上提出的種廣義的定義 7 】， 將其視為一類(lèi)計(jì)算機(jī)組織結(jié)構(gòu)，并具有區(qū)別于其它組織結(jié)構(gòu)的兩類(lèi)突出特點(diǎn)： 制造后芯片的定制能力( 區(qū)別于a s i c ) ； 能實(shí)現(xiàn)很大程度的算法到計(jì)算引擎的空間映射( 區(qū)別于通用處理器) 。 凡具備以上兩特點(diǎn)的計(jì)算方式都屬可重構(gòu)計(jì)算的范疇。 圖1 1 所描述的基本體系結(jié)構(gòu)可以基本概括和抽象目前已出現(xiàn)的可重構(gòu)計(jì)算 平臺(tái)。這種結(jié)構(gòu)結(jié)合了可編程處理器和可編程的硬件，因而能夠提供更多的設(shè)計(jì) 探索空間，同時(shí)也兼具了硬件的高性能和軟件的靈活性，這也是可重構(gòu)計(jì)算的研 究初衷和目標(biāo)。 圖1 1 可重構(gòu)計(jì)算的基本結(jié)構(gòu) 1 1 2 可重構(gòu)計(jì)算的起源 可重構(gòu)計(jì)算雖然直到最近才受到重視并逐漸流行起來(lái)，實(shí)際上其概念早在2 0 世紀(jì)6 0 年代就已經(jīng)提及。美國(guó)加利福尼亞大學(xué)的g e r a i de s 仃i n 提出可重構(gòu)的概 2 第1 章引言 多，總體的性能就越高，而平均每塊芯片提高的速度倍數(shù)越低。 可重構(gòu)計(jì)算系統(tǒng)已被廣泛地應(yīng)用于從嵌入式系統(tǒng)到高性能計(jì)算的許多領(lǐng)域 6 】，包括數(shù)字圖像處理、網(wǎng)絡(luò)安全、生物信息學(xué)和超級(jí)計(jì)算等。 ， 1 1 1 可重構(gòu)計(jì)算的概念 人們從不同的研究角度出發(fā)，對(duì)可重構(gòu)計(jì)算的理解也不盡相同。目前比較公 認(rèn)的定義由加州大學(xué)伯克利分?？芍貥?gòu)技術(shù)研究中心的a n 出ed e h o n 和j o h n w a 岍z y n e k 于1 9 9 9 年a c m 設(shè)計(jì)自動(dòng)化國(guó)際會(huì)議上提出的種廣義的定義 7 】， 將其視為一類(lèi)計(jì)算機(jī)組織結(jié)構(gòu)，并具有區(qū)別于其它組織結(jié)構(gòu)的兩類(lèi)突出特點(diǎn)： 制造后芯片的定制能力( 區(qū)別于a s i c ) ； 能實(shí)現(xiàn)很大程度的算法到計(jì)算引擎的空間映射( 區(qū)別于通用處理器) 。 凡具備以上兩特點(diǎn)的計(jì)算方式都屬可重構(gòu)計(jì)算的范疇。 圖1 1 所描述的基本體系結(jié)構(gòu)可以基本概括和抽象目前已出現(xiàn)的可重構(gòu)計(jì)算 平臺(tái)。這種結(jié)構(gòu)結(jié)合了可編程處理器和可編程的硬件，因而能夠提供更多的設(shè)計(jì) 探索空間，同時(shí)也兼具了硬件的高性能和軟件的靈活性，這也是可重構(gòu)計(jì)算的研 究初衷和目標(biāo)。 圖1 1 可重構(gòu)計(jì)算的基本結(jié)構(gòu) 1 1 2 可重構(gòu)計(jì)算的起源 可重構(gòu)計(jì)算雖然直到最近才受到重視并逐漸流行起來(lái)，實(shí)際上其概念早在2 0 世紀(jì)6 0 年代就已經(jīng)提及。美國(guó)加利福尼亞大學(xué)的g e r a i de s 仃i n 提出可重構(gòu)的概 2 第1 章引言 念，并研制了原型系統(tǒng)。該系統(tǒng)由非柔性但可編程的處理器和柔性的由程序控制 重構(gòu)的數(shù)字邏輯部件兩部分組成【8 】。盡管系統(tǒng)軟件和硬件的抽象層次不高但均 可編程重構(gòu)。由于當(dāng)時(shí)實(shí)現(xiàn)技術(shù)尚不完善，e s t r i n 研制的系統(tǒng)只是其設(shè)計(jì)理念的 粗略近似。但這種結(jié)構(gòu)奠定了以后可重構(gòu)計(jì)算系統(tǒng)的核心基礎(chǔ)。 1 1 ：ix 1 2 ：一ax 1 2 ：- 1 2 + 1 2 ：薯1 2x y ：i1 2 + x a y y b c 圖1 2 時(shí)空域計(jì)算模式 ( a ) 傳統(tǒng)處理器：時(shí)域計(jì)算( b ) a s i c 靜態(tài)r c ：空域計(jì)算( c ) 動(dòng)態(tài)r c ：時(shí)空域計(jì)算 1 9 8 6 年x i l i l l ) 【公司開(kāi)發(fā)出世界上第一片現(xiàn)場(chǎng)可編程門(mén)陣列( f p g a ) 芯片， 并在實(shí)踐中獲得了很好的應(yīng)用效果。到上世紀(jì)九十年代初期，出現(xiàn)了一些以 f p g a 為核心開(kāi)發(fā)的面向某一類(lèi)應(yīng)用的計(jì)算設(shè)備。一般做法是將一片或多片 f p g a 、c p u 和存儲(chǔ)器等組合到一起，f p g a 作為協(xié)處理器加速c p u 程序中的一 些可并行執(zhí)行成分( 一般為循環(huán)體) ，同時(shí)c p u 還要管理f p g a 的重構(gòu)。當(dāng)時(shí)這 種結(jié)構(gòu)的運(yùn)算設(shè)備被稱(chēng)為可重構(gòu)計(jì)算機(jī)，這種工作方式也被稱(chēng)為重構(gòu)計(jì)算。它們 在一些特殊的應(yīng)用領(lǐng)域顯示出了超強(qiáng)的計(jì)算性能和數(shù)據(jù)處理能力，尤其對(duì)于算法 內(nèi)部蘊(yùn)涵很大的并行性和流水性的應(yīng)用表現(xiàn)尤為出色，并顯著地降低了設(shè)計(jì)的費(fèi) 用。其中最具有代表性的是美國(guó)超級(jí)計(jì)算機(jī)研究中心( s u p e r o o m p u t i n gr e s e a r c h c e n t e r ) 在1 9 9 2 年研制的s p l a s h2 4 】，它對(duì)基因組測(cè)序的計(jì)算工作起到了極大的 加速作用。該研究成果的成功極大增強(qiáng)了人們對(duì)可重構(gòu)芯片進(jìn)一步研究和應(yīng)用的 信心，也引導(dǎo)人們開(kāi)始對(duì)其重新認(rèn)識(shí)和定位。九十年代中后期相繼出現(xiàn)了一些著 名的研究項(xiàng)目，其中包括g a 印【9 】，r a w 【1 0 】，m o 叩l l s o s 1 1 】等。 1 1 3 可重構(gòu)計(jì)算的特征 從本質(zhì)而言，可重構(gòu)計(jì)算是一種時(shí)空域上的計(jì)算模式【1 2 】，而傳統(tǒng)的通用處 理器計(jì)算是時(shí)域上的計(jì)算模式，a s i c 則位于空域上。圖1 2 顯示了它們的差別。 處理器具有通用的、固定的結(jié)構(gòu)，按照指令的命令執(zhí)行相應(yīng)的操作。在處理 3 第1 章引言 器上的計(jì)算首先要將問(wèn)題分解為一條條可以在處理器上運(yùn)行的指令，這些指令以 時(shí)間的順序依次流過(guò)處理器，產(chǎn)生時(shí)域的運(yùn)算序列。圖1 2 ( a ) 顯示了傳統(tǒng)處理器 計(jì)算表達(dá)式y(tǒng) = a 木x 幸x + b 木x + c 的過(guò)程。處理器被簡(jiǎn)單地表示為由保存數(shù)據(jù)的 寄存器和執(zhí)行運(yùn)算功能的a l u 部件組成。該問(wèn)題被分解為5 條指令，依次執(zhí)行 每條指令將得出最終結(jié)果。從運(yùn)算過(guò)程可知，雖然通用處理器的硬件結(jié)構(gòu)固定不 變，但依然可以通過(guò)指令序列的不同來(lái)實(shí)現(xiàn)不同的功能，因此具有很高的通用性。 但( 1 ) 出于同樣的原因，由于其硬件結(jié)構(gòu)是通用的，并不為特定的目標(biāo)算法優(yōu)化； ( 2 ) 同時(shí)為照顧通用性，其關(guān)鍵路徑上不可避免地存在一些不必要的計(jì)算，比如 即使x 是1 2 位整數(shù)，計(jì)算過(guò)程也必須運(yùn)行在3 2 位的a l u 通路上，造成性能浪 費(fèi)；( 3 ) 所有運(yùn)算過(guò)程必須映射到處理器指令集上，指令集的有限性造成了映射 效率下降，如即使處理器有可能同時(shí)執(zhí)行一條加法和一條乘法，但通常必須映射 到2 條指令上，對(duì)非亂序執(zhí)行結(jié)構(gòu)或同時(shí)發(fā)射指令數(shù)不足時(shí)，不能充分發(fā)揮處理 器的本身的計(jì)算帶寬；( 4 ) 數(shù)據(jù)通常保存在全局洲中，計(jì)算時(shí)需裝載入寄存器， 然而全局r 州的訪(fǎng)問(wèn)延遲非常大；( 5 ) 對(duì)于循環(huán)、跳轉(zhuǎn)等運(yùn)算不可避免地要安排 改變程序流向的控制指令，但這些控制指令就自身而言對(duì)數(shù)據(jù)運(yùn)算是毫無(wú)用處 的，白白浪費(fèi)了時(shí)鐘周期。這諸多的原因，使得通用處理器計(jì)算方式的運(yùn)算性能 并不理想。 一種改進(jìn)方式是使用運(yùn)算能力更強(qiáng)的定制指令集處理器( a s i p ) 、超長(zhǎng)指令集 處理器( v l i w ) 或數(shù)字信號(hào)處理器( d s p ) 等。它們繼承了通用處理器易編程 的優(yōu)點(diǎn)，通過(guò)提供更多的硬件運(yùn)算單元( 如多乘法部件) ，甚至使用專(zhuān)門(mén)的硬件 加速協(xié)處理器( 如向量處理器) ，以及增加特殊指令( 如乘加指令) 或提供更寬 的指令( 如v l i w ) ，提高了處理器對(duì)具有某類(lèi)運(yùn)算特征的應(yīng)用領(lǐng)域的處理能力， 如多媒體處理和網(wǎng)絡(luò)處理等。但很顯然，它們應(yīng)用范圍較為受限，甚至導(dǎo)致了在 通用處理方面的不足( 如d s p 的程序控制能力較弱) 。 一。 終極提速方案是使用硬件執(zhí)行上述算法。如圖l - 2 ( b ) 所示?？紤]到y(tǒng) = a 宰x 幸x + b 宰x + c 總共執(zhí)行3 次乘法2 次加法，在硬件上專(zhuān)門(mén)制作3 個(gè)乘法器，2 個(gè)加 法器，并按照計(jì)算要求的通訊關(guān)系安排乘法器和加法器之間的連接，能夠在一個(gè) 周期內(nèi)完成所有的運(yùn)算過(guò)程。如果x 寬度只有1 2 位，那么只需設(shè)計(jì)1 2 位的乘法 器，比3 2 位乘法運(yùn)算具有更快的速度。硬件針對(duì)算法的專(zhuān)門(mén)性?xún)?yōu)化是硬件具有 高性能的原因之一。同時(shí)，硬件執(zhí)行是全空間域、全芯片內(nèi)的并行執(zhí)行；其次， 硬件方式中只有必需的數(shù)據(jù)流過(guò)處理單元，沒(méi)有無(wú)關(guān)緊要的指令流和中間數(shù)據(jù) 流，去除了相互之間的依賴(lài)關(guān)系，進(jìn)而也消除了訪(fǎng)問(wèn)指令所需的存儲(chǔ)器帶寬。這 些原因使得硬化計(jì)算成為高性能計(jì)算中的一種值得期待的計(jì)算方式。 早期采用定制應(yīng)用專(zhuān)用芯片a s i c 的方式來(lái)硬化計(jì)算。但a s i c 一經(jīng)設(shè)計(jì)， 4 第1 章引言 其功能便不能發(fā)生變化。尤其是在制造后，用戶(hù)不能做任何的編程，除了一些參 數(shù)上的調(diào)整等。a s i c 的應(yīng)用范圍比a s i p 更為狹窄，但卻是性能最高的方案。 用戶(hù)要想改換用其它算法，必須重新設(shè)計(jì)電路、重新開(kāi)模制片，開(kāi)發(fā)難度、開(kāi)發(fā) 周期以及開(kāi)發(fā)費(fèi)用等都比較高，使得a s i c 只有在大批量生產(chǎn)的時(shí)候才能顯示出 其優(yōu)越性。 另一種方法是采用硬件可編程器件如f p g a 、c p l d 等來(lái)硬化算法。這種方 式無(wú)需一次性工程費(fèi)用，設(shè)計(jì)快速方便，逐漸有取代a s i c 的趨勢(shì)。這就是靜態(tài) 可重構(gòu)計(jì)算。設(shè)計(jì)時(shí)根據(jù)算法的特點(diǎn)，設(shè)計(jì)出最優(yōu)化的硬件電路，并在運(yùn)行過(guò)程 中保持該電路不變?？删幊绦允沟渺o態(tài)可重構(gòu)計(jì)算比a s i c 具有更高的靈活性。 但為了提供可編程能力，器件必須付出額外編程通路的開(kāi)銷(xiāo)；其次，算法必須映 射到器件特定的邏輯運(yùn)算資源和布線(xiàn)資源上，并不能完全自由地設(shè)計(jì)。因此性能 要比a s i c 大約低一個(gè)數(shù)量級(jí)，但比通用計(jì)算高出兩個(gè)數(shù)量級(jí)左右的性能依舊使 得靜態(tài)可重構(gòu)成為引人注目的高速運(yùn)算方式。 再進(jìn)一步，將算法在整個(gè)運(yùn)行過(guò)程中繼續(xù)細(xì)分，在不同的時(shí)刻研究算法的不 同特征。假設(shè)我們開(kāi)始要求計(jì)算y = a 幸x 木x + b 書(shū)x + c ，隨后隨著時(shí)間的推移要求 計(jì)算y = ( a + x x ) 幸( b 幸x + c ) 。后者也需要3 個(gè)乘法器和2 個(gè)加法器，但它們之 間的連接關(guān)系與前者不同。也就是說(shuō)，連接結(jié)構(gòu)的不同造成了系統(tǒng)具有不同的功 能。如果需要改變硬件以適配這兩個(gè)不同的表達(dá)式，這在a s i c 上是不可能做到 的，在靜態(tài)重構(gòu)計(jì)算中要求關(guān)機(jī)并重新加載硬件設(shè)計(jì)，這通常是不合適的。動(dòng)態(tài) 可重構(gòu)計(jì)算允許在運(yùn)行時(shí)改變硬件的功能，匹配目標(biāo)算法的動(dòng)態(tài)特征，如圖l 一2 ( c ) 所示。動(dòng)態(tài)可重構(gòu)計(jì)算的這種在時(shí)域上高度靈活的特點(diǎn)，更能充分發(fā)揮硬件的高 速計(jì)算的能力。 性 能 靈活性 圖1 3 四種計(jì)算模式的比較 根據(jù)以上分析，可得出四種計(jì)算模式在性能和編程靈活性方面的優(yōu)劣比較， 如圖l 一3 ?？芍貥?gòu)計(jì)算作為一種新型的計(jì)算模式，彌補(bǔ)了通用計(jì)算和專(zhuān)用計(jì)算之 間的空白，在大部分有高性能要求的專(zhuān)用應(yīng)用領(lǐng)域中，是一種較為合適的解決方 5 第1 章引言 案。 1 1 4 可重構(gòu)系統(tǒng)研究中存在的問(wèn)題 可重構(gòu)計(jì)算的發(fā)展現(xiàn)狀是硬件遠(yuǎn)遠(yuǎn)領(lǐng)先于軟件。當(dāng)前，f p g a 的容量正按照 摩爾定律的速度發(fā)展，大容量的f p g a 不僅提供了大量的可編程硬件資源，還集 成了乘法器、存儲(chǔ)器和微處理器等功能部件，形成了一個(gè)完整的可編程片上系統(tǒng)。 多個(gè)硬件計(jì)算模塊可以在大容量f p g a 上并行地運(yùn)行，動(dòng)態(tài)部分可重構(gòu)的f p g a 使得硬件計(jì)算模塊可在運(yùn)行時(shí)動(dòng)態(tài)配置，這進(jìn)一步提高了其性能優(yōu)勢(shì)。 另一方面，應(yīng)用開(kāi)發(fā)工具和設(shè)計(jì)方法卻還很原始，遠(yuǎn)遠(yuǎn)跟不上可重構(gòu)器件的 發(fā)展。目前各個(gè)公司及研究機(jī)構(gòu)發(fā)布的可重構(gòu)計(jì)算平臺(tái)均沿著各自的路線(xiàn)發(fā)展， 缺少統(tǒng)一的計(jì)算模型。絕大多數(shù)的可重構(gòu)計(jì)算平臺(tái)上的開(kāi)發(fā)工具還不成熟，軟硬 件的設(shè)計(jì)是分開(kāi)完成的，很少有統(tǒng)一的系統(tǒng)級(jí)的軟硬件協(xié)同開(kāi)發(fā)平臺(tái)，給實(shí)際應(yīng) 用造成了巨大障礙。 動(dòng)態(tài)可重構(gòu)系統(tǒng)的實(shí)現(xiàn)需要一個(gè)運(yùn)行時(shí)環(huán)境，以對(duì)豐富的可編程硬件資源進(jìn) 行有效的管理。這也對(duì)開(kāi)發(fā)工具提出了更高的要求。 目前可重構(gòu)系統(tǒng)的應(yīng)用開(kāi)發(fā)類(lèi)似于早期的計(jì)算機(jī)軟件開(kāi)發(fā)，程序員需要細(xì)致 地安排處理器、內(nèi)存、外存和外設(shè)等硬件資源的使用，操作系統(tǒng)的出現(xiàn)使得程序 員從這些瑣碎的細(xì)節(jié)中解脫出來(lái)。同樣，在可重構(gòu)計(jì)算中也需要一個(gè)操作系統(tǒng)來(lái) 管理新的可重構(gòu)硬件資源，屏蔽硬件的細(xì)節(jié)，并向開(kāi)發(fā)人員提供高層次的編程模 型。 1 2 工作重點(diǎn) 本文所作的工作主要包括： 詳細(xì)的研究了可重構(gòu)計(jì)算系統(tǒng)應(yīng)用的設(shè)計(jì)流程，介紹了幾種典型的可重構(gòu)計(jì) 算平臺(tái)，以及可重構(gòu)計(jì)算在各領(lǐng)域的應(yīng)用模型和實(shí)例。 研究了可重構(gòu)系統(tǒng)任務(wù)調(diào)度和放置問(wèn)題，設(shè)計(jì)了一個(gè)任務(wù)調(diào)度問(wèn)題的仿真環(huán) 境，提出了在線(xiàn)任務(wù)預(yù)約重調(diào)度算法，并取得較好的仿真結(jié)果。 研究了系統(tǒng)級(jí)f p g a 抗輻照方法，利用操作系統(tǒng)管理任務(wù)的檢錯(cuò)和重配置。 設(shè)計(jì)一個(gè)由a r m 開(kāi)發(fā)板和h ) p 3 0 0 0 k 組成的仿真平臺(tái)，并成功通過(guò)仿真。 1 3 論文組織 本文共分為5 個(gè)章節(jié)，其中第一章介紹了可重構(gòu)計(jì)算誕生的背景和特征，第 6 第1 章引言 2 章介紹可重構(gòu)計(jì)算的軟硬件發(fā)展及其應(yīng)用，第3 章研究可重構(gòu)系統(tǒng)任務(wù)調(diào)度和 放置問(wèn)題，第4 章提出了在線(xiàn)任務(wù)預(yù)約重調(diào)度算法，第5 章介紹系統(tǒng)級(jí)f p g a 抗 輻照設(shè)計(jì)，并提出系統(tǒng)級(jí)抗輻照仿真平臺(tái)，最后是對(duì)本論文工作的總結(jié)以及未來(lái) 工作的展望。 7 第2 章可重構(gòu)計(jì)算系統(tǒng) 第2 章可重構(gòu)計(jì)算系統(tǒng) 可重構(gòu)計(jì)算系統(tǒng)的體系結(jié)構(gòu)是由f p g a 發(fā)展而來(lái)的。目前已見(jiàn)報(bào)道的多數(shù)平 臺(tái)都采用了多f p g a 的結(jié)構(gòu)，根據(jù)應(yīng)用場(chǎng)景的不同，可能還包含多c p u 或?qū)Ｓ?存儲(chǔ)器 1 】。另外，為了減輕通信和訪(fǎng)存的開(kāi)銷(xiāo)，也有不少研究項(xiàng)目將處理器和 可重構(gòu)單元整合到一塊芯片上。總體來(lái)看，現(xiàn)代可重構(gòu)計(jì)算平臺(tái)的發(fā)展過(guò)程基本 上可以分為三個(gè)階段【1 4 】，如圖2 1 。第一代可重構(gòu)計(jì)算平臺(tái)的主要目標(biāo)是提供 一套高性能計(jì)算平臺(tái)，其典型代表為s p l a l s h 系統(tǒng)。在這個(gè)過(guò)程中，研究者們發(fā) 現(xiàn)通信、互連以及重構(gòu)時(shí)間都存在改進(jìn)和提升的空間，因此開(kāi)發(fā)了第二代可重構(gòu) 平臺(tái)( 典型代表有g(shù) m 沖、洲、s p l a s h 等) ，并提出了一些方法和手段進(jìn)行 改善，比如部分可重構(gòu)、上下文切換以及動(dòng)態(tài)重構(gòu)等。進(jìn)一步，開(kāi)發(fā)了主要面向 數(shù)據(jù)流應(yīng)用的第三代可重構(gòu)系統(tǒng)。 第一代 代表系統(tǒng) p r i s m d e c p e d e s p l h s p y d e r 配置時(shí)問(wèn) 過(guò)長(zhǎng) l第二代 ” i 解決方法億竺享墨絲 i 廣叵糾鬈r h 冀窶篙囂舅卜匝r 1 連重構(gòu)能力r 匕! 竺 部分，動(dòng)態(tài) 重構(gòu) d i s c f i p s o c 矗麟 第三代 特色方法代表系統(tǒng) 蠹蕊k 忑配置i i 1 蘭三竺蘭h ! 竺竺竺 霉攀h 篙沁 置 i7 l r j i l g 圖2 1 可重構(gòu)計(jì)算平臺(tái)的發(fā)展 通過(guò)將計(jì)算密集型的任務(wù)映射到可編程器件上，可重構(gòu)系統(tǒng)可以加速任務(wù)的 運(yùn)行速度進(jìn)而提高整體運(yùn)算性能。作為典型的可重構(gòu)單元陣列( r e c o i l f i 鼬l e c e u 岫，r c a ) ，f p g a 已經(jīng)可以提供上百萬(wàn)門(mén)的邏輯單元，允許多個(gè)硬件任 務(wù)同時(shí)運(yùn)行。 8 題一頸一 一構(gòu)活 問(wèn)一瓶一 一結(jié)靈 現(xiàn)一信一 一連夠 發(fā)一通一 一互不 第2 章可重構(gòu)計(jì)算系統(tǒng) 全自動(dòng) 2 1 可重構(gòu)計(jì)算軟件系統(tǒng) 全自動(dòng)手工結(jié)合 全手工 圖2 2 可重構(gòu)計(jì)算設(shè)計(jì)流程 可重構(gòu)計(jì)算系統(tǒng)對(duì)某些應(yīng)用的性能有顯著的提高，但前提是設(shè)計(jì)人員可以高 效的將可重構(gòu)計(jì)算系統(tǒng)包含在其設(shè)計(jì)中，這往往需要一個(gè)集成軟硬件開(kāi)發(fā)平臺(tái)， 該平臺(tái)可以協(xié)助設(shè)計(jì)人員生成系統(tǒng)配置，或是全自動(dòng)完成整個(gè)設(shè)計(jì)流程。圖2 2 列舉了三種可能設(shè)計(jì)流程，從全自動(dòng)到全手工設(shè)計(jì)。目前，除小規(guī)模設(shè)計(jì)或?qū)π?能、面積等因素有特殊要求外，基本沒(méi)有設(shè)計(jì)人員手工承擔(dān)全部設(shè)計(jì)工作，而是 將綜合、工藝映射和布局布線(xiàn)都交給機(jī)器執(zhí)行。在全自動(dòng)流程的設(shè)計(jì)輸入階段， 設(shè)計(jì)描述可以采用高層語(yǔ)言( h i g l l l e v e l l a i l g u a g e ，h l l ) ，例如c c + + 、j a v a 等 語(yǔ)言，經(jīng)過(guò)軟硬件任務(wù)劃分，將計(jì)算密集型任務(wù)映射到可重構(gòu)器件上，并輸出門(mén) 級(jí)網(wǎng)表，最后再交由后端流程處理。 2 1 1 設(shè)計(jì)周期 在衡量一個(gè)可重構(gòu)系統(tǒng)設(shè)計(jì)流程時(shí)，通常有以下幾點(diǎn)需要考慮： 抽象級(jí)別。抽象級(jí)別是算法級(jí)、行為級(jí)或是結(jié)構(gòu)級(jí)? 如何描述系統(tǒng)和組 件? 并行化和劃分。是自動(dòng)還是手工完成算法的并行化以及軟硬件任務(wù)劃 9 第2 章可重構(gòu)計(jì)算系統(tǒng) 全自動(dòng) 2 1 可重構(gòu)計(jì)算軟件系統(tǒng) 全自動(dòng)手工結(jié)合 全手工 圖2 2 可重構(gòu)計(jì)算設(shè)計(jì)流程 可重構(gòu)計(jì)算系統(tǒng)對(duì)某些應(yīng)用的性能有顯著的提高，但前提是設(shè)計(jì)人員可以高 效的將可重構(gòu)計(jì)算系統(tǒng)包含在其設(shè)計(jì)中，這往往需要一個(gè)集成軟硬件開(kāi)發(fā)平臺(tái)， 該平臺(tái)可以協(xié)助設(shè)計(jì)人員生成系統(tǒng)配置，或是全自動(dòng)完成整個(gè)設(shè)計(jì)流程。圖2 2 列舉了三種可能設(shè)計(jì)流程，從全自動(dòng)到全手工設(shè)計(jì)。目前，除小規(guī)模設(shè)計(jì)或?qū)π?能、面積等因素有特殊要求外，基本沒(méi)有設(shè)計(jì)人員手工承擔(dān)全部設(shè)計(jì)工作，而是 將綜合、工藝映射和布局布線(xiàn)都交給機(jī)器執(zhí)行。在全自動(dòng)流程的設(shè)計(jì)輸入階段， 設(shè)計(jì)描述可以采用高層語(yǔ)言( h i g l l l e v e l l a i l g u a g e ，h l l ) ，例如c c + + 、j a v a 等 語(yǔ)言，經(jīng)過(guò)軟硬件任務(wù)劃分，將計(jì)算密集型任務(wù)映射到可重構(gòu)器件上，并輸出門(mén) 級(jí)網(wǎng)表，最后再交由后端流程處理。 2 1 1 設(shè)計(jì)周期 在衡量一個(gè)可重構(gòu)系統(tǒng)設(shè)計(jì)流程時(shí)，通常有以下幾點(diǎn)需要考慮： 抽象級(jí)別。抽象級(jí)別是算法級(jí)、行為級(jí)或是結(jié)構(gòu)級(jí)? 如何描述系統(tǒng)和組 件? 并行化和劃分。是自動(dòng)還是手工完成算法的并行化以及軟硬件任務(wù)劃 9 第2 章可重構(gòu)計(jì)算系統(tǒng) 全自動(dòng) 2 1 可重構(gòu)計(jì)算軟件系統(tǒng) 全自動(dòng)手工結(jié)合 全手工 圖2 2 可重構(gòu)計(jì)算設(shè)計(jì)流程 可重構(gòu)計(jì)算系統(tǒng)對(duì)某些應(yīng)用的性能有顯著的提高，但前提是設(shè)計(jì)人員可以高 效的將可重構(gòu)計(jì)算系統(tǒng)包含在其設(shè)計(jì)中，這往往需要一個(gè)集成軟硬件開(kāi)發(fā)平臺(tái)， 該平臺(tái)可以協(xié)助設(shè)計(jì)人員生成系統(tǒng)配置，或是全自動(dòng)完成整個(gè)設(shè)計(jì)流程。圖2 2 列舉了三種可能設(shè)計(jì)流程，從全自動(dòng)到全手工設(shè)計(jì)。目前，除小規(guī)模設(shè)計(jì)或?qū)π?能、面積等因素有特殊要求外，基本沒(méi)有設(shè)計(jì)人員手工承擔(dān)全部設(shè)計(jì)工作，而是 將綜合、工藝映射和布局布線(xiàn)都交給機(jī)器執(zhí)行。在全自動(dòng)流程的設(shè)計(jì)輸入階段， 設(shè)計(jì)描述可以采用高層語(yǔ)言( h i g l l l e v e l l a i l g u a g e ，h l l ) ，例如c c + + 、j a v a 等 語(yǔ)言，經(jīng)過(guò)軟硬件任務(wù)劃分，將計(jì)算密集型任務(wù)映射到可重構(gòu)器件上，并輸出門(mén) 級(jí)網(wǎng)表，最后再交由后端流程處理。 2 1 1 設(shè)計(jì)周期 在衡量一個(gè)可重構(gòu)系統(tǒng)設(shè)計(jì)流程時(shí)，通常有以下幾點(diǎn)需要考慮： 抽象級(jí)別。抽象級(jí)別是算法級(jí)、行為級(jí)或是結(jié)構(gòu)級(jí)? 如何描述系統(tǒng)和組 件? 并行化和劃分。是自動(dòng)還是手工完成算法的并行化以及軟硬件任務(wù)劃 9 第2 章可重構(gòu)計(jì)算系統(tǒng) 分? 循環(huán)變換。編譯器是否實(shí)現(xiàn)循環(huán)展開(kāi)或流水化? 循環(huán)級(jí)和指令級(jí)流水線(xiàn) 如何交互? 指令級(jí)并行性( j n s l r u c t i o nl e v e ip a r a e i i s m ，l l p ) 提取。編譯器是否 自動(dòng)識(shí)別i l p 并調(diào)度可并行的活動(dòng)? 內(nèi)存層次管理。數(shù)組和變量分配在片上還是片外? 調(diào)式功能。提供何種程度的調(diào)式手段。 應(yīng)用 i i 任務(wù)劃分 軟件流程 硬件流程 布局布線(xiàn)，功 耗時(shí)序優(yōu)化 圖2 3 可重構(gòu)計(jì)算設(shè)計(jì)周期 通常，設(shè)計(jì)的整個(gè)周期既包含有軟件的編譯也包含硬件的綜合，如圖2 - 3 所 示。從一個(gè)順序執(zhí)行的應(yīng)用開(kāi)始，一般先要執(zhí)行如下準(zhǔn)備工作： 1 剖析程序( p r o g r 鋤p r o f i l i n g ) ，識(shí)別出計(jì)算密集模塊 2 粗略評(píng)估用硬件代替計(jì)算密集模塊所獲得的提升 3 在粗略評(píng)估的基礎(chǔ)上量化軟硬件通信帶來(lái)的數(shù)據(jù)交換開(kāi)銷(xiāo) 對(duì)于擁有傳統(tǒng)微處理器的可重構(gòu)計(jì)算系統(tǒng)，待執(zhí)行的應(yīng)用首先被劃分為軟件 部分和硬件部分。軟件部分在微處理器上以指令形式運(yùn)行；硬件部分被映射在可 重構(gòu)器件上執(zhí)行。例如，一般情況下，復(fù)雜控制序列例如變長(zhǎng)循環(huán)等適合用軟件 1 0 第2 章可重構(gòu)計(jì)算系統(tǒng) 實(shí)現(xiàn)；而固定的數(shù)據(jù)通路更適合在硬件中執(zhí)行。 實(shí)際中任務(wù)劃分大部分是由手工完成。性能剖析工具( p r o f i l i n gt o o l s ) 可以 識(shí)別出潛在的模塊以映射到硬件上。目前已經(jīng)有研究針對(duì)如何僅通過(guò)給出的算法 描述來(lái)評(píng)估使用硬件所可能獲得的面積、性能、延時(shí)等指標(biāo)的提升。通過(guò)分析這 些結(jié)果，設(shè)計(jì)者決定哪些模塊交給硬件來(lái)完成，并給出這些模塊的h d l 描述。 2 1 2 設(shè)計(jì)語(yǔ)言 對(duì)于通用處理器上的軟件設(shè)計(jì)，使用的編程語(yǔ)言本質(zhì)上是算法語(yǔ)言，即在圖 靈機(jī)的形式上對(duì)連續(xù)的指令流進(jìn)行取、譯、執(zhí)行操作并讀寫(xiě)內(nèi)存。與之不同，將 應(yīng)用映射到可重構(gòu)硬件上則需要包含底層自定義邏輯的描述，同時(shí)在硬件資源約 束下追求最大的并行性。 對(duì)于傳統(tǒng)硬件設(shè)計(jì)，設(shè)計(jì)工具通常抽象出底層硬件資源，例如移位寄存器、 比較器、加法器等作為基本單元，以便設(shè)計(jì)人員搭建層次化、并行的系統(tǒng)。 由于大部分基于f p g a 的應(yīng)用都可歸結(jié)為硬件設(shè)計(jì)問(wèn)題，可重構(gòu)計(jì)算設(shè)計(jì)語(yǔ) 言的選擇更偏向于硬件描述語(yǔ)言( h a r d w a r ed e s 嘶p t i o nl a l l g u a g e ，h d l ) 。在最 低層，設(shè)計(jì)者直接描述f p g a 上每個(gè)邏輯單元的功能和連接關(guān)系；在高一層，設(shè) 計(jì)者可以用i p 單元搭建系統(tǒng)，即結(jié)構(gòu)級(jí)描述；比結(jié)構(gòu)級(jí)再高一層的是寄存器傳 輸級(jí)( r e g i s t e r - t r 觚s f e rl e v e l ，r 阻) 描述；最高層是算法級(jí)描述和行為級(jí)描述。 2 1 2 1 算法級(jí) 最直觀的將算法映射到可重構(gòu)系統(tǒng)的方法是使用協(xié)處理器模型。在該模型 中，順序程序中的計(jì)算密集型模塊被映射到硬件中執(zhí)行，其余仍用軟件執(zhí)行。利 用該模型的順序c 語(yǔ)言硬件編譯器已被研究出來(lái) 1 5 】。在【1 6 】中，n a p ac 編譯 器利用一種宏驅(qū)動(dòng)的方法來(lái)識(shí)別欲映射到硬件的代碼。在【1 7 】中，設(shè)計(jì)工具通過(guò) 參數(shù)化的結(jié)構(gòu)模型來(lái)自動(dòng)完成軟硬件劃分。【9 】中的g a 印c 編譯器則同時(shí)產(chǎn)生計(jì) 算密集型模塊的軟硬件版本，然后通過(guò)自動(dòng)剖析來(lái)決定具體使用情況。 【1 8 】最早研究了一種從o c c 鋤語(yǔ)言演化而來(lái)的并行c 編譯器，它繼承了 o c c 鋤帶顯式的并行和順序塊的并行通信順序進(jìn)程模型( c o i i l 】 1 1 砌c a t i n g s e q u e n t i a lp r o c e s s ，c s p ) 。 1 9 】 2 0 】中的s 仃e 鋤s - c 編譯器支持帶f i f o 緩沖的既可 以運(yùn)行在硬件上也可以運(yùn)行在軟件上的進(jìn)程模型。通過(guò)宏指令，它還可以將數(shù)組 映射到內(nèi)存中。 基于j a v a 的編譯器也被開(kāi)發(fā)出來(lái)，例如x i l i l l ) 【的f o r g e 編譯器以及b y u 的 第2 章可重構(gòu)計(jì)算系統(tǒng) s c 編譯器【2 l 】。它們都是先生成j a v a 字節(jié)碼( b y t e c o d e ) ，然后將字節(jié)碼綜合為 硬件。 在信號(hào)處理領(lǐng)域，m a l l a b 編譯器也可用于可重構(gòu)計(jì)算 2 2 】。在s i m u l i n k 級(jí)別， x i l i 似發(fā)布了s y s t e mg e n e r a t o r 用來(lái)將s i i n u l i n k 中的模塊映射為s y s t c m ( 沁n e r a t o r 庫(kù)中的單元【2 3 】。 2 1 2 2h d l 級(jí) h d l 語(yǔ)言能夠在行為級(jí)、i 汀l 級(jí)、結(jié)構(gòu)級(jí)以及器件級(jí)對(duì)系統(tǒng)進(jìn)行描述。行 為級(jí)和算法級(jí)描述有很多相似之處，它具有算法級(jí)語(yǔ)言中的函數(shù)調(diào)用、循環(huán)結(jié)構(gòu) 等特點(diǎn)，也是根據(jù)算法描述綜合出數(shù)據(jù)通路和狀態(tài)機(jī)，但前者往往指利用v h d l 或v e r i l o g 等現(xiàn)有h d l 語(yǔ)言進(jìn)行高層次建模和仿真，且h d l 可綜合的子集中一 般不支持指針或動(dòng)態(tài)內(nèi)存分配等。 對(duì)于v h d l 和v e r i l o g 這兩種標(biāo)準(zhǔn)的工業(yè)級(jí)語(yǔ)言，已經(jīng)存在很多的仿真和綜 合工具，且一般都支持行為級(jí)、r 1 r l 級(jí)、器件級(jí)的混合使用，這給設(shè)計(jì)者提供了 很大的靈活性。例如，s y s t e mc 是另一種基于c + + 庫(kù)的行為級(jí)建模語(yǔ)言。相比 較傳統(tǒng)h d l 語(yǔ)言， s y s t e mc 使得軟件設(shè)計(jì)者可以輕松移植已有的應(yīng)用。但雖 然s y s t e mc 的綜合工具不斷的涌現(xiàn)，其成熟度與v h d l 或v e r i l o g 綜合工具相比 仍相距甚遠(yuǎn)。 1 2 第2 章可重構(gòu)計(jì)算系統(tǒng) 2 1 3 設(shè)計(jì)前端一高層編譯 語(yǔ)法解析 上 語(yǔ)義分析 上 代碼優(yōu)化 上 調(diào)度 l 山 中間代碼生成 圖2 4 前端流程 圖2 4 描述了一般的前端流程。可以發(fā)現(xiàn)，該流程同大部分高級(jí)語(yǔ)言編譯器 流程類(lèi)似，只是最后將產(chǎn)生r 1 兒或結(jié)構(gòu)級(jí)的電路網(wǎng)表。 可重構(gòu)計(jì)算系統(tǒng)編譯器設(shè)計(jì)通常比傳統(tǒng)處理器要復(fù)雜得多。對(duì)于后者而言， 其指令集架構(gòu)( i n s t m c t i o ns e ta r c l l i t e c t u r e ，i s a ) 固定，尤其是目前的超標(biāo)量 ( s u p e r s c a l a r ) 處理器架構(gòu)使得相當(dāng)多的優(yōu)化都發(fā)生在運(yùn)行時(shí)，進(jìn)而簡(jiǎn)化了編譯 器的設(shè)計(jì)。 f p g a 沒(méi)有指令集架構(gòu)，所以編譯器還將負(fù)責(zé)搭建所需指令操作的具體硬件 電路，包括數(shù)據(jù)通路( 算術(shù)單元和寄存器) 、存儲(chǔ)器結(jié)構(gòu)、i o 以及定序器( 包括 數(shù)據(jù)通路控制、存儲(chǔ)器訪(fǎng)問(wèn)和i o 等) 。編譯器還必須選擇所需的基本功能單元， 例如對(duì)于加法器，是用8 b i t ，1 6 - b i t 或是3 2 - b i t ? 是定點(diǎn)還是浮點(diǎn)? 是串行、流 水線(xiàn)、還是并行? 這些決策要取決于面積和性能的折中。綜合這些考慮，使得可 重構(gòu)計(jì)算編譯器的設(shè)計(jì)是一個(gè)復(fù)雜的多目標(biāo)的優(yōu)化問(wèn)題。 1 3 第2 章可重構(gòu)計(jì)算系統(tǒng) 2 1 4 設(shè)計(jì)后端一低層流程 邏輯綜合 上 工藝映射 上 布局 j ， 布線(xiàn) 圖2 5 后端流程 圖2 5 展示了一般的后端流程。該流程將r 幾級(jí)或結(jié)構(gòu)級(jí)網(wǎng)表轉(zhuǎn)化為f p g a 的配置位流。該流程目前己趨成熟，各f p g a 供應(yīng)商都提供了自己的完整的計(jì)算 機(jī)輔助設(shè)計(jì)( c o m p u t e ra i d e dd e s i 印，c a d ) 工具，還有像s y n p l i 匆系列的第三 方工具。 2 4 】提供了設(shè)計(jì)后端的詳細(xì)討論， 該流程第一步是邏輯綜合( 1 0 西cs y n t l l e s 知) ，它將r 幾級(jí)或結(jié)構(gòu)級(jí)的電路描 述轉(zhuǎn)化為優(yōu)化過(guò)的門(mén)級(jí)網(wǎng)表。邏輯綜合的難點(diǎn)在于如何在滿(mǎn)足設(shè)計(jì)約束的前提下 盡量?jī)?yōu)化電路并達(dá)到面積、速度和功耗的折中。優(yōu)化分為工藝無(wú)關(guān)優(yōu)化和工藝相 關(guān)優(yōu)化。 下一步的工藝映射( t e c l l i l o l o g ) rm a p p i i l g ) 將綜合后網(wǎng)表的基本單元映射為 具體f p g a 器件中的元件。首先，邏輯優(yōu)化將盡量消除冗余邏輯。接著，映射工 具將利用具體f p g a 的邏輯器件等價(jià)的替換綜合后網(wǎng)表中的器件。很多高效算法 都可以進(jìn)行這種轉(zhuǎn)化，例如【2 5 】 2 6 】。最后，打包工具將這些基本器件打包成f p g a 中的簇( c l u s t e r ) 。 布局( p l a c e m e n t ) 將工藝映射后的簇網(wǎng)表分配到具體f p g a 中的具體位置。 布局的目標(biāo)可以是降低線(xiàn)長(zhǎng)以提高布通率，也可以是優(yōu)化時(shí)序以提高電路性能。 1 4 第2 章可重構(gòu)計(jì)算系統(tǒng) 布局最多使用的是模擬退火( s i m u l a t e da m l e a l i n g ，s a ) 算法 2 7 】，但簡(jiǎn)單的s a 策略不能有效處理使用宏模塊的設(shè)計(jì)。【2 8 】提出的布局策略先對(duì)宏模塊進(jìn)行布局 規(guī)劃( n o o 印l a i l i l i n g ) ，然后再利用低溫模擬退火處理那些擁擠或時(shí)序不好的宏模 塊。 布線(xiàn)( r o u t i n g ) 負(fù)責(zé)布局后簇內(nèi)部和簇之間的互連。不同于a s i c ，f p g a 的 布線(xiàn)資源固定在預(yù)定義的布線(xiàn)通道內(nèi)。同布局一樣，布線(xiàn)也可以由擁擠度和時(shí)序 來(lái)驅(qū)動(dòng)，比較常見(jiàn)的布線(xiàn)算法有迷宮布線(xiàn)【2 9 】，p a d 正i n d e r 3 0 等。 后端流程的最后一步是生成f p g a 位流。該階段提供的一些特性直接為可重 構(gòu)計(jì)算開(kāi)辟新的應(yīng)用前景。例如利用x i l i n x 提供的j b i t sa p i ，設(shè)計(jì)者可利用j a v a 程序直接修改或創(chuàng)建新的位流，避免了執(zhí)行布局和布線(xiàn)的巨大時(shí)間消耗。j r o u t e 就是這樣一個(gè)例子【3 1 】。另外，j b i t s 還可與進(jìn)化算法結(jié)合來(lái)生成電路【3 2 】【3 3 】。 2 2 典型可重構(gòu)計(jì)算平臺(tái) 2 2 1s p l a s h 和s p l a s h 2 從概念上講，s p l a s h 和s p l a s h 2 可以看作由小的處理單元構(gòu)成的線(xiàn)性陣 列，這也使得s p l a s h 計(jì)算平臺(tái)非常適合于線(xiàn)性脈動(dòng)計(jì)算，如文本檢索 3 4 】、目 標(biāo)識(shí)別【3 5 】、邊緣檢測(cè)【4 】、數(shù)據(jù)庫(kù)檢索 3 6 】等應(yīng)用。s p l a s h2 系統(tǒng)包括一臺(tái)s u i l s p a r c 工作站，l 塊接口板，1 至1 6 塊s p l a s h 陣列板( 菊花鏈方式連接) 。圖2 6 為s p l a s h 2 計(jì)算平臺(tái)的結(jié)構(gòu)【3 】。 1 5 第2 章可重構(gòu)計(jì)算系統(tǒng) 布局最多使用的是模擬退火( s i m u l a t e da m l e a l i n g ，s a ) 算法 2 7 】，但簡(jiǎn)單的s a 策略不能有效處理使用宏模塊的設(shè)計(jì)?！? 8 】提出的布局策略先對(duì)宏模塊進(jìn)行布局 規(guī)劃( n o o 印l a i l i l i n g ) ，然后再利用低溫模擬退火處理那些擁擠或時(shí)序不好的宏模 塊。 布線(xiàn)( r o u t i n g ) 負(fù)責(zé)布局后簇內(nèi)部和簇之間的互連。不同于a s i c ，f p g a 的 布線(xiàn)資源固定在預(yù)定義的布線(xiàn)通道內(nèi)。同布局一樣，布線(xiàn)也可以由擁擠度和時(shí)序 來(lái)驅(qū)動(dòng)，比較常見(jiàn)的布線(xiàn)算法有迷宮布線(xiàn)【2 9 】，p a d 正i n d e r 3 0 等。 后端流程的最后一步是生成f p g a 位流。該階段提供的一些特性直接為可重 構(gòu)計(jì)算開(kāi)辟新的應(yīng)用前景。例如利用x i l i n x 提供的j b i t sa p i ，設(shè)計(jì)者可利用j a v a 程序直接修改或創(chuàng)建新的位流，避免了執(zhí)行布局和布線(xiàn)的巨大時(shí)間消耗。j r o u t e 就是這樣一個(gè)例子【3 1 】。另外，j b i t s 還可與進(jìn)化算法結(jié)合來(lái)生成電路【3 2 】【3 3 】。 2 2 典型可重構(gòu)計(jì)算平臺(tái) 2 2 1s p l a s h 和s p l a s h 2 從概念上講，s p l a s h 和s p l a s h 2 可以看作由小的處理單元構(gòu)成的線(xiàn)性陣 列，這也使得s p l a s h 計(jì)算平臺(tái)非常適合于線(xiàn)性脈動(dòng)計(jì)算，如文本檢索 3 4 】、目 標(biāo)識(shí)別【3 5 】、邊緣檢測(cè)【4 】、數(shù)據(jù)庫(kù)檢索 3 6 】等應(yīng)用。s p l a s h2 系統(tǒng)包括一臺(tái)s u i l s p a r c 工作站，l 塊接口板，1 至1 6 塊s p l a s h 陣列板( 菊花鏈方式連接) 。圖2 6 為s p l a s h 2 計(jì)算平臺(tái)的結(jié)構(gòu)【3 】。 1 5 第2 章可重構(gòu)計(jì)算系統(tǒng) 圖2 6s p l a s h 2 系統(tǒng)結(jié)構(gòu)圖 接口板包括4 路d m a 通道( 兩路輸入，兩路輸出) 。每路帶寬為5 0 m b y t e s ，s ， 通過(guò)2 5 6 個(gè)字的f i f o 與主機(jī)通信。用戶(hù)可以通過(guò)定制f p g a ( x l ，x r ) 來(lái)對(duì)輸入輸出數(shù)據(jù)進(jìn)行預(yù)處理，其時(shí)鐘主頻可以從1 0 k 4 0 m h z 選擇。 陣列板一共包括仃個(gè)處理單元( p r o c e s s i n g 日e m e n t s ，p e s ) ，處理單元 x 1 x 1 6 通過(guò)交叉開(kāi)關(guān)完成全互連，其輸入輸出由x 0 進(jìn)行管理。每個(gè)p e 包括一片x c 4 0 1 0 和5 1 2 k b y t e s 的存儲(chǔ)器，其中存儲(chǔ)器采用統(tǒng)一編址，可以 被主機(jī)直接訪(fǎng)問(wèn)。每個(gè)p e 可以通過(guò)3 6 位的數(shù)據(jù)總線(xiàn)與左右相鄰的p e 或者 交叉開(kāi)關(guān)通信。 主機(jī)的信息通過(guò)x l 和x 0 ( x 1 ) 之間的3 6 位s i m d 總線(xiàn)傳輸。多塊陣列