Transcript Evolvable Hardware: By Antony Savich

Evolvable Hardware
(EHW)
Topic Review
S08*ENGG*6530
Antony Savich
Topic Review Outline
Motivation
Concept details
Problems and bottlenecks
General applications
Personal Retrospect
Conclusion
Design project summary
A. Savich
S08*ENGG*6530 - EHW
2
References
Jim Torresen, An Evolvable Hardware Tutorial. In proc. of
14th International Conference on Field Programmable
Logic and Applications (FPL'2004), August 2004,
Antwerp - Belgium
P Haddow, G Tufte, P Van Remortel, Evolvable
hardware: pumping life into dead silicon. In On Growth,
Form and Computers. Sanjeev Kumar, Peter J. Bentley,
Editors. Elsevier, 2003
Langdon, W.B. and Gustafson, S. (2005) Genetic
Programming and Evolvable Machines: five years of
reviews. Genetic Programming and Evolvable Machines,
6 (2). pp. 221-228. Springer, 2005
A. Savich
S08*ENGG*6530 - EHW
3
What is Evolvable Hardware?
EHW is hardware which is generated or
regenerated by special means
Goal: improve circuit performance
parameters via dynamic autonomous
regeneration

speed, area, power, output quality
Hardware Auto Evolution
A. Savich
S08*ENGG*6530 - EHW
4
What do we normally do?
Hardware engineering





Application analysis
Requirement specification
Circuit design (RTL, layout, routing)
Test suite formulation
Circuit verification and validation
Simulation
Hardware

A. Savich
Field performance evaluation
S08*ENGG*6530 - EHW
5
What do we normally do?
A. Savich
S08*ENGG*6530 - EHW
6
Why should we bother?
From design specification on,

85% (approx) of human time is spent on
product (circuit) generation
Human time = expensive
Machine time = cheap…….
Design complexity exponentially increases


A. Savich
Easy to hierarchaly specify
Difficult to optimize as a whole
S08*ENGG*6530 - EHW
7
Why should we bother?
Sizing limitation is not valid (Moore’s law)


~1billion transistors per chip (Intel 2006)
How much is this better than ~100million tr. chips?
Designability is the current hurdle
Nowadays, improvement in transistor count does
not equate to a similar functional or performance
improvement, the gap grows…
A. Savich
S08*ENGG*6530 - EHW
8
What is the benefit?
If it were possible to evolve inefficient
circuits…
The circuits created by evolution can be:


A. Savich
much simpler than human creations
not always comprehendible by humans
S08*ENGG*6530 - EHW
9
By autoevolution we get…
Reduced complexity, smaller circuits

In turn helps simplify the evolutionary process
More efficient circuits
Better performing circuits
New ideas and innovation
At the expense of machine time…
gives us extra time to do other things
than do boring circuit design?
A. Savich
S08*ENGG*6530 - EHW
10
How do we do it?
Specification
A. Savich
S08*ENGG*6530 - EHW
11
How do we do it?
Usually implies evolutionary techniques:



A. Savich
Genetic Algorithms
Genetic Programming
Evolutionary Programming
S08*ENGG*6530 - EHW
12
How do we do it?
Can be applied to various circuits


Digital (commercial or custom)
Analog
Off-line or on-line evolution
A. Savich
S08*ENGG*6530 - EHW
13
How do we do it?
Use requirements
Random
using defined
representation
Determine
fitness
Implement on
technology
Evolve
A. Savich
S08*ENGG*6530 - EHW
14
How do we do it?
Ideas?
Random
using defined
representation
Need to map a circuit description (phenotype)
to an evolutionary technique description (genotype)
How do we represent a circuit?
A. Savich
S08*ENGG*6530 - EHW
15
How FPGAs are relevant?
FPGAs are a natural
example of reconfigurable
digital technology
Can use the programming bitstream as the
genotype directly
Can rapidly reconfigure to fit new solutions
A. Savich
S08*ENGG*6530 - EHW
16
How do we do it?
Need to evaluate
generated circuits
(typically many)
How would you normally
evaluate a circuit?
Assign a fitness
parameter
A. Savich
S08*ENGG*6530 - EHW
17
Evaluation methods
A. Savich
S08*ENGG*6530 - EHW
18
How do we do it?
What are the evaluation
criteria for fitness?
Use requirements
A. Savich
S08*ENGG*6530 - EHW
19
Problem Redefinition
Sometimes…
The task of finding a solution is redefined as
a task of


Specifying the problem
Representing the solution
Sometimes, one is not easier than the other
A. Savich
S08*ENGG*6530 - EHW
20
How do we do it?
This step depends on the algorithm you choose,
In EHW this is typically GA (genetic algorithms)
Evolve
A. Savich
S08*ENGG*6530 - EHW
21
Genetic Algorithm
Initial circuit population using
a chosen representation
Parents
Evolution
Children
A. Savich
S08*ENGG*6530 - EHW
22
A cycle of evolution
A. Savich
S08*ENGG*6530 - EHW
23
Issues by design…
Using FPGAs leads naturally to direct mapping
(genotype – phenotype)

Creates a search space explosion for larger circuits
Indirect mapping – reduces genotype
description vs. phenotype requirements


A. Savich
Less information in genotype, not all phenotypes are
mapped (best solution may be skipped)
Changes complexity of finding a best solution into
complexity of finding the right mapping to include it
S08*ENGG*6530 - EHW
24
Issues by design…
Representation of genes – quick failure


A. Savich
If short, 1’s or 0’s, a single bit mutation may
lead to complete circuit failure
It’s difficult to encode genes in a genotype
such that a small gene change will result in
small functionality change
S08*ENGG*6530 - EHW
25
Issues by design…
Technological evolution is a problem




Better flexibility means increased granularity
Increased complexity means larger phenotype
Larger phenotype means slower configuration times
New heterogeneous FPGA features pose mapping
difficulties – not EHW friendly.
Complexity of system means complexity of
fitness functions, longer evaluation times
A. Savich
S08*ENGG*6530 - EHW
26
Solutions
‘Virtual’ FPGAs are possible:


A. Savich
Reduce genotype by simplifying routing
choices; logic component choices
Can be mapped onto commercial FPGAs
S08*ENGG*6530 - EHW
27
Solutions
Development of EHW friendly features

Map only the features that are suitable for
evolution
Partially evolvable systems


A. Savich
Design most of the system (fixed portion)
Allow only a portion to be evolved
S08*ENGG*6530 - EHW
28
An Interesting Application
On-line evolutionary systems:




A. Savich
Create competing nodes
Operate one in real time
Evolve others in parallel
Another reaches maturity - swap
S08*ENGG*6530 - EHW
29
Personal Retrospective: 1
On-line HW/SW evolvable system:


Why only require hardware execution vs.
software processing?
Why only evolve hardware?
The key – hardware/software cohabitation
within an on-line self-evolvable system.
A. Savich
S08*ENGG*6530 - EHW
30
Personal Retrospective: 1
Evolving a
scheduled
Unit
(co-evolution)
Scheduled for
optimization
Task set {1..n}
Task set {1..m}
Hard
model
Load monitor
& scheduler
Soft
model
With current advances in self-reconfiguration technology
and device size, this is all possible as a SoC!
A. Savich
S08*ENGG*6530 - EHW
31
Personal Retrospective: 2
Current research:
Neural Network (ANN) implementations



Rough model of the brain
ANNs provide approximating solutions to problems
ANNs are trained on a sample of the problem space
Quality of results highly depends on parameters
used in constructing ANN:



A. Savich
Topology (number and type of neurons)
Arithmetic representation
Learning function
S08*ENGG*6530 - EHW
32
Personal Retrospective: 2
Fitness determined by training a configuration
Training is expensive, best done in hardware
(currently FPGA), many configs to train
This process can benefit from automated design
evolution, the technology is directly correlated
with EHW methods:
A. Savich
S08*ENGG*6530 - EHW
33
Summary: EHW
Evolved
using
GA
ReduceEncoded by
Represented by
Genotype
Phenotype
Need a
Circuit
101011
1011010101010100
Fitness
Evaluated
Technology
Implemented on
A. Savich
S08*ENGG*6530 - EHW
34
Topic Conclusion
Evolvable Hardware – great circuits made easy
(in theory)
Typically Genetic Algorithm is used to evolve
Rephrases the “circuit design” problem into the
“pheno-genotype... mapping” problem.
Currently, can evolve small circuits
New hardware not friendly
A. Savich
S08*ENGG*6530 - EHW
35
Course Project Direction
Take an existing architecture


monolithic, full hardware acceleration
a type of ANN for this project
Use Tensilica tools
Profile and map portions of hardware to
produce:

software execution + smaller accelerator
Goal: compare resulting performance vs.
consumption of FPGA resources.
A. Savich
S08*ENGG*6530 - EHW
36
Thank you
S. Dali, Man with His Head Full of Clouds, 1936
A. Savich
S08*ENGG*6530 - EHW
37