Skip to main content

Über dieses Buch

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.



Chapter 1. Evolutionary Testing of Embedded Systems

Testing is the most important analytical quality assurance measure for embedded systems. Test case design is the decisive testing activity for the quality of the test. Until now it has not been possible to automate test case design for common function-oriented and structure-oriented test procedures. This causes test case design to be fault-prone and cost-intensive. The evolutionary test is a new, promising approach for the automation of test case design. Evolutionary tests can be used to automate both the testing of functional and non-functional properties. For this purpose the respective test goal is transformed into an optimization problem which is solved by means of meta-heuristic search techniques. The definition of the fitness function is decisive. This chapter presents the fitness functions for testing the temporal behavior of systems, for the execution of safety tests, and for structure tests. Experiments performed demonstrate the effectiveness of the evolutionary test.
Joachim Wegener

Chapter 2. Genetic Algorithm Based DSP Code Optimization

This chapter describes a genetic algorithm (GA) designed for machine code optimization for a class of digital signal processors (DSPs). Due to the very high code quality demands in this area, novel optimization techniques beyond the scope of traditional compiler technology are of high interest. Embedded processors like DSPs show application-specific hardware features. For instance, in contrast to standard processors used in desktop computers, DSPs are mostly equipped with a dedicated address generation unit (AGU) capable of performing pointer arithmetic in parallel to the main data path. Effectively exploiting this AGU for variable address generation is a complex optimization problem. After an introduction to the area and a brief discussion of related work, we present the details of the proposed GA. Furthermore, we provide comprehensive experimental results indicating that the GA is superior to heuristic techniques in many cases, while still achieving acceptable runtimes.
Rainer Leupers

Chapter 3. Hierarchical Synthesis of Embedded Systems Using Evolutionary Algorithms

A Multi-Objective Approach
In this chapter, we propose an approach for the synthesis of heterogenous em-bedded systems, including allocation and binding problems. For solving these in general NP-complete problems, Evolutionary Algorithms have been proven to provide good solutions for search spaces of moderate size. For realistic embedded system applications, however, two more challenges must be considered: a) the complexity of the search space, and b) the multi-objective nature of the optimization problem to solve. I.e., the desired result of system synthesis is a design space exploration that provides the set of so-called Pareto-optimal solutions or an approximation thereof instead of just a single solution. Here, we propose a solution based on a Multi-Objective Evolutionary Algorithm (MOEA) which denotes a class of Evolutionary Algorithms that have recently proposed for design space exploration problems. Secondly, in order to reduce the complexity of typical search spaces, we propose a hierarchical problem and solution structure.
Christian Haubelt, Sanaz Mostaghim, Frank Slomka, Jürgen Teich, Ambrish Tyagi

Chapter 4. Functional Test Generation

Overview and Proposal of a Hybrid Genetic Approach
Functional testing is a common methodology for a quick verification of the cor‑rect implementation of a design. Moreover, functional testing allows to higher the level of abstraction at which test pattern generators (TPGs) are applied, in order to overcome the increasing complexity of the gate-level test pattern gen­eration task. Functional TPGs extend gate-level TPG techniques to the RT and behavioral levels by defining error models applicable to hardware description lan­guages (HDLs). In this chapter potentialities of genetic algorithms are exploited to propose a hybrid TPG, which allows to generate functional test patterns for HDL design descriptions. Genetic algorithms are mixed with a deterministic methodology based on binary decison diagrams and the respective advantages and drawbacks are compared. This analysis allows to define a hybrid genetic approach for functional testing.
Fabrizio Ferrandi, Donatella Scutio, Alessandro Fin, Franco Fummi

Chapter 5. Built-In Self Test of Sequential Circuits

A New Evolutionary Paradigm for Cultivating Cellular Automata
This chapter describes an innovative Built-In Self Test architecture based oncellular automata. The architecture is an enhancement of standard Circular Self-Test Path, and increases stuck-at fault coverage while maintaining all advantages, such as low timing intrusiveness, easy integration into design flow, at-speed testing. Cellular automaton rules are devised using the Selfish Gene algorithm, a new evolutionary algorithm based on an unorthodox view of the Darwinian theory, where the basic units of selection are genes rather than individuals. Experimental results show the effectiveness of the approach and the efficacy of the Selfish Gene algorithm.
Fulvio Corno, Matteo Sonza Reorda, Giovanni Squillero


Weitere Informationen