Applying Genetic Parallel Programming to Synthesize Combinational Logic Circuits

Experimental results show that parallel programs can be evolved more easily than sequential programs in genetic parallel programming (GPP). GPP is a novel genetic programming paradigm which evolves parallel program solutions. With the rapid development of lookup-table-based (LUT-based) field programmable gate arrays (FPGAs), traditional circuit design and optimization techniques cannot fully exploit the LUTs in LUT-based FPGAs. Based on the GPP paradigm, we have developed a combinational logic circuit learning system, called GPP logic circuit synthesizer (GPPLCS), in which a multilogic-unit processor is used to evaluate LUT circuits. To show the effectiveness of the GPPLCS, we have performed a series of experiments to evolve combinational logic circuits with two- and four-input LUTs. In this paper, we present eleven multi-output Boolean problems and their evolved circuits. The results show that the GPPLCS can evolve more compact four-input LUT circuits than the well-known LUT-based FPGA synthesis algorithms.     

Evolving oscillators in silico

We use evolutionary search to automatically find electronic circuits that oscillate, i.e., that periodically toggle an output line from low to high. Reconfigurable hardware in the form of field programable gate arrays (FPGA's)-as opposed to circuit simulation-computes a circuit's fitness which guides the evolutionary search. We find empirically that oscillating circuits can be evolved that closely approximate target frequencies specified a priori. Our evolved oscillators alias a harmonic of the target frequency to satisfy the fitness goal. Frequencies of the evolved oscillators are sensitive to temperature and to the physical piece of silicon in which they operate. Such sensitivities have negative implications for deployment of evolved circuits in conventional applications, but may have positive implications for adaptive computing. We observe that operating the FPGA's transistors at voltages below specification often increases the number and quality of evolved solutions     

Real-time reconfigurable subthreshold CMOS perceptron.

In this paper, a new, real-time reconfigurable perceptron circuit element is presented. A six-transistor version used as a threshold gate, having a fan-in of three, producing adequate outputs for threshold of T =1, 2 and 3 is demonstrated by chip measurements. Subthreshold operation for supply voltages in the range of 100-350 mV is shown. The circuit performs competitively with a standard static complimentary metal-oxide-semiconductor (CMOS) implementation when maximum speed and energy delay product are taken into account, when used in a ring oscillator. Functionality per transistor is, to our knowledge, the highest reported for a variety of comparable circuits not based on floating gate techniques. Statistical simulations predict probabilities for making working circuits under mismatch and process variations. The simulations, in 120-nm CMOS, also support discussions regarding lower limits to supply voltage and redundancy. A brief discussion on how the circuit may be exploited as a basic building block for future defect tolerant mixed signal circuits, as well as neural networks, exploiting redundancy, is included.     

Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm

Evolutionary design of circuits (EDC), an important branch of evolvable hardware which emphasizes circuit design, is a promising way to realize automated design of electronic circuits. In order to improve evolutionary design of logic circuits in efficiency, scalability and capability of optimization, a genetic algorithm based novel approach was developed. It employs a gate-level encoding scheme that allows flexible changes of functions and interconnections of logic cells comprised, and it adopts a multi-objective evaluation mechanism of fitness with weight-vector adaptation and circuit simulation. Besides, it features an adaptation strategy that enables crossover probability and mutation probability to vary with individuals' diversity and genetic-search process. It was validated by the experiments on arithmetic circuits especially digital multipliers, from which a few functionally correct circuits with novel structures, less gate count and higher operating speed were obtained. Some of the evolved circuits are the most efficient or largest ones (in terms of gate count or problem scale) as far as we know. Moreover, some novel and general principles have been discerned from the EDC results, which are easy to verify but difficult to dig out by human experts with existing knowledge. These results argue that the approach is promising and worthy of further research.     

Analog and digital FPGA implementation of BRIN for optimization problems.

The binary relation inference network (BRIN) shows promise in obtaining the global optimal solution for optimization problem, which is time independent of the problem size. However, the realization of this method is dependent on the implementation platforms. We studied analog and digital FPGA implementation platforms. Analog implementation of BRIN for two different directed graph problems is studied. As transitive closure problems can transform to a special case of shortest path problems or a special case of maximum spanning tree problems, two different forms of BRIN are discussed. Their circuits using common analog integrated circuits are investigated. The BRIN solution for critical path problems is expressed and is implemented using the separated building block circuit and the combined building block circuit. As these circuits are different, the response time of these networks will be different. The advancement of field programmable gate arrays (FPGAs) in recent years, allowing millions of gates on a single chip and accompanying with high-level design tools, has allowed the implementation of very complex networks. With this exemption on manual circuit construction and availability of efficient design platform, the BRIN architecture could be built in a much more efficient way. Problems on bandwidth are removed by taking all previous external connections to the inside of the chip. By transforming BRIN to FPGA (Xilinx XC4010XL and XCV800 Virtex), we implement a synchronous network with computations in a finite number of steps. Two case studies are presented, with correct results verified from simulation implementation. Resource consumption on FPGAs is studied showing that Virtex devices are more suitable for the expansion of network in future developments.     

Generating synthetic benchmark circuits for accelerated life testing of field programmable gate arrays using genetic algorithm and particle swarm optimization

Accelerated life testing (ALT) of a field programmable gate array (FPGA) requires it to be configured with a circuit that satisfies multiple criteria. Hand-crafting such a circuit is a herculean task as many components of the criteria are orthogonal to each other demanding a complex multivariate optimization. This paper presents an evolutionary algorithm aided by particle swarm optimization methodology to generate synthetic benchmark circuits (SBC) that can be used for ALT of FPGAs. The proposed algorithm was used to generate a SBC for ALT of a commercial FPGA. The generated SBC when compared with a hand-crafted one, demonstrated to be more suitable for ALT, measured in terms of meeting the multiple criteria. The SBC generated by the proposed technique utilizes 8.37% more resources; operates at a maximum frequency which is 40% higher; and has 7.75% higher switching activity than the hand-crafted one reported in the literature. The hand-crafted circuit is very specific to the particular device of that family of FPGAs, whereas the proposed algorithm is device-independent. In addition, it took several man months to hand-craft the SBC, whereas the proposed algorithm took less than half-a-day.     

Reconfiguring one-time programmable FPGAs

Field-programmable gate arrays can suffer from a variety of faults, ranging from wire anomalies and defects to inoperative programmable connections. The solution to these faults depends on whether or not we are dealing with a reprogrammable FPGA or a one time programmable (OTP) FPGA. To correct faults, developers can reconfigure FPGAs such as those made by Xilinx and Altera by reprogramming. These devices can be programmed many times, for different designs and applications. Correcting faults in OTP FPGAs, such as those made by Actel is more difficult. For one thing, OTP FPGAs are based on antifuses. With an antifuse, the FPGAs configuration information has an initial (default) value that can be changed, but once changed cannot be restored. Therefore, the procedures to bypass faulty cells or faulty routing in an OTP FPGA must meet more stringent requirements than for reprogrammable FPGAs. The “Reconfiguration Approaches” sidebar describes two methods other researchers have tried. This article describes our approach to reconfiguring OTP FPGAs. We explain how we determine if reconfiguration is feasible, the algorithms we used, and the results of our experiments on a generic OTP FPGA model and a generic detail router     

Evaluating fault-tolerance of redundant FPGA structures using Boolean difference calculus

The reliability of FPGA based hardware designs has become an important field of research particularly for space computing. Traditionally, redundancy is utilized in FPGA based designs to achieve reliable or error-tolerant computing. However, the redundant designs vary according to the granularity level and the voter placement algorithms used for the hardware design. The resulting circuit configurations vary in area, latency and power as well as in the achieved reliability. While the evaluation of area, latency and power is done by the FPGA design tools, quantitative data for reliability are usually not derived. Consequently, there is a need for an automated reliability evaluation tool especially considering the huge design space of redundant circuit structures. In this paper, we combine the Boolean difference error calculator (BDEC), a probabilistic reliability model for hardware designs, with a reliability model for fault-tolerant circuit structures. As a result, we are able to study the reliability of fault-tolerant circuit structures at the logic layer. We focus on fault-tolerant circuits to be implemented in FPGAs and show how to extend our combined model from combinational to sequential circuits. For an automated analysis, we develop a MATLAB-based tool utilizing our extended BDEC model. With this tool, we conduct a case study on dynamic reliability management and show how quantitative reliability data obtained from this tool improves the four-dimensional Pareto optimization for area, latency, power and reliability.     

Performance evaluation and optimal design for FPGA-based digit-serial DSP functions

As field programmable gate array (FPGA) technology has steadily improved, FPGAs are now viable alternatives to other technology implementations for high-speed classes of digital signal processing (DSP) applications. Digit-serial DSP architectures have been effective implementation method for FPGAs. In this work, a method of implementing digit-serial DSP architectures on FPGAs is presented, and their performance is evaluated with the objective of finding and developing the most efficient digit-serial DSP architectures on FPGAs. This paper discusses area costs and operational delays of the various digit-serial DSP functions and presents the area/delay models on Xilinx XC4000-series FPGAs. These area/delay models can make predictions of performance and hardware resource utilization before a lengthy layout and synthesis process is undertaken. The results show that the area/delay models proposed here are valid and the digit-serial DSP designs are promising candidates for efficient FPGA implementations.     

Algorithm and Implementation of Parallel Multiplication in a Mixed Number System

This paper presents a high-speed multiplication algorithm for the mixed number system of the ordinarybinary number and the symmetric redundant binary number.It is implemented with the multivalned logictheory,and 3-valued and 2-valued circuits are used.The 3-valued circuit proposed in this paper is anemitter-coupled logic circuit with high speed,simplicity and powerful functions.A 3-valued ECL thresholdgate can simultaneously produce six types of one-variable operations.The array multiplier,designed withthe algorithm and the circuits,is fast and simple,and is suitable for building LSI.It can be used in a high-speed computer just as an ordinary binary multiplier.     

A programmable spike-timing based circuit block for reconfigurable neuromorphic computing

A generic programmable spike-timing based circuit which forms the building block of a reconfigurable neuromorphic array is implemented in analog VLSI. An array of programmable spike time event coded circuit blocks is configured to implement functional circuit blocks of a spike time based neuromorphic model. A reconfigurable neuromorphic array chip with 10 event blocks is fabricated using Austria Microsystems m CMOS technology to demonstrate the functionality of the circuits in silicon.     

A novel genetic algorithm with different structure selection for circuit design optimization

In the traditional GA, the tournament selection for crossover and mutation is based on the fitness of individuals. This can make convergence easy, but some useful genes may be lost. In selection, as well as fitness, we consider the different structure of each individual compared with an elite one. Some individuals are selected with many different structures, and then crossover and mutation are performed from these to generate new individuals. In this way, the GA can increase diversification into search spaces so that it can find a better solution. One promising application of GA is evolvable hardware (EHW), which is a new research field to synthesize an optimal circuit. We propose an optimal circuit design by using a GA with a different structure selection (GAdss), and with a fitness function composed of circuit complexity, power, and signal delay. Its effectiveness is shown by simulations. From the results, we can see that the best elite fitness, the average fitness value of correct circuits, and the number of correct circuits with GAdss are better than with GA. The best case of optimal circuits generated by GAdss is 8.1% better in evaluation value than that by traditional GA.     

Optimal utilization of available reconfigurable hardware resources

Field programmable gate arrays (FPGAs) are continuously gaining momentum and becoming essential part of today’s digital systems and applications. The growing use of these devices coupled with increasingly more complex and integrated designs necessitates search for techniques in efficient utilization of their internal resources. Standard HDL coding techniques and synthesis tools implement logic to look up table (LUT) based architecture. The resulting design utilizes more area on the chip and some fast and dedicated areas and resources of the chip remain unutilized. This in turn results in slower clock rates and larger critical path lengths, hence the design remains inefficient in terms of both speed and area. In this paper we present and discuss techniques to effectively utilize the FPGA dedicated resources in order to speed up achievable clock rates and reduce the FPGA area utilization. Various useful HDL constructs are presented that utilize dedicated hardware resources of modern Xilinx FPGAs. Optimization techniques are presented with implementation examples and corresponding quantitative performance evaluation. In most of the cases we have achieved 50% reduction in chip area utilization and simultaneously improved timing results significantly.     

Toward Increasing FPGA Lifetime

Field-Programmable Gate Arrays (FPGAs) have been aggressively moving to lower gate length technologies. Such a scaling of technology has an adverse impact on the reliability of the underlying circuits in such architectures. Various different physical phenomena have been recently explored and demonstrated to impact the reliability of circuits in the form of both transient error susceptibility and permanent failures. In this work, we analyze the impact of two different types of hard errors, namely, Time- Dependent Dielectric Breakdown (TDDB) and Electromigration (EM) on FPGAs. We also study the performance degradation of FPGAs over time caused by Hot-Carrier Effects (HCE) and Negative Bias Temperature Instability (NBTI). Each study is performed on the components of FPGAs most affected by the respective phenomena, from both the performance and reliability perspective. Different solutions are demonstrated to counter each failure and degradation phenomena to increase the operating lifetime of the FPGAs.     

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

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

Orthogonal defect classification-a concept for in-processmeasurements

Orthogonal defect classification (ODC), a concept that enables in-process feedback to software developers by extracting signatures on the development process from defects, is described. The ideas are evolved from an earlier finding that demonstrates the use of semantic information from defects to extract cause-effect relationships in the development process. This finding is leveraged to develop a systematic framework for building measurement and analysis methods. The authors define ODC and discuss the necessary and sufficient conditions required to provide feedback to a developer; illustrate the use of the defect type distribution to measure the progress of a product through a process; illustrate the use of the defect trigger distribution to evaluate the effectiveness and eventually the completeness of verification processes such as inspection or testing; provides sample results from pilot projects using ODC; and open the doors to a wide variety of analysis techniques for providing effective and fast feedback based on the concepts of ODC     

门电路延时查找表的凸平滑算法

门电路延时参数的查找表在电路逻辑综合及静态时序分析中均有重要应用。其精度及数学上的凸特性和平滑程度对电路最终的设计结果有较大的影响。基于绝大多数门电路延时模型的实际特性,提出了一种在给定查找表的基础上进行凸平滑的算法。该算法使用了计算机辅助几何设计中的张量积B样条技术,并通过调整样条系数使平滑后得到的延时模型为凸函数。为了使新延时模型的构造快速且准确,样条系数的求解过程被描述为一个半定规划问题,因此得到的新模型具有全局最小的拟合误差。最后以标准单元库门电路通过SPICE仿真得到的查找表数据为实例,并与其他方法进行对照,验证了该方法的有效性和精度。     

Xilinx XC4000系列FPGA自动测试平台搭建

随着FPGA的发展,FPGA测试技术也得到了相应的发展。因为FPGA的结构和传统专用集成电路(ASIC)有着本质的区别,在FPGA中不能形成可测性设计电路,但它的可编程能力决定了其测试电路可以通过编程的方法来实现。本文讨论了Xilinx XC4000系列FPGA中CLB资源和互连资源的自动测试方法。而且提出了一种新的测试资源坐标定位方法,使得由软件仿真向器件真实测试取得了突破。并搭建了硬件测试平台。     

Using laser defect avoidance to build large-area FPGAs

Wafer-scale techniques of defect avoidance expend the complexity limits of field-programmable gate arrays by routing around flawed blocks to build working systems. Experiments on test FPGAs show that laser defect avoidance produces signal delays half those of active switches