Approximate circuits often achieve exceptional trade-offs between computational accuracy and hardware efficiency, making them attractive for deployment as reusable Intellectual Property (IP) cores. However, safeguarding such circuits against piracy is critical for enabling sustainable commercialization of approximate computing. This work addresses the emerging challenge of IP protection and piracy detection in the context of approximate hardware. We introduce a novel adversarial threat model, approximate obfuscation, in which an attacker not only conceals the design through structural obfuscation but also introduces functional modifications to ensure that the resulting circuit exhibits nearly identical error characteristics and hardware metrics as the original IP. To counter this threat, we propose an automated framework that extracts and compares statistical error profiles of protected IP cores and suspicious circuits, enabling systematic detection of potential IP theft. Through extensive experiments on a diverse set of approximate multipliers, we analyze the resilience of different approximate multipliers against approximate obfuscation. Our results provide new insights into the interplay between obfuscation, approximation, and IP protection.

A new field programmable gate array (FPGA)-based emulation platform is proposed to accelerate fault tolerance analysis of inference accelerators of convolutional neural networks (CNN). For a given CNN model, hardware accelerator architecture, and FT analysis target, an FPGA-based CNN implementation is generated (with the help of the Tengine framework), and fault injection logic is added. In our first case study, we report how the classification accuracy drop depends on the faults injected into multipliers used in Multiply-and-Accumulate Units of NVDLA inference accelerator executing ResNet-18 CNN. The FT analysis emulated on Zynq UltraScale+ SoC is an order of magnitude faster than software emulation.

Hardware-aware neural architecture search (HW-aware NAS) methods are crucial for designing and optimizing convolutional neural networks (CNNs) and their efficient deployment on hardware accelerators. In this work, we analyze two HW-aware NAS methods, EvoApproxNAS and ApproxDARTS, and investigate the impact of precise hardware parameter measurement on the performance of resulting CNNs. In particular, we compare the precise measurement of inference energy using the extended Timeloop tool with the original approach employed by EvoApproxNAS and ApproxDARTS, which relies on a simple analytical energy estimation based on the number of multiplications performed during the inference. The analysis demonstrates how improved energy measurements can enhance the search process of HW-aware NAS methods, resulting in more energy-efficient architectures. Our results show that without precise hardware parameter measurement, the HW-aware NAS can produce acceptable results but may fail to fully exploit the potential of hardware accelerator, especially if the 8×N -bit approximate multipliers are implemented in convolutional layers.

A fundamental assumption for search-based circuit approximation methods is the ability to massively and efficiently traverse the search space and evaluate candidate solutions. For complex approximate circuits (adders and multipliers), common error metrics, and error analysis approaches (SAT solving, BDD analysis), we perform a detailed analysis to understand the behavior of the error analysis methods under constrained resources, such as limited execution time. In addition, we show that when evaluating the error of a candidate approximate circuit, it is highly beneficial to reuse knowledge obtained during the evaluation of previous circuit instances to reduce the total design time. When an adaptive search strategy that drives the search towards promptly verifiable approximate circuits is employed, the method can discover circuits that exhibit better trade-offs between error and desired parameters (such as area) than the same method with unconstrained verification resources and within the same overall time budget. For 16-bit and 20-bit approximate multipliers, it was possible to achieve a 75% reduction in area when compared with the baseline method.

Energy efficiency and memory footprint of a convolutional neural network (CNN) implemented on a CNN inference accelerator depend on many factors, including a weight quantization strategy (i.e., data types and bit-widths) and mapping (i.e., placement and scheduling of DNN elementary operations on hardware units of the accelerator). We show that enabling rich mixed quantization schemes during the implementation can open a previously hidden space of mappings that utilize the hardware resources more effectively. CNNs utilizing quantized weights and activations and suitable mappings can significantly improve trade-offs among the accuracy, energy, and memory requirements compared to less carefully optimized CNN implementations. To find, analyze, and exploit these mappings, we: (i) extend a general-purpose state-of-the-art mapping tool (Timeloop) to support mixed quantization, which is not currently available; (ii) propose an efficient multi-objective optimization algorithm to find the most suitable bit-widths and mapping for each DNN layer executed on the accelerator; and (iii) conduct a detailed experimental evaluation to validate the proposed method. On two CNNs (MobileNetV1 and MobileNetV2) and two accelerators (Eyeriss and Simba) we show that for a given quality metric (such as the accuracy on ImageNet), energy savings are up to 37% without any accuracy drop.

The use of evolutionary algorithms (EAs) for the automated design of programs, electronic circuits, neural networks, and other computational structures has become a fruitful approach in the last two decades. The advantage of EAs is that they can handle the design process in a holistic, multi-objective way and create solutions with unique properties. This tutorial surveys the key ingredients of EAs and focuses mainly on genetic programming. It presents several techniques (such as incorporating formal verification methods and surrogate models) to improve the scalability of the method. Examples of evolved solutions (approximate arithmetic circuits, neural network architectures, and image filters) that show unique properties compared to conventional designs are presented and discussed.

Integrating the principles of approximate computing into the design of hardware-aware deep neural networks (DNN) has led to DNNs implementations showing good output quality and highly optimized hardware parameters such as low latency or inference energy. In this work, we present ApproxDARTS, a neural architecture search (NAS) method enabling the popular differentiable neural architecture search method called DARTS to exploit approximate multipliers and thus reduce the power consumption of generated neural networks. We showed on the CIFAR-10 data set that the ApproxDARTS is able to perform a complete architecture search within less than 10 GPU hours and produce competitive convolutional neural networks (CNN) containing approximate multipliers in convolutional layers. For example, ApproxDARTS created a CNN showing an energy consumption reduction of (a) 53.84% in the arithmetic operations of the inference phase compared to the CNN utilizing the native 32-bit floating-point multipliers and (b) 5.97% compared to the CNN utilizing the exact 8-bit fixed-point multipliers, in both cases with a negligible accuracy drop. Moreover, the ApproxDARTS is 2.3× faster than a similar but evolutionary algorithm-based method called EvoApproxNAS.

The polygenic risk score has proven to be a valuable tool for assessing an individual's genetic predisposition to phenotype (disease) within biomedicine in recent years. However, traditional regression-based methods for polygenic risk scores calculation have limitations that can impede their accuracy and predictive power. This study introduces an innovative approach to enhance polygenic risk scores calculation through the application of genetic programming. By harnessing the power of genetic programming, we aim to overcome the limitations of traditional regression techniques and improve the accuracy of polygenic risk scores predictions. Specifically, we showed that a polygenic risk score generated through Cartesian genetic programming yielded comparable or even more robust statistical distinctions between groups that we evaluated within three independent case studies.

Levodopa, a drug used to treat symptoms of Parkin-son's disease, is connected to side effects known as Levodopa-induced dyskinesia (LID). LID is difficult to classify during a physician's visit. A wearable device allowing long-term and continuous classification would significantly help with dosage adjustments. This paper deals with an automated design of energy-efficient hardware accelerators for such LID classifiers. The proposed accelerator consists of a feature extractor and a classifier co-designed using genetic programming. Improvements are achieved by introducing a variable bit width for arithmetic operators, eliminating redundant registers, and using precise energy consumption estimation for Pareto front creation. Evolved solutions reduce energy consumption while maintaining classification accuracy comparable to the state of the art.

Taking levodopa, a drug used to treat symptoms of Parkinson’s disease, is often connected with severe side effects, known as Levodopa-induced dyskinesia (LID). It can fluctuate in severity throughout the day and thus is difficult to classify during a short period of a physician’s visit. A low-power wearable classifier enabling long-term and continuous LID classification would thus significantly help with LID detection and dosage adjustment. This paper deals with an automated design of energy-efficient hardware accelerators of LID classifiers that can be implemented in wearable devices. The accelerator consists of a feature extractor and a classification circuit co-designed using genetic programming (GP). We also introduce and evaluate a fast and accurate energy consumption estimation method for the target architecture of considered classifiers. In a multiobjective design scenario, GP evolves solutions showing the best trade-offs between accuracy and energy. Compared to the state-of-the-art solutions, the proposed method leads to classifiers showing a comparable accuracy while the energy consumption is reduced by 49 %.

Design methodologies developed for optimizing hardware implementations of convolutional neural networks (CNN) or searching for new hardware-aware neural architectures rely on the fast and reliable estimation of key hardware parameters, such as the energy needed for one inference. Utilizing approximate circuits in hardware accelerators of CNNs faces the designers with new problems during their simulation — commonly used tools (TimeLoop, Accelergy, Maestro) do not support approximate arithmetic operations. This work addresses the fast and efficient prediction of consumed energy in hardware accelerators of CNNs that utilize approximate circuits such as approximate multipliers. First, we extend the state-of-the-art software frameworks TimeLoop and Accelergy to predict the inference energy when exact multipliers are replaced with various approximate implementations. The energies obtained using the modified tools are then considered the ground truth (reference) values. Then, we propose and evaluate, using two accelerators (Eyeriss and Simba) and two types of networks (CNNs generated by EvoApproxNAS and standard ResNet CNNs), two predictors of inference energy. We conclude that a simple predictor based on summing the energies needed for all multiplications highly correlates with the reference values if the CNN’s architecture is fixed. For complex CNNs with variable architectures typically generated by neural architecture search algorithms, a more sophisticated predictor based on a machine learning model has to be employed. The proposed predictors are 420-533× faster than reference solutions.

Generation and exploration of approximate circuits and accelerators has been a prominent research domain to achieve energy-efficiency and/or performance improvements. This research has predominantly focused on ASICs, while not achieving similar gains when deployed for FPGA-based accelerator systems, due to the inherent architectural differences between the two. In this work, we propose a novel framework, Xel-FPGAs, which leverages statistical or machine learning models to effectively explore the architecture-space of state-of-the-art ASIC-based approximate circuits to cater them for FPGA-based systems given a simple RTL description of the target application. We have also evaluated the scalability of our framework on a multi-stage application using a hierarchical search strategy. The Xel-FPGAs framework is capable of reducing the exploration time by up to 95%, when compared to the default synthesis, place, and route approaches, while identifying an improved set of Pareto-optimal designs for a given application, when compared to the state-of-the-art. The complete framework is open-source and available online at https://github.com/ehw-fit/xel-fpgas.

The non-local means image filter is a non-trivial denoising algorithm for color images utilizing floating-point arithmetic operations in its reference software implementation. In order to simplify this algorithm for an on-chip implementation, we investigate the impact of various number representations and approximate arithmetic operators on the quality of image filtering. We employ Cartesian Genetic Programming (CGP) to evolve approximate implementations of a 20-bit signed multiplier which is then applied in the image filter instead of the conventional 32-bit floating-point multiplier. In addition to using several techniques that reduce the huge design cost, we propose a new mutation operator for CGP to improve the search quality and obtain better approximate multipliers than with CGP utilizing the standard mutation operator. Image filters utilizing evolved approximate multipliers can save 35% in power consumption of multiplication operations for a negligible drop in the image filtering quality.

Fast and high-quality network flow hashing is an essential operation in many high-speed network systems such as network monitoring probes. We propose a multi-objective evolutionary design method capable of evolving hash functions for IPv4 and IPv6 flow hashing. Our approach combines Cartesian genetic programming (CGP) with Non-dominated sorting genetic algorithm II (NSGA-II) and aims to optimize not only the quality of hashing, but also the execution time of the hash function. The evolved hash functions are evaluated on real data sets collected in computer network and compared against other evolved and conventionally created hash functions.

The multiplicative complexity (MC) is a cryptographic criterion that describes the vulnerability of a Boolean function to certain algebraic attacks, and in many important cryptographic applications also determines the computational cost. In this paper, we use Cartesian genetic programming to find various types of cryptographic Boolean functions, improve their implementation to achieve the minimal MC, and examine how difficult these optimized functions are to find in comparison to functions than only need to satisfy some base cryptographic criteria. To provide a comparison with other state-of-the-art optimization approaches, we also use our method to improve the implementation of several generic benchmark circuits. Our results provide new upper limits on MC of certain functions, show that our approach is competitive, and also that finding functions with an implementation that has better MC is not mutually exclusive with improving other performance criteria.

There has been abundant research on the development of Approximate Circuits (ACs) for ASICs. However, previous studies have illustrated that ASIC-based ACs offer asymmetrical gains in FPGA-based accelerators. Therefore, an AC that might be pareto-optimal for ASICs might not be pareto-optimal for FPGAs. In this work, we present the ApproxFPGAs methodology that uses machine learning models to reduce the exploration time for analyzing the state-of-the-art ASIC-based ACs to determine the set of pareto-optimal FPGA-based ACs. We also perform a case-study to illustrate the benefits obtained by deploying these pareto-optimal FPGA-based ACs in a state-of-the-art automation framework to systematically generate pareto-optimal approximate accelerators that can be deployed in FPGA-based systems to achieve high performance or low-power consumption.

Energy efficiency of hardware accelerators of deep neural networks (DNN) can be improved by introducing approximate arithmetic circuits. In order to quantify the error introduced by using these circuits and avoid the expensive hardware prototyping, a software emulator of the DNN accelerator is usually executed on CPU or GPU. However, this emulation is typically two or three orders of magnitude slower than a software DNN implementation running on CPU or GPU and operating with standard floating point arithmetic instructions and common DNN libraries. The reason is that there is no hardware support for approximate arithmetic operations on common CPUs and GPUs and these operations have to be expensively emulated. In order to address this issue, we propose an efficient emulation method for approximate circuits utilized in a given DNN accelerator which is emulated on GPU. All relevant approximate circuits are implemented as look-up tables and accessed through a texture memory mechanism of CUDA capable GPUs. We exploit the fact that the texture memory is optimized for irregular read-only access and in some GPU architectures is even implemented as a dedicated cache. This technique allowed us to reduce the inference time of the emulated DNN accelerator approximately 200 times with respect to an optimized CPU version on complex DNNs such as ResNet. The proposed approach extends the TensorFlow library and is available online at github.com/ehw-fit/tf-approximate.

Today, the concept of approximation in computing is becoming more and more a “hot topic” to investigate how computing systems can be more energy efficient, faster, and less complex. Intuitively, instead of performing exact computations and, consequently, requiring a high amount of resources, Approximate Computing aims at selectively relaxing the specifications, trading accuracy off for efficiency. While Approximate Computing gives several promises when looking at systems' performance, energy efficiency and complexity, it poses significant challenges regarding the design, the verification, the test and the in-field reliability of Approximate Computing systems. This tutorial paper covers these aspects leveraging the experience of the authors in the field to present state-of-the-art solutions to apply during the different development phases of an Approximate Computing system.

Improving the accuracy of a neural network (NN) usually requires using larger hardware that consumes more energy. However, the error tolerance of NNs and their applications allow approximate computing techniques to be applied to reduce implementation costs. Given that multiplication is the most resource-intensive and power-hungry operation in NNs, more economical approximate multipliers (AMs) can significantly reduce hardware costs. In this article, we show that using AMs can also improve the NN accuracy by introducing noise. We consider two categories of AMs: 1) deliberately designed and 2) Cartesian genetic programing (CGP)-based AMs. The exact multipliers in two representative NNs, a multilayer perceptron (MLP) and a convolutional NN (CNN), are replaced with approximate designs to evaluate their effect on the classification accuracy of the Mixed National Institute of Standards and Technology (MNIST) and Street View House Numbers (SVHN) data sets, respectively. Interestingly, up to 0.63% improvement in the classification accuracy is achieved with reductions of 71.45% and 61.55% in the energy consumption and area, respectively. Finally, the features in an AM are identified that tend to make one design outperform others with respect to NN accuracy. Those features are then used to train a predictor that indicates how well an AM is likely to work in an NN.

Approximate computing is an emerging paradigm for developing highly energy-efficient computing systems such as various accelerators. In the literature, many libraries of elementary approximate circuits have already been proposed to simplify the design process of approximate accelerators. Because these libraries contain from tens to thousands of approximate implementations for a single arithmetic operation it is intractable to find an optimal combination of approximate circuits in the library even for an application consisting of a few operations. An open problem is "how to effectively combine circuits from these libraries to construct complex approximate accelerators". This paper proposes a novel methodology for searching, selecting and combining the most suitable approximate circuits from a set of available libraries to generate an approximate accelerator for a given application. To enable fast design space generation and exploration, the methodology utilizes machine learning techniques to create computational models estimating the overall quality of processing and hardware cost without performing full synthesis at the accelerator level. Using the methodology, we construct hundreds of approximate accelerators (for a Sobel edge detector) showing different but relevant tradeoffs between the quality of processing and hardware cost and identify a corresponding Pareto-frontier. Furthermore, when searching for approximate implementations of a generic Gaussian filter consisting of 17 arithmetic operations, the proposed approach allows us to identify approximately 103 highly relevant implementations from 1023 possible solutions in a few hours, while the exhaustive search would take four months on a high-end processor.

The rapid progress in artificial intelligence technologies based on deep and convolutional neural networks (CNN) has led to an enormous interest in efficient implementations of neural networks in embedded devices and hardware. We present a new software framework for the development of (approximate) convolutional neural networks in which the user can define and use various data types for forward (inference) procedure, backward (training) procedure and weights. Moreover, non-standard arithmetic operations such as approximate multipliers can easily be integrated into the CNN under design. This flexibility enables to analyze the impact of chosen data types and non-standard arithmetic operations on CNN training and inference efficiency. The framework was implemented in C++ and evaluated using several case studies.

We propose an application-tailored data-driven fully automated method for functional approximation of combinational circuits. We demonstrate how an application-level error metric such as the classification accuracy can be translated to a component-level error metric needed for an efficient and fast search in the space of approximate low-level components that are used in the application. This is possible by employing a weighted mean error distance (WMED) metric for steering the circuit approximation process which is conducted by means of genetic programming. WMED introduces a set of weights (calculated from the data distribution measured on a selected signal in a given application) determining the importance of each input vector for the approximation process. The method is evaluated using synthetic benchmarks and application-specific approximate MAC (multiply-and-accumulate) units that are designed to provide the best trade-offs between the classification accuracy and power consumption of two image classifiers based on neural networks.

The state-of-the-art approaches employ approximate computing to reduce the energy consumption of DNN hardware. Approximate DNNs then require extensive retraining afterwards to recover from the accuracy loss caused by the use of approximate operations. However, retraining of complex DNNs does not scale well. In this paper, we demonstrate that efficient approximations can be introduced into the computational path of DNN accelerators while retraining can completely be avoided. ALWANN provides highly optimized implementations of DNNs for custom low-power accelerators in which the number of computing units is lower than the number of DNN layers. First, a fully trained DNN (e.g., in TensorFlow) is converted to operate with 8-bit weights and 8-bit multipliers in convolutional layers. A suitable approximate multiplier is then selected for each computing element from a library of approximate multipliers in such a way that (i) one approximate multiplier serves several layers, and (ii) the overall classification error and energy consumption are minimized. The optimizations including the multiplier selection problem are solved by means of a multiobjective optimization NSGA-II algorithm. In order to completely avoid the computationally expensive retraining of DNN, which is usually employed to improve the classification accuracy, we propose a simple weight updating scheme that compensates the inaccuracy introduced by employing approximate multipliers. The proposed approach is evaluated for two architectures of DNN accelerators with approximate multipliers from the open-source “EvoApprox” library, while executing three versions of ResNet on CIFAR-10. We report that the proposed approach saves 30% of energy needed for multiplication in convolutional layers of ResNet-50 while the accuracy is degraded by only 0.6% (0.9% for the ResNet-14). The proposed technique and approximate layers are available as an open-source extension of TensorFlow at https://github.com/ehw-fit/tf-approximate.

The paper is a contribution to the 50th anniversary celebration of the International Test Conference (ITC) and its Global Test Forum (GTF), which honors the geographic breadth of the test community and highlights the global reach of ITC during the past 50 years. It covers the past, present, and future of the International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS), a symposium which belongs to prominent test technology related events initiated and supported by the ITC.

In genetic programming (GP), computer programs are often coevolved with training data subsets that are known as fitness predictors. In order to maximize performance of GP, it is important to find the most suitable parameters of coevolution, particularly the fitness predictor size. This is a very time-consuming process as the predictor size depends on a given application, and many experiments have to be performed to find its suitable size. A new method is proposed which enables us to automatically adapt the predictor and its size for a given problem and thus to reduce not only the time of evolution, but also the time needed to tune the evolutionary algorithm. The method was implemented in the context of Cartesian genetic programming and evaluated using five symbolic regression problems and three image filter design problems. In comparison with three different CGP implementations, the time required by CGP search was reduced while the quality of results remained unaffected.

Randomness testing is an important procedure that bit streams, produced by critical cryptographic primitives such as encryption functions and hash functions, have to undergo. In this paper, a new hardware platform for the randomness testing is proposed. The platform exploits the principles of genetic programming, which is a machine learning technique developed for the automated program and circuit design. The platform is capable of evolving efficient randomness distinguishers directly on a chip. Each distinguisher is represented as a Boolean polynomial in the algebraic normal form. The randomness testing is conducted for bit streams that are either stored in an on-chip memory or generated by a circuit placed on the chip. The platform is developed with a Xilinx Zynq-7000 All Programmable System on Chip that integrates a field programmable gate array with on-chip ARM processors. The platform is evaluated in terms of the quality of randomness testing, performance, and resources utilization. With power budget less than 3 W, the platform provides comparable randomness testing capabilities with the standard testing batteries running on a personal computer.

Approximate circuits with relaxed requirements on functional correctness play an important role in the development of resource-efficient computer systems. Designing approximate circuits is a very complex and time-demanding process trying to find optimal trade-offs between the approximation error and resource savings. In this paper, we present ADAC—a novel framework for automated design of approximate arithmetic circuits. ADAC integrates in a unique way efficient simulation and formal methods for approximate equivalence checking into a search-based circuit optimisation. To make ADAC easily accessible, it is implemented as a module of the ABC tool: a state-of-the-art system for circuit synthesis and verification. Within several hours, ADAC is able to construct high-quality Pareto sets of complex circuits (including even 32-bit multipliers), providing useful trade-offs between the resource consumption and the error that is formally guaranteed. This demonstrates outstanding performance and scalability compared with other existing approaches.

The security of cryptographic algorithms (such as block ciphers and hash functions) is often evaluated in terms of their output randomness. This paper presents a novel method for the statistical randomness testing of cryptographic primitives, which is based on the evolutionary construction of the so-called randomness distinguisher. Each distinguisher is represented as a Boolean polynomial in the Algebraic Normal Form. The previous approach, in which the distinguishers were developed in two phases by means of the brute-force method, is replaced with a more scalable evolutionary algorithm (EA). On seven complex datasets, this EA provided distinguishers of the same quality as the previous approach, but the execution time was in practice reduced 40 times. This approach allowed us to perform a more efficient search in the space of Boolean distinguishers and to obtain more complex high-quality distinguishers than the previous approach.

Two AxC techniques have been successfully applied to hardware components. The first one is the functional approximation [1]that modifies the circuit structure replacing the original function F with the function G. G implementation leads to area/energy reduction at the cost of reduced accuracy, meaning that some errors can be observed at the outputs of G. The observed errors are a variation between the output values of F (precise) and G (approximate). The variation is the accuracy loss measured by means of quality metric(s) [1]. The second AxC technique is the over-scaling based approximation. Basically, the HW component is forced to work outside its specified operating conditions [1]. The classical example is the reduction of the supply voltage under the minimum value.

Hashing is a critical function in capturing and analysis of network flows as its quality and execution time influences the maximum throughput of network monitoring devices. In this paper, we propose a multi-objective linear genetic programming approach to evolve fast and high-quality hash functions for common processors. The search algorithm simultaneously optimizes the quality of hashing and the execution time. As it is very time consuming to obtain the real execution time for a candidate solution on a particular processor, the execution time is estimated in the fitness function. In order to demonstrate the superiority of the proposed approach, evolved hash functions are compared with hash functions available in the literature using real-world network data.

Approximate circuits and approximate circuit design methodologies attracted a significant attention of researchers as well as industry in recent years. In order to accelerate the approximate circuit and system design process and to support a fair benchmarking of circuit approximation methods, we propose a library of approximate adders and multipliers called EvoApprox8b. This library contains 430 non-dominated 8-bit approximate adders created from 13 conventional adders and 471 non-dominated 8-bit approximate multipliers created from 6 conventional multipliers. These implementations were evolved by a multi-objective Cartesian genetic programming. The EvoApprox8b library provides Verilog, Matlab and C models of all approximate circuits. In addition to standard circuit parameters, the error is given for seven different error metrics.

Video processing performed directly on IoT nodes is one of the most performance as well as energy demanding applications for current IoT technology. In order to support real-time high-definition video, energy-reduction optimizations have to be introduced at all levels of the video processing chain. This paper deals with an efficient implementation of Discrete Cosine Transform (DCT) blocks employed in video compression based on the High Efficiency Video Coding (HEVC) standard. The proposed multiplierless 4-input DCT implementations contain approximate adders and subtractors that were obtained using genetic programming. In order to manage the complexity of evolutionary approximation and provide formal guarantees in terms of errors of key circuit components, the worst and average errors were determined exactly by means of Binary decision diagrams. Under conditions of our experiments, approximate 4-input DCTs show better quality/power trade-offs than relevant implementations available in the literature. For example, 25% power reduction for the same error was obtained in comparison with a recent highly optimized implementation.

We present a novel method allowing one to approximate complex arithmetic circuits with formal guarantees on the approximation error. The method integrates in a unique way formal techniques for approximate equivalence checking into a search-based circuit optimisation algorithm. The key idea of our approach is to employ a novel search strategy that drives the search towards promptly verifiable approximate circuits. The method was implemented within the ABC tool and extensively evaluated on functional approximation of multipliers (with up to 32-bit operands) and adders (with up to 128-bit operands). Within a few hours, we constructed a high-quality Pareto set of 32-bit multipliers providing trade-offs between the circuit error and size. This is for the first time when such complex approximate circuits with formal error guarantees have been derived, which demonstrates an outstanding performance and scalability of our approach compared with existing methods that have either been applied to the approximation of multipliers limited to 8-bit operands or statistical testing has been used only. Our approach thus significantly improves capabilities of the existing methods and paves a way towards an automated design process of provably-correct circuit approximations.

A new design paradigm - approximate computing - was established to investigate how computer systems can be made better - more energy efficient, faster, and less complex - by relaxing the requirement that they are exactly correct. The purpose of this paper is to introduce the principles of approximate computing and survey the research conducted in major subareas of approximate computing which are relevant for design and test of digital circuits.

Approximate computing is capable of exploiting the error resilience of various applications with the aim of improving their parameters such as performance, energy consumption and area on a chip. In this paper, a new systematic approach for the approximation and optimization of circuits intended for LUT-based field programmable gate arrays (FPGAs) is proposed. In order to deliver a good trade-off between the quality of processing and implementation cost, the method employs a genetic programming-based optimization engine. The circuits are internally represented and optimized at the gate level. The resulting LUT-based netlists are obtained using a commercial FPGA tool. In the experimental part, four commonly available commercial FPGA design tools (Xilinx ISE, Xilinx Vivado, Precision, and Quartus) and state-of-the-art academia circuit synthesis and optimization tool ABC are compared. The quality of approximated circuits is evaluated using relaxed equivalence checking by means of Binary decision diagrams. An important conclusion is that the improvements (i.e. area reductions) at the gate level are preserved by the FPGA design tools and thus the number of LUTs is also adequately reduced. It was shown that the current state-of-the-art synthesis tools provide (for some instances) the results that are far from an optimum. For example, a 40% reduction (68 LUTs) was achieved for `clmb' benchmark circuit (Bus Interface) without introducing any error. Additional 43% reduction can be obtained by introducing only a 0.1% error.

High speed networks operating at 100 Gbps pose many challenges for hardware and software involved in the packet processing. As the time to process one packet is very short the corresponding operations have to be optimized in terms of the execution time. One of them is non-cryptographic hashing implemented in order to accelerate traffic flow identification. In this paper, a method based on linear genetic programming is presented, which is capable of evolving high-quality hash functions primarily optimized for speed. Evolved hash functions are compared with conventional hash functions in terms of accuracy and execution time using real network data.

Artificial neural networks (NN) have shown a significant promise in difficult tasks like image classification or speech recognition. Even well-optimized hardware implementations of digital NNs show significant power consumption. It is mainly due to non-uniform pipeline structures and inherent redundancy of numerous arithmetic operations that have to be performed to produce each single output vector. This paper provides a methodology for the design of well-optimized power-efficient NNs with a uniform structure suitable for hardware implementation. An error resilience analysis was performed in order to determine key constraints for the design of approximate multipliers that are employed in the resulting structure of NN. By means of a search based approximation method, approximate multipliers showing desired tradeoffs between the accuracy and implementation cost were created. Resulting approximate NNs, containing the approximate multipliers, were evaluated using standard benchmarks (MNIST dataset) and a real-world classification problem of Street-View House Numbers. Significant improvement in power efficiency was obtained in both cases with respect to regular NNs. In some cases, 91% power reduction of multiplication led to classification accuracy degradation of less than 2.80%. Moreover, the paper showed the capability of the back propagation learning algorithm to adapt with NNs containing the approximate multipliers.

Technology scaling poses an increasing challenge to the reliability of digital circuits. Hardware redundancy solutions, such as triple modular redundancy (TMR), produce very high area overhead, so partial redundancy is often used to reduce the overheads. Approximate logic circuits provide a general framework for optimized mitigation of errors arising from a broad class of failure mechanisms, including transient, intermittent, and permanent failures. However, generating an optimal redundant logic circuit that is able to mask the faults with the highest probability while minimizing the area overheads is a challenging problem. In this study, we propose and compare two new approaches to generate approximate logic circuits to be used in a TMR schema. The probabilistic approach approximates a circuit in a greedy manner based on a probabilistic estimation of the error. The evolutionary approach can provide radically different solutions that are hard to reach by other methods. By combining these two approaches, the solution space can be explored in depth. Experimental results demonstrate that the evolutionary approach can produce better solutions, but the probabilistic approach is close. On the other hand, these approaches provide much better scalability than other existing partial redundancy techniques.

In approximate computing, the requirement of perfect functional behavior can be relaxed because some applications are inherently error resilient. Approximate circuits, which fall into the approximate computing paradigm, are designed in such a way that they do not fully implement the logic behavior given by the specification and, hence, their accuracy can be exchanged for lower area, delay or power consumption. In order to automate the design process, we propose to evolve approximate digital circuits that show a minimal error for a supplied amount of resources. The design process, which is based on Cartesian genetic programming (CGP), can be repeated many times in order to obtain various tradeoffs between the accuracy and area. A heuristic seeding mechanism is introduced to CGP, which allows for improving not only the quality of evolved circuits, but also reducing the time of evolution. The efficiency of the proposed method is evaluated for the gate as well as the functional level evolution. In particular, approximate multipliers and median circuits that show very good parameters in comparison with other available implementations were constructed by means of the proposed method.

Field-programmable gate arrays (FPGAs) can be considered to be the most popular and successful platform for evolvable hardware. They allow one to establish and later reconfigure candidate solutions. Recent work in the field of evolvable hardware includes the use of virtual and native reconfigurations. Virtual reconfiguration is based on the change of functionality by hardware components implemented on top of FPGA resources. Native reconfiguration changes the FPGA resources directly by means provided by the FPGA manufacturer. Both of these approaches have their disadvantages. The virtual reconfiguration is characterized by lower maximal operational frequency of the resulting solutions, and the native reconfiguration is slower. In this work, a hybrid approach is used merging the advantages while limiting the disadvantages of the virtual and native reconfigurations. The main contribution is the new low-level architecture for evolvable hardware in the new Zynq-7000 all-programmable system-on-chip. The proposed architecture offers high flexibility in comparison with other evolvable hardware systems by considering direct modification of the reconfigurable resources. The impact of the higher reconfiguration time of the native approach is limited by the dense placement of the proposed reconfigurable processing elements. These processing elements also ensure fast evaluation of candidate solutions. The proposed architecture is evaluated by evolutionary design of switching image filters and edge detectors. The experimental results demonstrate advantages over the previous approaches considering the time required for evolution, area overhead, and flexibility.

Logic synthesis and optimization methods work either globally on the whole logic network or locally on preselected subnetworks. Evolutionary design methods have already been applied to evolve and optimize logic circuits at the global level. In this paper, we propose a new method based on Cartesian genetic programming (CGP) as a local area optimizer in combinational logic networks. First, a subcircuit is extracted from a complex circuit, then the subcircuit is optimized by CGP and finally the optimized subcircuit replaces the original one. The procedure is repeated until a termination criterion is satisfied. We present a performance comparison of local and global evolutionary optimization methods with a conventional approach based on ABC and analyze these methods using differently pre-optimized benchmark circuits. If a sufficient time is available, the proposed locally optimizing CGP gives better results than other locally operating methods reported in the literature; however, its performance is significantly worse than the evolutionary global optimization.

Approximate circuits are digital circuits which are intentionally designed in such a way that the specification is not met in terms of functionality in order to obtain some improvements in power consumption, performance or area, in comparison with fully functional circuits. In this paper, we propose to design approximate circuits using evolutionary design techniques. In particular, different error metrics are utilized to assess the circuit functionality. The proposed method begins with a fully functional circuit which is then intentionally degraded by Cartesian genetic programming (CGP) to obtain a circuit with a predefined error. In the second phase, CGP is used to minimize the number of gates or another error criterion. The effect of various error metrics on the search performance, area and power consumption is evaluated in the task of multiplier design.

Most implementations of Cartesian genetic programming (CGP) which can be found in the literature are sequential. However, solving complex design problems by means of genetic programming requires parallel implementations of search methods and fitness functions. This paper deals with the design of highly optimized implementations of CGP and their detailed evaluation in the task of evolutionary circuit design. Several sequential implementations of CGP have been analyzed and the effect of various additional optimizations has been investigated. Furthermore, the parallelism at the instruction, data, thread and process level has been applied in order to take advantage of modern processor architectures and computer clusters. Combinational adders and multipliers have been chosen to give a performance comparison with state of the art methods.

Multiple constant multiplier (MCM) is a digital circuit which multiplies its single input by N constants. As MCMs are composed of adders and shifters, their implementation cost is relatively low. In this paper, we propose a method for design of approximate multiple constant multipliers where the requirement on functional equivalence between the specification and implementation is relaxed in order to further reduce the area on a chip or minimize delay. The proposed method is based on multiobjective Cartesian Genetic Programming. It provides many trade-off solutions among accuracy, area and delay.

This paper presents an evolvable hardware system, fully contained in an FPGA, which is capable of autonomously generating digital processing circuits, implemented on an array of processing elements (PEs). Candidate circuits are generated by an embedded evolutionary algorithm and implemented by means of dynamic partial reconfiguration, enabling evaluation in the final hardware. The PE array follows a systolic approach, and PEs do not contain extra logic such as path multiplexers or unused logic, so array performance is high. Hardware evaluation in the target device and the fast reconfiguration engine used yield smaller reconfiguration than evaluation times. This means that the complete evaluation cycle is faster than software-based approaches and previous evolvable digital systems. The selected application is digital image filtering and edge detection. The evolved filters yield better quality than classic linear and nonlinear filters using mean absolute error as standard comparison metric. Results do not only show better circuit adaptation to different noise types and intensities, but also a nondegrading filtering behavior. This means they may be run iteratively to enhance filtering quality. These properties are even kept for high noise levels (40 percent). The system as a whole is a step toward fully autonomous, adaptive systems.

This paper proposes to implement multifunctional image filters using multifunctional gates such as polymorphic gates or multiplexed ordinary gates. The design procedure is based on evolutionary design and optimization conducted using Cartesian genetic programming (CGP). Because of the complexity of the problem the design is decomposed to two phases. In the first step, a multifunctional filter is evolved at the register-transfer level (RTL) using a set of processing elements containing functions such as minimum/maximum, minimum/average etc. over two pixels. In the second step, gate-level implementations of the processing elements utilized in evolved filters are designed and optimized using CGP in combination with conventional logic synthesis tools. It is shown that resulting filters exhibit good filtering capabilities. They are also area-efficient in comparison with solutions based on multiplexing of ordinary filters.

The paper deals with the evolutionary post synthesis optimization of complex combinational circuits with the aim of reducing the area on a chip as much as possible. In order to optimize complex circuits, Cartesian Genetic Programming (CGP) is employed where the fitness function is based on a formal equivalence checking algorithm rather than evaluating all possible input assignments. The standard selection strategy of CGP is modified to be more explorative and so agile in very rugged fitness landscapes. It was shown on the LGSynth93 benchmark circuits that the modified selection strategy leads to more compact circuits in roughly 50% cases. The average area improvement is 24% with respect to the results of conventional synthesis. Delay of optimized circuits was also analyzed.

Multifunctional (or polymorphic) gates are capable of performing two or more logic functions according to the setting of control signals. They can be considered as building blocks for new and cheap reconfigurable chips. In this paper, we utilized multifunctional components that can be implemented using multifunctional gates as building blocks of image filters. We applied genetic programming to evolve image filters performing different filtering tasks under different settings of control signals. Evolved solutions exhibit a significant reduction in utilized operations and interconnects w.r.t. the multiplexing of conventional solutions.

Multifunctional (or polymorphic) gates have been utilized as building blocks for multifunctional circuits that are capable of performing various logic functions under different settings of control signals. In order to effectively synthesize polymorphic circuits, several methods have been developed in the recent years. Unfortunately, the methods are applicable for small circuits only. In this paper, we propose a SAT-based functional equivalence checking algorithm to eliminate the fitness evaluation time which is the most critical overhead for genetic programming-based design and optimization of complex polymorphic circuits. The proposed approach has led to a 20%-40% reduction in gate count with respect to the solutions created using the polymorphic multiplexing.

Adaptive hardware requires some reconfiguration capabilities. FPGAs with native dynamic partial reconfiguration (DPR) support pose a dilemma for system designers: whether to use native DPR or to build a virtual reconfigurable circuit (VRC) on top of the FPGA which allows selecting alternative functions by a multiplexing scheme. This solution allows much faster reconfiguration, but with higher resource overhead. This paper discusses the advantages of both implementations for a 2D image processing matrix. Results show how higher operating frequency is obtained for the matrix using DPR. However, this is compensated in the VRC during evolution due to the comparatively negligible reconfiguration time. Regarding area, the DPR implementation consumes slightly more resources due to the reconfiguration engine, but adds further more capabilities to the system.

A genetic programming-based circuit synthesis method is proposed that enables to globally optimize the number of gates in circuits that have already been synthesized using common methods such as ABC and SIS. The main contribution is a proposal for a new fitness function that enables to significantly reduce the fitness evaluation time in comparison to the state of the art. The fitness function performs optimized equivalence checking using a SAT solver. It is shown that the equivalence checking time can significantly be reduced when knowledge of the parent circuit and its mutated offspring is taken into account. For a cost of a runtime, results of conventional synthesis conducted using SIS and ABC were improved by 20-40% for the LGSynth93 benchmarks.

The paper describes a series of experiments performed with the aim to analyze the fundamental impact of high temperatures on behavior of polymorphic digital circuits. These experiments were conducted using a reconfigurable polymorphic chip REPOMO32 which is configured (in addition to the configuration bit stream) using the level of power supply voltage (Vdd). Experiments show that polymorphic gates in the chip can be easily involved (in terms of functionality) not only by Vdd, but also by temperature. Because experiments also prove that the physical design of the REPOMO32 chip is robust enough to keep the functionality of all circuitry of the REPOMO32 and its dynamic parameters are stable enough under wide range of operating temperature, the chip can also be used for future designs of digital polymorphic circuits controlled by temperature.

This paper presents a new model for simulations of very large scale traffic networks. The proposed model is based on microscopic cellular automata (CA) extended to eliminate unwanted properties of ordinary CA based models, such as stopping from maximum speed to zero in one time step. The accuracy of the model has been validated by comparisons with various fundamental diagrams. A parallel implementation developed using the proposed model allows for an almost linear speedup. This allows to run a simulation multiple in real-time, that the traffic state of very large scale networks can be precisely predicted, for example, with various scenarios.

This paper deals with the evolutionary design of area-efficient filters for impulse bursts noise which is often present in remote sensing images such as satellite images. Evolved filters require much smaller area in the FPGA than conventional filters. Simultaneously, they exhibit at least comparable filtering capabilities with respect to conventional filters. Low-cost embedded systems equipped with low-end FPGAs represent a target application for presented filters.

Recently, it has been shown that synthesis of some circuits is quite difficult for conventional methods. In this paper we present a method of minimization of multi-level logic networks which can solve these difficult circuit instances. The synthesis problem is transformed on the search problem. A search algorithm called Cartesian genetic programming (CGP) is applied to synthesize various difficult circuits. Conventional circuit synthesis usually fails for these difficult circuits; specific synthesis processes must be employed to obtain satisfactory results. We have found that CGP is able to implicitly discover new efficient circuit structures. Thus, it is able to optimize circuits universally, regardless their structure. The circuit optimization by CGP has been found especially efficient when applied to circuits already optimized by a conventional synthesis. The total runtime is reduced, while the result quality is improved further more.

Evolutionary algorithms (EAs) are population-based search algorithms that have been successfully applied to solve hard optimization problems in many application domains. Since the early 1990's researchers have begun to apply evolutionary algorithms to synthesize electronic circuits. Nowadays it is evident that the evolutionary design approach can automatically create efficient electronic circuits in many domains. In this tutorial, fundamental concepts of evolutionary design of digital circuits are presented. In particular, the tutorial deals with Cartesian Genetic Programming (CGP) — a method of genetic programming that in many cases outperforms conventional synthesis tools in terms of achievable circuit size reduction. Innovative designs will be presented in domains of small combinational circuits (where the goal is to minimize the number of gates), middle-size circuits (such as image filters intended for FPGAs where the goal is to obtain the quality of filtering of conventional methods for a significantly lower cost on a chip) and large circuits (such as benchmark circuits for comparison of testability analysis methods), covering thus circuit complexity from a few gates to millions of gates. For example, one of evolved image filters is now protected by utility model in the Czech Republic (patent pending). Evolved circuits will be compared with the best-known conventional designs. We will also show how to deal with the so-called scalability problems of evolutionary design which have been identified as the most important problems from the point of view of practical applications. In summary, tutorial participants will become familiar with the state of the art methods in the area of digital circuit evolution. They will learn how to apply CGP, construct the fitness function and run experiments.

The paper describes a reconfigurable polymorphic chip REPOMO32, experiments carried out with this chip and provides report on important experiences with regard to practical applications of digital polymorphic circuits sensitive to the power supply voltage (Vdd). REPOMO32 contains array of 32 configurable logic elements which can perform polymorphic NAND/NOR function controlled by the level of the Vdd. Moreover, it can be declared as the first fabricated chip of this kind which basically allows the user to design more complex circuits than only a few gates.

The work reported in this paper describes the steps given towards an FPGA-based implementation of evolvable wavelet transforms for image compression in embedded systems. An Evolutionary Algorithm (EA) for the design and optimization of the transform coefficients is tailored for a suitable System on Chip implementation. Several cut downs on the computing requirements have been done to the original algorithm, adapting it for the FPGA implementation. What this paper addresses more specifically is the validation of the algorithm using fixed point arithmetic for the whole optimization process. The results show how high quality transforms are evolved from scratch with limited precision arithmetic. Also, preliminary results of the implementation in an FPGA device are included.

A new method is proposed to minimize the number of gates in combinational circuits using Cartesian Genetic Programming (CGP). We show that when the selection of the parent individual is performed on basis of its functionality solely (neglecting thus the phenotype size) smaller circuits can be evolved even if the number of gates is not considered by a fitness function. This phenomenon is confirmed on the evolutionary design of combinational multipliers.

Polymorphic digital circuits contain ordinary and polymorphic gates. In the past, Cartesian genetic programming (CGP) has been applied to synthesize polymorphic circuits at the gate level. However, this approach is not scalable. Experimental results presented in this paper indicate that larger and more efficient polymorphic circuits can be designed by a combination of conventional design methods (such as BDD, Espresso or ABC system) and evolutionary optimization (conducted by CGP). Proposed methods are evaluated on two benchmark circuits - multiplier/sorter and parity/majority circuits of variable input size.

We propose a new method for automatic generation of secrecy amplification protocols for wireless sensor networks, utilizing evolutionary algorithms. We were able to rediscover all published protocols for secrecy amplification we are aware of, and found a new protocol that outperforms the existing ones. An alternative construction of secrecy amplification protocols with a comparable fraction of secure links to that of the original "node-oriented" approach was also designed. This new construction exhibits only linear (instead of exponential) increase of necessary messages when the number of communication neighbours grows. This efficient protocol can significantly reduce the sensor battery power consumption because of the decreased message transmission rate. We used a combination of linear genetic programming and a network simulator in this work.

Polymorphic gates can be considered as a new reconfigurable technology capable of integrating logic functions with sensing in a single compact structure. Polymorphic gates whose logic function can be controlled by the level of the power supply voltage (Vdd) represent a special class of polymorphic gates. A new polymorphic NAND/NOR gate controlled by Vdd is presented. This gate was fabricated and utilized in a self-checking polymorphic adder. This paper presents an experimental evaluation of this novel implementation.

This article presents a new real-world application of evolutionary computing in the area of digital-circuits testing. A method is described which enables to evolve large synthetic RTL benchmark circuits with a predefined structure and testability. Using the proposed method, a new collection of synthetic benchmark circuits was developed. These benchmark circuits will be useful in a validation process of novel algorithms and tools in the area of digital-circuits testing. Evolved benchmark circuits currently represent the most complex benchmark circuits with a known level of testability. Furthermore, these circuits are the largest that have ever been designed by means of evolutionary algorithms. This work also investigates suitable parameters of the evolutionary algorithm for this problem and explores the limits in the complexity of evolved circuits.

This paper presents a new approach to the FPGA implementation of image filters which are utilized to remove the salt-and-pepper noise of high intensity (up to 70% of corrupted pixels). The proposed solution combines image filters designed by means of evolutionary algorithm with a simple human-designed preprocessing and post-processing unit. It provides the same filtering capability as a standard adaptive median filter; however, using four times less Virtex slices.

This paper shows that the evolutionary design of digital circuits which is conducted at the gate level is able to produce human-competitive circuits at the transistor level. In addition to standard gates, we utilize unconventional gates (such as the NAND/NOR gate and NOR/NAND gate) that consist of a few transistors but exhibit non-trivial 3-input logic functions. Novel implementations of adders and majority circuits evolved using these gates contain fewer transistors than the smallest existing implementations of these circuits. Moreover, it was shown that the use of these gates significantly improves the success rate of the search process.

A virtual reconfigurable circuit (VRC) is a domain-specific reconfigurable device developed using an ordinary FPGA in order to easily implement evolvable hardware applications. While a fast partial runtime reconfiguration and application-specific programmable elements represent the main advantages of VRC, the main disadvantage of the VRC is the area consumed. This study describes experiments conducted to estimate how the use of VRC influences the dependability of FPGA-based evolvable systems. It is shown that these systems are not as sensitive to faults as their area-demanding implementations might suggest. An evolutionary algorithm is utilized to design fault tolerant circuits as well as to perform an automatic functional recovery when faults are detected in the configuration memory of the FPGA. All the experiments are performed on models of reconfigurable devices.

Multifunctional digital circuits are circuits composed of polymorphic (multifunctional) gates. In addition to its standard logic function (such as NAND), a polymorphic gate exhibits another logic function (such as NOR) which is activated under a specific condition, for example, when Vdd, temperature or illumination reaches a certain level. This paper describes the evolutionary design of multifunctional combinational circuits at the gate level using a circuit simulator and in a field programmable gate array (FPGA). The FPGA-based implementation exhibits a significant speedup against a highly optimized software simulator.

In the paper a method for estimation the circuit testability on the Register Transfer Level (RTL) is presented. The method allows to perform fast testability estimation in linear time complexity (regarding the number of components and interconnects of the circuit). Proposed approach is based on utilization of controllability and observability measurement for estimation of overall circuit testability. The application of developed method is demonstrated in a software tool for the development of RTL benchmark circuits with predefined testability properties. The results gained by our testability analysis method are compared with the results of professional ATPG tool. Experiments show the good correlation of the results obtained by our method and professional ATPG tool with significantly lower time complexity when our algorithm is used.