Metaheuristics for Hardware Evolution (2V, 1U; 4 LP ECTS)
Course number in SS 2016: L.079.05820
Lecturer
Dr. Paul Kaufmann
Office: O3.116
Office hours: by appointment
News
First lecture (14:15-15:45) on May, the 31st, will take place in P1.4.17
26.06.2016 MOEA, EHW, Desing Space Exploration slides online
20.06.2016 Time slots for next lecture and lab: June, 28th, 16:00 - 17:30 and 17:45 - 19:15 in O3.219
29.05.2016 Lab3 materials online
29.05.2016 ES, PSO, ANT, GP, CGP slides online
04.05.2016 Algorithm evaluation slides updated
04.05.2016 Lab2 materials online
25.04.2016 Lab1 materials online at Sciebo
25.04.2016 Floorplanning and Placement slides online at Sciebo
25.04.2016 Algorithm evaluation slides online at Sciebo
25.04.2016 All slides updated at Sciebo
15.04.2016 First lecture uploaded to koaLA
Goals and Contents of the Lecture
This lecture introduces modern metaheuristics, a family of optimization algorithms based on the principles of analogy, induction and decomposition and inspired by mechanisms such as the annealing process in metallurgy and the biological evolution of species. Metaheuristics are used when computational challenges are getting to large and complex to solve them optimally. Examples for such challenges are, for instance, the design of digital and analog circuits, the identification of bugs in programs, finding new types of antennas, and the computation of large scheduling plans.
While the lecture focuses on the algorithmic aspects of metaheuristics and on statistical tools for algorithm evaluation and comparison, the labs are organized as theoretical and programming exercises requiring the students to implement, apply, evaluate, and compare the algorithms introduced in the lecture on tasks such as Floorplanning, chip heat flow forecasting, evolution of hardware signal classifiers, optimization of smart grid extensions, and electric power grid restoration.
The lecture covers the following algorithmic topics
- The basic notion of Optimization
- Gradient / Steepest Descent and Hill Climbing
- Statistical analysis for Metaheuristics
- The Metropolis Algorithm, Simulated Annealing, Tabu Search, Variable Neighborhood Search
- Genetic Algorithms, Evolutionary Strategies, Genetic Programming
- Particle Swarm Optimization, Ant Colony Optimization
- Multi-objective Evolutionary Algorithms
- Neural Networks
The lecture covers the following application cases
- Floorplanning
- Placement
- High Level Synthesis Design Space Exploration
- Evolvable Hardware
- Hardware Neural Networks
- Approximate Computing
The labs cover the following implementation exercises
- Algorithms for floorplanning and placement
- SmartGrid optimization (network extension and restoration)
- Evolution of digital circuits
Schedule and Materials
The course is held on Tuesday, 14:15-15:45 o'clock in room O1.258. The labs are held on every second Tuesday, 16:15-17:45 o'clock in room O3.219. The course materials can be downloaded here.
Date | Content | ToDo | Lab |
---|---|---|---|
12.04.2016 | Introduction to Metaheuristics 1 | no lab | |
19.04.2016 | Introduction to Metaheuristics 2 | Please read §1-§3 of the paper: "Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison" | no lab |
26.04.2016 | Introduction to Metaheuristics 2 | Lab 1: Optimization of Smart Grids | |
03.05.2016 | Statistical Methods for Algorithm Comparison I,II,III | ||
10.05.2016 | Floorplanning I,II | Lab 1: Discussion Lab 2: Implementation of a floorplanner | |
24.05.2016 | Evolutionary Algorithms I,II,III | ||
31.05.2016 | ES, PSO, ACO, GP, CGP | Lab 2: Discussion Lab 3 | |
28.06.2016 | Multi-objective Evolutionary Algorithms Design Space Exploration | Lab 3: Discussion |
Exercises and Labs
The goal of the lecture is to provide hands-on knowledge for applying Metaheuristics on real world optimization problems. The labs are therefore focusing on implementation exercises (hill climbing, SA, GA, GP, CGP, MOEA, tabu search,…) optimizing smart grids (network reinforcement), floor plans, and gate logic circuits.
The lab materials can be downloaded from the sciebo website. A uniform development environment can be downloaded from here: link The instructions on how to use the development environment are given in the first lab.
Literature
- Weicker, Karsten: "Evolutionäre Algorithmen", Springer, 2007. ISBN 978-3-8351-9203-4
- Kruse et al.: "Computational Intelligence - A Methodological Introduction", Springer, 2013. ISBN 978-1-4471-5012-1
- Kruse et al.: "Computational Intelligence [DE]", Vieweg+Teubner-Verlag, Wiesbaden, 2011. ISBN 978-3-8348-1275-9
- Wang et al.: "Electronic Design Automation", Morgan Kaufmann, 2009. ISBN: 0-1237-4364-8