Evolutionary Approach to Approximate
Digital Circuits Design
1
This paper proposed the automatic design process to evolve approximate digital circuits that show a minimal error for a supplied amount of resources.
2
First of all, let’s try to understand the title.
The paper proposed the evolutionary approach to design digital circuits.
But what does ‘Approximate’ mean?
Approximate computing is a new design paradigm to make a computer system with better performance and better energy efficiency. The circuits that are intentionally designed to save energy, performance, or area are called approximate circuits.
There were some basic design techniques like over-scaling and functional approximation so far. In the case of over-scaling, circuits are designed to be working perfectly under a normal environment and their energy consumption can be reduced by voltage over-scaling which is using deliberately lower power supply voltage.
Functional approximation means that the circuit is designed not to fully implement the logic behaviours by the specification. A simple method is to reduce the precision of computations in the case of arithmetic circuits by ignoring the least significant bits. For example, the original function F is replaced by G whose implementation leads to energy, delay, area reduction and non-zero error.
3
Of course, the manual redesign is not efficient, automatic methods with some heuristics are currently being developed. SALSA, short for the systematic methodology for the automatic logic synthesis of circuits, introduces the function takes the outputs from the original and approximate circuits and decides if the conditions are satisfied. Another approach SASIMI, short for substitute-and-simplify, identified signal pairs in the circuit. Well, SALSA and SASIMI were not available to the public when this research is on the process. Finally, evolutionary algorithm based methods came out with the hypothesis ‘Better approximations can be discovered than conventional methods can provide.’
4
Why evolutionary approximation? Because it is natural! In the case of the approximation computing, partially working circuits are sought. And evolutionary algorithms can do genetic improving partially working circuits.
Also, evolutionary algorithms are good at multi-objective design as we have learned. In the circuit design, the area, delay and error are optimized together. Constraints are easily handled /which is the error in this case. And It doesn’t need the original circuit which is 100% accurate.
But there are some problems in the evolutionary design, scalability and runtime. These will be mentioned with the proposed method later.
5
From now on, the overall idea of the proposed method will be introduced. Existing systematic approximate circuit synthesis methods always begin with a fully functional circuit and a given quality constraint, error. Then the fully functional circuit undergoes the approximating procedure and an approximate circuit is generated. The design process is usually repeated for several error values and yielding approximate circuits. However, the area, power consumption, and delay are not directly under the control of the approximating procedure. This is a multiobjective circuit design problem that could be solved by a suitable multiobjective evolutionary algorithm. According to some related works, this will have some difficulties with delivering really compact approximate circuits for complex problem instances because of some reasons.
First, the evolutionary design of non-trivial combinational circuits from scratch is super hard. Only a small fraction of runs usually produce a working circuit because of the very rugged corresponding fitness landscapes. Second, it is even harder to evolve a circuit better than a conventional design. Third, a reasonably reliable estimate of power consumption is important because it can be very time consuming for complex circuits.
Another difficulty is the scalability of the evolutionary circuit design as I mentioned before. In this paper, 2 approaches are adopted to solve this problem. First, complex approximate median circuits are evolved by means of the functional-level evolution. Second, they focus on arithmetic circuits and small approximate circuits are used as building blocks of complex approximate circuits. These small approximate circuits are evolved by CGP short for Cartesian Genetic Programming.
6
These are the main features of the proposed method. The direct control of the resulting area and power consumption/ could be very useful for scenarios like/ computing with the minimum error with a power budget. So, the proposed method generates approximate circuits as a function of the area rather than the error. This area-oriented approach cannot be accomplished by conventional circuit design tools.
And the procedure is capable of creating an approximation version of a fully functional circuit with n gates. The design procedure is repeated but it is for the various number of gates to obtain different tradeoffs among design objectives.
To implement this procedure, a single-objective Cartesian Genetic Programming is chosen in a functional level evolution. Multiple runs of CGP are performed to find a circuit with the smallest possible error in a certain condition of resource amount.
Also, there are some features to accelerate the whole design process. The initial population is seeded by approximate circuits to find much better solutions than random seeding. Power consumption is computed only for selected best circuits at the end of each CGP runs. Fitness evaluation exploits the idea of a parallel simulation of candidate circuits and binary circuit code. And multiple runs are executed on a computer cluster.
7
Cartesian Genetic Programming(CGP) is a form of genetic programming that uses a graph representation to encode computer programs. In this case, it is about how to represent a circuit in the chromosome. This representation is very simple, flexible and convenient. A candidate circuit is modelled by means of an array of processing nodes arranged in the number of columns and the number of rows. The processing elements can be elementary gates/ or functional level components/ like adders, comparators and shifters. The set of functions implemented by processing elements/ will be denoted GAMMA. The circuit utilizes primary inputs and outputs. Each node input /can be connected /to the output of a previous gate /or one of the primary circuit inputs. A candidate solution /consisting of two input nodes/ is represented in the chromosome with its function,/ and addresses of connected nodes. The last part of the chromosome/ contains no integers specifying the nodes/ or logic constants (‘0’ and ‘1’). It can be directly connected to the primary output.
8
In figure 1, the chromosome represented the multipliers with inputs and the logic constants.
9
The goal of evolution is to maximize the functionality of approximate circuits. In the yellow box, the fitness is defined as the error to be minimized where y is a candidate circuit’s response and t is target response. Isn’t it familiar? This definition is preferred over the Hamming distance.
This is the overall algorithm.
1) The initial population of the size 1 + λ is created.
2) The fitness function f is called for each candidate circuit.
3) The highest-scored candidate circuit is selected as the new parent.
4) and apply a point mutation, λ offspring individuals are generated from the parent.
5) Steps 2–4 are repeated until the termination condition is not satisfied.
10
The heuristic seeding the initial population is based on a local search. Every single gate of C is replaced by a wire connection independently. The fitness values are calculated for all n circuits. The whole procedure is repeated, but now the lower input is connected to the output for all the gates. The circuit producing the smallest error is taken as the seed for CGP.
A natural extension of this heuristic for a circuit in which gates have to be reduced consists of:
1) a random selection and their replacement by wire connections
2) calculating the fitness value of the modified circuit
3) repeating steps random selection /and calculating fitness value/ and outputting the circuit with the best fitness value.
11
Providing a single approximate circuit is not actually the most valuable output of approximate circuit design methods. To find approximate circuits for every possible number of gates, the proposed approximate circuit design flow will call CGP several times. So there are two approaches for embedding the heuristic into CGP /to obtain approximate circuits /containing every number of gates from n to 1. They proposed and compared Random Seeding, Heuristic Seeding 1 and Heuristic Seeding 2.
Random seeding is that all initial populations are randomly generated. Heuristic seeding 1 means that each CGP run is interleaved by a single run of the heuristic procedure removing just one gate from the best-evolved solution. Heuristic seeding 2 means that all requested seeds are generated by the heuristic and independent CGP runs.
