时序逻辑电路在片进化设计与实现

娄建安，李川涛，常小龙，满梦华

(1．军械工程学院 电气工程系，河北 石家庄050003;2．军械工程学院 静电与电磁防护研究所，河北 石家庄050003)

0 引言

演化硬件技术可根据环境变化改变电路内部结构，从而实现电子电路的结构自组织、环境自适应以及故障自修复功能［1］． 全世界有许多机构进行了演化硬件的研究，并且成果丰硕，特别是姚新、Higuichi 等学者提出了基于FPGA 结构可重配置特性的EHW 具体实现方法，将研究进程大大加速［2］．之后，演化硬件在理论研究和工程应用方面均发展迅猛．其中，在电路容错运行和自修复方面，满梦华等［3］利用演化硬件技术实现了逻辑门单元在线自修复;在图像处理方面，王珑等［4］将演化硬件技术应用到了图像加密技术中;在信号传输和处理方面，Faleoner 等［5］使用内部型可进化硬件完成了高速数据线的信号完整性检查．

1 时序逻辑电路演化模型设计

电路演化设计的关键在于设计结构可重构的电路演化模型，利用演化算法不断变化电路结构从而实现目标功能．但目前此类研究多以加法器、乘法器等组合电路为对象，而时序电路的研究相对较少［6］．其主要原因在于时序电路内部存在反馈连接，使得电路的染色体编码更为复杂，而且，验证测试评估困难，进化成功率较低，仿真速度缓慢．有鉴于此，笔者专门设计并实现了一种通用的时序电路演化模型．

1．1 硬件演化平台构建

硬件进化平台主要包括基于Microblaze 软核的CPU 设计、可重构数字电路网络模型设计两部分内容．Microblaze 软核的主要功能是运行GA 算法，进行VRC(Virtual Reconfigurable Circuit)矩阵演化． Microblaze 软核可以根据实际需要予以裁剪，其GPIO 的数目不限，对VRC 的配置都是全并行的．如串口、DMA 控制器、CAN 控制器等诸多外部设备，均可十分方便地通过选择而增删．而并行配置方式最大的优点就是VRC 配置速度快，不仅可以提高演化速度，而且设计简单;它的缺点是演化电路的规模不易直接扩充，如图1 所示．

1．2 时序逻辑电路的全向连接演化模型

图1 中的VRC 演化模型主要由两部分组成，即逻辑组合电路和D 触发器组．逻辑组合电路是由m×n 个PE(Programmable Element)单元构成的阵列，PE 单元的运算结果只能前馈输出到下一列．D 触发器组的输出既可以前馈也可以反馈，于是整个电路就可以成为一个全向连接的网络． 实验证明这种全向连接的方法对于提高电路的演化速度和成功率都有非常大的帮助．

PE 单元是VRC 演化模型的基本元素． 其结构设计对电路的演化的成功率和演化算法的收敛速度都有很大的影响，其结构如图2 所示．

PE 中包含AND、OR、NOT 以及XOR 等基本单元，以便构成各种复杂的组合电路功能．同时，PE 还添加了NAND、NOR 以及NXOR 等逻辑门，一旦用到时可以直接调用而不必通过基本单元的合成，以提高电路的演化速度，但是用不到时会降低FPGA 内部逻辑资源的使用率．矩阵中每个PE单元相互连接构成功能电路时，只会选择上述其中一种逻辑门作为自己的运算功能．

图中的chose_3_8_1 为8 选1 多路选择器，从上到下其功能依次为输入选择、输出选择和功能选择．DataInHigh 为该层单元的一个8 输入数据．这8 个数据可能来自VRC 的输入，也可以为上层PE 的输出，或者为前层或者后层保存电路的输出．HighDataInSel 端口为输入选择信号，选择该PE 的输入为DataInHigh(7:0)中的某一个．Functionsel(2:0)为功能选择端口，选择使用某一个逻辑门，端口signal_out 为该PE 的输出．

用PE 可以组成一个可编程功能的矩阵． 该矩阵中存在大量冗余且可编程的资源，所以实现同样功能的目标电路可以有多种结构形式． 当有个别或相对较少的单元受损之后，通过重新配置电路结构，完全可能避开损伤部分，从而使得该矩阵仍然可以继续正常工作，即具有了容错运行和自修复的功能．

时序逻辑电路内进化模型中必须有电路保存的部分，其结构如图3 所示．

图3 电路保存部分Fig．3 Circuit’s temporary part

元件Chose4_16_1 是16 选1 的多路选择器，控制信号为4 位，通过该元件选择D 触发器所要保存的数据．端口clk 和clr 分别为时钟信号和D触发器清零信号，在同步时序组合逻辑电路中，所有D 触发器的clk 和clr 均连接在一起．D_out 的输出既可当做整个VRC 的输出，也可做下层PE单元的输入或者上层PE 单元的输入，即保存部分输出，使其既可反馈，也可向前传输．

2 演化模型在ISE 开发环境中的实现

在本文的VRC 模型设计中，选择了原理图和VHDL 代码相结合的方式设计． 需要逻辑转换的部分用VHDL 代码编写，如多路选择器． 而在图形化显示更容易理解的地方，采用原理图编辑的方法设计．笔者设计的内进化VRC 分别由12 个如图4 所示的逻辑PE 层和4 个如图5 所示的保存PE 层构成．

图4 逻辑PE 层Fig．4 Logic PE layer

如图1 所示，12 个逻辑PE 层在前，4 个保存PE 层在后，共16 列．第n(n≤12)列可以接受Microblaze 输出、保存PE 层的输出、第m(m ＜n)列逻辑PE 输出和FPGA 管脚的信号作为输入．第n(n ＜13)列可以接受Microblaze 输出信息、FPGA管脚的信号、m(m≠n)列的输入信息或者输出信息作为输入．

演化阵列的列数要结合所要演化的目标电路的规模大小而设定．若阵列规模过小，目标电路可能演化不出来，而规模太大则演化时间可能过长．本设计中，所演化的电路都是以分为时间单位，一般目标电路的演化都不会超过10 min． 在目标电路难以确定的情况下，可以尽量扩大演化层数．

图5 保存PE 层Fig．5 Temporary PE layer

3 时序逻辑电路演化算法和演化结果分析

时序逻辑电路在片进化设计的过程有两个关键．一是在线进化设计目标电路，CPU 利用遗传算法不停地改变电路结构编码，利用编码配置VRC 演化阵列，直至满足目标电路要求． 二是目标电路的配置，寻找到目标电路后，把该电路对应的染色体编码重新配置VRC 阵列，最终形成正确的目标电路．当外部环境变化导致VRC 不能正常工作或任务变更时，两者之间重新建立通信，运行进化算法，对目标电路进行演化，直至满足功能要求．

3．1 演化算法

目标电路的搜索采用遗传算法． 遗传算法是通过模拟自然进化过程搜索最优解的方法，包含选择、交叉、变异等基本操作．本实验采用经典的(1 +λ)演化策略，实现的步骤如下:

(1)根据VRC 结构确定配置编码的格式和长度． VRC 的配置编码为一长串二进制数，由VRC 的第一列开始编码到最后一列组成如“b1b2b3b4b5b6…bn”，b 为1 或者0，其中n 为配置编码的总位数． 配置编码的排列遵循PE 单元的排列，如b1b2b3代表第一层PE 的功能配置位，b4b5b6代表第一层PE 左侧的输入信号选择，b7b8b9代表第一层PE 右侧的输入信号选择……，b146b147b148代表最后一层的左侧信号输入选择．

(2)初始化种群． 在初始化种群的过程中需要注意的有两个方面． 一方面是随机数种子的选择，经验证明随机数种子对演化代数的影响非常大．第二是结合具体的VRC 设计，在利用随机数初始化种群之后，需要适当的修改，如第一层VRC 的输入端必需有外部输入或者来自FPGA管脚的输入．

(3)寻找最优个体． 将种群的编码配置到VRC 当中去，根据目标电路确定目标输入数组M与其对应的目标输出数组N，给VRC 输出目标输入数组M，读取输出数组I，将数组I 与数组N 比较，相同的值越多则说明适应度越高．如果全部相同则停止演化．

(4)变异．令种群个数为n，利用找到的最优个体变异出(n-1)个新个体．

(5)交叉．令种群个数为n，(n -1)个新个体之间进行交叉．

(6)生成新种群．删除适应度最低的个体，并用最优个体替换掉最差个体结合4，5 步生成的(n-1)个新个体，生成当前种群;返回到第3 步．

3．2 结果分析

利用上述硬件演化平台、演化模型和遗传算法，分别演化了1001 序列检测器、二分频、四分频以及八分频等电路，相应的演化代数分布情况如图6 ～9 和表1 所示．

图6 演化1001 序列检测器Fig．6 Sequence detector evolution

表1 不同目标电路的演化数据统计Tab．1 Statistics of difference target circuit evolution

可以看出，设计的演化模型能够成功演化多种时序电路．演化的成功率证明，该模型特别适宜于演化分频器电路．遗传算法执行时，需要利用伪随机数发生器初始化种群．在实验过程中发现，伪随机数的种子对电路演化的收敛速度有十分重要的影响．为此，分别将随机数种子从1 到70 依次进行了电路演化． 种群的规模大小为5，变异率［7-8］都是用0．01，每个随机数对应的演化时间均未超过10 分钟．需要说明的是，演化1001 检波器时，其演化成功率为74%． 但是当随机数种子为73 时，演化代数只需要135 代．与此相同，在演化分频电路时，不同的种子演化速度差别亦很大．因此，在实际演化电路时可以参照本实验结果选取适当的随机数种子来初始化种群，提高电路演化的收敛速率．

4 结论

随着嵌入式技术的发展，更多的电子系统都需要脱离PC 机运行，笔者只用一片FPGA 实现了片内运行演化算法和实时配置全向连接的VRC矩阵．通过改变遗传算法，利用同一个模型实现了二分频、四分频、八分频和序列检测器，验证了本模型的通用性．由于时序电路的输出不仅取决于当前的输入也与前一个状态相关，所以其研究难度大，笔者结合其电路中间状态有限的特点，成功的解决了这个问题． 时序逻辑电路利用演化硬件技术设计的研究较少，笔者详细论述并实现了时序逻辑电路在片演化，将有效扩展演化EHW 技术的应用范围．

［1］ 刘尚合，原亮，褚杰． 电磁仿生学——电磁防护研究的新领域［J］．自然杂志，2009，31(1):1 -7．

［2］ YAO Xin，HIGUCHI T． Promises and challenges of evolvable hardware［J］． IEEE Trans on Systems Man and Cybernetics-Part C:Applications and Reviews，1999，29(1):87 -97．

［3］ 满梦华，原亮，巨政权．嵌入式系统门级在线自修复技术研究［J］．计算机工程，2011，37(19):9 -11．

［4］ 王珑，李元香，金彤． 基于演化硬件的图像加密技术研究［J］．计算机科学与工程，2009，31(12):31 -34．

［5］ FALEONER M C，KAMISETTY K，NORMAN A，et al． Using evolutionary algorithms for signal integrity checks of high speed data buses［C］//Proceedings of the 2007 IEEE Workshopon Evolvable and Adaptive Hardware(WEAH 2007)． Honolulu Hawaii:IEEE press，2007:35 -39．

［6］ ALI B，ALMAINI A E A，KALGANOVA T，et al．Evolutionary algorithms and their use in the design of sequential logic circuits ［J］． Genetic Programming and Evolvable Machines，2004(5):11 -29．

［7］ STOMEO E，KALGANOVA T，LAMBERT C． Mutation rate for evolvable hardware［C］// Proceedings of World Academy of Science，Engineering and Technology．［S．1．］:World Academy of Science Engineering and Technology，2005:117 -124．

［8］ KEYMEULEN D，STOICA A，ZEBULUM R，et al．Self-reconfigured mixed -signal integrated circuits architecture comprising a field programmable analog Array and a general purpose genetic algorithm IP core［C］//ICES．［S．1．］:［S．n．］，2008:225 -236．