The increasing demand for energy-efficient solutions has led to the emergence of an approximate computing paradigm that enables power-efficient implementations in various application areas such as image and data processing. The median filter, widely used in image processing and computer vision, is of immense importance in these domains. We propose a systematic design methodology for the design of power-efficient median networks suitable for on-chip or FPGA-based implementations. A search-based design method is used to obtain approximate medians that show the desired trade-offs between accuracy, power consumption and area on chip. A new metric tailored to this problem is proposed to quantify the accuracy of approximate medians. Instead of the simple error rate, our method analyses the rank error. A significant improvement in implementation cost is achieved. For example, compared to the well-optimized high-throughput implementation of the exact 9-input median, a 30% reduction in area and a 36% reduction in power consumption was achieved by introducing an error by one position (i.e., allowing the 4th or 6th lowest input to be returned instead of the median).

Approximate computing, leveraging the inherent resilience to errors, emerges as a promising strategy for reducing power consumption in digital systems. The primary objective of this paper is to introduce an efficient method based on Cartesian Genetic Programming for designing approximate arithmetic circuits with commutative property. Specifically, this work focuses on the design of 8-bit approximate multipliers and 32-bit approximate adders, both serving as foundational components for hardware accelerators in neural networks. We have identified that while the design of commutative approximate adders poses no issues for evolution, the design of commutative approximate multipliers represents a challenging problem causing the commonly used CGP stuck at highly sub-optimal solutions. In response to this challenge, we propose a novel application-specific mutation operator. This operator significantly enhances the efficiency of the search process, enabling the discovery of solutions that were previously unreachable. The achieved results revealed that imposing the requirement for a commutative property does not substantially compromise the quality-error trade-offs of the obtained approximate circuits, making the resulting Pareto front comparable to that of unconstrained designs.

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.

Printed electronics offer ultra-low manufacturing costs and the potential for on-demand fabrication of flexible hardware. However, significant intrinsic constraints stemming from their large feature sizes and low integration density pose design challenges that hinder their practicality. In this work, we conduct a holistic exploration of printed neural network accelerators, starting from the analog-to-digital interface---a major area and power sink for sensor processing applications---and extending to networks of ternary neurons and their implementation. We propose bespoke ternary neural networks using approximate popcount and popcount-compare units, developed through a multi-phase evolutionary optimization approach and interfaced with sensors via customizable analog-to-binary converters. Our evaluation results show that the presented designs outperform the state of the art, achieving at least 6× improvement in area and 19× in power. To our knowledge, they represent the first open-source digital printed neural network classifiers capable of operating with existing printed energy harvesters.

Just over a decade ago, the first comprehensive review on the state of benchmarking in Genetic Programming (GP) analyzed the mismatch between the problems that are used to test the performance of GP systems and real-world problems. Since then, several benchmark suites in major GP problem domains have been proposed over time, filling some of the major gaps. In the framework of the first review about the state of benchmarking in GP, logic synthesis (LS) was classified as one of the major GP problem domains. However, a diverse and accessible benchmark suite for LS is still missing. In this work, we propose a benchmark suite for LS that covers different types of Boolean functions that are commonly used in the field of GP. We analyze the complexity of the proposed benchmark by using popular complexity measures that are commonly used to classify and characterize Boolean functions and digital circuits.

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.

Approximate computing is an emerging paradigm that trades the accuracy of computation to achieve gain in terms of design area, critical path delay and/or power consumption. There is a rich body of literature showing that the approximate hardware components serving as basic building blocks for energy-efficient implementation of complex systems offer a remarkable gain in efficiency and/or performance in exchange for small losses in output quality. However, recent studies revealed that the approximate components optimized mainly for ASICs offer asymmetric gain when used in FPGAs. In this work, we present an iterative design method for automated synthesis of elementary approximate components natively optimized for usage in LUT-based FPGAs. The method takes into account the number of LUTs and LUT-level propagation delay instead of the number of gates and logic levels typically considered in other works. Using this method, we synthesized various approximate adders (up to 64-bit) and multipliers (8-bit and 16-bit). Compared to the current state-of-the-art, our designs achieve better trade-off when considered the worst case absolute error, number of LUTs and propagation delay. The discovered approximate adders and multipliers are available online in the form of Verilog netlists consisting of 4, 5 and 6-input LUTs.

Boolean network scoping represents a common approach incorporated in conventional synthesis tools for maintaining good scalability of the synthesis process. Recently, an approach to the local resynthesis based on combination of evolutionary optimization with the principle of Boolean network scoping has been proposed. Local resynthesis is an iterative process based on the extraction of smaller sub-circuits from a complex circuit that are optimized locally and implanted back to the original circuit. The main advantage of the local resynthesis is that it can mitigate the problem of scalability of representation which is typical to the evolutionary algorithms as the efficiency of the evolutionary optimization applied at the global level deteriorates with the increasing circuit complexity. Unfortunately, the efficiency of local resynthesis depends on the efficiency of the sub-circuit extraction process. We propose an alternative method, based on the reconvergent paths. The evaluation is performed on a set of highly optimized benchmark problems representing various real-world controllers, logic and arithmetic circuits. The method provides better results compared to the state-of-the-art logic synthesis tool and evolutionary optimization techniques operating locally and globally. A substantially higher number of redundant gates was removed in more than 70% cases, while keeping the computational effort at the same level. A huge improvement was achieved especially for the controllers. On average, the proposed method was able to remove more than 14.3% of gates. The highest achieved gate reduction was more than 45% of gates.

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.

Despite many successful applications, Cartesian Genetic Programming (CGP) suffers from limited scalability, especially when used for evolutionary circuit design. Considering the multiplier design problem, for example, the 5×5-bit multiplier represents the most complex circuit evolved from a randomly generated initial population. The efficiency of CGP highly depends on the performance of the point mutation operator, however, this operator is purely stochastic. This contrasts with the recent developments in Genetic Programming (GP), where advanced informed approaches such as semantic-aware operators are incorporated to improve the search space exploration capability of GP. In this paper, we propose a semantically-oriented mutation operator (SOMO) suitable for the evolutionary design of combinational circuits. SOMO uses semantics to determine the best value for each mutated gene. Compared to the common CGP and its variants as well as the recent versions of Semantic GP, the proposed method converges on common Boolean benchmarks substantially faster while keeping the phenotype size relatively small. The successfully evolved instances presented in this paper include 10-bit parity, 10+10-bit adder and 5×5-bit multiplier. The most complex circuits were evolved in less than one hour with a single-thread implementation running on a common CPU.

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.

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 increasing complexity of the designs and problematic scalability of original representations led to a shift in internal representations used in logic synthesis and optimization. Heterogeneous representations were replaced with homogeneous intermediate representations. And-inverter graph (AIG) has been identified as the most promising structure for scalable logic optimization and many efficient algorithms were implemented on top of it. However, the inability of AIG to efficiently represent XOR gates together with heuristic nature of logic optimization algorithms leads to some inefficiency causing that the logic can be further minimized even after it has been mapped. This paper presents an optimization technique based on refactoring targeting mapped combinational circuits. It iteratively selects large cones of logic, optimizes them and returns them back to the original structure provided that there is an improvement in some metric. Performance of the method is evaluated on a set of complex academic and industrial benchmarks. We show that a 9.2% reduction in area can be achieved in average compared to the highly optimized results obtained using the academic state-of-the-art synthesis tool. In average, more than 14% reduction was observed for arithmetic circuits.

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.

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.

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.

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.

In order to satisfy a constant need of reducing energy consumption of electronic devices, the approximate computing paradigm has been introduced in recent years. This paradigm is based on the fact that there are applications that are inherently capable of absorbing some errors in computation. Multimedia signal processing represents a typical example that allows for quality to be traded off for power. Typicaly, the approximate circuits are designed at gate level. This paper introduces an automatic design method that is able to operate directly at transistor level which offers a great potential for discovering novel implementations of approximate circuits. The method combines a stochastic search algorithm with transistor-level circuit simulator and is able to handle the circuits consisting of hundreds of transistors. The goal of the search strategy is to improve the power consumption. To estimate power consumption, an algorithm based on transistor switching activity is proposed. A design of 4-bit multiplier was chosen as a case study. Two scenarios were considered. Firstly, the proposed method is applied to improve the power consumption of a common 4-bit multiplier and a 4-bit multiplier consisting of manually designed 2-bit multipliers. In both cases, approx. 3% power reduction was achieved. Then, it is demonstrated that a noticeable improvement can be obtained when the multipliers are designed using a hybrid approach operating at transistor as well as gate level. We discovered a novel implementation of an approximate 4-bit multiplier which has approximately by 40% better power-delay product and exhibits 14% lower worst-case error compared to the best known 4-bit multiplier consisting of 2-bit manually optimized approximate multipliers.

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.

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.

This paper introduces a method of representing transition functions for the purposes of evolutionary design of cellular automata. The proposed approach is based on conditions specified in the transition rules that have to be satisfied in order to determine the next state of a cell according to a specific rule. The goal of this approach is to reduce the number of elements needed to represent a transition function while preserving the possibility to specify traditional transition rules known from the conventional table-based representation. In order to demonstrate abilities of the proposed approach, the replication problem and pattern transformation problem in cellular automata will be investigated. It will be shown that the evolution is able to design transition functions for non-trivial behavior of two-dimensional cellular automata that perfectly fulfil the specified requirements.

This paper introduces a method of encoding cellular automata local transition function using an instruction-based approach and their design by means of genetic algorithms. The proposed method represents an indirect mapping between the input combinations of states in the cellular neighborhood and the next states of the cells during the development steps. In this case the local transition function is described by a program (algorithm) whose execution calculates the next cell states. The objective of the program-based representation is to reduce the length of the chromosome in case of the evolutionary design of cellular automata. It will be shown that the instruction-based development allows us to design complex cellular automata with higher success rate than the conventional table-based method especially for complex cellular automata with more than two cell states. The case studies include the replication problem and the problem of development of a given pattern from an initial seed.

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 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.

Evolutionary design has shown as a powerful technique in solving various engineering problems. One of the areas in which this approach succeeds is digital image processing. Image filtering represents a wide topic in 2D signal processing. In this case different types of noise are considered in the filtering process to restore the image quality that has been decreased by changing values of some pixels in the image (e.g. due to the transmission through unreliable lines or in the process of acquiring the image). Impulse noise represents a basic type of non-linear noise typically affecting a single pixel in different regions of the image. In order to eliminate this type noise median filters have usually been applied. However, for higher noise intensity or wide range of the noise values this approach leads to corrupting non-noise pixels as well which results in images that are smudged or lose some details after the filtering process. Therefore, advanced filtering techniques have been developed including a concept of noise detection or iterative filtering algorithms. In case of the high noise intensity, a single filtering step is insufficient to eliminate the noise and obtain a reasonable quality of the filtered image. Therefore, iterative filters have been introduced. In this paper we apply an evolutionary algorithm combined with Cartesian Genetic Programing representation to design image filters for the impulse noise that are able to compete with some of the best conventionally used iterative filters. We consider the concept of noise detection to be designed together with the filter itself by means of the evolutionary algorithm. Finally, it will be shown that if the evolved filter is applied iteratively on the filtered image, a high-quality results can be obtained utilizing lower computational effort of the filtering process in comparison with the conventional iterative filters.

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.

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.

Cellular automata represent a computational model that is based on updating the states of the cells, that are arranged in a regular structure, by means of local interactions between the cells. Cellular automata have often been utilized as a developmental model in engineering areas to solve many complex problems. In the area of the evolutionary algorithms, cellular automata can be applied as an indirect mapping between genotypes and phenotypes. In the recent years, this approach has successfully been applied on the evolutionary development of digital circuits at the gate level. Combinational multipliers represent a class of circuits that is usually considered as hard task for the design using the evolutionary techniques. In our previous research regarding the cellular automata-based development, 2times2-bit multipliers were successfully evolved using this approach. Combinational multipliers have been chosen in this paper to demonstrate capabilities of an advanced developmental system that allows to apply cellular automata of different sizes in order to design larger instances of this kind of circuits. In the experiments presented herein, the 2times3-bit and 3times3-bit multipliers will be considered which represent the first case when such instances of multipliers have been successfully developed at the gate level using cellular automata. The proposed developmental model is investigated in detail with respect to the success rate of the evolutionary experiments for different experimental setups (such as the cellular automata size, the number of cell states and developmental steps). Moreover, it will be demonstrated that different ways of connections of the circuit outputs can be utilized without a significant influence on the successfulness of the evolutionary process.

A non-uniform cellular automata-based model is presented for the evolutionary development of digital circuits at the gate level. The main feature of this model is the modified local transition function of the cellular automaton in which a gate is associated with each rule of the transition function. A logic gate is generated by each cell when the cell determines its next state according to the appropriate rule. An evolutionary algorithm is utilized to design a non-uniform cellular automaton (its local transition function) for the development of a target circuit. In this paper, initial results will be presented that were obtained using the non-uniform cellular automata.

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.