Architectural Design Exploration of Embedded Systems

Investigators

• Xiaobo (Sharon) Hu, University of Notre Dame
• Garrison W. Greenwood, Western Michigan University

Project Information

This collaborated research effort attempts to develop a methodology for efficiently exploring design options and to provide a means for assessing changes to existing designs in the embedded system development process.

The research proposed performs design exploration at the system level. At this level, a system is specified as a collection of task graphs and an implementation is described by an interconnection of hardware components and an assignment of processes to the hardware components. The overall approach is based on identifying the ``best'' mapping of a given system specification to a given set of hardware and software components. Though the problem shares some similarities with the hardware synthesis problem, many different issues need to be addressed in order for this approach to be effective. The following list identifies several innovations that will be produced as a result of this research:

• Efficient Design Space Exploration: We formulate our design exploration problem as a multi-attribute optimization problem. The success of our approach hinges on identifying an efficient means of exploring a large design space [1][2]. We propose to use techniques from the evolutionary computation field.
• Multi-attribute System Optimization: Another challenge we face is how to deal with the often conflicting performance requirements which include both functional and non-functional attributes. We will investigate techniques from decision theory such as imprecise value functions. This approach allows the identification of good configurations under the guidance of the designer's preferences. Our unique contribution is to combine the techniques from the utility theory and evolutionary computation field.
• System Reuse: In some instances it is not cost effective to initiate a totally new design effort in order to satisfy a new or changed specification. Non-recurring engineering costs can be minimized by reusing previously designed systems. Our design space exploration and system optimization techniques will provide the capability of evolving a currently existing designs to configurations that will satisfy new performance requirements.

General Approach

Our approach to performing hardware/software partitioning can be summarized as follows. Initially, we obtain a small set of alternatives which can be either extracted from the initial population of an evolutionary algorithm (EA) or which can be given by the designer. The designer then qualitatively ranks these alternatives. Imprecisely Specified, Multiple Attribute Utility Theory (ISMAUT) can then be used to define a set of designer's preferences which are stored into a file. (The reader is referred to [3], for details on ISMAUT.)

The EA works in a conventional manner of using genetic operators to generate new potential solutions. ISMAUT returns the dominant solutions (i.e., solutions which are at least as good as any other solutions) which the EA uses to determine which individuals survive. This process continues until a satisfactory solution has been found or a fixed number of generations have been produced and evaluated. We have implemented this approach as a software package called EvoC (Evolutionary Codesign).

Evolutionary Algorithms as a Search Mechanism

For the partitioning problem, individuals in the search space are design alternatives. The data structure for each individual encodes all of the relevant parameters needed to construct the alternative (processor type, task assignments to resources, etc.)

The EA terminates after a fixed number of generations (N) have been produced and evaluated or earlier if an acceptable assignment has been found. The EA algorithm is implemented as follows:

1. Create an initial population of P design alternatives by randomly assigning functions as either hardware or software implementations.
2. Conduct a tournament to select alternatives for reproduction. Each selected alternative generates one offspring by applying mutation operators that stochastically alter the problem parameters. This process creates a population with a total of 2P alternatives.
3. Rank all alternatives according to their fitness.
4. Deterministically select the P alternatives with the highest fitness.
5. Proceed to step 2 unless an acceptable solution has been found or N generations have been evaluated.

We use the preference relationship discussed in [4] to assign fitness to each alternative as follows. Using ISMAUT, all preferred alternatives are identified, assigned rank 1, and then removed from further contention. A new set of preferred alternatives can then be found, ranked 2, and so on until all alternatives have been ranked. Note that any alternatives which violate constraints (e.g., failure to meet a deadline) will not be preferred and thus ISMAUT will assign these a high numerical rank. Tournament selection is used to select alternatives for the reproduction in the next generation. Specifically, two distinct candidate alternatives are randomly selected from the current population and three additional distinct alternatives are randomly selected as a comparison set. If one candidate has a lower ranking than some alternative in the comparison set, and the other candidate does not, then the latter is selected for reproduction. If neither (or both) candidates have a lower ranking than some alternative in the comparison set, then a candidate is randomly chosen.

The interested reader can find more information on evolutionary algorithms in [5].

References

1. G. Greenwood and X. Hu, ``On the Use of Random Walks to Estimate Correlation in Fitness
   Landscapes'', Computational Statistics and Data Analysis (in press)

2. G. Greenwood and X. Hu, ``Are Landscapes for Constrained Optimization Problems Statistically
   Isotropic?'', Physica Scripta, Vol. 57, 321-323, 1998

3. C. White, A. Sage, and S. Dozono, ``A Model of Multiattribute Decisionmaking and Tradeoff Weight
   Determination Under Uncertainty'', IEEE Trans. Syst., Man, Cybern.'', Vol SMC-14, 223-229, 1984

4. G. Greenwood, X. Hu and J. D'Ambrosio, ``Fitness Functions for Multipleobjective Optimization
   Problems: Combining Preferences with Pareto Rankings'' Foundations of Genetic Algorithms,
   R. Belew and M. Vose (Eds.), Morgan-Kaufmann,San Francisco, CA, 437-455, 1997

5. T. Back, U. Hammel and H. -P. Schwefel ``Evolutionary Computation: Comments on the History and Current
   State'', IEEE Trans. on Evolutionary Comp., Vol. 1, No. 1, 3-17, 1997

Last updated by Sharon Hu 10 July 1998.