FPGA在演化硬件中的应用

    摘要：介绍了FPGA的新应用一演化硬件（EHW）的进展和现状，其中主要包括EHW的概念、工作原理、存在问题和应用领域。阐述了EHW在电路与系统学科中的科学意义及对新兴电子信息产业将产生的深远影响。

    关键词：演化硬件 遗传算法 FPGA

二十世纪70年代初出现了可编程逻辑器件（PLD），发展至今已出现简单PLD（SPLD）、复杂PLD（CPLD）和现场可编程门阵列（FPGA）等各类器件。自1985年叛国Xilinx公司推出第一片FPGA以来，以今已有多家公司开发销售自己的FPGA产品。FPGA有更高的集成度、更复杂的布线结构和逻辑实现，它与以往的PLD之间的差别有于PLD一般是通过修改内连电路的逻辑功能来实现编程的，而FPGA则是通过修改一根或多根内连线来编程。FPGA的在线可编程技术（ISP）及动态重构技术进一步提高了FPGA的应用灵活性和自由度，重组及配置工作速度极快，从而为EHW的实现创造了坚的实的物质基础。

1 EHW的概念

早在二十世纪50年代，计算机之父Von Neumann就提出了研制具有自繁殖与自修复能力并能进行通用计算的机器的设想，这就是演化硬件的概念雏形。一直到演化算法和大规模PLD的出现，这一梦想才具备了实现的可能。1992年日本的Hugo de Garis和瑞士联邦工学院的科学家同时正式提出了EHW的构想[1]，短短几年这一新的领域获得了广泛的关注，并且正处于急剧升温之中。

EHW指的是在与外部环境相互作用之后，能自主地、动态地改变自身结构和行为的硬件电路。它具有自组织、自适应、自修复功能，能适应不同环境要求和提高自身性能。这一特性获得主要归功于演化算法（Evolvable Algorithms,简称EAs）。

EaAs是一类模拟自然界遗传进化规律的仿生学算法，它们首先随机产生一组待求优化问题的潜在可能矢量解（解称为染色体，解的集合称为种群，解中的分量称为基因）；然后采用变异、交叉、评价、选择等手段，优胜劣汰，不能进化，最后获得优化解。作为一种优化算法，它们也具有自适应、自组织、自修复的特性，本身还具有随机性和并行性。在搜索解空间时，能以很大概率找到全局解，不易陷入局部优化点。嵌入问题方式简单，寻优鲁棒性强，可以解决不连续、不可导、多目标、带各种约束条件的优化问题，因而成为EHW演化的“发动机”或“引擎”。

EHW的简单定义为：演化算法+可编程逻辑器件。从目前EHW研究的内容看，EHW具两个方面的内容：①根据功能或指标的要求，采用EA技术对电路进行合成，形成新电路结构和参数。值得一提的是EA用于电路及系统设计由来已欠，但主要集中于利用电路参数设计电路板、布线、布局优化等方面[2]，与本文所指的EHW有本质区别。②具有自组织、自适应自修复特性的硬件电路。此为EHW最吸引人的地方，其核心为“自适应”。由于FPGA比以往PLD具有独特的优越性，目前大多数的EHW都采用FPGA器件。

2 EHW的实现方法和演化方式

从FPGA的原理可知，FPGA结构可以最终描述为配置数据。因此对FPGA的演化，最终可归结为对配置数据的演化，整个演化过程大约可描述成如下步骤：

①设定EA参数，如交叉率、变异率、种群数等；

②随机产生初始化种群Xi={xi1,xi2,…，xiR}，其中1≤i≤POP_SIZE；Xi为染色体，代表FPGA结构编码，如二进制串等；R为基因总数；

③评价种群中的各染色体，获取相应的适应度函数值；

④以某种方式选择部分种群，按指定的变异率、交叉率进行交叉、变异，形成新的子染色体；

⑤评价表的染色体，与父代染色体一起按适应度函数值大小选出POP_SIZE的个体染色体作为下一代种群；

⑥判别是否满足终止条件：是，结束；否，回到④重复演化过程。

EA染色体编码方式是影响EA计算速度和有效性的重要因素。根据编码方式和级别的不同，可将EHW进化方式分为三类：直接型、间接型和函数型。直接型的任务是直接进化结构位串以改变门级电路的连接。结构位串为染色体，通过专用的软件工具，下载到FPGA中，以获得新的电路，如图1所示[3]。这种演化层次属于门级水平，缺点是染色体的表示过于庞大。一般情况下（不考虑其他结束条件），n个逻辑门的进化，染色体的串位数为O（n2）数量级，无论是表示或进化都是十分困难的。间接型的任务并不直接进化结构位串，它采用了高级的表达方式，即用树或法则产生电路。文献[4]提供了一个很典型的例子，它采用了硬件描述语言（HDL）程序实现一个二进制加法器，染色体为按规则产生的衍生树（derivationtree），树的所有可能结果钭与电路结构的所有可能结果一一对应。每一个树可以产生一个结构功能描述程序块，如果该树是合活的话，则将衍生出HDL的EHW结构描述程序。EA的交叉、变异等算子对树的作用与一般的EA算法对二进制串的作用相似，但EA进化含有结束条件，以确保树（或程序）的合法性。这种方法降低了结构位串造成的计算复杂度，因此在实际EHW中应用较多。函数型进化也是另一种降低EA复杂性的方法，也属于高级表达，其进化的基本元素不是门电路，而是个基本的功能模块，如加、减模块等。这样既可以获得更为复杂功能的电路，又不增加EA进化的困难。当然，其在FPGA中占用门电路资源要比前两种方法多，电路结构不很精简。

对染色体的评价方式分为外向型和内向型两种。外向型的EA是在仿真环境中用软件进行的，染色体的评价值由仿真给出，只将每代最佳的染色体（配置数据）才载到FPGA中，即在每代EA过程结束后EHW才重组一次。而内向型则将每代种群中的每个染色体都下载到FPGA中，把实际运行结果作为评价值，具有真实性，显然EHW重组的次数等于种群数的大小。

EHW的自适应工作方式分为在线自适应和离线自适应两种。在线自适应又称为实时自适应，其学习过程、进化过程和运作过程是同步进行的。离线自适应则把实际工作和进化过程分为两个独立的阶段，一般先做进化设计，后投入实际工作。

3 演化硬件存在的问题和发展前景

EHW是一个新生事物，尚有许多不成熟和亟待解决问题。EHW的在线自适应方法还不完善。EA的特点就是是要重复进行“试凑性”的实验，在试凑过程中可能产生劣质的染色体，造成系统严重的故障和灾难（如果不采取适当的防范措施的话），因而当前报道的实例大多数属于离线自适应。解决方法是建立专家识别或仿真环境，从中提前判别和滤去可能对环境造成危害的劣质染色体，从而保证系统安全。

目前成功应用的EHW电路规模都比较小，这主要是因为EA算法复杂性随EHW元件数的增加呈非线性上升趋势，计算量变得不可忍受。解决的办法是寻求更为有效的EA，如新的染色体编码方式或硬件加速器[5]等。适应度函数的选取也是一个值得注意的问题，高适应度的结果并不一定能保证电路的完整和正确性，因为EA毕竟无法将所的输入都做一番试凑性的实验，为提高EHW的正确性而付出的计算成本将大幅增加。这一问题还引发了EA结束判定准则难以确定的问题。另外，EHW强调的是终结果达到目标要求，而电路内部的结构、设计原理等对用户来讲属于“黑箱”的范畴，因而一旦EHW发生故障，人工无法修理补救，解决的方向是采用自修复的EHW。

从某种意义上余，EHW给系统和电路科学带来了革命性的理念和突破，作为新的电路设计手段，它能提供人工意想不到的设计方案，设计人员主要思考要完成什么电路、实现什么功能，而不是过多地考虑如何实现实。该方法对专业化的先验知识要求不高，特别善于处理特殊和复杂的约束条件（可通过EA的染色体及适应度函数灵活地表达出来），因此可大大减轻了工劳动负担，有效地提高产品质量。作为一种新的自适应电路，EHW在机器学习、人工神经网络、自适应控制、信号处理与识别、容错系统和机器人等方面有广阔的应用前景。从1992年到现在，已有不少获得实际应用和总商品化的例子，如EHW制成的控制器成功地实现了假肢控制[6]；EHW取代神经网络实现了高速的模式辩识，结果比神经网络好[7]；EHW芯片实现了（电极采色打印机）数据压缩[7]等。也有人大胆地设想，随着EHW技术的发燕尾服，新型计算机可实现自动升级[8]。