Transcript elg7186_9_Optim

SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Hardware/Software
Codesign of
Embedded Systems
OPTIMIZATION
Voicu Groza
SITE Hall, Room 5017
562 5800 ext. 2159
[email protected]
Voicu Groza, 2008
1
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Dominance, Pareto Points
• A (design) point Jk is dominated by Ji, if Ji is
– better or equal than Jk in all criteria and
– better in at least one criterion.
• A point is Pareto-optimal or a Pareto-point, if
it is not dominated.
• The domination relation imposes a partial
order on all design points
– We are faced with a set of optimal solutions.
– Divergence of solutions vs. convergence.
Voicu Groza, 2008
2
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Multiobjective Optimization
• Maximize (y1, y2, …, yk) = ƒ(x1, x2, …, xn)
•Pareto set = set of all Pareto-optimal solutions
Voicu Groza, 2008
3
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Multi-objective Optimization
Voicu Groza, 2008
4
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Design Space, Pareto Points
• The task graph shows a system specification with four tasks, T1 ...T4.
The tasks can be executed on different components.
• The following table displays the execution times for the tasks on
the different components as well as the component cost.
For example, the MIPS processor costs 200 units and can run
tasks T1 in 5 ms and task T4 in 2 ms.
The table shows also the number of components available for
each component type (MIPS, DSP, FPGA and ASIC).
• All components execute tasks sequentially – at any given time a
component executes at most one task. Task execution is nonpreemptive – once a task is started, it runs to completion.
Voicu Groza, 2008
5
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
cost
(a) Construct the design space by
listing all possible design points.
A design point consists of an allocation (selection of
components), a binding (assignment of tasks to
selected components) and a schedule (execution
order for the tasks). Determine the total cost and
execution time for each design point.
(b) Draw the design points in a cost-time diagram.
Which design points are Pareto points?
Pareto Points
texec (ms)
T1
T2
T3
T4
Cost
texec
Voicu Groza, 2008
6
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
cost
Pareto Points
(c) Consider an allocation without resource constraints. That means
we are given an arbitrarily high number of components of each
type (MIPS, DSP, FPGA and ASIC). Are there new design
points?
Does the set of Pareto points change?
T1
T2
T3
T4
Cost
texec
Voicu Groza, 2008
7
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Genetic Algorithms
• Directed search algorithms based on the mechanics
of biological evolution
• Developed by John Holland, University of Michigan
(1970’s)
– To understand the adaptive processes of natural systems
– To design artificial systems software that retains the
robustness of natural systems
• Provide efficient, effective techniques for
optimization and machine learning applications
• Widely-used today in business, scientific and
engineering circles
Voicu Groza, 2008
8
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Classes of Search Techniques
Search techniques
Calculus-based techniques
Direct methods
Finonacci
Guided random search techniques
Indirect methods
Newton
Evolutionary algorithms
Evolutionary strategies
Voicu Groza, 2008
Dynamic programming
Genetic algorithms
Parallel
Centralized
Simulated annealing
Enumerative techniques
Distributed
Sequential
Steady-state
Generational
9
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Components of a GA
A problem to solve, and ...
• Encoding technique
(gene, chromosome)
• Initialization procedure
(creation)
• Evaluation function
(environment)
• Selection of parents
(reproduction)
• Genetic operators (mutation, recombination)
• Parameter settings
(practice and art)
Voicu Groza, 2008
10
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
GA Algorithmic Phases
Chromosome
Gene
Locus
Population
Phenotype
Initialize the population
Select individuals for the mating pool
Perform crossover
Perform mutation
Insert offspring into the population
no
Stop?
yes
The End
Voicu Groza, 2008
11
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Voicu Groza, 2008
12
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Simple Genetic Algorithm
{
initialize population;
evaluate population;
while TerminationCriteriaNotSatisfied
{
select parents for reproduction;
perform recombination and mutation;
evaluate population;
}
}
Voicu Groza, 2008
13
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
The GA Cycle of Reproduction
reproduction
children
modified
children
parents
population
modification
evaluation
evaluated children
deleted
members
discard
Voicu Groza, 2008
14
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Population
population
Chromosomes could be:
–
–
–
–
–
–
Voicu Groza, 2008
Bit strings
Real numbers
Permutations of element
Lists of rules
Program elements
... any data structure ...
(0101 ... 1100)
(43.2 -33.1 ... 0.0 89.2)
(E11 E3 E7 ... E1 E15)
(R1 R2 R3 ... R22 R23)
(genetic programming)
15
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Reproduction
reproduction
children
parents
population
Parents are selected at random with
selection chances biased in relation to
chromosome evaluations.
Voicu Groza, 2008
16
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Chromosome Modification
children
modification
modified children
• Modifications are stochastically triggered
• Operator types are:
– Mutation
– Crossover (recombination)
Voicu Groza, 2008
17
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Mutation: Local Modification
Before:
(1 0 1 1 0 1 1 0)
After:
(0 1 1 0 0 1 1 0)
Before:
(1.38 -69.4 326.44 0.1)
After:
(1.38 -67.5 326.44 0.1)
• Causes movement in the search space (local or global)
• Restores lost information to the population
• The Mutation Rate is the chance that a bit within a
chromosome will be flipped. This is usually a very low value
for binary encoded genes, say 0.001
Voicu Groza, 2008
18
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Crossover: Recombination
One point crossover is performed by selecting a random
gene along the length of the chromosomes and swapping
all the genes after that point
*
10001001101000011
10001001110010010
01010001001000011
01010001010010010
Crossover is a critical feature of genetic algorithms:
– It greatly accelerates search early in evolution of a population
– It leads to effective combination of schemata (subsolutions on
different chromosomes)
The Crossover Rate is the chance that two chromosomes will
swap their bits. A good value for this is around 0.7.
Voicu Groza, 2008
19
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Two point crossover
Two point crossover calls for two points to be selected on the parent
chromosome strings. Everything between the two points is swapped
between the parent organisms, rendering two child organisms:
"Cut and splice"
Another crossover variant, the "cut and splice" approach, results in a
change in length of the children strings. The reason for this difference is
that each parent string has a separate choice of crossover
point.
Voicu Groza, 2008
20
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Evaluation
evaluated
children
modified
children
evaluation
• The evaluator decodes a chromosome and
assigns it a fitness measure
• The evaluator is the only link between a
classical GA and the problem it is solving
Voicu Groza, 2008
21
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Fitness Function
• Quantifies the optimality of a solution (a chromosome)
such that particular chromosome may be ranked against all
the other chromosomes. Optimal chromosomes, are
allowed to breed and mix their datasets producing a new
generation that will (hopefully) be even better.
• An ideal fitness function correlates closely with the
algorithm's goal, and may be computed quickly. Speed of
execution is very important, as a typical genetic algorithm
must be iterated many, many times in order to produce a
usable result for a non-trivial problem.
• Definition of the fitness function is not straightforward in
many cases and often is performed iteratively if the fittest
solutions produced by GA are not what is desired.
Voicu Groza, 2008
22
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Deletion
population
discarded members
discard
• Generational GA:
entire populations replaced with each iteration
• Steady-state GA:
a few members replaced each generation
Voicu Groza, 2008
23
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Stopping Criteria
• Final problem is to decide when to stop
execution of algorithm.
• There are two possible solutions to this problem:
– First approach:
• Stop after production of definite number of
generations
– Second approach:
• Stop when the improvement in average fitness
over two generations is below a threshold
Voicu Groza, 2008
24
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
An Abstract Example
Distribution of Individuals in Generation 0
Distribution of Individuals in Generation N
Rennard Genetic Algorithm Viewer 1.0
• http://www.rennard.org/alife/english/gavgb.html
Voicu Groza, 2008
25
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
A Simple Example
The Traveling Salesman Problem:
Find a tour of a given set of cities so that
– each city is visited only once
– the total distance traveled is minimized
Voicu Groza, 2008
26
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Representation
Representation is an ordered list of city
numbers known as an order-based GA.
1) London
2) Venice
3) Dunedin
4) Singapore
CityList1
(3 5 7 2 1 6 4 8)
CityList2
(2 5 7 6 8 1 3 4)
Voicu Groza, 2008
5) Beijing 7) Tokyo
6) Phoenix 8) Victoria
27
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Crossover
• Crossover might combine inversion & recombination;
• e.g. given two chromosomes
*
*
Parent1
(3 5 7 2 1 6 4 8)
Parent2
(2 5 7 6 8 1 3 4)
Child
Voicu Groza, 2008
(8 5 7 2 1 6 3 4)
28
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Mutation
Mutation involves reordering of the list:
Before:
*
*
(5 8 7 2 1 6 3 4)
After:
(5 8 6 2 1 7 3 4)
• the Crossover Rate is the chance that two chromosomes
will swap their bits. A good value for this is around 0.7
Voicu Groza, 2008
29
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
TSP Example: 30 Cities
120
100
y
80
60
40
20
0
0
10
20
30
40
50
60
70
80
90
100
x
Voicu Groza, 2008
30
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Solution i (Distance = 941)
TSP30 (Performance = 941)
120
100
y
80
60
40
20
0
0
10
20
30
40
50
60
70
80
90
100
x
Voicu Groza, 2008
31
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Voicu Groza, 2008
TSP30 (Performance = 800)
120
100
80
y
44
62
69
67
78
64
62
54
42
50
40
40
38
21
35
67
60
60
40
42
50
99
Solution j(Distance = 800)
60
40
20
0
0
10
20
30
40
50
60
70
80
90
100
x
32
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Solution k(Distance = 652)
TSP30 (Performance = 652)
120
100
y
80
60
40
20
0
0
10
20
30
40
50
60
70
80
90
100
x
Voicu Groza, 2008
33
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Best Solution (Distance = 420)
Voicu Groza, 2008
TSP30 Solution (Performance = 420)
120
100
80
y
42
38
35
26
21
35
32
7
38
46
44
58
60
69
76
78
71
69
67
62
84
94
60
40
20
0
0
10
20
30
40
50
60
70
80
90
100
x
34
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Overview of Performance
TSP30 - Overview of Performance
1800
1600
1400
Distance
1200
1000
800
600
400
200
0
Best
1
3
5
7
9
11
13
15
17
19
21
Generations (1000)
Voicu Groza, 2008
23
25
27
29
31
Worst
Average
35
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
GA For Optimal Implementation
of Logic Functions in FPGAs
1.
2.
Attempting to evolve the minimized logic solution of
a logic function
The evolution is done through a hardware
implementation of a genetic algorithm (GA), while
the minimization is one of FPGA look-up tables
(LUTs) and logic levels
Voicu Groza, 2008
36
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
System Architecture
•
•
•
•
•
•
•
•
Optimizer = ECP Controller
(ECPC)
Host = ECP
Both optimizer and host are PLDs
Optimizer is where function is
evolved
Host is where circuit is tested
Optimizer/Host = Server/Client
Multiple hosts can connect to one
optimizer
Multiple functions can be evolved
on one optimizer
Voicu Groza, 2008
37
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Optimizer Module
1. HIGA (HW implemented GA)
•
Much faster because done
mostly in H/W
•
Adds caveats on the std. GA
2. ECLBs
Evolvable Configuration Logic Blocks
•
Where the chromosomes are
evaluated for fitness
assignment
1. hcache
•
Voicu Groza, 2008
Common DB for future use
38
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Optimizer Architecture
Voicu Groza, 2008
39
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
System Operation
Voicu Groza, 2008
40
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
System
Operation
(2)
Figure 5
Voicu Groza, 2008
41
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
FPGA
Voicu Groza, 2008
42
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Figure 7
Voicu Groza, 2008
43
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Figure 8
Voicu Groza, 2008
44
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Issues for GA Practitioners
• Choosing basic implementation issues:
–
–
–
–
representation
population size, mutation rate, ...
selection, deletion policies
crossover, mutation operators
• Termination Criteria
• Performance, scalability
• Solution is only as good as the evaluation
function (often hardest part)
Voicu Groza, 2008
45
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Benefits of Genetic Algorithms
•
•
•
•
•
Concept is easy to understand
Modular, separate from application
Supports multi-objective optimization
Good for “noisy” environments
Always an answer; answer gets better
with time
• Inherently parallel; easily distributed
Voicu Groza, 2008
46
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Benefits of Genetic Algorithms (cont.)
• Many ways to speed up and improve a
GA-based application as knowledge
about problem domain is gained
• Easy to exploit previous or alternate
solutions
• Flexible building blocks for hybrid
applications
• Substantial history and range of use
Voicu Groza, 2008
47
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
When to Use a GA
• Alternate solutions are too slow or overly
complicated
• Need an exploratory tool to examine new
approaches
• Problem is similar to one that has already been
successfully solved by using a GA
• Want to hybridize with an existing solution
• Benefits of the GA technology meet key problem
requirements
Voicu Groza, 2008
48
SITE, 2008 - HARDWARE/SOFTWARE CODESIGN OF EMBEDDED SYSTEMS
Some GA Application Types
Domain
Application Types
Control
gas pipeline, pole balancing, missile evasion, pursuit
Design
Scheduling
semiconductor layout, aircraft design, keyboard
configuration, communication networks
manufacturing, facility scheduling, resource allocation
Robotics
trajectory planning
Machine Learning
Signal Processing
designing neural networks, improving classification
algorithms, classifier systems
filter design
Game Playing
poker, checkers, prisoner’s dilemma
Combinatorial
Optimization
set covering, travelling salesman, routing, bin packing,
graph colouring and partitioning
Voicu Groza, 2008
49