進化硬件發展綜述

鮑治國，孫 楠

(河南財經政法大學計算機與信息工程學院，河南鄭州，450046)

進化硬件發展綜述

鮑治國，孫 楠

(河南財經政法大學計算機與信息工程學院，河南鄭州，450046)

進化硬件是進化算法和可編程芯片相結合的研究熱點。介紹了進化硬件的由來和基本概念，總結了國內外主要研究者的研究成果。分析了進化硬件發展中面臨的問題，討論了解決對策，展望了發展前景。

進化硬件；進化算法；數字電路優化設計

0 引言

從二十世紀九十年代初，用于硬件設計的進化硬件（Evolvable Hardware，EHW）[1-6]開始興起了。進化硬件可以分為兩類：電路的進化設計和自適應系統。電路的進化設計是，用進化算法設計出符合預期要求的電路；自適應系統是，重構現有的系統使其可以容錯或者適應環境的變化。進化硬件技術可以作為一種替代傳統硬件設計技術的選擇。

隨著現場可編程陣列(Field Programmable Gate Array, FPGA)的出現，關于進化硬件的研究開始火熱了。在許多方面，進化硬件都表現的比較成功和有前景，因為它可以通過進化算法自動的生成電路。通過進化硬件可以產生多種數字電路，如：加法器，乘法器，神經網路，機器控制器，交通信號分類器，數字圖像濾波器，等。

1 國外發展狀況

1992年，日本學者Garis H de和瑞士聯邦工學院的科學家們同時提出了將FPGA的結構可重配置特性與進化算法相結合的方案，標志著進化硬件這一新興研究領域的正式誕生[7,8]。1995年10月在瑞士洛桑召開了進化硬件國際專題會議(Towards Evolvable Hardware)。1996年在日本筑波召開了第一屆國際進化系統會議(International Conference on Evolvable Systems，ICES)，1998年在瑞士召開了第二屆ICES會議，2000年在英國召開了第三屆ICES會議。1999年前，硬件進化技術的研究主要在歐洲和日本。1999年，美國國家航空航天局(NASA)與美國國防部(DoD)成立了進化硬件小組，召開NASA／DoD Conference on Evolvable Hardware(EH)會議；從2006年起，該會議由NASA／ESA Conference on Adaptive Hardware and Systems(AHS)取代，每年舉辦1次。從2007年起，由計算機智能協會發起并召開的IEEE WEAH (Workshop on Evolvable and Adaptive Hardware)會議，主要關注進化硬件的自適應性和容錯系統。

目前，美國在EHW理論與應用研究方面取得了較大的進展，在這一領域已處于國際領先地位。此外，相關的國際會議還包 括 Genetic and Evolutionary Computation Conference (GECCO)、IEEE Congress on Evolutionary Computation (CEC)、European Conference on Genetic Programming等。許多國際知名的學術刊物對于EHW領域的研究和進展重點進行了刊登和報道，如德國Springer出版社專門用于刊登EHW領域文章的 Genetic Programming and Evolvable Machines、美國 ACM的 ACM Transactions on Design Automation of Electronic Systems、IEEE Transactions on Evolutionary Computation、IEEE Transactions on Systems Man and Cybernetics 等。此外，IEEE Transactions on Computer 于2013年門推出一期特刊 “Adaptive Hardware and Systems”用于EHW領域研究進展與成果的報道。

目前，國際EHW研究領域主要的研究機構及其研究成果概述如下。

(1)美國NASA噴氣動力實驗室（JPL)：主要從事模擬電路進化設計、EHW平臺設計[9]，致力于未來NASA太空任務中硬件對于未知環境（極端溫度和輻射）的容忍和自適應能力以及硬件的長時間生命存活能力研究[10,11]。其研究成果不僅提高了EHW的仿真和實驗技術，更重要的是在芯片級別設計及實現了一系列晶體管級的模擬和數字電路。

Stoica等發表了關于晶體管級EHW的研究成果[12]并申請了專利（Patent NO:US 6728666 Bl),利用DSP(Digital Signal Process，數字信號處理)芯片運行遺傳算法作為可重構機制控制架在一塊自容式電路板上的EHW平臺，快速可重構使得算法在數秒內實現了收斂。進化結果表明，采用JPL開發的FPTA-2芯片，通過進化方式硬件電路功能能夠從極端溫度或輻射環境中恢復，在230度高溫及250kRad輻射下仍能正常工作。Fernando等在Xilinx Virtex FPGA(Field－Programmable Gate Array，現場可編程門陣列)上構造了一個片上實現GA(Genetic Algorithm，遺傳算法)的IP核，不僅能夠實現通用的GA引擎，還能根據種群大小、進化代數等參數實現用戶定制功能，具有可編程、占用空間小及低功耗的優點[13]。Keymeulen等利用JPL的EHW系統及FPTA(可編程晶體管陣列，Field Programmable Transistor Array)芯片實現了具有信號分離與噪聲抑制功能電路的在片進化[14]。為了確保在太空的極端溫度條件下電路能夠正常工作，Zebulum等利用EHW對于環境變化的自適應特性，通過電路重構保證系統在液氮低溫達-196.6°C及高溫280°C的情況下仍能正常工作[10]。此外，Stoica等首先提出了多態電路及多態電子學的概念并設計了一系列多態門，開啟了EHW領域的一個重要發展方向及應用領域[15]。

(2)捷克Bmo科技大學FIT演化硬件研究小組:主要致力于多態電路設計及應用、濾波器設計、多態芯片設計等方面的研究[16-18]。

Sekanina于2005年率先將多態門應用于門級多態電路進化設計，利用多態門的功能轉換特性實現了硬件電路對于特定環境變化的自動響應[19]，隨后，又將多態電路應用于圖像濾波器設計[17]及容錯系統設計中的自動檢測問題[20]。Gajda等通過結合傳統設計方法與進化方法進行了多態電路設計，提高了設計方法的可擴展性[18]。Vasicek等針對衛星圖像傳輸中常出現的脈沖突發噪聲（impulse burst noise)，利用擴展形式的笛卡爾遺傳規劃(Cartesian genetic programming, CGP)減少了進化方法輸入個數，設計了一種具有5x5像素濾波窗口的圖像濾波器，其性能優于傳統中值濾波器[21]。Vasicek等針對進化方法適應度評價時間過長、影響算法可擴展性的問題，利用基于SAT (Satisfiability,可滿足性)的功能等價校驗方法替代原有適應度評價方法，將其應用于電路后綜合優化階段，減少了評價時間及資源消耗[16,22]。FIT演化硬件研究小組于2008年設計制造了第一款能夠用于小型多態電路設計的可重構多態模塊（REP0M032)芯片，實現了多態電路內部進化設計，為研究多態電路實際電路特性及應用提供了平臺[23]。

(3)日本的ETL:主要將EHW用于模式識別、容錯、圖像壓縮及人工手設計等方面[24]。

Higuchi等在原有門級電路進化基礎上提出了函數級電路進化設計方法，提高了進化設計方法可擴展性及進化規模，并利用該方法研究了用于數字移動通信的自適應均衡器及有損數據壓縮等[25]。ETL演化系統實驗室設計了多種EHW芯片用于實際應用[26]:在門級電路方面，如用于人工手控制及機器人導航的芯片，用于打印機的數據壓縮芯片；在函數級電路方面，如用于神經網絡自動重構的EHW芯片；除了上述三種用于數字電路進化的芯片外，還研制了用于模擬電路的EHW芯片。如在外部進化模式下，用于移動電話制造的EHW芯片，其生成的電路具有低功耗、低生產成本的特點，以及用于保證高速數字系統時鐘分配精確度的時鐘延遲調整芯片。

(4)英國York大學：主要致力于EHW中進化算法的研究和應用。

Miller于2000年提出了后來被廣泛應用于數字電路進化設計領域的CGP。Walker等在CGP基礎上，借鑒了遺傳規劃(genetic programming, GP)中的自定義功能（ADF)，通過將相鄰邏輯門裝配成可共享模塊的方法提高了CGP的性能[27]。Harding等提出了自修改笛卡爾遺傳規劃（SMCGP)用于解決進化設計方法擴展性問題，隨著電路復雜度的增加通過表現型電路自動修改完成求解過程[28]。

(5)此外，還有如日本Hugo de garis 領導的 CAM-Brain (Cellular Automata Machines, CAM)項目組[29],英國 Sussex大學[30],美國 Stanford 大學[31]等眾多的研究機構致力于EHW領域的研究。

2 國內發展現狀

國內開展EHW 的研究起步較晚，國內少數單位的研究人員也開始對進化硬件進行研究。國內學者主要集中于研究算法的改進以及采用基于模型的軟件仿真，但是越來越多的研究者開始利用更符合進化硬件研究發展趨勢的進化技術或者自行研究適合進化的硬件平臺。

國內主要的研究機構包括：中國地質大學、深圳大學、中國科學技術大學，武漢大學、南京航空航天大學、西安電子科技大學等。

中國地質大學（武漢）的康立山教授等研究了三維“人工腦”模型，并提出了以樹型結構函數可編程器件作為EHW的結構[32]。深圳大學的朱明程教授等以國家自然科學基金項目“現場可編程門陣列系統動態可重構技術的關鍵問題研究”（編號：NO.69976020)為背景，主要進行FPGA動態可重構技術及其基礎上的數字電路系統容錯研究[33]。中國科學技術大學王照法教授等在國家自然科學基金項目“進化型硬件理論與應用研究”（編號：NO. 60404004)的資助下，主要進行EHW中電路進化設計、進化型SOC及容錯系統研究[34]。武漢大學李元香教授等承擔的國家自然科學基金項目“軟硬件協同的自主進化技術及其系統”（編號：NO. 60773009),進行了容錯系統、元胞自動機及進化算法等的研究和應用[35,36]。南京航空航天大學王友仁教授等依托國家自然科學基金項目“芯片級自修復數字系統體系結構與自愈機制研究”（編號：NO. 60871009)，主要進行容錯系統及量子可逆邏輯電路進化設計的研究[37]。西安電子科技大學的趙曙光教授等對于進化算法進行了重點研究，將其用于數字與模擬電路進化設計，并提出了基于函數級進化的“最小項編碼”方法[38,39]。

3 進化硬件所面臨的挑戰

作為一個新興的研究領域，進化硬件前景廣闊，但仍面臨著巨大挑戰。數字電路進化設計面臨的最大挑戰就是進化方法擴展性問題，主要表現在兩個方面。

3.1 表達擴展性問題

隨著待求解問題復雜度的提高，實現電路功能所需資源及對其結構進行編碼的染色體長度不斷增加，造成算法搜索空間加大，影響進化方法有效性。

在現有電路編碼方式下，受限于搜索空間，染色體的長度約在幾百位，進化電路仍局限于乘法器等簡單電路。隨著問題越來越復雜，基因型的長度也隨之增長，伴隨著搜索空間的指數增長，從而增加了求解問題的難度。目前己有一些文獻致力于解決該問題，概括起來有以下兩個方向：一是研究新的染色體編碼方案和進化算法；二是研究新的電路分解方法。電路編碼方面提出了可變長度的染色體編碼方法(Variable-based Genetic Algorithm，VGA)[40],函數級的編碼方法[41]以及間接的“基因型一表現型”方法等。在電路分解方面主要有雙向增量進化算法(Bidirectional Incremental Evolution，BIE)[42]和廣義分解析取算法(Generalised Disjunction Decomposition，GDD)等。這些方法從一定程度上緩解了問題，但距離實際應用還有不少的差距。

3.2 評價擴展性問題

候選電路適應度評價時間隨著輸入輸出個數的增加呈指數級別的增長，這也是進化方法設計復雜電路的主要瓶頸。

進化算法在搜索最優解的過程中的耗時和適應度評估時的耗時是影響進化速度的主因。對于復雜系統，評估時的耗時對進化速度的影響更大。在改進算法執行速度方面，軟件上已有基于硬件實現的進化算法[13]和基于并行計算等算法，硬件上圖形處理器(Graphic Processing Unit，GPU)[43]的運用，都加快了進化硬件的執行速度，不過并未從根本上解決該問題。

4 結束語

進化硬件是進化算法和可編程芯片相結合的研究熱點。本文介紹了進化硬件的由來和基本概念，總結了國內外主要研究者的研究成果。分析了進化硬件發展中面臨的問題，討論了解決對策，展望了發展前景。

[1] Schwartz J T, Burks A W. Theory of Self-Reproducing Automata[J].The Quarterly Review of Biology, 1967, 21(Volume 42, Number 4)：745.

[2] 趙曙光,劉貴喜,楊萬海.可進化硬件的基本原理與關鍵技術[J].系統工程與電子技術,2002, 24(1)：70-73.

[3] 陳利光.適合于硬件進化的FPGA平臺設計實現[D].復旦大學,2009.

[4] 紀震,田濤,朱澤軒.進化硬件研究進展[J].深圳大學學報理工版,2011,28(3)：255-263.

[5] Chiong R, Weise T, Michalewicz Z. Variants of Evolutionary Algorithms for Real-World Applications[M]. Springer Berlin Heidelberg, 2012.

[6] Sironi F, Cuoccio A, Hoffmann H, et al. Evolvable systems on reconfigurable architecture via self-aware adaptive applications[C]// Adaptive Hardware and Systems. IEEE, 2011：176-183.

[7] Garis H D. EVOLVABLE HARDWARE Genetic Programming of a Darwin Machine[M]// Artificial Neural Nets and Genetic Algorithms. Springer Vienna, 1993：441-449.

[8] Sekanina L. Evolvable Hardware[M]. Springer Berlin Heidelberg, 2012.

[9] Stoica A, Keymeulen D, Zebulum R, et al. Adaptive and evolvable analog electronics for space applications[J]. Lecture Notes in Computer Science, 2007, 4684：379-390.

[10] Imran N, Demara R F, Lee J, et al. Self-Adapting Resource Escalation for Resilient Signal Processing Architectures[J]. Journal of Signal Processing Systems, 2014, 77(3)：257-280.

[11] Siddhartha, Krishna G, Jalali-Farahani B. A fast settling Slew Rate Enhancement technique for operational amplifiers[C]// IEEE International Midwest Symposium on Circuits and Systems. IEEE Xplore, 2010：965-968.

[12] Stoica A, Zebulum R, Keymeulen D, et al. Transistor-Level Circuit Experiments Using Evolvable Hardware[M]// Artificial Intelligence and Knowledge Engineering Applications： A Bioinspired Approach. Springer Berlin Heidelberg, 2005：366-375.

[13] Fernando P R, Katkoori S, Keymeulen D, et al. Customizable FPGA IP core implementation of a generalpurpose genetic algorithm engine[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(1)：133-149.

[14] Mohanty B K, Meher P K. A High-Performance FIR Filter Architecture for Fixed and Reconfigurable Applications[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(2)：444-452.

[15] Tesar R, Ruzicka R, Simek V. Resistant Gates for Polymorphic Electronics[C]// Modelling Symposium. IEEE, 2015：513-518.

[16] Tao Y, Zhang L, Zhang Y. A projection-based decomposition for the scalability of evolvable hardware[J]. Soft Computing, 2016, 20(6)：2205-2218.

[17] Lloydr S, Johnc B, Dnicholas M L, et al. Towards new applications of multi-function logic： Image multifiltering[C]// Design, Automation & Test in Europe Conference & Exhibition. IEEE, 2012：824-827.

[18] Gajda Z, Sekanina L. On Evolutionary Synthesis of Compact Polymorphic Combinational Circuits[J]. Journal of Multiple-Valued Logic & Soft Computing, 2011, 17：607-631.

[19] Vasicek Z, Sekanina L. Evolutionary design of complex approximate combinational circuits[M]. Kluwer Academic Publishers, 2016.

[20] Vaddi R, Agarwal R P, Dasgupta S, et al. Design and Analysis of Double-Gate MOSFETs for Ultra-Low Power Radio Frequency Identification (RFID)： Device and Cir-cuit Co-Design[J]. Journal of Low Power Electronics & Applications, 2011, 1(3)：277-302.

[21] Vasicek Z, Bidlo M, Sekanina L, et al. Evolution of Impulse Bursts Noise Filters[C]// Adaptive Hardware and Systems, 2009. AHS 2009. NASA/ESA Conference on. IEEE, 2009：27-34.

[22] Vasicek Z, Sekanina L. Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware[J]. Genetic Programming and Evolvable Machines, 2011, 12(3)：305-327.

[23] Graczyk R, Stolarski M, Cormery P. Exploratory study about the use of new reconfigurable FPGAs in space[C]// Adaptive Hardware and Systems. IEEE, 2011：220-226.

[24] Kojima K. Emergent functions of HDL-based controller of inverted pendulum in consideration for disturbance[C]// Ieee/sice International Symposium on System Integration. IEEE, 2011：1352-1356.

[25] Higuchi T, Murakawa M, Iwata M, et al. Evolvable hardware at function level[C]// IEEE International Conference on Evolutionary Computation. IEEE Xplore, 1997：187-192.

[26] Yan X, Zhang H, Wu J, et al. Design the Evolutionary Algorithms Kernel in Adaptive Systems[J]. Procedia Engineering, 2011, 15(1)：2937-2942.

[27] Walker J A, Miller J F. Embedded cartesian genetic programming and the lawnmower and hierarchical-if-and-only-if problems[C]// Conference on Genetic and Evolutionary Computation. ACM, 2006：911-918.

[28] Harding S, Miller J F, Banzhaf W. Self modifying cartesian genetic programming： finding algorithms that calculate pi and e to arbitrary precision[C]// Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, Usa, July. DBLP, 2010：579-586.

[29] Garis H D, Yu T J, Di H. Artificial Brains - A Cheap Method for Speeding the Evolution of Neural Network Modules for Artificial Brain Building[C]// International Joint Conference on Neural Networks. IEEE, 2007：2835-2839.

[30] Thompson A, Wasshuber C. Design of single-electron systems through artificial evolution[J]. International Journal of Circuit Theory & Applications, 2000, 28(6)：585-599.

[31] Koza J R. Human-competitive results produced by genetic programming[J]. Genetic Programming and Evolvable Machines, 2010, 11(3)：251-284.

[32] 康立山, 何巍, 陳毓屏. 用函數型可編程器件實現演化硬件[J]. 計算機學報, 1999, 22(7)：781-784.

[33] 劉慧, 朱明程. 仿生容錯系統的可靠性分析[J]. 半導體技術, 2003, 28(2)：36-40.

[34] 林勇, 羅文堅, 王煦法. 基于遺傳算法的異構硬件電路冗余系統構造方法[J]. 新能源進展, 2009, 14(3)：61-66.

[35] 侯子錦, 劉晨. 復雜數字電路的分解演化研究[J]. 求知導刊, 2016(4)：53-53.

[36] 朱繼祥, 李元香, 邢建國. 可重構系統的演化修復機制[J].計算機學報, 2014, 37(7)：1599-1606.

[37] 張砦, 王友仁. 基于可靠性優化的芯片自愈型硬件細胞陣列布局方法[J]. 航空學報, 2014, 35(12)：3392-3402.

[38] 趙曙光, 楊萬海. 基于函數級FPGA原型的硬件內部進化[J].計算機學報, 2002, 25(6)：666-669.

[39] 劉培龍. 基于FPGA的神經網絡硬件實現的研究與設計[D].電子科技大學, 2012.

[40] Hrbacek R, Sekanina L. Towards highly optimized cartesian genetic programming：from sequential via SIMD and thread to massive parallel implementation[C]// GECCO‘14 Genetic and Evolutionary Computation Conference. 2014：1015-1022.

[41] Petrlik J, Sekanina L. Multiobjective evolution of approximate multiple constant multipliers[C]// IEEE, International Symposium on Design and Diagnostics of Electronic Circuits & Systems. IEEE, 2013：116-119.

[42] Xiong Y, Hui S, Hu Z, et al. From Bidirectional Model Transformation to Model Synchronization[M]// Transitions to Adulthood in the Middle East and North Africa. Palgrave Macmillan UK, 2014.

[43] Tsutsui S, Collet P. Massively Parallel Evolutionary Computation on GPGPUs[M]. Springer Publishing Company, Incorporated, 2013.

A survey of evolvable hardware

Bao Zhiguo, Sun Nan
(College of Computer and Information Engineering, Henan University of Economics and Law,Zhengzhou Henan，450046)

Evolvable hardware is the research focus of evolutionary algorithm and programmable chip. Evolvable hardware is a research hotspot. The origin and basic concept of evolvable hardware are introduced. The main research results of domestic and foreign researchers are summarized. The problems in the development of evolvable hardware are analyzed. The countermeasures are discussed. The development prospects are expected.

evolvable hardware; evolutionary computation; digital circuit optimal design

鮑治國(1977年－),男,博士,講師,研究領域為進化計算,優化設計。孫楠(1983年－),男,碩士,講師，研究領域為軟件工程。

貿澤備貨Cypress S71KL512SC0 HyperFlash和HyperRAM 功能更強大、表現更出色的多芯片封裝解決方案

河南省科技攻關項目(No. 162102210274)；鄭州市科技局普通科技攻關項目(No.153PKJGG116)。

近日，半導體和電子元器件的全球授權分銷商貿澤電 子 (Mouser Electronics) 即日起開始分銷Cypress Semiconductor的S71KL512SC0 HyperFlash?和HyperRAM?多芯片封裝 (MCP) 產品。此存儲器子系統解決方案采用小尺寸、低引腳數封裝，結合了用于快速引導和即時接通的高速NOR閃存與用于擴展高速暫存器的自刷新DRAM，是空間受限、成本優化的嵌入式設計的理想之選。

貿澤備貨的 Cypress Semiconductor S71KL512SC0 HyperFlash和 HyperRAM MCP采用Cypress HyperBus?接口，能夠支持更快的系統速度，更短的響應時間以及更豐富的用戶體驗。此系列器件具有512Mb HyperFlash和64 Mb HyperRAM，與現有SDRAM和四通道SPI解決方案相比，其引腳數減少70%，尺寸縮小77%，對于尋求完整高性能存儲器子系統的設計人員來說，是絕佳的多芯片封裝解決方案。