Approximate Computing:
An Evolutionary Computing Perspective(Tutorial at IEEE CEC 2017)

Lukáš Sekanina
Faculty of Information Technology, Brno University of Technology
Brno, Czech Republicsekanina@fit.vutbr.cz

The notion of approximation is well known in …
• Theoretical computer science– polynomial time approximation algorithms to find approximate solutions
to NP-hard optimization problems• Stringology, bioinformatics– approximate string matching• Bio-inspired models in AI– approximation of functions using artificial neural networks• Mathematics– approximation of functions; numerical mathematics• Computer engineering– FP numbers, computer arithmetic, …
– S. H. Nawab et al.: Approximate Signal Processing, Journal of VLSI Signal
Processing , vol. 15, pp. 177-200, Jan. 1997.

Why Approximate Computing again?
2

Approximate computing (AC) in literature• Search for "approximate computing" in articles by Google Scholar(April, 2017)

700
100600

Search for "approximate computing"Search for "approximate computing"in the title of the article

80500
400
60
300
40200
20100
0
0

Search for "approximate adder" and"approximate multiplier" in the title of
the article

2009 2010 2011 2012 2013 2014 2015 2016 20172009 2010 2011 2012 2013 2014 2015 2016 2017

16
14
12
10
8
6
4
2
0
2010

2011

2012

2013

approximate multiplier

2014

2015

2016

2017

approximate adder3

Tutorial Outline• Approximate Computing– Motivation– Error resilience– Sensitivity analysis and error metrics– Overview of approximation techniques• Evolutionary algorithms and genetic improvement• EA in SW approximations– Extension of Java - ExpAX– Median• EA in HW approximations– Approximations at the hardware description language level– Approximate multipliers in ANN– Library of approximate components• Formal relaxed equivalence checking in approximate computing– Binary decision diagrams– Approximate circuits with formal error guarantees• Conclusions
4

The end of Dennard scaling
The end of Dennard scaling

Moore’s law willsurvive next 10-15
years (ITRS).

Kirk M. Bresniker et al. “Adapting toThrive in a New Economy of Memory
Abundance”, Computer, 48, 2015.

Power density (power consumption per chip area) remained
acceptable from one technology node to another even withincreasing frequency (based on data for common processors).

5

Roots of the new interest in AC
Data centers - monthly costs• Energy efficiency and dark silicon0%– High performance & low power computing isrequested (Big data processing in data centres;
Mobile electronics with limited power budget)

20%

40%

60%

Servers
Power (distribution,…
Networking equipment
Other infrastructure

Gupta, Accelerating Datacenter Workloads
Intel, FPL 2016

• Variability issues– Many “unreliable” components on a chip
fabricated with modern process technologies(Limited use of fault tolerant mechanisms
because they are expensive; Reliable computing
with unreliable components)

22nm MOSFET (line-edge and surface
roughness, random dopant fluctuations=> threshold voltage variation)• Error resilience– Many applications are error-resilient.
(We are willing to tolerate errors.)

golden solution

60% instructions
6

Error resilience• Typical machine learning, signal processing and document processing
applications have a mix of resilient and sensitive computations.
• Chippa, 2013: 83% runtime spent in computations (such as matrix and vector
operations) that can be approximated.

% Runtime in resilient kernels
Online Data Clustering

Dominant resilient kernel (% runtime)
Distance Computation

Digit Recognition

Distance Computation

Nutrition and Health Inf. Analysis

Dot Product Computation

Census Data Classification

Matrix Vector Multiplication

Census Data Modeling

Matrix Vector Multiplication

Image Segmentation

Distance Computation

Eye Model Generation

Distance Computation

Eye Detection

Distance Computation

Hand-writ. Digit Model Train.

Dot Product Computation

Hand-writ. Digit Classification

Dot Product Computation

Image Search

Dot Product Computation

Document Search

Dot Product Computation
0%

10% 20% 30% 40% 50% 60% 70% 80% 90% 100%0%Chippa, et al. Analysis and characterization of inherent application resilience for approximate computing , DAC 2013

20%

40%

60%

80%

100%

7

The origin of resilience• Applications with analog inputs– image processing, sensor data processing, voicerecognition, etc., that operate on noisy real-world data.
They are inherently resilient to some noise.

• Applications with analog output– multimedia, image rendering, sound synthesis, etc. The
output is intended for human perception and caninherently tolerate errors imperceptible to users.

• Applications with no unique answer– web search, machine learning, autonomous agents, etc.,
which do not offer a unique answer and multiple possible
answers are acceptable.

• Iterative and convergent applications– data analytics and numerical computations that iteratively
process large amounts of data. They often sample data,stop the convergence procedure early, or apply
approximate heuristics.
Esmaeilzadeh et al.: COMM. OF THE ACM, 59(1), 20158

Approximate computing• The concept of approximate computing has been developed indifferent ways and at various levels of computing stack (circuit,component, memory, processor, compilers, applications, …)• Software-level approximations– Extensions of general purpose languages (Java, Verilog) to support
approximations in data types, operators, … e.g. EnerJ, Axilog, ExpAx …
– Neural network replaces general purpose code [Esmaeilzadeh el al., 2013]• Specialized processors supporting approximate computing– Improving Efficiency of Extensible Processors by Using Approximate
Custom Instructions [Kamal et al., 2014]• Circuit approximation– over-scaling based approximations– functional approximations• Memory approximation– approximations in memory cells, organization, access, hierarchy …
9What is Approximate computing?
“Approximate computing exploits the gap between thelevel of accuracy required by the applications/users andthat provided by the computing system, for achieving
diverse optimizations.”[Mittal S., ACM Computing Surveys 2016]“The requirement of exact numerical or Booleanequivalence between the specification andimplementation of a circuit is relaxed in order toachieve improvements in performance or energy
efficiency.”[Venkatesan et al., 2011]“Computing efficiently by producing results that aregood enough or of sufficient quality.”[Venkataramani et al., DAC 2015]10

Approximate computing as a new paradigm• Approximations are conducted across the whole computer stack:– Circuit– Component– Memory– (Parallel) Processor architecture– Algorithm– Compiler– Operating system– Application• A holistic approach is needed to find the best trade-off between
error, power and performance at the global (system) level.
• AC reduced energy requirements of many applications: image
processing, video processing, deep neural networks, …

A great opportunity for EAs!
11

Sensitivity analysis• The goal is to identify subsystems suitable for undergoing the approximation.
• Method: Random/guided modification of the original implementation andstatistical evaluation of the impact on the quality of result.
In software• precision of number representation• data storage strategies• code simplification• relaxed synchronization• unfinished loops• skipped function calls

In hardware• bit width reduction• intentional disconnecting ofcomponents• timing changes• power supply voltage changes• fault injection

Chippa et al., ACSSC 201312

Error metrics used in approximate computing• Arithmetic error metrics– The worst-case error(error magnitude, error significance)– Relative worst-case error– The average-case error(average error magnitude, meanerror distance)• Generic error metrics– Error probability (error rate)– Maximum Hamming distance(bit-flip error)– Average Hamming distance• Application-specific error metrics– Distance error– Accumulated worst-case error andaccumulated error rate

𝑒𝑤𝑠𝑡 𝑓, 𝑓 = max𝑛 | int 𝑓 𝑥− int(𝑓 𝑥 ) |∀𝑥∈ℬ| int 𝑓 𝑥 − int(𝑓 𝑥 ) |∀𝑥∈ℬ
int(𝑓 𝑥 )𝑒𝑟𝑒𝑙 𝑓, 𝑓 = max𝑛𝑒𝑎𝑣𝑔 𝑓, 𝑓 =12𝑛| int 𝑓 𝑥

− int(𝑓 𝑥 ) |∀𝑥∈ℬ 𝑛𝑒𝑝𝑟𝑜𝑏 𝑓, 𝑓 =12𝑛

𝑓 𝑥 ≠ 𝑓(𝑥)∀𝑥∈ℬ 𝑛𝑚−1

𝑒𝑏𝑓 𝑓, 𝑓 = max𝑛∀𝑥∈ℬ

1𝑒ℎ𝑑 𝑓, 𝑓 = 𝑛2

𝑓𝑖 𝑥 ⊕ 𝑓𝑖 (𝑥)
𝑖=0

𝑚−1

𝑓𝑖 𝑥 ⊕ 𝑓𝑖 (𝑥)∀𝑥∈ℬ 𝑛 𝑖=0f, 𝑓 – original and approximate solutionn, m – the number of inputs and outputs
int – returns a decimal value from m bits
13

Approximation techniques - examples• precision scaling• loop perforation• load value approximation• memorization• task dropping/skipping• memory access skipping• data sampling• using different program(circuit) versions

Mittal S., ACM Computing Surveys, 2016

• using inexact or faulty
hardware• voltage scaling• refresh rate reducing• inexact read/write• reducing divergence inGPUs• lossy compression• use of neural networks.

14

SW approximation: Code replaced by ANN

Esmaeilzadeh et al.: COMM. OF THE ACM, 59(1), 201515

Functional approximation• Principle: To implement a slightly different function that leads toenergy/delay/area reduction but a non-zero error.

F(x)Power: 193 uW
Delay: 10 ns
Area: 35um2F’(x)Power: 100 uW
Delay: 5 ns
Area: 20 um2
Error: 5%

Traditional view

Functional equivalenceis requested between the specificationand implementation at all levels.

Approximate computing

Relaxed functional equivalenceError as a design metric!

A complex multi-objective design/optimization problem!

16

Languages supporting approximate computing• EnerJ [Sampson et al., PLDI 2011]––––

An extension to Java that adds approximate data types.
Approximate data can be processed more cheaply but less reliably.
Approximate operations by generating code with cheaper approximate instructions.
The system can statically guarantee isolation of the precise program component fromthe approximate component.

• Rely [Carbin et al., OOPSLA 2013]– Programmer can mark both variables and operations as approximate.
– Rely works at the granularity of instructions and symbolically verifies whether thequality-of-result requirements are satisfied for each function.
– Rely requires programmer to provide preconditions on the reliability and range of thedata• Axilog [Yazdanbakhsh et al., DATE 2015]– A set of language annotations that provide the necessary syntax and semantics forapproximate hardware design and reuse in Verilog.
– Axilog enables the designer to relax the accuracy requirements in certain parts of thedesign, while keeping the critical parts strictly precise.

• Others: ExpAX, Chisel, …
• They require a hardware (CPU) supporting approximate computing
17

Quality programmable processors: Concept

Example: Quora is an experimental quality configurable vector processor with 289 processing
elements in 45 nm technology [Venkataramani et al. Micro 46, 2013]

18

Timing induced approximations

Pdyn = CVdd2 f

speed

delay target

TimingerrorsVdd = 1.2Vf
2f

path delay

power# of paths• Design techniques
over-clocking
voltage over-scaling

Vdd = 1.2V

path delay# of paths

Assume: Accurate circuit D1 atfrequency f1
D1 is approximated to D2 which
can work at higher freq. f2 (f2 > f1)
But, D2 is operated at f1 withlower Vdd => power saving# of paths• Power reduction tricks

Vdd = 0.9V

delay target

path delay
Courtesy of K. Roy

Timingerrors19

Tutorial Outline• Approximate Computing– Motivation– Error resilience– Sensitivity analysis and error metrics– Overview of approximation techniques• Evolutionary algorithms and genetic improvement• EA in SW approximations– Extension of Java - ExpAX– Median• EA in HW approximations– Approximations at the hardware description language level– Approximate multipliers in ANN– Library of approximate components• Formal relaxed equivalence checking in approximate computing– Binary decision diagrams– Approximate circuits with formal error guarantees• Conclusions
20

Evolutionary algorithms: GA, GP, LGP, CGP, GE …
GA: vectors of parameters

GP: syntax trees

LGP: machine level code

GE: grammatical evolution

Cartesian GP: Directed acyclic graphs(0, 2, 2) (0, 1, 0) (1, 3, 2)(3, 2, 0) (5, 6, 3) (4, 6, 1) (5, 8)

cf. HeuristicLab21

Cartesian Genetic Programming (CGP) [Miller, 1999]
•
•
•
•

•
•
•

ni primary inputs
no primary outputs
nc columns
nr rows

na inputs of each nodefunction set
L-back parameter

ni

ni+nr

ni+1

ni+nr+1

ni+nr-1

ni+2nr-1

0

ni

1

ni-1

nc

a
b g(a,b)Nodes in the same
column are not allowed
to be connected toeach other.
No feedback!

ni+(nc-1)nrnrnoni+ncnr-1

22

CGP: Representation for logic networks•

CGP parameters
•
•
•
•
•
•
•

nr=3 (#rows)
nc = 3 (#columns)
ni = 3 (#inputs)
no = 2 (#outputs)
na = 2 (max. arity)
L = 3 (level-backparameter)= {NAND(0), NOR(1),
XOR(2), AND(3), OR(4),NOT (5)}

Genotype (netlist):na+1 integers per node; no integers for outputs;
Constant size: ncnr(na + 1) + no integers
Phenotype (directed acyclic graphcircuit):
Variable size; unused nodes are ignored.

23

CGP: Fitness function for circuit design
Specification(1-bit adder),target table:

Typical fitness function (circuit functionality):
The number of test vectors

𝐾𝑓=|𝑦𝑖 − 𝑤𝑖 |𝑖=1
Desired response

Additional objectives:•••area (the number of gates)
delay
power consumption etc.

Circuit response

K = 2inputs for combinational circuits. Not scalable!!!
24

CGP: Mutation-based search•

Mutation: Randomly select h integers and replace them by randomly
generated (but legal) values:

mutation(for full adder)25

CGP: Search algorithm (1 + )26

Why EA in Approximate computing?
• Why EA in AC?
– In AC, partially working solutions are sought.
– In EA, partially working solutions are improved.
– EAs are excellent in multi-objective design and optimization.
– Constraints can easily be handled.
– EA can be seeded with the original code (circuit).

• Is AC similar to Genetic improvement?
– Genetic improvement (of existing SW/HW) is the application ofevolutionary and search-based optimization methods with the aimof improving functional and/or non-functional properties of existing
software/hardware

27

Genetic improvement of SW: Examples• automatic bug fixing (real bugs in real C programs)–

W. Weimer, et al. Automatic program repair with evolutionary computation. Communications of the ACM,
vol. 53, no. 5, pp. 109–116, 2010.

• an improved version of C++ code from multiple versions of a program written
by different domain experts (e.g. improved MiniSAT)–

J. Petke, et al. Using genetic improvement and code transplants to specialise a C++ program to a problem
class. In 17th European Conference on Genetic Programming, LNCS, vol. 8599. Springer, 2014, pp. 137–149• improved CUDA programs (DNA analysis SW)–

W. Langdon. Improving CUDA DNA Analysis Software with Genetic Programming. In Genetic andEvolutionary Computation Conference (GECCO 2015): 1063-1070• Bowtie2, a widely-used DNA sequencing system, consisting of 50k lines of C++
code, was reduced by GI to 20k lines of code; with an average 70 times faster
execution than the original code
- W. Langdon and M. Harman: IEEE Tr. on
Evol. Computing. 19(1), 201528

Genetic improvement vs. Approximate computing

error

The Genetic improvement method does not usually accept
solutions increasing the error (w.r.t the original implementation)
In AC, genetic improvement can tolerate some errors.

acceptableerror

approximate computing
initial solution
power

genetic improvement

29How are EAs used in Approximate computing?
• Evolutionary optimization– optimization of the data type (bit width) to variable assignment - inthe source code (e.g. GRATER)– selection of operations to be approximated – in the source code(e.g. ExpAX)• Genetic improvement with errors enabled– existing solutions (SW or HW) are approximated by GP to get asuitable trade-off between error and power/performance (e.g.
ABACUS, EvoApprox8b, …)• Evolutionary design (from scratch)– GP is used to evolve desired approximate solutions from scratch(e.g. CGP in the multipliers approximatio, median, image filter …)

30

Tutorial Outline• Approximate Computing– Motivation– Error resilience– Sensitivity analysis and error metrics– Overview of approximation techniques• Evolutionary algorithms and genetic improvement• EA in SW approximations– Extension of Java - ExpAX– Median• EA in HW approximations– Approximations at the hardware description language level– Approximate multipliers in ANN– Library of approximate components• Formal relaxed equivalence checking in approximate computing– Binary decision diagrams– Approximate circuits with formal error guarantees• Conclusions
31

SW approximation
Software is annotated in order to introduce approximations• ExpAX– A new programming framework that employs error expectations.
– HW/CPU supporting approximate computing is assumed.
– A static safety analysis is performed that uses the high-level expectations toautomatically infer a safe-to-approximate set of program operations

ExpAX: A Framework for Automating Approximate Programming, SCS Technical Report, GT-CS-14-05, Georgia Institute of Technology, July, 201432

SW approximation: GA in ExpAX•

Programming model with expectations (vis variable)

Approximate HW– accept rate(v) < 0.2– accept magnitude(v) > 0.9 with rate < 0.3•

Finding possible safe-to-approximate
variables– Unsafe-to-approximate variables arevariables violating memory safety orfunctional correctness•

GA used to find a subset of safe-toapproximate operations– Fitness = min. (W1.error + W2.energy)– Chromosome: a bit vector representing a
subset (approximate (‘0’) or precise(‘1’))••

ExampleGreedy algorithm used to refine the GA
result.
Significant energy savings (up to 35%) withlarge reduction in programmer effort (3xto 113x less annotations w.r.t EnerJ) whileproviding formal safety and statisticalquality-of-result guarantees.

ExpAX: A Framework for Automating Approximate Programming, SCS Technical Report, GT-CS-14-05, Georgia Institute of Technology, July, 201433

Median in image filters
corrupted image(10% pixels, impulse noise)

filtered image(9-input exact median filter)

original
34

9-input median function#define PIX_SORT(a,b) {if ((a)>(b))
PIX_SWAP((a),(b));}

pixelvalue opt_med9 (pixelvalue * p){
PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;PIX_SORT(p[4], p[2]) ; return(p[4]) ;}Source: http://ndevilla.free.fr/median/median.pdf

35

Approximate median using CGP
Cartesian Genetic Programming (CGP) for median approximation• Median network (consisting of up to N operations) is represented by means ofan one-dimensional array of N nodes.
• Each node can act as: identity (0), minimum (1), maximum (2)• Each candidate solution is encoded using 3N + 1 integers.
• Fitness function (single objective)e𝑟𝑟𝑜𝑟 =

𝑂𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒 𝑖 − 𝑂𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑐𝑒 (𝑖)𝑖∈𝑆• Example for 3-input median:

Chromosome: 0, 2, 3; 3, 2, 0; 0, 2, 2; 5, 3, 1; 6, 1, 2; 7, 0, 0; 6, 8, 2; 836

Approximate median using CGP
Experimental setup• (1+4)-ES, no crossover, 5 % of the chromosome mutatedMedian-9Median-25

Inputs925

Outputs

1

1

3 × 106 (3 hours)

3 × 105 (3 hours)

1 × 104

1 × 105

38 operations

220 operations

6 – 34 operations

10 – 200 operations

Generations
Training vectors
Reference (exact) solution
Number of nodes

20% operations

60% operation

original
37

Approximate median: Quality
9-input median

25-input medianfully-working: 38 operations

fully-working: 220 operations

95.2%

21% reduction

94.4%

27% reduction

52% reduction

45.9%

54% reduction

4.8%

65.1%
20.2%

13.4%

1.2%

84% reduction
24.6%
14.3%

23.8%

81% reduction

19.0%

19.4%
12.3%

5.5%

38

Approx. 9-median as SW for microcontrollers

34.9% error prob.,max. error dist. 2
52% power reduction
4.8% error prob.,max. error dist. 1
21% power reduction
fully-working median

ops = operations in the source code.
#define PIX_SORT(a,b) {if ((a)>(b))
PIX_SWAP((a),(b));}

V. Mrazek, Z. Vasicek and L. Sekanina. GECCO GI Workshop, 201539

Energy-efficient implementation of sorting networks• Key idea: reduce the number of compare-and-swap operation insorting networks to improve energy-efficiency• To model the error introduced by the approximations in sorting
networks, the distance between the rank of the returned element andrank given by the specification is measured.
16-input sorting network

256-input sorting network

power reduction: 9%
error: <2 for 99% cases

power reduction: 52%
error: <14 for 99% cases

MRAZEK V., VASICEK Z.: Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee. In: PATMOS
2016, pp. 221-228
VASICEK Z., MRAZEK V.: Trading between Quality and Non-functional Properties of Median Filter in Embedded Systems. Genetic
Programming and Evolvable Machines, 2017, 18:45–82
40Tutorial Outline• Approximate Computing– Motivation– Error resilience– Sensitivity analysis and error metrics– Overview of approximation techniques• Evolutionary algorithms and genetic improvement• EA in SW approximations– Extension of Java - ExpAX– Median• EA in HW approximations– Approximations at the hardware description language level– Approximate multipliers in ANN– Library of approximate components• Formal relaxed equivalence checking in approximate computing– Binary decision diagrams– Approximate circuits with formal error guarantees• Conclusions
41

Functional circuit approximation
Original design:gate level / RTL / behavioral
Quality metric1𝑒𝑎𝑣𝑔 𝑓, 𝑓 = 𝑛
2| int 𝑓 𝑥

− int(𝑓 𝑥 ) |Design Process

Approximate circuit∀𝑥∈ℬ 𝑛• Design methodology• Manual [Kulkarni et al.: J. Low Power Electronic 2011]• Automatic (= some heuristics used)• Heuristic algorithms: SALSA (DAC 2012), SASIMI (DATE 2013), ABACUS(DATE 2014), ASLAN (DATE 2014), AIG-REV (ICCAD 2016) …
• GP-based methods: CGP (ICES 2013, DDECS 2014, EuroGP 2015, IEEE
Tr. on EC 2015, FPL 2016, GENP 2016), GP (ABACUS with NSGA-II 2017)42

Manual approximation: Multipliers
MSB removed!
AxB
0
1
2
3

0

1

2

3

0
0
0
0

0
1
2
3

0
2
4
6

0
3
6
7

approximatedaccurate• Correct results for 15 out of 16 input combinations (almost 50% area
reduction, lower delay).
• Used as a building block for larger multipliers and then in image processing
applications.
Error probability

Dynamic power reduction for various frequencies

Kulkarni et al. Trading Accuracy for Power in a Multiplier Architecture, VLSI Design, 201143

ABACUS: Approximations at Behavioral RT-level••

Original file: Verilog
Abstract Syntax Tree (AST) transformations(mutations)
–
–
–
–
–

•
•

Data type simplification
Operation transformations (e.g. + -> or)Arithmetic expression transformation
Variable to Constant transformations
Loop transformations

Search algorithm: NSGA-II – based
Fitness is obtained by circuit simulation andcombines the error & power

Nepal K. et al.: Automated High-Level Generation of Low-Power Approximate Computing Circuits, Trans. on Emerging Topics in Computing, 201744

ABACUS: Results
Benchmark problems:

Results of evolutionary approximation:

Nepal K. et al.: Automated High-Level Generation of Low-Power Approximate Computing Circuits, Trans. on Emerging Topics in Computing, 201745

GRATER: GA-based optimization of data types• Sensitivity analysis performed to find safe-toapproximate variables (AV) in OpenCL kernel.
• Chromosome: n integers specifying precision(i.e. data type) of n variables from AV.
• Objective: to find an approximate kernel thatminimizes the resource utilization on FPGA
while meeting the target quality.

Lotfi A. et al.: GRATER: An Approximation Workflow for Exploiting Data-Level Parallelism in FPGA Acceleration. DATE 201646

CGP for circuit (functional) approximation
Initial circuit
Resulting circuit• Resources-oriented (single-objective)
method• CGP is used to minimize the error, but only
limited resources (components) are provided,
insufficient for constructing a fully functional
circuit.

Error
Error

• CGP gradually degrades a fully functional circuit
until a circuit with a required error is obtained.
Then, the area (and so power consumption) is
minimized for this error.

Area• Error-oriented (single-objective) method

Area• All target parameters are optimized together.

Area• Multi-objective optimization
Pareto
front

Error

47

Energy-efficient implementation of ANNs
weights

H1

Approximations introduced in:• ANN structure – removing nodes of NN

weights

I1
H2

O1

H3

O2

I2

[Venkataramani et al. ISLPED’14]

I3
H4
Input layer

Hidden layer

Output layer• Learning algorithm• Memory – approximate Load/Store[Srinivasan et al. DATE’16]• Pipeline• Reducing data bit-width[Judd et.al. WAPCO’16]
I0
w0

I1

w1

[Judd et al. ICS’16]• Multiplication (approx. 45% of total power)

Multiplierless multiplication∑wI

Activation
function[Sarwar et al. DATE’16]• Activation functionwn
In[Du et al. ASP-DAC’14]• Sum function48

Energy-efficient implementation of ANNs
MNIST dataset classification: 32x32 – 100 – 10 MLP network (classification accuracy
94.16% with accurate implementation). We introduced an approximate multiplierby adding a jitter function Δ(𝑎, 𝑏), resulting in a 5.2% error for multiplication.
Scenario A:
Scenario B:• Multiplication• 80% of multiplications are by 0
𝑚 𝑎, 𝑏 = 𝑎 ⋅ 𝑏 + Δ 𝑎, 𝑏
• Multiplication0
𝑖𝑓 𝑎 = 0 ∨ 𝑏 = 0• Classification accuracy :𝑚′ 𝑎, 𝑏 =10.77%𝑎 ⋅ 𝑏 + Δ 𝑎, 𝑏

𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒• Classification accuracy : 94.20%

Mrazek, Sarwar, Sekanina, Vasicek, Roy: “Design of power-efficient approximate multipliers for approximate artificial neural networks,”
49
ICCAD 2016

CGP in approx. multiplier design for ANNs
Accurate multiplier – initial circuit (6)• CSAM RCA, CSAM RCA, RCAM, WTM CLA, WTM CSA, WTM RCA

Allowed errors: 𝜀 ∈ {0.5%, 1%, 2%, 5%, 10%, 15%, 20%}
CGP parameters• 𝑛𝑖 ∈ 14,22 ; 𝑛𝑜 ∈ 14,22 ; 𝑛𝑟 = 1; 250 < 𝑛𝑐 < 780• Functions: {NOT, AND, NAND, OR, NOR, XOR, XNOR}• Error constraints:
1. ∀𝑎, 𝑏: 𝑚 𝑎, 𝑏 − 𝑎 ∗ 𝑏 ≤ 𝜀 ⋅ 2𝑛𝑜2. ∀𝑎: 𝑚 𝑎, 0 = 𝑚 0, 𝑎 = 0• Fitness function:−𝐺𝑎𝑡𝑒𝑠𝐶𝑜𝑢𝑛𝑡(𝑚) 𝑖𝑓 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 1 𝑎𝑛𝑑 (2) 𝑚𝑒𝑡,𝐶 𝑚 =−∞𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Mrazek, Sarwar, Sekanina, Vasicek, Roy: “Design of power-efficient approximate multipliers for approximate artificial neural networks,”
50
ICCAD 2016

CGP in approx. multiplier design for ANNs
• In total, 852 approximate 7-bit and 11-bit multipliers were evolved by
CGP.
• Multipliers were sign-extended using one’s complement.
• The 8-bit and 12-bit multipliers were applied in NNs.
• The NNs were retrained with approximate multiplication operation using
backpropagation algorithm.
• Approximate multipliers showing the best trade off between power andaccuracy in NN were selected (for different error targets).

Mrazek, Sarwar, Sekanina, Vasicek, Roy: “Design of power-efficient approximate multipliers for approximate artificial neural networks,”
51
ICCAD 2016

Evolved approximate multipliers for ANNs
Power and area of 12 bit approximate multipliersPower and area of 8 bit approximate multipliers
1400

500
450
400
350
300
250
200
150
100
50
0

1200
1000
800
600

400
200
0
0%

0,50%

1%

2%
PWR μW

5%
AREA μm2

10%

15%

20%

0%

0,50%

1%

2%

PWR μW

5%

10%

15%

20%

AREA μm2

Results of synthesis of sign-extended multipliers with Synopsys DC
45 nm technology
Timing:8-bit multipliers: 2.5 GHz
12-bit multipliers: 2 GHz
Accurate multiplier was implemented in Verilog using standard * arithmetic
operator

Mrazek, Sarwar, Sekanina, Vasicek, Roy: “Design of power-efficient approximate multipliers for approximate artificial neural networks,”
52
ICCAD 2016

Energy-efficient implementation of ANNs: MLP• Handwritten number dataset(dataset used for benchmarking)• Fully connected MLP network• 28x28 inputs, 300 hidden neurons,
10 outputs• 60k training images• 10k testing images• More than 238k multiplications forapproximation• Initial classification accuracy:

weights

H1

weights

I1
H2

O1

H3

O2

I2
I3
H4
Input layer

Hidden layer

Output layer– 8b: 97.67%– 12b: 97.70%

53

Energy-efficient implementation of ANNs: LeNet
•
•
•
•
•
•

Complex real-world problem
Convolutional LeNet NN
278,104 multiplications in 6 layers
73k training images
26k testing images
Approximation introduced in L1,L3,L5
and L6 layers• Initial classification accuracy:– 8b: 86.85%– 12b: 86.90%
L1 – Convolutional
117,600 multiplications

Input image
32x32

L2 – Subsampling
4,704 multiplications

6@28x28

L3 – Convolutional
150,000 multiplications

6@14x14

L4 – Subsampling
1,600 multiplications

16@10x10

L5 – Convolutional
3,000 multiplications

16@5x5

L6 – Fully connected
1,200 multiplications

120@1x1

10 values

54Energy-efficient implementation of ANNs: Summary
Classification Accuracy and power reduction (in multiplication)Power(8 bit)(12 bit)

-20%
-50%

-30%
-43%

-57%
-66%

-77%
-70%

-82%
-85%

-91%
-86%

-91%
-87%

-36%
-60%

-25%
-20%

-9%
-1%

Classification accuracy of NN

100%
95%

MNIST w=890%

MNIST w=1285%

SVHN w=880%

SVHN w=12

75%
70%
0%

0.50%

1%

2%

5%

10%

15%

20%

{1}

{1,3}

{1,3,5,7}

Approximation error ε of multipliers
Multiplierless multiplication by
Sarwar et al. DATE’2016
Mrazek, Sarwar, Sekanina, Vasicek, Roy: “Design of power-efficient approximate multipliers for approximate artificial neural networks,”
55
ICCAD 2016

Library of approximate 8 bit adders and multipliers• Parallel multi-objective CGP:
• CGP + Non-dominated Sorting Genetic Algorithm II (NSGA-II) [Hrbáček, GECCO2015]• Parallel implementation: vectorized, multi-threaded, multiple islands(computer cluster employed)• Constraints: worst case error, worst case relative error• Initial population: a set of fully working conventional circuits• Fitness: mean relative error, power consumption, delay
O(i) is the i-th circuit output
i = 1 … 2NiTarget circuits - Inputs: Ni = 16; Outputs: No = 9 (adders), 16 (multipliers)
56

CGP parameters• Population size: 500 candidate circuits• Generations: 100k
• Mutation: 5%• Parallel CGP: 10 islands exchanging circuits every 1000
generations (120 cores)• CGP array: 1 x 200 nodes (adders), 1 x 1000 nodes (mult.)• CGP function set (180 nm technology library):• BUF, INV, AND2, OR2, XOR2, NAND2, NOR2, XNOR2, NAND3, NOR3,
MUX2, AOI21,OAI21, Full Adder, Half Adder• 3-input/2-output nodes used57

CGP: Initial population
Architecture

Power

Area

Delay

Ripple-Carry Adder

100.00%100.00%100.00%Carry-Select Adder

201.18%174.78%61.15%

Carry-Lookahead Adder

414.74%334.78%61.99%

HVTA (Brent-Kung)

286.00%201.74%68.52%

HVTA (Han-Carlson)

286.00%201.74%68.52%

HVTA (Kogge-Stone)

371.48%257.39%59.77%

HVTA (Sklansky)

305.07%215.65%60.45%TA (Brent-Kung)

282.99%201.74%67.25%TA (Han-Carlson)

295.74%212.17%61.87%TA (Knowles)

362.25%257.39%59.94%TA (Kogge-Stone)

342.20%243.48%57.68%TA (Ladner-Fischer)

282.99%201.74%67.25%TA (Sklansky)

298.34%212.17%57.84%

Architecture

Power

Area

Delay

Ripple-Carry Array

100.00%100.00%100.00%Carry-Save Array using RCA

102.30%100.00%71.16%

Carry-Save Array using CSA

108.42%106.16%62.03%

Wallace Tree using RCA

104.29%107.39%68.91%

Wallace Tree using CLA

116.10%148.48%51.26%

Wallace Tree using CSA

120.12%

122.35%53.28%

13 conventional 8-bit adders
TA = Tree Adder
HVTA = Higher Valency Tree Adder

6 conventional 8-bit multipliers
RCA = Ripple-Carry Adder
CSA = Carry-Save Adder
CLA = Carry-Lookahead Adder

58

Library of 8-bit approx. adders and multipliers• Large library of approximate arithmetic circuits• 430 non-dominated adders (evolved from 13 accurate adders)• 471 non-dominated multipliers (evolved from 6 accurate multipliers)

Approximate adders

Approximate multipliers(100% is Ripple-Carry Adder)(100% is Ripple-Carry Array Multiplier)

V. Mrazek, R. Hrbacek, Z. Vasicek, L. Sekanina: EvoApprox8b: Library, DATE 2017, p. 1-4
KIT: M. Shafique, W. Ahmad, R. Hafiz, and J. Henkel: A low latency generic accuracy configurable adder, DAC 2015, pp. 86:1–86:6.
59

Library of 8-bit approx. adders and multipliers
Approximate adders (430), exact adders (43)…………………………………………………………………………………………………………………………………………………
Approximate multipliers (471), exact multipliers (28)…………………………………………………………………………………………………………………………………………………

Synthesis results for 45 nm and 180 nm technology (Cadence Encounter RTL
Compiler), 7 error metrics

http://www.fit.vutbr.cz/research/groups/ehw/approxlib/
60

Tutorial Outline• Approximate Computing– Motivation– Error resilience– Sensitivity analysis and error metrics– Overview of approximation techniques• Evolutionary algorithms and genetic improvement• EA in SW approximations– Extension of Java - ExpAX– Median• EA in HW approximations– Approximations at the hardware description language level– Approximate multipliers in ANN– Library of approximate components• Formal relaxed equivalence checking in approximate computing– Binary decision diagrams– Approximate circuits with formal error guarantees• Conclusions
61

Are F1 and F2 functionally equivalent?

𝐹1 = (𝑥1 ∧ ¬𝑥2 ) ∨ ¬𝑥3

𝐹2 = ¬ ¬(𝑥1 ∧ ¬𝑥2 ) ∧ 𝑥3

x3

x2

x1

F1

F2

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

0

0

1

0

1

1

1

1

1

0

0

0

1

1

1

0

0

• Functional equivalence checking methods have been developed for decades.
‒ They exploit the model canonicity, SAT solving, algebraic approaches, …
• Relaxed functional equivalence checking is a new topic!
‒ How to prove the equivalence up to some bound?
• Scalability problem of (relaxed) equivalence checking!
62

How to determine the error?
Error “estimation”• Simulation• Probabilistic models, e.g. Li at al., DAC 2015

All possible
input vectors

Exact error calculation• Exhaustive Simulation – small problem instances only
• Analysis of Binary decision diagrams• Average error, worst case, error rate …
• M. Soeken, D. Grosse, A. Chandrasekharan, and R. Drechsler: BDD
minimization for approximate computing, ASP-DAC 2016

Approximate
circuit• Average Hamming distance:• Z. Vasicek and L. Sekanina: Circuit approximation using single- andmulti-objective cartesian GP. Gen. Prog. Evol. Mach., 17(2), 2016

• Not scalable for some problems such as multipliers• Transforming to SAT problem

1.3%

4.5%

Error = 3.1%

• Worst case error• S. Venkataramani et al. : SALSA: systematic logic synthesis ofapproximate circuits, DAC 201263

Binary Decision Diagrams

f = ac + bc

f= (a+b)c

f

a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

f
0
0
0
1
0
1
0
1

Truth table

a

a
b

b
c

0

c

0

0

b

c

1

0

c

1

Decision tree
1 edge0 edge

0

c

1

0

1

Reduced Ordered
BDD (ROBDD)(canonical form)

Operations over (RO)BDDs implemented by many libraries, e.g. Buddy.
64

Pitfalls of Binary Decision Diagrams• Variable ordering is important, may result in a more complex (orsimple) BDD.
x1

x1

x1x2 + x3x4

x2
x3

x3

x3

x2

x4

x2

x4
0

1

x1<x2<x3<x4(optimal)

0x1<x3<x2<x41
65

Equivalence checking using ROBDDs
ROBDD construction:
Apply (op, a, b) – creates ROBDD representing
logic function op over two ROBDDs a and b

Are circuits C1 and C2
functionally equivalent?

5

7

4
6

F1
G1

10
8

F2
9

G2

The decision procedure istrivial and reduces topointer comparison.
66

Other operations on ROBDDs• Many logic operations can be performed efficiently on BDDs
– usually linear in size of result– tautology and complement are constant time

Bryant R.: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. on Comp. 1986
67

Hamming distance using BDDs
SatCount (f) – gives thenumber of input
assignments for which f is
‘1’.

SatCount(z1) = 2
SatCount(z2) = 0• Create ROBDD for the parent circuit CA, theoffspring circuit CB and the XOR gates.
• Average Hamming distance:𝑒𝐻𝐷 =1
2𝑖𝑛𝑝𝑢𝑡𝑠

x1

x2

x3

x4

# combinations

0

0

0

0

1

0

1

1

0

1

𝑜𝑢𝑡𝑝𝑢𝑡𝑠

𝑆𝑎𝑡𝐶𝑜𝑢𝑛𝑡(𝑧𝑖 )𝑖=1

Vasicek Z., Sekanina L.: Evolutionary Design of Complex Approximate Combinational Circuits. Gen. Prog. and Evol. Mach. 17(2), 2016

68

Circuit approximation with CGP and BDD• Three criteria• relative area, delay and error• Error is the average Hamming distance (10 target error values Ei = 0.1 … 0.9 %)• CGP parameters• Rows = 1; Columns = # of gates in the original circuit• 5 mut./chromosome, = 5, 30 min/run, 10 independent runs
• Function set (relative area): and (1.333), or (1.333), xor (2.0), nand (1.0), nor (1.0),
xnor (2.0), buf (1.333), inv (0.667)• Two stages:• Find a circuit showing Ei , but a small (< 5%) imperfection tolerated• weight fitness (error / area / delay): (we; wa; wd) = (0.12; 0.5; 0.38)(but the error still kept under 5% of Ei)• 16 benchmark circuits

Vasicek Z., Sekanina L.: Evolutionary Design of Complex Approximate Combinational Circuits. Gen. Prog. and Evol. Mach. 17(2), 2016

69

CGP with BDD in the fitness function: Example
error/area only

error/delay only
single run

globalPareto front

Clmb (bus interface): 46 inputs, 33 outputs
Original clmb: 641 gates, 19 logic levels, |BDD| = 6966, |BDDopt| = 627 (SIFT in 2.3 s)
Optimized by CGP (no error allowed):
Best: 410 gates, 12 logic levels -- in 29 minutes (2.9 x 106 generations)Median: 442 gates, 13 logic levels

Properly optimize before doing approximations!
Vasicek Z., Sekanina L.: Evolutionary Design of Complex Approximate Combinational Circuits. Gen. Prog. and Evol. Mach. 17(2), 201670

Average-case error analysis• Let 𝑓: ℬ 𝑛 → ℬ 𝑚 be a Boolean function that describes correctfunctionality and 𝑓: ℬ 𝑛 → ℬ 𝑚 an approximation of it. The
average-case error is defined as the sum of absolute differences
in magnitude between the original and approximate circuit,averaged over all inputs:
1
𝑒𝑎𝑣𝑔 𝑓, 𝑓 = 𝑛
2| int 𝑓 𝑥

− int(𝑓 𝑥 ) |∀𝑥∈ℬ 𝑛where int x represents a function returning a decimal value ofthe m-bit binary vector x.
• No practically useful method capable of establishing the
average-case error using a SAT-based solver has been proposed
up to now. The BDDs seem to be the only viable option how to
calculate this error metrics.
71

Average-case error analysis using BDD
m=n+2
Example for n = 4: Because theresult of SUB is -32 … +31, themax absolute value is 32 and 6
bits are needed for m.

Approximate adderAccurate adder

CGP in approximate 16 bit adder design

VASICEK Z., MRAZEK V., SEKANINA L.: Towards Low Power Approximate DCT Architecture for HEVC Standard. DATE 201772

BDD vs exhaustive simulation
The average time needed to perform the worst-case and the average-case error
analysis for w-bit adders:

bit-width

inputs4-bit
8-bit
12-bit16-bit8
16
24
32

parallel simulation
emax + eavg
4.5 us
1.9 ms
682.4 ms
140.9 s

BDD-based method

emax

10.3 us
3.5 ms127.9 ms
1.38 seavg

speedupemax

14.0 us0.43
4.6 ms
0.54
312.7 ms
5.33
2.93 s 102.3

eavg

0.32
0.42
2.18
48.09

Notes
1)
2)

More than 100 randomly generated approximate adders were evaluated for each bit-width.
Time required to construct a BDD for a virtual circuit is included.

VASICEK Z., MRAZEK V., SEKANINA L.: Towards Low Power Approximate DCT Architecture for HEVC Standard. DATE 201773

Is the search-based approximation competitive?
• Approximate 16 bit multipliers created using different methods• PDP = Power Delay Product16-bit mul. constructedfrom 2-bit mults.

16-bit mul. constructedfrom 8-bit mults.

Evolved 16-bit
mult.approximate multipliers
16-bitVasicek Z.: DDECS 2017, Tutorial

74

Approx. circuits with formal error guarantees
List of the most complex arithmetic circuits that were successfully approximatedand whose error is formally guaranteed.
Aprox. circuit ewst eavg eprob ebf ewstac eHD methodpaper

authors

conference

32-bit adder!analysed only!

X

BDDs

MACACO: Modeling and Analysis of Circuits for
Approximate Computing

Venkatesan, Agarwal, Roy,
Raghunathan

ICCAD 2011

8-bit multiplier

X

BDDs

MACACO: Modeling and Analysis of Circuits for
Approximate Computing

Venkatesan, Agarwal, Roy,
Raghunathan

ICCAD 2011

8-bit multiplierXsimulation Evolutionary Design of Approximate Multipliers Under
Different Error Metrics
BDDs Analyzing Imprecise Adders Using BDDs - A Case Study
SAT, bin Approximation-aware Rewriting of AIGs for Error
search Tolerant Applications
BDDs Approximation-aware Rewriting of AIGs for Error
Tolerant Applications
PDR
Precise Error Determination of ApproximatedComponents in Sequential Circuits with Model Checking
BDDs BDD Minimization for Approximate Computing

Vasicek, Sekanina

DDECS 2014

Yu, Ciesielski

ISVLSI 2016
ICCAD 2016

simulation Design of power-efficient approximate multipliers forapproximate artificial neural networks

X

64-bit adder
16-bit adder
16-bit adder

X
X
X

X

16-bit adderX

8-bit ALU c3540

X

12-bit multiplier X

X

8-bit mutiplierXX

16-bit adder

X

X

X

X

Chandrasekharan, Soeken,
Grosse, Drechsler
Chandrasekharan, Soeken,
Grosse, Drechsler

ICCAD 2016

Chandrasekharan, Soeken,
Grosse, Drechsler

DAC 2016

Soeken, Grosse,
Chandrasekharan, Drechsler

ICCAD 2016

Mrazek, Sarwar, Sekanina,
Vasicek, Roy

ICCAD 2016

X simulation Automatic Design of Approximate Circuits by Means of Hrbacek, Mrazek, Vasicek
Multi-Objective Evolutionary Algorithms
BDDs
Towards Low Power Approximate DCT Architecture for Vasicek,Mrazek,Sekanina
HEVC Standard

DTIS 2016
DATE 2017

Vasicek Z.: DDECS 2017, Tutorial

75

Conclusions• Approximate computing is a hot topic!
– It addresses one of the most critical challenges of our society -- energy efficiency.

• The roots of approximate computing:– energy-efficient computing is needed– high variability in current/future technology nodes– many applications are error resilient• The approximation problem can be formulated as a multi-objective
design/optimization problem– A holistic approach is needed.
– A great opportunity for EAs!

• Current use of EA in Approximate computing– Optimization tasks (selection of types, variables, …)– Genetic improvement (with errors enabled)– Evolutionary design from scratch76

References• See references on particular slides• Selected tutorial and survey papers on Approximate Computing– J. Han and M. Orshansky, “Approximate computing: An emerging paradigm forenergy-efficient design,” in Proc. of the 18th IEEE European Test Symposium. IEEE,
2013, pp. 1–6– H. Esmaeilzadeh, A. Sampson, L. Ceze, D. Burger, “Neural acceleration for generalpurpose approximate programs,” Commun. ACM, 58(1): 105-115, 2015
– S. Mittal, “A survey of techniques for approximate computing,” ACM Computing
Surveys, 48(4), 1–34, 2016.
– Q. Xu, T. Mytkowicz, N. S. Kim. “Approximate Computing: A Survey,” IEEE Design
and Test, 33(1), 8-22, 2016.
– L. Sekanina, “Introduction to Approximate Computing” (embedded tutorial). IEEE
International Symposium on Design and Diagnostics of Electronic Circuits, DDECS
2016– Z. Vasicek, “Relaxed equivalence checking: a new challenge in logic synthesis”(embedded tutorial). IEEE International Symposium on Design and Diagnostics ofElectronic Circuits, DDECS 201777

Acknowledgement• EHW group at Brno University of Technology– Zdeněk Vašíček, Michal Bidlo, Roland Dobai– Michaela Šikulová, Radek Hrbáček, Vojtěch Mrázek, David Grochol, Miloš Minařík,Jakub Husa, Marek Kidoň, Michal Wiglasz and other students• Research projects– IT4Innovations Centre of Excellence – National supercomputing center– Advanced Methods for Evolutionary Design of Complex Digital Circuits, 2014 –2016 (Czech Science Foundation)– Relaxed equivalence checking for approximate computing, 2016 – 2018 (Czech
Science Foundation)

78

Thank you for your attention!

http://www.fit.vutbr.cz/research/groups/ehw

EHW @FIT