Intrinsic evolvable hardware platform for digital circuit design and repair using genetic algorithms

A hardware/software platform for intrinsic evolvable hardware is designed and evaluated for digital circuit design and repair on Xilinx Field Programmable Gate Arrays (FPGAs). Dynamic bitstream compilation for mutation and crossover operators is achieved by directly manipulating the bitstream using a layered framework. Experimental results on a case study have shown that benchmark circuit evolution from an unseeded initial population, as well as a complete recovery of a stuck-at fault is achievable using this platform. An average of 0.47 μs is required to perform the genetic mutation, 4.2 μs to perform the single point conventional crossover, 3.1 μs to perform Partial Match Crossover (PMX) as well as Order Crossover (OX), 2.8 μs to perform Cycle Crossover (CX), and 1.1 ms for one input pattern intrinsic evaluation. These represent a performance advantage of three orders of magnitude over the JBITS software framework and more than seven orders of magnitude over the Xilinx design tool driven flow for realizing intrinsic genetic operators on Xilinx Virtex Family devices.     

可用于演化硬件的改进自适应遗传算法研究

为提高演化硬件在演化过程中的收敛速度,以解决其可扩展性问题,研究了标准遗传算法的3个遗传算子,分析了进化不同阶段对遗传算子的不同要求及其对收敛速度的影响.在Srinivas的自适应策略和基于阶段进化的自适应策略的基础上,提出一种新的针对变异算子的自适应策略,并在轮盘赌选择方式中加入适应值标度变换.结合实例,对改进后的算法进行了仿真,结果表明了加入适应值尺度变换和新的自适应策略后,算法的收敛性有所提高.     

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.     

Secure evolvable hardware for public-key cryptosystems

In this paper, genetic programming is used as an alternative means to automatically generate secure and minimal hardware designs of public-key cryptosystems such as the RSA cryptosystem. We evolve optimal hardware circuits for modular exponentiation, which is a cornerstone operation in many public-key cryptographic system. The evolved circuits minimize both space (i.e. required gate number) and time (i.e. encryption and decryption time). The evolved designs are shielded against side-channel leakage and hence secure. The structure of the cryptographic circuit is random and so the private key cannot be deduced using known attacks. We compare our results against existing well-known designs, which were produced by human designers based on the binary method. Nadia Nedjah, Ph.D.: She is an associate professor in the Department of Electronics Engineering and Telecommunications at the Faculty of Engineering, State University of Rio de Janeiro, Brazil. Her research interests include functional programming, embedded systems and reconfigurable hardware design as well as cryptography. Nedjah received her Ph.D. in Computation from the University of Manchester — Institute of Science and Technology (UMIST), England, her M.S.c. in System Engineering and Computation from the University of Annaba, Algeria and her Engineerind degree in Computer Science also from the University of Annaba, Algeria. Luiza de Macedo Mourelle, Ph.D.: She is an associate professor in the Department of System Engineering and Computation at the Faculty of Engineering, State University of Rio de Janeiro, Brazil. Her research interests include computer architecture, embedded systems design, hardware/software codesign and reconfigurable hardware. She received her Ph.D. in Computation from the University of Manchester — Institute of Science and Technology (UMIST), England, her M.S.c. in System Engineering and Computation from the Federal University of Rio de Janeiro (UFRJ), Brazil and her Engineering degree in Electronics also from UFRJ, Brazil.     

Elitism-based compact genetic algorithms

This paper describes two elitism-based compact genetic algorithms (cGAs)-persistent elitist compact genetic algorithm (pe-cGA), and nonpersistent elitist compact genetic algorithm (ne-cGA). The aim is to design efficient cGAs by treating them as estimation of distribution algorithms (EDAs) for solving difficult optimization problems without compromising on memory and computation costs. The idea is to deal with issues connected with lack of memory by allowing a selection pressure that is high enough to offset the disruptive effect of uniform crossover. The pe-cGA finds a near optimal solution (i.e., a winner) that is maintained as long as other solutions generated from probability vectors are no better. The ne-cGA further improves the performance of the pe-cGA by avoiding strong elitism that may lead to premature convergence. It also maintains genetic diversity. This paper also proposes an analytic model for investigating convergence enhancement.     

Generalized disjunction decomposition for evolvable hardware.

Evolvable hardware (EHW) refers to self-reconfiguration hardware design, where the configuration is under the control of an evolutionary algorithm (EA). One of the main difficulties in using EHW to solve real-world problems is scalability, which limits the size of the circuit that may be evolved. This paper outlines a new type of decomposition strategy for EHW, the "generalized disjunction decomposition" (GDD), which allows the evolution of large circuits. The proposed method has been extensively tested, not only with multipliers and parity bit problems traditionally used in the EHW community, but also with logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library and randomly generated circuits. In order to achieve statistically relevant results, each analyzed logic circuit has been evolved 100 times, and the average of these results is presented and compared with other EHW techniques. This approach is necessary because of the probabilistic nature of EA; the same logic circuit may not be solved in the same way if tested several times. The proposed method has been examined in an extrinsic EHW system using the (1 + lambda) evolution strategy. The results obtained demonstrate that GDD significantly improves the evolution of logic circuits in terms of the number of generations, reduces computational time as it is able to reduce the required time for a single iteration of the EA, and enables the evolution of larger circuits never before evolved. In addition to the proposed method, a short overview of EHW systems together with the most recent applications in electrical circuit design is provided.     

演化硬件在模式识别中的应用综述

演化硬件以其速度快、灵活性强、实时适应等特点,在模式识别应用中易于建立学习时间短、识别速度快、精确分类的高效识别系统。在论述基于演化硬件模式识别技术的体系结构基础上,总结了不同的演化模型和各自的特性,并对各模型适合的应用领域进行了对比分析。介绍了国内外演化硬件模式识别技术研究的主要方向和发展现状,讨论了演化硬件在模式识别应用中的未来发展趋势和亟需解决的问题。     

A reconfigurable HexCell-based systolic array architecture for evolvable hardware on FPGA

Evolvable hardware is a system that modifies its architecture and behavior to adapt with changes of the environment. It is formed by reconfigurable processing elements driven by an evolutionary algorithm. In this paper, we study a reconfigurable HexCell-based systolic array architecture for evolvable systems on FPGA. HexCell is a processing element with a tile-able hexagonal-shaped cell for reconfigurable systolic arrays on FPGAs. The cell has three input ports feed into an internal functional-unit connected to three output ports. The functional-unit is configured using dynamic partial reconfiguration (DPR), and the output ports, in contrast, are configured using virtual reconfiguration circuit (VRC). Our proposed architecture combines the merits of both DPR and VRC to achieve fast reconfiguration and accelerated evolution. A HexCell-based 4 × 4 array was implemented on FPGA and utilized 32.5% look-up tables, 31.3% registers, and 1.4% block RAMs of Artix-7 (XC7Z020) while same-size conventional array consumed 8.7%, 5.1%, and 20.7% of the same FPGA, respectively. As a case study, we used an adaptive image filter as a test application. Results showed that the fitness of the best filters generated by our proposed architecture were generally fitter than those generated by the conventional state-of-the-art systolic array on the selected application. Also, performing 900,000 evaluations on HexCell array was 2.6 × faster than the conventional one.     

演化硬件在图像边缘检测中的应用

设计基于演化硬件（Evolvable Hardware，EHW）的快速边缘检测进化系统，提出一种适于此系统的图像边缘提取操作结构，给出进化算法的编码方案，设计用于染色体评估的适应度函数，利用标准遗传算法来实现可变结构参数的图像边缘提取进化方法，并采用Roberts，Sobel，LOG，Robinson等传统边缘检测算法与进化方法进行对比试验。结果表明：进化方法边缘检测误差率最低，只有9．87％，其边缘提取的效果优于传统检测方法，     

Real-world applications of analog and digital evolvable hardware

In contrast to conventional hardware where the structure is irreversibly fixed in the design process, evolvable hardware (EHW) is designed to adapt to changes in task requirements or changes in the environment, through its ability to reconfigure its own hardware structure dynamically and autonomously. This capacity for adaptation, achieved by employing efficient search algorithms based on the metaphor of evolution, has great potential for the development of innovative industrial applications. This paper introduces EHW chips and six applications currently being developed as part of MITI's Real-World Computing Project; an analog EHW chip for cellular phones, a clock-timing architecture for Giga hertz systems, a neural network EHW chip capable of autonomous reconfiguration, a data compression EHW chip for electrophotographic printers, and a gate-level EHW chip for use in prosthetic hands and robot navigation     

函数级进化型硬件在模式识别中的应用

设计了一个基于函数级进化型硬件(FEHW)的高速模式识别系统,并提出了一种适合此系统的改进遗传学习算法——可变染色体长度遗传算法(VGA)。利用VGA代替简单的遗传算法(SGA)来处理大输入的图像数据,实时实现了3类飞机识别。仿真结果表明,VGA进化速度是SGA的9倍,识别率达到80％以上。     

基于EHW的可进化传感器的研究

为克服常规传感器对信号采集和处理的局限,探求了一种具有智能传感并自适应于外部环境的机理,将常规传感器和可进化硬件相结合,提出了一种可进化传感器的基本框架,介绍了基于遗传算法和可进化硬件原理的具有自适应能力和容错特性的可进化传感器的初步研究。     

硬件进化中演化算法的研究及应用

详细介绍了硬件进化的概念,硬件进化的原理与实现思想,遗传算法与蚁群算法动态融合的基本原理,融合后算法中遗传算法及蚁群算法规则.融合过程中遗传算法与蚁群算法动态衔接问题以及融合后的算法在硬件进化中的应用过程.最后,分析了通过该算法进化后硬件的进化应用前景.     

Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware

We propose to utilize a formal verification algorithm to reduce the fitness evaluation time for evolutionary post-synthesis optimization in evolvable hardware. The proposed method assumes that a fully functional digital circuit is available. A post-synthesis optimization is then conducted using Cartesian Genetic Programming (CGP) which utilizes a satisfiability problem solver to decide whether a candidate solution is functionally correct or not. It is demonstrated that the method can optimize digital circuits of tens of inputs and thousands of gates. Furthermore, the number of gates was reduced for the LGSynth93 benchmark circuits by 37.8% on average with respect to results of the conventional SIS tool.     

多种哈希算法的可重构硬件架构设计

针对现有的哈希算法硬件架构仅实现少量几种算法的问题,设计了一种可实现SM3,MD5,SHA-1以及SHA-2系列共7种哈希算法的可重构IP,以满足同一系统对安全性可选择的需求。通过分析各哈希算法及其运算逻辑的相似性,该设计最大化地重用加法器和寄存器,极大地减少了总的实现面积。此外,该设计灵活可配,可以对内存直接存取。以Altera的Stratix II为FPGA目标器件,其最高频率可达100 MHz,总面积较现有设计减少26.7%以上,且各算法单位面积吞吐率均优于现有设计。     

一种KNN算法的可重构硬件加速器设计

设计并实现了一种可快速运算基于哈尔小波变换的KNN(Knearest neighbors)算法且具备可重构能力的硬件结构.该硬件结构通过增减哈尔小波变换组件即可适应不同维度样本的哈尔小波变换;对同样维度样本的计算则可以通过调整并行度满足对逻辑资源和处理时间的不同需求,克服了现有软件KNN计算速度慢、硬件实现的KNN不够灵活的缺陷.通过在Xilinx VC707 FPGA开发板上实现该硬件结构,实验结果展示了不同维度及并行度下算法实现在逻辑资源耗费及运算时间方面的变化.此外,将该硬件结构作为一种高质量轮廓提取算法硬件加速器的纹理分类模块时,在保持计算准确度的情况下获得了远高于软件运行的速度.     

基于进化硬件的自修复TMR系统设计及其可靠性分析

将进化硬件与传统TMR容错设计思想相结合,提出了一种具有在线自修复功能的自修复TMR系统设计方法。该系统具有多重容错和修复机制:总体采用TMR,可自动检测到故障模块;系统中每个模块均采用组件备份法,可通过组件切换法快速修复模块故障;而模块中每个组件也可通过进化进行修复。因而具有更强的容错能力和更高的可靠性。以具有片内三模冗余的2 bit乘法器为例进行了验证。最后,给出了该系统的可靠性模型,推出了可靠性计算公式,从理论上对该系统的可靠性进行了分析。结果表明:该系统能有效修复stuck-at故障,具有更长的使用寿命和更高的可靠性。     

A genetic engineering approach to genetic algorithms

We present an extension to the standard genetic algorithm (GA), which is based on concepts of genetic engineering. The motivation is to discover useful and harmful genetic materials and then execute an evolutionary process in such a way that the population becomes increasingly composed of useful genetic material and increasingly free of the harmful genetic material. Compared to the standard GA, it provides some computational advantages as well as a tool for automatic generation of hierarchical genetic representations specifically tailored to suit certain classes of problems.