Embedded system designs must meet several different design criteria. The traditional operations research approach of defining a single objective function and perhaps some minor objective functions, along with design constraints, may not adequately describe the system requirements.

Economist Vilfredo Pareto developed a theory for multi-objective analysis known as Pareto optimality. An important concept provided by this theory is the way in which optimal solutions are judged: an optimal solution cannot be improved without making some other part of the solution worse.

D’Ambrosio and Hu [D’Am94] developed the GOPS system to co-synthesize real-time embedded systems; they called this level of design configuration synthesis because it does not use detailed models of the processing elements.

GOPS uses a feasibility factor to estimate the schedulability of a set of tasks. Feasibility is determined relative to the speed of the PE and is defined in terms of several throughput factors. The upper-bound throughput TRU is an upper bound on the throughput required for the PE to finish the task. If ratemonotonic scheduling is used, then TRU for a set of N tasks is

where ci is the computation time, di is the deadline, and ai is the activation time, respectively, for task i. If earliest-deadline-first scheduling is used, then

However, because these bounds are loose, D’Ambrosio and Hu provided some tighter bounds. They first showed that a set of n tasks arranged in ascending order of deadlines cannot be feasibly scheduled if

where

They also showed that

and

Based on these results, they showed that TRL can be computed as

The actual throughput required to finish all tasks on time is TRp, which lies between TRL and TRU. They define the feasibility factor in terms of these throughput estimates:

During optimization, the feasibility factor can be used to prune the search space. Candidate architectures with negative feasibility factors can be eliminated as infeasible. The feasibility factor is also used as an optimization objective. The two criteria of GOPS are cost and feasibility factor.

Genetic algorithms have also been used for co-synthesis. This class of algorithms is modeled on genes and mutations. A solution to the problem is represented by a string of symbols. Strings can be modified and combined in various ways to create new designs. There are three basic types of moves in genetic algorithms:

1. A reproduction step makes a copy of a string.

2. A mutation step randomly changes a string.

3. A crossover step interchanges parts of two strings.

The new designs are then evaluated for quality and possibly reused to create still further mutations. One advantage of genetic algorithms is that they can easily handle complex objective functions.

***a***

Dick and Jha [Dic97; Dic98] developed a genetic algorithm for hardware/ software co-synthesis. Their algorithm can generate architectures with multiple processors and communication links; the architecture is optimized for both performance and power consumption. The synthesis procedure characterizes PEs as either independent or grouped. A processor can perform only one task at a time; an IC can have multiple cores on one chip so that a chip can simultaneously run several tasks.

The tasks are characterized by technology tables that give the worst-case execution time and power consumption of each task on each feasible processor. It also keeps arrays that map given the worst-case performance, average power consumption, and peak power consumption for each task on each feasible core.

2

3

4

5

>

>>