演化硬件的實(shí)現(xiàn)方式

1、0 引言演化硬件（Evolvable Hardware），簡稱EHW或E-Hard。它是一種硬件電路（現(xiàn)在是一種大規(guī)模集成電路），其能夠像生物一樣根據(jù)環(huán)境的變化而改變自身的結(jié)構(gòu)以適應(yīng)其生存環(huán)境，具有自組織、自適應(yīng)、自修復(fù)功能。演化硬件這一概念是在1992年由日本Hugo de Garis和瑞士聯(lián)邦工學(xué)院同時(shí)正式提出【1】，從而初步實(shí)現(xiàn)了早在20世紀(jì)50年代計(jì)算機(jī)之父John Von Neumann所提出的關(guān)于研制具有自繁殖與自修復(fù)能力的機(jī)器的設(shè)想【2】。經(jīng)過十幾年的發(fā)展，隨著對演化硬件的研究的不斷深入，人們愈發(fā)地認(rèn)識到演化硬件在未來科技發(fā)展中的重要性。演化硬件的實(shí)現(xiàn)，建立在演化算法和可編程邏輯

2、器件發(fā)展的基礎(chǔ)之上?？删幊踢壿嬈骷脱莼惴ǖ目焖侔l(fā)展極大地推動和促進(jìn)了演化硬件的實(shí)現(xiàn)進(jìn)程。演化算法為演化硬件提供了理論和方法學(xué)基礎(chǔ)；可編程邏輯器件（Programmable Logic Device）為演化硬件提供了物質(zhì)基礎(chǔ)。由于演化過程具有隨機(jī)性，進(jìn)化次數(shù)較多，從而要求相應(yīng)的器件也要能夠被反復(fù)配置，因此可以無窮次重復(fù)配置的現(xiàn)場可編程門陣列（Field Programmable Gate Array）也就成為當(dāng)前比較理想的實(shí)現(xiàn)器件，目前FPGA器件為大多數(shù)的演化硬件所采用。1主流演化算法（Evolvable Algorithm） 在演化硬件中所使用的算法主要分為以下三類：遺傳算法（GA），遺

3、傳規(guī)劃（GP）和演化策略（ES）。當(dāng)前使用較多的演化算法主要有CGP【3】（Cartesian Genetic Programming）、*CGA【4】（A family of Compact Genetic Algorithms）、CoCGA【5】（Cooperative Compact Genetic Algorithms）和CCGA【6】（Cellular Compact Genetic Algorithms）。CGP算法使用一個(gè)m行n列的細(xì)胞陣列來表示染色體，陣列中每一個(gè)細(xì)胞都是一個(gè)功能單元，如非門、或門等。每個(gè)細(xì)胞的輸入限于前一個(gè)細(xì)胞的輸出。該陣列有三個(gè)參數(shù)：輸入數(shù)目，輸出數(shù)目和L-

4、back ，其中L-back參數(shù)決定了細(xì)胞單元的最左列。*CGA是對CGA的一系列改良，使用較為廣泛。CGA使用概率變量（probability vectors）描述種群，與傳統(tǒng)的GA不同。傳統(tǒng)的GA采用一系列位串來描述候選解決方法種群，以致于在硬件實(shí)現(xiàn)時(shí)，需要消耗大量的資源，且實(shí)現(xiàn)過程相對較為復(fù)雜。而CGA減少了種群所需的存儲資源，在硬件實(shí)現(xiàn)時(shí)不需要使用RAM，僅僅使用D觸發(fā)器實(shí)現(xiàn)的寄存器即可。但是CGA的標(biāo)準(zhǔn)形式只能用來解決一階簡單問題，其搜索能力不足，不適合現(xiàn)實(shí)EHW的應(yīng)用實(shí)現(xiàn)，同時(shí)CGA在準(zhǔn)確度和處理速度上也存在不足。*CGA是通過對CGA在精英策略、染色體突變、優(yōu)勝再采樣幾方面的改良

5、而實(shí)現(xiàn)，更加適合于現(xiàn)實(shí)EHW的應(yīng)用實(shí)現(xiàn)。CoCGA由一組CGA構(gòu)成，各CGA之間進(jìn)行協(xié)同運(yùn)算。CoCGA具有更強(qiáng)大的搜索能力，收斂速度更快，計(jì)算更精確，同時(shí)更適合于FPGA實(shí)現(xiàn)。CCGA基于并行遺傳算法，為概率建模遺傳算法的一種，其基本思想是將一個(gè)問題劃分為多個(gè)子任務(wù)，然后同時(shí)使用多重遺傳算法解決這些任務(wù)。CCGA具有統(tǒng)一的細(xì)胞結(jié)構(gòu)，每個(gè)細(xì)胞只與其鄰近的細(xì)胞有聯(lián)系，演化分級到各個(gè)細(xì)胞進(jìn)行，并且適應(yīng)概率變量復(fù)合。CCGA與協(xié)同CGA相似，但是比CGA更加適合于FPGA實(shí)現(xiàn)。2 EHW的實(shí)現(xiàn)2.1 硬件方面實(shí)現(xiàn)演化硬件的芯片可分為商業(yè)FPGA芯片和專用演化芯片。商業(yè)FPGA芯片的內(nèi)部結(jié)構(gòu)不公開，不

6、能接收隨機(jī)配置位串，重構(gòu)過程依賴于廠商提供的軟件工具?；谏虡I(yè)FPGA芯片進(jìn)行內(nèi)部演化，需要利用廠商提供的工具軟件對演化產(chǎn)生的隨機(jī)配置位串加以過濾，只將FPGA芯片內(nèi)部結(jié)構(gòu)允許的配置位串用于FPGA芯片的配置，以避免不合法的配置對器件造成損壞。模擬電路的演化大多采用自制的由分立元器件組成的實(shí)驗(yàn)平臺。當(dāng)前主要用于演化硬件研究的芯片及平臺有Xilinx Virtex系列FPGA芯片、Xilinx Virtex- Pro FPGA芯片、RISA平臺【7】以及FPTA【8】拓?fù)浣Y(jié)構(gòu)平臺。Xilinx Virtex-II Pro FPGA芯片，可利用片上的Power PC微處理器硬核執(zhí)行演化算法，并在同

7、一片F(xiàn)PGA上演化生成電路，從而減少演化操作相關(guān)的數(shù)據(jù)傳輸時(shí)間對演化電路生成時(shí)間所造成的影響。RISA（Reconfigurable Integrated System Array）平臺是FPGA芯片和微型控制器陣列（microcontroller array）的組合，如圖1所示。RISA平臺使用4個(gè)連續(xù)的數(shù)據(jù)鏈配置系統(tǒng)，并且數(shù)據(jù)鏈成對使用，其中一條替換實(shí)際配置數(shù)據(jù)，另一條對要替換的部分進(jìn)行標(biāo)識。該平臺能夠?qū)崿F(xiàn)快速的細(xì)粒度的局部配置，配置系統(tǒng)簡單、快速，并且提供了不建立在商業(yè)FPGA芯片上的控制級。圖1 RISA的結(jié)構(gòu)圖FPTA（Field Programmable Transistor Ar

8、ray）拓?fù)浣Y(jié)構(gòu)首先由美國噴氣發(fā)動機(jī)推進(jìn)實(shí)驗(yàn)室（JPL）提出，是一種細(xì)粒度的可重構(gòu)結(jié)構(gòu)。芯片可以在晶體管級進(jìn)行重構(gòu)，構(gòu)建的可編程晶體管陣列既可以生成模擬電路又可以生成數(shù)字電路。FPTA每個(gè)單元由8個(gè)晶體管組成，內(nèi)部采用24個(gè)開關(guān)連接，如圖2所示，用來演化各種電路，包括數(shù)字門，跨導(dǎo)放大器，運(yùn)算電路等等，對產(chǎn)生新的電路如混合演化、多態(tài)電子以及電路修復(fù)發(fā)揮了極大的作用。FPTA的單元是一個(gè)通過可編程開關(guān)相互連接的晶體管陣列，每個(gè)單元可以在晶體管級進(jìn)行配置，以實(shí)現(xiàn)不同的模擬和數(shù)字功能，而開關(guān)的狀態(tài)決定了線路的拓?fù)浜妥罱K的響應(yīng)。因此，這個(gè)拓?fù)淇梢杂瞄_關(guān)狀態(tài)的方程加以考慮，可以用二進(jìn)制序列來表示，如“l(fā)0

9、l1”，1表示開關(guān)閉合，0表示開關(guān)斷開。圖2 FPTA單個(gè)細(xì)胞的結(jié)構(gòu)圖2.2 軟件方面 由于商業(yè)FPGA芯片需要通過廠商提供的工具軟件來完成對其內(nèi)部結(jié)構(gòu)的配置， Xilinx公司設(shè)計(jì)出支持在商業(yè)FPGA芯片上進(jìn)行演化的軟件工具鏈，包括GeneticFPGA、JBits和XHWIF（Xilinx HardWare Interface），其演化過程如圖3所示，當(dāng)前種群中的每一個(gè)染色體經(jīng)過JBits轉(zhuǎn)換為合法的配置位串并加入相應(yīng)的測試向量形成配置信息，通過XHWIF接口下載到FPGA芯片中，經(jīng)過規(guī)定時(shí)間后再通過XHWIF接口回讀FPGA芯片內(nèi)部狀態(tài)位串，由JBits轉(zhuǎn)換后就得到了該染色體的適應(yīng)度值。

10、圖3利用工具軟件的演化過程JBits由一系列的Java類庫組成，可以控制位流配置數(shù)據(jù)的產(chǎn)生，并提供了能夠直接訪問Xilinx Virtex-II(tm) FPGA芯片位流結(jié)構(gòu)文件的應(yīng)用程序接口（API）。API可以用來構(gòu)建能夠在Xilinx Virtex-II FPGA芯片內(nèi)部執(zhí)行的數(shù)字電路設(shè)計(jì)和參數(shù)核。同時(shí)API還提供了對Virtex-II結(jié)構(gòu)的最底層的接口，因此它也能充當(dāng)基礎(chǔ)來構(gòu)造傳統(tǒng)電路的布局和布線，并且應(yīng)用針對性的工具來完成更為精細(xì)的規(guī)定任務(wù)。JBits程序流程包括以下步驟，首先創(chuàng)建一個(gè)JBits對象，然后輸入配置位流到JBits對象，再根據(jù)設(shè)計(jì)數(shù)據(jù)改變配置位流，最后輸出設(shè)計(jì)的配置位流

11、。JBits可單獨(dú)使用，也可用作開發(fā)其他工具的基礎(chǔ)。JBits3.0版本支持Virtex-系列芯片，允許對該系列的FPGA芯片中所有的可設(shè)置參數(shù)進(jìn)行編程存取。XHWIF提供了與FPGA硬件通信的便捷的硬件接口。XHWIF API可以通過多種方法來描述FPGA單板，并且發(fā)送數(shù)據(jù)開啟和關(guān)閉單板。其中包括對FPGA芯片的配置位流進(jìn)行讀寫、表述單板上FPGA芯片的種類和數(shù)目、增加單板時(shí)鐘，以及在單板存儲器存在時(shí)對其進(jìn)行讀寫操作。當(dāng)XHWIF API與指定的單板相連接時(shí)，XHWIF接口能夠?qū)崿F(xiàn)與FPGA單板之間的通信交流。一旦API連接到指定的單板上，那些通過XHWIF API實(shí)現(xiàn)各種硬件單板操作的工具

12、和應(yīng)用就能夠在最近被支持的硬件部分上運(yùn)行，而且不需要再進(jìn)行編譯。3 發(fā)展趨勢搜索空間的規(guī)模和復(fù)雜性是影響演化速度的重要因素，同時(shí)可擴(kuò)展性問題也在很大程度上限制了演化硬件（EHW）在現(xiàn)實(shí)中的應(yīng)用。為了解決以上問題，實(shí)現(xiàn)大規(guī)模復(fù)雜電路的演化，當(dāng)前演化硬件的發(fā)展趨勢主要集中在以下幾個(gè)方面：細(xì)胞分層、分級獨(dú)立演化、實(shí)時(shí)自適應(yīng)性、在片演化（System on chip）。當(dāng)前解決以上問題的方法【9】主要有變長染色體、分級演化、函數(shù)級模塊（Function Building Blocks）、雙指向遞增演化（BIE）、通用分離分解（GDD）和逐步降維壓縮（SDR）。另外，尋找適合于硬件實(shí)現(xiàn)的演化算法，通過對

13、算法的硬件化，來減少硬件演化所需的時(shí)間，也是一種提高整個(gè)演化系統(tǒng)實(shí)時(shí)性的途徑。參考文獻(xiàn)【1】 H.de Garis.Evovable hardware:Genetic programming of a Darwin1993,pp.441-449【2】 J.von Neumann.Theory of Self-Reproducing Automata. A. W.Burks Ed.Urbana,IL:Univ.of Illinois Press,1966【3】 Miller, J.F., Thomson, P.: Cartesian genetic programming. In: Poli,

14、R., Banzhaf,W., Langdon, W.B., Miller, J., Nordin, P., Fogarty, T.C. (eds.) EuroGP 2000.LNCS, vol. 1802, pp. 121-132. Springer, Heidelberg (2000).【4】 John C. Gallagher, Saranyan Vigraham, and Gregory Kramer.A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware. IEEE Transcations on

15、 Evolutionary Computation, vol. 8, No. 2, April 2004,pp.111-127.【5】 Yutzina Jewajinda, Prabhas Chongstitvatana. A Cooperative Approach to Compact Genetic Algorithm for Evolvable Hardware. 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada July

16、16-21, 2006.【6】 Yutana Jewajinda,Prabhas Chongstitvatana.Celluar compact genetic algorithm for evovable hardware.Proceedings of ECTI-CON 2008.【7】 Andrew J. Greensted，Andy M. Tyrrell. RISA: A Hardware Platform for Evolutionary Design. Proceedings of the 2007 IEEE Workshop on Evolvable and Adaptive Hardware (WEAH 2007).【8】 A. Stoica, R. Zebulum, D. Keymeulen, R. Tawel, T.Daud, and A. Thakoor, “Reconfigurable VLSI Architectures for Evolvable Hardware: from Experimental Field Programmable Transistor Arrays to Evolution-Oriented Chips”, IEEE Transactions on VLSI Systems, Special Issue on R