采用输入输出分解的分区分段演化机制

姚睿，陈芹芹，孙艳梅，张砦，王友仁

(南京航空航天大学自动化学院，江苏南京210000)

演化硬件(evolvable hardware，EHW)将演化算法与可编程逻辑器件有机结合［1］，能根据环境的变化自动、实时地调整其内部结构，以适应内部条件(如局部故障)和外部环境的变化，为有效设计新型仿生电子系统提供了新的方法。但由于演化设计的可扩展性问题，应用直接演化方法和现有计算资源较难演化规模较大的电路［2-8］。.

为解决EHW的扩展性问题，文献［9］设计了一种Cartesian进化编程编码的电路演化Memetic算法，提高了演化算法的搜索能力。文献［10］将输入转换为输出及双向积累式进化结合，提出了GDD演化方法，可进化出多达17个输入的复杂电路。但由于该方法是对分解后的子电路进行逐个演化，总体所需演化代数很大。为此，文献［11］提出了一种使用多核虚拟可重构结构(virtual reconfigurable architecture，VRA)加速组合逻辑电路演化设计过程的内部演化方法。通过各子电路并行演化和利用演化完成的子电路对应的空闲VRA演化相邻的子电路，大大减少了演化时间。但由于演化过程中仅用了输出分解，演化输入个数较多的复杂逻辑电路时仍面临挑战。且各VRA模块的调用关系由硬件平台固定，第2阶段的并行演化只能调用临近的一个空闲VRA，不仅不利于硬件资源的有效利用，且演化不同的电路需要编写不同的硬件平台结构，增加了设计工作量，使得设计灵活性受限。

为解决这些问题，本文提出了一种基于输入、输出分解的分区分段并行在线自演化机制。采用输入、输出分解策略将需演化电路分解为多个具有较少输入、输出的子电路。首先对各子电路单独分配进化区域进行并行演化(即第1阶段并行演化);某些子电路演化完毕时，释放演化区域，并用其实现任意一个未演化完毕的子电路的并行演化(即第2阶段并行演化);所有子电路均演化成功后，将其整合得到顶层电路。实验结果表明，该方法具有较大的灵活性，可进化出多达21个输入的组合逻辑电路。

1 输入输出分解策略

输入输出分解策略的基本思想如图1所示:首先将复杂的原组合逻辑电路S经输入、输出分解策略分解为n个具有更少输入输出的较简单子电路S1，S2···Sn，对其分别进行演化;n个子电路演化完毕，对其进行整合，得到期望的顶层电路。

图1 输入输出分解策略Fig.1 Inputs and outputs decomposition strategy

1.1 输入分解

组合电路输入分解采用真值表分解实现。分解的依据是任何组合逻辑电路的真值表均可根据其某一输入的取值情况(0或1)分解为2个较简单的真值表［12］。根据需要对原始真值表逐级分解，即可得到期望复杂度的子电路。以图2(a)所示具有n输入m输出的原始组合逻辑电路F为例，其真值表如图2(b)所示，包含p=2n个输入输出组合。

图2 原组合逻辑电路及其真值表Fig.2 Original logic circuit and its truth table

如图3(a)所示该电路可分解为r输入s输出、可进化生成的新电路G以及s+n－r输入m输出、由选择器组成的不参与进化的固定电路部分M，其中s=m×2n-r［14］。对于原始电路F，在确定了子电路G的输入个数之后，新电路G的真值表以及电路M的结构即可确定。通过减少子电路G的输入个数，可以减小其输入输出组合个数，降低电路进化的复杂度。

子电路G的真值表产生过程如下:首先确定其输入个数r的值，从而确定子电路G的输入输出组合个数;其次对F的真值表进行检索，找出只与G的r个输入和F中对应输入片段匹配的对应于电路F的s/m个输出组合;重复此过程，直至找到G的所有输入输出组合，如图3(b)所示。

图3 分解模型及新电路的真值表Fig.3 Decomposition model and truth table of the new circuit G

1.2 输出分解

原组合电路F经输入分解得到的新可进化电路G，虽然输入个数有所减少，但输出相对于F增加了2n-r倍。根据增量分解策略中的输出分解，G可进一步分解为多个具有相同输入较少输出的子电路。如图4(a)所示4输入4输出原始组合逻辑电路，可分解为图4(b)所示2个4输入2输出的子电路A与B，其真值表如图4(c)所示。这样只需先分别演化每个子电路对应的2位输出，然后将2个子电路整合即可正确表达2位乘法器。

图4 两位乘法器的输出分解Fig.4 The outputs decomposition of 2-bit multiplier

1.3 整合电路的演化

各子电路分区分段并行演化完毕之后，将其整合为顶层电路，基本步骤为:首先将各子电路并联在一起，得到可进化电路G;然后将G和由多路选择器构成的固定电路M级联起来，得到原始电路F。

2 分区分段并行演化机制

结合输入、输出分解策略，提出一种分区分段在线并行演化机制，以加速组合电路演化速度。其核心是把顶层电路经输入、输出分解，拆分为多个较简单子电路，对这些子电路进行分区、分阶段并行演化，以有效减少演化算法的计算复杂度、染色体长度及电路输入输出组合个数。

为便于说明，假设顶层组合逻辑电路分解后仅包含A与B2个子电路，且A先于B演化完毕，相应分区分段并行演化机制如图5所示。图5(a)为分区并行演化机制示意图，子电路A、B分别由其对应的独立进化区域VRA1、VRA2并行演化。实验过程中将VRA1和VRA2封装定制为一个虚拟可重构IP核，由运行于Microblaze软核处理器上的演化算法控制，实现第1阶段的并行演化，其演化流程图如图5(c)下方的虚线框所示。图5(b)为第2阶段并行演化示意图，子电路A演化成功后，对应的空闲进化区域VRA1被用于与VRA2并行演化未演化完成的子电路B，其演化流程图如图5(c)上方的虚线框所示。

图5 分区分段并行演化机制Fig.5 Parallel evolution mechanism by partition in stages

各子电路个体适应度计算方法为:使用同或门将其实际输出值与真值表中期望输出进行比较，若二者的某一位相同，适应度值增1;否则，适应度值保持不变。图5(c)上方虚线框中，检测到子电路A演化成功时，首先记录成功染色体，然后将VRA1的适应度单元输入切换为子电路B的真值表，即可使用VRA1演化子电路B，从而使VRA1和VRA2以并行演化子电路B，完成第2阶段的并行演化。分区分段并行演化步骤如下:1)初始化种群POPA和POPB;

2)分别评价其适应度;

3)记录最佳染色体的适应度bestfitA和bestfitB与最佳染色体bestA和bestB;

4)若bestfitA与子电路A的最大适应度相同(即演化出期待结果子电路A)，bestfitB与子电路B的最大适应度不相同，跳到6);否则进入5);

5)对种群POPA和POPB中个体进行均匀变异得到新的个体，跳到2);

6)评价最佳染色体bestB的适应度以及VRA1在演化子电路B时bestA的适应度;

7)记录最佳染色体的适应度bestfitA和bestfitB与最佳染色体bestA和bestB;

8)若bestfitA或者bestfitB与子电路B的最大适应度相等，跳到10);否则，进入9);

9)变异得到新的个体，进入6);

10)子电路A与子电路B的演化同时停止。

若原始组合逻辑电路分解后包含多个简单子电路，某子电路演化成功后，通过切换其对应VRA核心的适应度单元的真值表输入，该空闲VRA核心可用于演化未演化完毕的任意子电路;多个子电路演化成功后，亦可使用2个以上的空闲VRA同时并行演化某个未演化完成的子电路。

文献［11］中，每个VRA只能调用其临近的一个VRA资源实现并行演化，2个以上的子电路并行运行时，不能充分利用硬件资源;且由于其硬件资源的调用在硬件平台上实现，演化不同电路时需要构造不同的硬件结构，增加了设计工作量，限制了设计的灵活性。本文将多个VRA在ISE上以VHDL语言编程实现，演化不同电路时，只需在软件中修改电路的输入、输出以及真值表特性，而不需要修改硬件架构，因此本文的方法具有极大的灵活性。另外，由于本文的并行算法是软件实现的，任何多个非邻近空闲VRA核心均可并行演化未演化完成的子电路，有效提高了演化效率。

3 实验结果

本文使用Xilinx公司的Virtex-5 ML507开发板作硬件平台。首先在Xilinx ISE12.4开发环境下使用VHDL语言编写分解后各子电路对应的VRA结构，作为可进化模块，并生成RTL模型进行自我诊断。接着在EDK中把这些模块封装、定制成IP核，挂接到PLB总线上，构成自演化系统，同时作为系统的验证评估平台。然后在SDK中，使用C语言对染色体长度、适应度评估及各模块之间的相互调用等进行编程，并调用搭建好的硬件平台。最后，将PC机中的比特流文件下载到FPGA中，实现分区、分阶段并行演化，并将演化结果通过UART通信在PC机的超级终端显示。演化算法选择标准遗传算法，为了降低计算复杂度，仅采用了均匀变异操作，未使用交叉操作。

3.1 本文方法与其他方法对比

3位无进位加法器、2位乘法器和Con1是EHW研究中常用的3种基准测试电路。为评估本文提出方法的性能，分别采用直接演化、文献［10］、文献［11］和本文方法在搭建的验证评估平台上对3种基准电路进行了对比实验。其中遗传算法的种群规模为128，均采用联赛选择机制和均匀变异、变异比率为2/256;最大演化代数为50 000。直接演化时所采用演化区域功能单元阵列大小为8行×5列，其他方法中功能单元阵列大小为4行×5列。

4种演化方法下的染色体长度、硬件代价、平均演化代数以及平均演化时间如表1所示。其中每组实验结果是20次成功进化的平均值。文献［10］和本文方法对原电路进行了输入输出分解，文献［11］方法仅进行了输出分解。Con1和Adder3*3经输入分解后的新可进化子电路G的输入为4;对G进行输出分解，分解为2n－4个具有4输入m输出的较简单子电路以分别演化(其中n、m分别为原电路的输入、输出个数)。Mult2*2电路具有4输入4输出，实验中仅进行输出分解，分解为2个具有4输入2输出的子电路分别进行演化。

表1 不同演化方法实验结果对比Table 1 Experimental result of different evolutionary methods

由表1可见，对于Mult2*2、Adder3*3和Con1电路，相较于直接演化，本文方法演化时间分别提升了3.9倍、19.5倍以及122.8倍。这是由于3种电路的复杂程度以及顶层电路的分解程度不同，在此实验中具有4输入4输出的Mult2*2只采用输出分解策略分解为2个子电路并行演化;具有6输入4输出的Adder3*3经过输入输出分解后分解为4个4输入6输出的子电路并行演化;具有7输入2输出的Con1经过输入输出分解后分解为8个4输入2输出的子电路并行演化。由此可知，相对于直接演化，本文方法在演化时间上提高的倍数与原组合电路的复杂程度以及原顶层电路的分解程度密切相关。原组合电路的输入输出越多(尤其是输入)以及其分解越精细，相较于直接演化，本文方法在演化性能上提高的倍数越大。

对于Mult2*2、Adder3*3和 Con1电路，相对于文献［10］的GDD方法，本文方法在演化时间性能上分别提升了3.2倍、10.9倍和3.8倍。这是因为GDD方法是将分解后的多个子电路逐个单独演化，系统的总演化时间为所有子电路演化时间之和。

对于Mult2*2、Adder3*3和 Con1电路，相对于文献［11］的多核VRA演化方法，本文方法演化时间性能分别提升了1倍、3.5倍和30.8倍。这是因为随着原组合电路输入个数的增加，输入输出组合个数以近似指数的规律增长，相应计算复杂度增大，演化时间随之迅速增大。文献［11］中仅采用了输出分解策略，同时当分解后的某些子电路演化成功后，其对应的空闲VRA核心只能用来演化相邻子电路;这样，在某一时刻，系统最多只能实现相邻的2个VRA核心并行演化同一子电路。表1中，本文方法对Mult2*2进行分解时，由于只采取了输出分解策略，分解为2个子电路进行演化，故本文演化方法与文献［11］方法在相同实验参数下，演化结果相同。

综上，本文演化方法演化时间上总体优于其他演化方法。其根本原因在于本文方法不仅结合了输入、输出分解技术，而且采用了分区分段并行演化技术。输入输出分解策略有效减少了每个子电路的计算复杂度和演化算法的搜索空间;在FPGA上多个子电路分区分段并行演化大大减小了演化时间。从表1可知，相较于分解前，子电路染色体的长度几乎都减少1倍。同时，每个VRA核心都能对任意多个子电路实现双阶段并行演化。这样，通过在FPGA上实现分区分段并行演化机制，方便数据流水线处理，提高演化性能。

从硬件代价上分析，由表1可见，本文方法相对于直接演化，硬件资源消耗只增长了1倍左右。这是因为针对输入输出个数较小的子电路，可使用更小的功能单元阵列对子电路进行演化。采用本文、文献［10］及文献［11］方法时，对于 Mult2*2、Adder3*3和 Con1电路，为了使实验结果更具有说服力，硬件资源设置相同。注意表1中资源消耗是指进化区域的虚拟可重构结构消耗的总体资源，实际上最终演化出的电路仅使用了这些资源的一部分。

3.2 其他基准电路进化结果

为了证明本文提出的基于输入输出分解的分区分段并行演化机制能够实现演化比较复杂组合逻辑电路，以乘法器电路以及10个MCNC基准电路为例，在搭建的验证评估平台上对提出的观点进行了验证。各种电路的实验参数如表2所示。

表2 实验参数Table 2 Experimental parameters

表3给出了3个乘法器以及10个MCNC基准电路的输入个数、输出个数、每个电路的输入输出组合个数以及在验证评估平台上的最高工作频率fm、平均演化时间以及平均演化代数。其中每组实验结果是20次成功进化的平均值。组合电路5xp1、Add2_7、Majority、Con1、Mult2、Mult3、Mult4、Adder3*3以及 Alu4经输入分解后的新可进化子电路G的输入为4，再对G进行输出分解，分解为2n－4个4输入m输出的较简单子电路(n、m分别为原电路的输入、输出个数)。组合电路Parity经输入分解后的新可进化子电路G的输入为8。这里之所以选择8而不选择4是由于奇偶校验器只有一个输入，其分解后的8输入1输出子电路并不复杂;若将其输入再进一步分解，会使演化过程过于复杂。

由表3可见，本文方法可以进化出多达21位输入的组合逻辑电路，且所有应用中系统都能以大于84 MHz的频率运行。

本文中依据输入输出分解策略理论上可将任意组合电路分解为多个期望复杂度的简单子电路，但分解后子电路并非越简单越好，其规模视电路复杂度而定。一般情况下，若原组合电路的输出数较多，对其进行输入分解时可进化子电路的输入可选为4;而当原组合电路的输出数较少时(比如Parity)，输入分解时可进化子电路的输入个数可适当增加。采用基于输入输出分解的分区分段并行演化方法，在硬件资源消耗变化不大的情况下，可以较好地演化出较大规模的组合逻辑电路。

表3 乘法器电路以及MCNC基准电路的实验结果Table 3 Experimental results of multiplier and MCNC benchmark circuits

4 结束语

本文提出一种基于输入输出分解的分区分段并行演化机制以演化复杂组合逻辑电路。该方法首先采用输入分解策略，将顶层电路的输入转换为输出，再对此可进化子电路进行输出函数分解，将其分解为多个具有较少输出的子电路，对每个子电路单独分配进化区域，以并行演化的方式进行演化，有子电路演化成功后，其对应的VRA核心即可释放，用来并行演化其他未演化完毕的任意子电路。以加法器、乘法器和部分MCNC基准电路为例在Xilinx Virtex-5 FX上进行了验证，结果表明该方法可大大提高演化时间性能，有效解决EHW的可扩展性问题。目前，该方法仅适用于组合电路的演化，未来将进一步研究复杂时序电路的演化机制。

［1］LIN B，IRIE M.Evolvable hardware［J］.CIT595 Research Project，2008，4(8):162-164.

［2］平建军，王友仁，高桂军，等.数字演化硬件的函数级在线进化技术研究［J］.高技术通讯，2009，19(1):61-65.PING Jianjun，WANG Youren，GAO Guijun，et al.Research on the technology for on-line evolution of digital hardware at function level［J］.Chinese High Technology Letters，2009，19(1):61-65.

［3］吴江，唐常杰，李太勇，等.基于多目标并行基因表达式编程的电路演化算法［J］.武汉大学学报:工学版，2012，45(4):532-538.WU Jiang，TANG Changjie，LI Taiyong，et al.Evolutionary algorithm of circuits based on multi-objective parallel gene expression programming［J］.Engineering Journal of Wuhan University，2012，45(4):532-538.

［4］何国良，李元香，史忠植.基于精英池演化算法的数字电路在片演化方法［J］.计算机学报，2010，33(2):365-372.HE Guoliang，LI Yuanxiang，SHI Zhongzhi.Elitist pool evolutionary algorithm for on-line evolution of digital circuits［J］.Chinese Journal of Computers，2010，33(2):365-372.

［5］BIDLO M.Evolutionary design of generic combinational multipliers using development［C］//7th International Conference Evolvable Systems:from Biology to Hardware.Wuhan，China，2007:77-88.

［6］STOMEO E，KALGANOVA T，LAMBERT C.Generalized disjunction decomposition for evolvable hardware［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2006，36(5):1024-1043.

［7］王婷.基于演化硬件的可重构技术研究［D］.郑州:解放军信息工程大学，2012:24-32.WANG Ting.Research on reconfigurable technology based on evolvable hardware［D］.Zhengzhou:The PLA Information Engineering University，2012:24-32.

［8］ZHAO S，JIAO L.Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm［J］.Genetic Programming and Evolvable Machines，2006，7(3):195-210.

［9］莫宏伟，徐立芳.基于Memetic算法的电路演化设计研究［J］.电子学报，2013，41(5):1036-1040.MO Hongwei，XU Lifang.Research on evolvable hardware design based on memetic algorithm［J］.Acta Electronica Sinica，2013，41(5):1036-1040.

［10］STOMEO E，KALGANOVA T.Improving EHW performance introducinga new decomposition strategy［C］//2004 IEEE Conference on Cybernetics and Intelligent Systems.Singapore，2004:439-444.

［11］王进，李丽芳，任小龙.多核虚拟可重构结构加速逻辑电路演化设计的研究［J］.高技术通讯，2012，22(4):340-347.WANG Jin，LI Lifang，REN Xiaolong.Using MuViRaC to accelerate evolutionary design of combinational logic circuits［J］.Chinese High Technology Letters，2012，22(4):340-347.

［12］ZHANG X，LUO W.Evolutionary repair for evolutionary design of combinational logic circuits［C］//2012 IEEE Congress on Evolutionary Computation(CEC).Brisbane，Australia，2012:1-8.