A three-step decomposition method for the evolutionary design of sequential logic circuits

Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition, output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability. It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.     

复杂数字电路多级在线进化技术研究

复杂数字电路的在线进化是目前演化硬件领域的难题之一.本文阐述了基于多级分解进化的复杂数字电路在线进化思想,给出了数字电路进化设计算法,分析了数字电路编码方案,研究了数字电路在线验证评估方法,设计了适应度函数,给出了数字电路在线进化设计实验系统方案.以典型数字电路为例,验证了多级分解进化方法的有效性,实验结果表明,采用多级分解进化方法可大大提高数字电路在线进化设计的速度与成功率,也有利于提高数字电路在线验证评估效率.     

A projection-based decomposition for the scalability of evolvable hardware

Scalability is a main and urgent problem in evolvable hardware (EHW) field. For the design of large circuits, an EHW method with a decomposition strategy is able to successfully find a solution, but requires a large complexity and evolution time. This study aims to optimize the decomposition on large-scale circuits so that it provides a solution for the EHW method to scalability and improves the efficiency. This paper proposes a projection-based decomposition (PD), together with Cartesian genetic programming (CGP) as an EHW system namely PD-CGP, to design relatively large circuits. PD gradually decomposes a Boolean function by adaptively projecting it onto the property of variables, which makes the complexity and number of sub-logic blocks minimized. CGP employs an evolutionary strategy to search for the simple and compact solutions of these sub-blocks. The benchmark circuits from the MCNC library, \(n\)-parity circuits, and arithmetic circuits are used in the experiment to prove the ability of PD-CGP in solving scalability and efficiency. The results illustrate that PD-CGP is superior to 3SD-ES in evolving large circuits in terms of complexity reduction. PD-CGP also outperforms GDD+GA in evolving relatively large arithmetic circuits. Additionally, PD-CGP successfully evolves larger \(n\)-even-parity and arithmetic circuits, which have not done by other approaches.     

基于精英池演化算法的数字电路在片演化方法

20世纪末演化硬件技术的提出为实现硬件系统的自适应与智能化等特征提供了一种可行的新技术,现阶段电路进化是演化硬件研究的热点之一.该文引入人工经验与规则,提出一种扩展矩阵编码法,保护具有较优结构的电路个体不易被淘汰;其次,基于多目标和局部寻优技术,结合子电路杂交与单元重要性的自适应变异策略,提出了一种设计数字电路的精英池演化算法,并在可编程逻辑器件上实现电路的自主动态重构与评价等演化过程.     

一种基于GEP的演化硬件复杂电路优化算法

演化硬件是近年来新兴的研究热点,它是演化算法和可编程逻辑器件相结合而形成的硬件设计新方法。在演化硬件中门电路的优化设计是一个重要的研究领域。提出一种新的基于基因表达式程序设计（GEP）的算法来进行复杂优化电路的设计,通过仿真实验表明,该算法不仅收敛速度快,而且还能利用该算法优化大规模的门电路,克服了传统优化方法的求解速度慢甚至不收敛等缺点。该算法较传统的电路优化方法更简单、更高效。     

Practical and scalable evolution of digital circuits

This paper addresses the scalability problem prevalent in the evolutionary design of digital circuits and shows that Evolvable Hardware (EHW) can indeed be considered as a viable alternative design methodology for large and complex circuits. Despite the effort by the EHW community to overcome the scalability problems using both direct mapped techniques and developmental approaches, so far only small circuits have been evolved. This paper shows that, by partitioning a digital circuit and making use of a modular developmental approach, namely, the Modular Developmental Cartesian Genetic Programming (MDCGP) technique, it is indeed possible to evolve large circuits. As a proof of concept, a 5 × 5 multiplier is evolved for partition sizes of 32 and 64. It is shown that compared to the direct evolution technique, the MDCGP technique provides five times reduction in terms of evolution times, 6–56% reduction in area and improved fault tolerance. The technique is readily scalable and can be applied to even larger partition sizes, and also to sequential circuits, thus providing a promising path to evolve large and complex circuits.     

硬件演化原理及实现方法研究

文章对基于Virtex系列FPGA的硬件外部演化技术进行了研究，对演化算法的流程进行了分析，介绍了演化硬件的概念、原理、JBits API软件以及Virtex器件结构。基于JBits软件，采用外部演化的方式对电路进行演化，并通过仿真实例证明了这种方法的有效性。     

A Scalable Approach to Evolvable Hardware

Evolvable Hardware (EHW) has been proposed as a new method for designing systems for complex real-world applications. However, so far, only relatively simple systems have been shown to be evolvable. In this paper, it is proposed that concepts from biology should be applied to EHW techniques to make EHW more applicable to solving complex problems. One such concept has led to the increased complexity scheme presented, where a system is evolved by evolving smaller sub-systems. Experiments with two different tasks illustrate that inclusion of this scheme substantially reduces the number of generations required for evolution. Further, for the prosthesis control task, the best performance is obtained by the novel approach. The best circuit evolved performs better than the best trained neural network.     

基于演化算法的电路自动设计方法

在电路设计中引入演化计算,在可编程逻辑器件上通过对基本电路元器件进行演化而自动生成人工不可能设计出的电路结构,称为演化硬件设计。文中介绍了演化硬件实现的物质基础、演化计算在硬件自动设计方法的实现过程以及该方法要解决的问题,并对演化数字电路、模拟电路的设计进行了分析,说明演化算法在电路自动设计中是切实有效的。     

基于动态可重构FPGA的自演化硬件概述

演化硬件研究如何利用遗传算法进行硬件自动设计,或者设计随外界环境变化而自适应地改变自身结构的硬件,在电子设计自动化、自主移动机器人控制器、无线传感器网络节点等领域都有潜在的应用价值. 自演化硬件是在硬件内部完成遗传操作和适应度计算,利用支持动态部分可重构的FPGA芯片上的微处理器核实现遗传算法,模拟生物群体演化过程搜索可能的电路设计并配置片上的可重构逻辑,找到最优或较优的设计结果,从而实现自适应硬件. 当电路发生故障时,自演化硬件自动搜索新的配置,利用片上冗余资源取代故障区域,从而实现自修复硬件. 介绍了基于动态部分可重构FPGA的自演化硬件的基本思想、体系结构以及研究现状,总结并提出了亟待解决的关键技术,指出高效的电路染色体编码表示与可重构逻辑配置位串之间的映射方式是当前研究的重点之一.     

基于FPGA的数字电路进化设计与实现

针对目前演化硬件研究中的关键问题:电路的数学表示方法、遗传算法和快速重构硬件平台,文章建立了一个用于描述数字电路的电路网络演化模型;设计了矩阵组编码算子,改进了精英保留策略;最后基于虚拟可重构技术在FPGA中建立了一个适于演化操作的硬件平台,实现了数字电路的内部进化;实验结果验证了该模型的可行性与有效性,采用的矩阵组编码算子在(8,8,8,4)演化区域内显著提高了电路演化的速度,为演化硬件的进一步发展了提供新的方法。     

基于信息论的时序电路演化设计

时序电路由于存在反馈连接,因此是数字型演化硬件研究中的难点问题。为此,对时序电路的演化设计方法进行改进,提出一种针对时序电路演化的虚拟可重构平台,阐述在此平台上演化时序电路的方法。基于信息论改进电路的适应度评估方法,以目标函数和电路实测输出之间的信息熵设计适应度评估函数。实验结果表明,该方法具有较好的稳定性和全局寻优能力。     

Improving evolvable hardware by applying the speciation technique

Evolvable hardware (EHW) has recently become a highly attractive topic of study because it offers a way of adapting hardware to a given embedded environment. However, it is not easy to evolve hardware efficiently and effectively, so many challenges continue to exist when trying to solve problems. In this paper, we propose a method that uses the speciation technique to enable diverse circuits to evolve efficiently by the process of one-step evolution. As a result of studying the landscape contained in the EHW example, we have found complicated spaces contain many peaks that can lead to deceptions when using the evolving process, and the speciation technique profits from the evolution of EHW. We also studied that the speciated hardware ensemble might be a good candidate for more complex and rigorous function. In the experiments, we applied the fitness sharing method as the speciation technique, and obtained diverse hardware modules, then ascertained the efficiency of these structures. We also show that several useful extra functions and better overall performance can be obtained by analyzing diverse circuits with the speciation technique.     

基于虚拟可重构平台的时序电路演化设计

目前,电路进化设计是演化硬件研究的主要方向之一。而时序电路由于存在反馈环不便于进行电路描述和软件仿真。文中对时序电路的演化设计方法进行了改进,提出了专门针对时序电路演化的虚拟可重构平台,建立起电路编码与HDL代码的映射关系。应用TEXTIO和MATLAB来辅助仿真测试过程,使测试向量数量巨大、难以处理的问题得到很好地解决。最后调用ModelSim完成了FSM的演化实验。实验结果验证了基于此平台演化时序电路的可行性和有效性。     

基于函数级FPGA原型的硬件内部进化

电路进化设计是现阶段可进化硬件（EHW）研究的重点内容，针对制约进化设计能力的主要“瓶颈”，该文提出并讨论了一种简洁高效的内部进化方法，包括基于函数变换的染色体高效编码方案，与之配套的函数级FPGA原型和进化实验平台以及在线评估与遗传数自适应方法等，交通灯控制器，4位可级联比较器等相对复杂且具应用价值的电路的成功进化，证明该方法适用于组合，时序电路的进化设计，并可显著地减少运算量，提高进化设计的速度和规模。     

用遗传算法实现逻辑函数的化简

在硬件设计中引入演化计算,在可编程逻辑器件上通过对基本硬件元器件进行演化而自动生成人工难以设计出的硬件结构,称为演化硬件设计。代数法和卡诺图法用来化简给定的逻辑函数,但它们难以化简规模很大的逻辑函数。这里用演化硬件设计方法实现了区别于传统的代数化简法和卡诺图化简法的一种新的对给定的某一逻辑函数进行化简的方法。实验表明演化硬件设计方法能够化简规模很大的逻辑函数。     

数字系统硬件在线进化技术研究

电路的在线进化设计是通过演化的方式实现电路的功能,可视为进化算法与可编程逻辑器件的结合;针对制约进化设计能力的主要“瓶颈”一染色体过长导致进化设计受限,文中一方面结合FPGA中的逻辑资源,采用基于LUT（查找表）逻辑功能与连线的分段编码方案,降低染色体长度,另一方面,采用了改进了的进化策略（ES）,以克服算法的早熟并加快收敛速度;文中以两位乘法器电路的在线进化作为实例,给出了具体的实现方法。     

一种外部进化的函数级演化硬件

提出了一种函数级演化硬件的实现方案,这是一种间接演化的方法。它将电路分层表示,用有向图和树对电路结构及元素进行编码,运用遗传程序设计的思想演化构造实际电路,并且通过软件仿真来评价电路。也给出了数字电路仿真算法设计的具体描述。通过该方案构造了一个随机数发生器,并用Diehard测试程序对其随机性进行了测试。实验结果表明,用该方案构造大规模数字电路是可行的。     

基于基因表达式的演化硬件进化和优化算法

电路进化设计是可进化硬件研究的重要内容．针对电路进化设计做了如下工作：(1)融合了数据挖掘、基因表达式编程与传统电路进化技术,提出两阶段电路进化方法．该方法包括基于表达式树遗传编程进化算法的电路进化阶段和基于挖掘频繁数字电路算法的电路优化阶段。(2)给出了详尽的实验．实验表明6次多项式函数发现的平均进化代数为442代、乘法器电路的平均进化代数为2292代．比笛卡尔遗传编程和NEHF(Novel Evolvable Hardware Framework)快6倍以上．用MFDC对乘法器电路进化结果进行挖掘后,得到了比传统电路更有效的乘法器电路。     

使用常规IC的演化硬件电路设计实例

在讨论了EHW运行机制及其在一般硬件实验环境中所面临问题的基础上,具体针对一种分频电路进行了基于常规计算设备和普通TTL芯片的演化研究和具体实现,进而完成了能以闭环方式进行系统演化的实验环境;运行结果表明,该方式既从原理上保留了演化硬件的全部特点,又在一定程度上摆脱了对FPGA等类型可编程芯片和相关软件环境的依赖,可以在此基础之上有效地进行多种演化策略和演化方式的研究,具有一定的实用价值。