FPGA在演化硬件中的應(yīng)用

摘要：介紹了FPGA的新應(yīng)用一演化硬件（EHW）的進(jìn)展和現(xiàn)狀，其中主要包括EHW的概念、工作原理、存在問題和應(yīng)用領(lǐng)域。闡述了EHW在電路與系統(tǒng)學(xué)科中的科學(xué)意義及對新興電子信息產(chǎn)業(yè)將產(chǎn)生的深遠(yuǎn)影響。

關(guān)鍵詞：演化硬件 遺傳算法 FPGA

二十世紀(jì)70年代初出現(xiàn)了可編程邏輯器件（PLD），發(fā)展至今已出現(xiàn)簡單PLD（SPLD）、復(fù)雜PLD（CPLD）和現(xiàn)場可編程門陣列（FPGA）等各類器件。自1985年叛國Xilinx公司推出第一片F(xiàn)PGA以來，以今已有多家公司開發(fā)銷售自己的FPGA產(chǎn)品。FPGA有更高的集成度、更復(fù)雜的布線結(jié)構(gòu)和邏輯實(shí)現(xiàn)，它與以往的PLD之間的差別有于PLD一般是通過修改內(nèi)連電路的邏輯功能來實(shí)現(xiàn)編程的，而FPGA則是通過修改一根或多根內(nèi)連線來編程。FPGA的在線可編程技術(shù)（ISP）及動(dòng)態(tài)重構(gòu)技術(shù)進(jìn)一步提高了FPGA的應(yīng)用靈活性和自由度，重組及配置工作速度極快，從而為EHW的實(shí)現(xiàn)創(chuàng)造了堅(jiān)的實(shí)的物質(zhì)基礎(chǔ)。

1 EHW的概念

早在二十世紀(jì)50年代，計(jì)算機(jī)之父Von Neumann就提出了研制具有自繁殖與自修復(fù)能力并能進(jìn)行通用計(jì)算的機(jī)器的設(shè)想，這就是演化硬件的概念雛形。一直到演化算法和大規(guī)模PLD的出現(xiàn)，這一夢想才具備了實(shí)現(xiàn)的可能。1992年日本的Hugo de Garis和瑞士聯(lián)邦工學(xué)院的科學(xué)家同時(shí)正式提出了EHW的構(gòu)想[1]，短短幾年這一新的領(lǐng)域獲得了廣泛的關(guān)注，并且正處于急劇升溫之中。

EHW指的是在與外部環(huán)境相互作用之后，能自主地、動(dòng)態(tài)地改變自身結(jié)構(gòu)和行為的硬件電路。它具有自組織、自適應(yīng)、自修復(fù)功能，能適應(yīng)不同環(huán)境要求和提高自身性能。這一特性獲得主要?dú)w功于演化算法（Evolvable Algorithms,簡稱EAs）。

EaAs是一類模擬自然界遺傳進(jìn)化規(guī)律的仿生學(xué)算法，它們首先隨機(jī)產(chǎn)生一組待求優(yōu)化問題的潛在可能矢量解（解稱為染色體，解的集合稱為種群，解中的分量稱為基因）；然后采用變異、交叉、評價(jià)、選擇等手段，優(yōu)勝劣汰，不能進(jìn)化，最后獲得優(yōu)化解。作為一種優(yōu)化算法，它們也具有自適應(yīng)、自組織、自修復(fù)的特性，本身還具有隨機(jī)性和并行性。在搜索解空間時(shí)，能以很大概率找到全局解，不易陷入局部優(yōu)化點(diǎn)。嵌入問題方式簡單，尋優(yōu)魯棒性強(qiáng)，可以解決不連續(xù)、不可導(dǎo)、多目標(biāo)、帶各種約束條件的優(yōu)化問題，因而成為EHW演化的“發(fā)動(dòng)機(jī)”或“引擎”。

EHW的簡單定義為：演化算法+可編程邏輯器件。從目前EHW研究的內(nèi)容看，EHW具兩個(gè)方面的內(nèi)容：①根據(jù)功能或指標(biāo)的要求，采用EA技術(shù)對電路進(jìn)行合成，形成新電路結(jié)構(gòu)和參數(shù)。值得一提的是EA用于電路及系統(tǒng)設(shè)計(jì)由來已欠，但主要集中于利用電路參數(shù)設(shè)計(jì)電路板、布線、布局優(yōu)化等方面[2]，與本文所指的EHW有本質(zhì)區(qū)別。②具有自組織、自適應(yīng)自修復(fù)特性的硬件電路。此為EHW最吸引人的地方，其核心為“自適應(yīng)”。由于FPGA比以往PLD具有獨(dú)特的優(yōu)越性，目前大多數(shù)的EHW都采用FPGA器件。

2 EHW的實(shí)現(xiàn)方法和演化方式

從FPGA的原理可知，F(xiàn)PGA結(jié)構(gòu)可以最終描述為配置數(shù)據(jù)。因此對FPGA的演化，最終可歸結(jié)為對配置數(shù)據(jù)的演化，整個(gè)演化過程大約可描述成如下步驟：

①設(shè)定EA參數(shù)，如交叉率、變異率、種群數(shù)等；

②隨機(jī)產(chǎn)生初始化種群Xi={xi1,xi2,…，xiR}，其中1≤i≤POP_SIZE；Xi為染色體，代表FPGA結(jié)構(gòu)編碼，如二進(jìn)制串等；R為基因總數(shù)；

③評價(jià)種群中的各染色體，獲取相應(yīng)的適應(yīng)度函數(shù)值；

④以某種方式選擇部分種群，按指定的變異率、交叉率進(jìn)行交叉、變異，形成新的子染色體；

⑤評價(jià)表的染色體，與父代染色體一起按適應(yīng)度函數(shù)值大小選出POP_SIZE的個(gè)體染色體作為下一代種群；

⑥判別是否滿足終止條件：是，結(jié)束；否，回到④重復(fù)演化過程。

EA染色體編碼方式是影響EA計(jì)算速度和有效性的重要因素。根據(jù)編碼方式和級(jí)別的不同，可將EHW進(jìn)化方式分為三類：直接型、間接型和函數(shù)型。直接型的任務(wù)是直接進(jìn)化結(jié)構(gòu)位串以改變門級(jí)電路的連接。結(jié)構(gòu)位串為染色體，通過專用的軟件工具，下載到FPGA中，以獲得新的電路，如圖1所示[3]。這種演化層次屬于門級(jí)水平，缺點(diǎn)是染色體的表示過于龐大。一般情況下（不考慮其他結(jié)束條件），n個(gè)邏輯門的進(jìn)化，染色體的串位數(shù)為O（n2）數(shù)量級(jí)，無論是表示或進(jìn)化都是十分困難的。間接型的任務(wù)并不直接進(jìn)化結(jié)構(gòu)位串，它采用了高級(jí)的表達(dá)方式，即用樹或法則產(chǎn)生電路。文獻(xiàn)[4]提供了一個(gè)很典型的例子，它采用了硬件描述語言（HDL）程序?qū)崿F(xiàn)一個(gè)二進(jìn)制加法器，染色體為按規(guī)則產(chǎn)生的衍生樹（derivationtree），樹的所有可能結(jié)果鈄與電路結(jié)構(gòu)的所有可能結(jié)果一一對應(yīng)。每一個(gè)樹可以產(chǎn)生一個(gè)結(jié)構(gòu)功能描述程序塊，如果該樹是合活的話，則將衍生出HDL的EHW結(jié)構(gòu)描述程序。EA的交叉、變異等算子對樹的作用與一般的EA算法對二進(jìn)制串的作用相似，但EA進(jìn)化含有結(jié)束條件，以確保樹（或程序）的合法性。這種方法降低了結(jié)構(gòu)位串造成的計(jì)算復(fù)雜度，因此在實(shí)際EHW中應(yīng)用較多。函數(shù)型進(jìn)化也是另一種降低EA復(fù)雜性的方法，也屬于高級(jí)表達(dá)，其進(jìn)化的基本元素不是門電路，而是個(gè)基本的功能模塊，如加、減模塊等。這樣既可以獲得更為復(fù)雜功能的電路，又不增加EA進(jìn)化的困難。當(dāng)然，其在FPGA中占用門電路資源要比前兩種方法多，電路結(jié)構(gòu)不很精簡。

對染色體的評價(jià)方式分為外向型和內(nèi)向型兩種。外向型的EA是在仿真環(huán)境中用軟件進(jìn)行的，染色體的評價(jià)值由仿真給出，只將每代最佳的染色體（配置數(shù)據(jù)）才載到FPGA中，即在每代EA過程結(jié)束后EHW才重組一次。而內(nèi)向型則將每代種群中的每個(gè)染色體都下載到FPGA中，把實(shí)際運(yùn)行結(jié)果作為評價(jià)值，具有真實(shí)性，顯然EHW重組的次數(shù)等于種群數(shù)的大小。

EHW的自適應(yīng)工作方式分為在線自適應(yīng)和離線自適應(yīng)兩種。在線自適應(yīng)又稱為實(shí)時(shí)自適應(yīng)，其學(xué)習(xí)過程、進(jìn)化過程和運(yùn)作過程是同步進(jìn)行的。離線自適應(yīng)則把實(shí)際工作和進(jìn)化過程分為兩個(gè)獨(dú)立的階段，一般先做進(jìn)化設(shè)計(jì)，后投入實(shí)際工作。

3 演化硬件存在的問題和發(fā)展前景

EHW是一個(gè)新生事物，尚有許多不成熟和亟待解決問題。EHW的在線自適應(yīng)方法還不完善。EA的特點(diǎn)就是是要重復(fù)進(jìn)行“試湊性”的實(shí)驗(yàn)，在試湊過程中可能產(chǎn)生劣質(zhì)的染色體，造成系統(tǒng)嚴(yán)重的故障和災(zāi)難（如果不采取適當(dāng)?shù)姆婪洞胧┑脑挘蚨?dāng)前報(bào)道的實(shí)例大多數(shù)屬于離線自適應(yīng)。解決方法是建立專家識(shí)別或仿真環(huán)境，從中提前判別和濾去可能對環(huán)境造成危害的劣質(zhì)染色體，從而保證系統(tǒng)安全。

目前成功應(yīng)用的EHW電路規(guī)模都比較小，這主要是因?yàn)镋A算法復(fù)雜性隨EHW元件數(shù)的增加呈非線性上升趨勢，計(jì)算量變得不可忍受。解決的辦法是尋求更為有效的EA，如新的染色體編碼方式或硬件加速器[5]等。適應(yīng)度函數(shù)的選取也是一個(gè)值得注意的問題，高適應(yīng)度的結(jié)果并不一定能保證電路的完整和正確性，因?yàn)镋A畢竟無法將所的輸入都做一番試湊性的實(shí)驗(yàn)，為提高EHW的正確性而付出的計(jì)算成本將大幅增加。這一問題還引發(fā)了EA結(jié)束判定準(zhǔn)則難以確定的問題。另外，EHW強(qiáng)調(diào)的是終結(jié)果達(dá)到目標(biāo)要求，而電路內(nèi)部的結(jié)構(gòu)、設(shè)計(jì)原理等對用戶來講屬于“黑箱”的范疇，因而一旦EHW發(fā)生故障，人工無法修理補(bǔ)救，解決的方向是采用自修復(fù)的EHW。

從某種意義上余，EHW給系統(tǒng)和電路科學(xué)帶來了革命性的理念和突破，作為新的電路設(shè)計(jì)手段，它能提供人工意想不到的設(shè)計(jì)方案，設(shè)計(jì)人員主要思考要完成什么電路、實(shí)現(xiàn)什么功能，而不是過多地考慮如何實(shí)現(xiàn)實(shí)。該方法對專業(yè)化的先驗(yàn)知識(shí)要求不高，特別善于處理特殊和復(fù)雜的約束條件（可通過EA的染色體及適應(yīng)度函數(shù)靈活地表達(dá)出來），因此可大大減輕了工勞動(dòng)負(fù)擔(dān)，有效地提高產(chǎn)品質(zhì)量。作為一種新的自適應(yīng)電路，EHW在機(jī)器學(xué)習(xí)、人工神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、信號(hào)處理與識(shí)別、容錯(cuò)系統(tǒng)和機(jī)器人等方面有廣闊的應(yīng)用前景。從1992年到現(xiàn)在，已有不少獲得實(shí)際應(yīng)用和總商品化的例子，如EHW制成的控制器成功地實(shí)現(xiàn)了假肢控制[6]；EHW取代神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了高速的模式辯識(shí)，結(jié)果比神經(jīng)網(wǎng)絡(luò)好[7]；EHW芯片實(shí)現(xiàn)了（電極采色打印機(jī)）數(shù)據(jù)壓縮[7]等。也有人大膽地設(shè)想，隨著EHW技術(shù)的發(fā)燕尾服，新型計(jì)算機(jī)可實(shí)現(xiàn)自動(dòng)升級(jí)[8]。