进化硬件发展综述

鲍治国，孙 楠

(河南财经政法大学计算机与信息工程学院，河南郑州，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%，对于寻求完整高性能存储器子系统的设计人员来说，是绝佳的多芯片封装解决方案。