Evolutionary algorithms for embedded system design

Evolutionary Algorithms for Embedded System Design describes how Evolutionary Algorithm (EA) concepts can be applied to circuit and system design - an area where time-to-market demands are critical. EAs create an interesting alternative to other approaches since they can be scaled with the problem size and can be easily run on parallel computer systems. This book presents several successful EA techniques and shows how they can be applied at different levels of the design process. Starting on a high-level abstraction, where software components are dominant, several optimization steps are demonstrated, including DSP code optimization and test generation. Throughout the book, EAs are tested on real-world applications and on large problem instances. For each application the main criteria for the successful application in the corresponding domain are discussed. In addition, contributions from leading international researchers provide the reader with a variety of perspectives, including a special focus on the combination of EAs with problem specific heuristics.

Evolutionary Algorithms for Embedded System Design is an excellent reference for both practitioners working in the area of circuit and system design and for researchers in the field of evolutionary concepts.

Rolf Drechsler and Nicole DrechslerJoachim WegenerRainer LeupersChristian Haubelt and Sanaz Mostaghim and Frank Slomka and Jurgen Teich and Ambrish TyagiFabrizio Ferrandi and Donatella Scutio and Alessandro Fin and Franco FummiFulvio Corno and Matteo Sonza Reorda and Giovanni Squillero

Preface	p. ix
Contributing Authors	p. xiii
Foreword	p. xix
Introduction	p. xxi
1. Evolutionary Algorithms	p. xxii
1.1 Biological Background	p. xxii
1.2 Algorithmic Formulation	p. xxiii
1.2.1 Representation	p. xxiii
1.2.2 Objective Function	p. xxiv
1.2.3 Selection	p. xxiv
1.2.4 Initialization	p. xxv
1.2.5 Evolutionary Operators	p. xxv
1.2.6 Algorithm	p. xxvi
2. Contributions to this Book	p. xxvi
1 Evolutionary Testing of Embedded Systems	p. 1
1. Introduction	p. 1
2. Test Methods	p. 3
2.1 Comparative Evaluation	p. 5
3. Evolutionary Testing	p. 6
3.1 Suitability of Evolutionary Algorithms for the Evolutionary Test	p. 9
3.2 Tool Support	p. 12
3.2.1 Test Data Generation	p. 12
3.2.2 Test Driver	p. 13
3.2.3 Process Monitoring	p. 13
3.3 Configuration of Evolutionary Operators	p. 13
4. Evolutionary Testing of Non-Functional Properties	p. 14
4.1 Testing Temporal Behavior of Real-Time Systems	p. 15
4.1.1 Experiments on Sorting Methods	p. 16
4.1.2 Experiments on Computer-Graphics Example	p. 20
4.2 Safety and Robustness Testing	p. 23
5. Evolutionary Testing of Functional Behavior	p. 24
5.1 Experiments	p. 27
6. Conclusion, Future Work	p. 28
2 Genetic Algorithm Based DSP Code Optimization	p. 35
1. Compilers for Digital Signal Processors	p. 38
2. Address Generation in DSPs	p. 39
3. Offset Assignment Problem	p. 40
3.1 Motivating Example	p. 40
3.2 Simple Offset Assignment	p. 42
3.3 Generalized Offset Assignment	p. 43
3.4 Related Work	p. 47
4. Genetic Algorithm Formulation	p. 48
4.1 Motivation	p. 48
4.2 Chromosomal Representation	p. 49
4.3 Parameters and Initialization	p. 50
4.4 Crossover	p. 50
4.5 Mutation	p. 52
4.6 Fitness Function	p. 52
5. Experimental Results	p. 53
5.1 Statistical Evaluation	p. 53
5.2 Results for Application Programs	p. 56
6. Conclusions	p. 59
3 Hierarchical Synthesis of Embedded Systems	p. 63
1. Introduction	p. 64
1.1 Motivation	p. 64
1.2 Related Work	p. 64
1.3 Contribution	p. 65
2. A Model for Embedded System Synthesis	p. 66
2.1 The Specification Graph Model	p. 66
2.2 Hierarchical Modeling	p. 69
3. System Synthesis	p. 72
3.1 Implementation	p. 72
3.2 The Task of System Synthesis	p. 74
3.3 Objective Space	p. 79
4. System Synthesis Using Evolutionary Algorithms	p. 81
4.1 Multi-Objective Evolutionary Algorithms	p. 82
4.2 Strength Pareto Evolutionary Algorithm	p. 83
4.3 Chromosome Structure for System Synthesis	p. 85
4.3.1 The Function allocation()	p. 87
4.3.2 The Function binding()	p. 89
5. Hierarchical Design Space Exploration	p. 90
5.1 Pareto-Front Arithmetics	p. 91
5.2 Hierarchical Chromosomes	p. 93
5.2.1 Composite Mutation	p. 94
5.2.2 Composite Crossover	p. 96
6. Case Study	p. 97
6.1 Example	p. 97
6.2 Parameters of the Evolutionary Algorithm	p. 98
6.3 Exploration Results	p. 99
6.3.1 Pareto-Front Arithmetics	p. 100
6.3.2 Hierarchical Chromosomes	p. 101
6.3.3 Non-Hierarchical EAs	p. 101
7. Conclusions	p. 102
4 Functional Test Generation	p. 105
1. Introduction	p. 105
2. Functional Test Generation Algorithms	p. 110
2.1 Models	p. 110
2.1.1 Conjunctive Normal Form (CNF)	p. 111
2.1.2 Binary Decision Diagrams (BDDs)	p. 111
2.1.3 Assignment Decision Diagram (ADD)	p. 111
2.1.4 Finite State Machine	p. 113
2.2 Basic Concepts in Test Pattern Generation	p. 115
2.2.1 Justification, Implication and Backtracking	p. 115
2.2.2 SAT based Algorithms	p. 115
2.2.3 Time Frame Expansion	p. 115
2.3 Functional Test Generation Algorithms: A Taxonomy	p. 117
2.3.1 ATPGs based on Finite State Machines	p. 117
2.3.2 ATPGs based on Controllability, Observability and Structural Description of Data paths	p. 118
2.3.3 ATPG based on Assignment Decision Diagrams	p. 120
2.4 Genetic Approaches to Test Pattern Generation	p. 122
2.4.1 Gene Definition and Representation	p. 124
2.4.2 Fitness Function	p. 125
2.4.3 Crossover Operator	p. 125
2.4.4 Mutation Operator	p. 126
2.4.5 Selection Strategy	p. 126
2.4.6 Genetic Algorithms Advantages	p. 127
2.4.7 Genetic Algorithms Limitations	p. 127
3. Proposed Hybrid Approach	p. 127
3.1 Error Model	p. 128
3.2 GAs and BDDs Integration	p. 129
3.3 HTD and ETD Errors	p. 135
4. Experimental Results	p. 136
5. Concluding Remarks	p. 139
5 Built-In Self Test of Sequential Circuits	p. 143
1. Introduction	p. 143
2. Cellular Automata	p. 146
3. Test Architecture	p. 149
3.1 Circular Self-Test Path	p. 149
3.2 Cellular-Automata Circular Self-Test Path	p. 152
4. The Selfish Gene Algorithm	p. 154
4.1 Levels of Selection in Natural and Artificial Evolution	p. 155
4.2 Virtual Population	p. 158
4.3 High-Level Implementation	p. 159
4.3.1 Tournament	p. 161
4.3.2 Qualitative Analysis of Selfish Gene Behavior	p. 162
4.3.3 Polarization	p. 164
5. Selfish Gene for CA-CSTP	p. 164
6. Experimental Results	p. 166
7. Conclusions	p. 169
Index	p. 175

Available:*

On Order

Summary

Summary

Table of Contents