System-Level Synthesis Using Evolutionary Algorithms

Tobias Blickle, Jürgen Teich, Lothar Thiele, April 1996, TIK-Report No. 16

available as PostScript

In this paper, we consider system- level synthesis as the problem of optimally mapping an algorithm-level specification onto a heterogeneous hardware/software architecture. This problem requires
(1) the selection of the architecture (allocation) including general purpose and dedicated processors, ASICs, buses and memories,
(2) the mapping, of the algorithm onto the selected architecture in space (binding) and time (scheduling) and
(3) the design space exploration with the goal to find a set of implementations that satisfy a number of constraints on cost and performance.
Existing methodologies often consider a fixed architecture, perform the binding only, do not reflect the tight interdependency between binding and scheduling, require long run-times preventing design space exploration or yield only one implementation with optimal cost.
Here, a model is introduced that handles all mentioned requirements and allows the task of system-synthesis to be specified as an optimization problem. Furthermore, the application of an Evolutionary Algorithm to solve this problem is described.