 |
Embedded System Design Methodologies
-
Project MEAT
Abstract
System-level synthesis may be considered as the problem of optimally mapping an algorithm-level specification onto a heterogeneous hardware/software architecture.
This problem is more than a simple bi-partitioning problem in hardware and software.
It 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, do not consider communication (tasks and resources), or require long run-times preventing design space exploration or yield only one implementation with optimal cost.
Our goal is to understand the complete problem, find a formal model for it, and define the task of system-synthesis to as an optimization problem.
The application and adaptation of an Evolutionary Algorithm to solve the tasks of optimization and design space exploration has proven to provide nice results for certain application domains.
Recent directions deal with finding good exploration methods (Pareto sets).
This project could be divided in three major tasks:
- Modeling of Embedded Systems
- Synthesis and Analysis of Embedded Systems
- Design Space Exploration
Modeling of Embedded Systems
Investigated are new models appropriate for modeling the behavior of heterogeneous embedded system applications, typically requiring as well control flow as data flow.
Existing approaches so far do only treat control-flow (e.g. embedded control) dominant or data-flow dominated applications (e.g., signal processing algorithms).
However, typical applications consist of a mixture of control and data flow.
This mixture, however, requires new models and also introduces uncertainties...
Addressing those problems has led to the SPI (System Property Intervals) project.
The SPI project goal is to enable global system analysis, in order to allow reliable and optimized implementation of heterogeneously specified embedded real-time systems on heterogeneous architectures.
The project focus is on global system modeling and analysis techniques, and on optimized implementation decisions with verified satisfaction of timing and memory constraints.
The actual implementation of system functions in hardware and software is left to existing code generators, compilers and (co)synthesis tools as much as possible.
To achieve these project goals, two key SPI elements are essential:
- The abstraction of both heterogeneous specification and heterogeneous architecture into a set of system properties necessary for global analysis.
- Modeling of uncertainty and non-determinism using property intervals at variable levels of modeling accuracy.
SPI is an open project and currently developed by research groups at TU Braunschweig, Germany (Prof. Ernst), Uni Erlangen, Germany (Prof. Teich) and ETH Zürich, Switzerland (Prof. Thiele).
The total research staff working in the SPI project is about 10 researchers, with funding from the German Science Foundation (DFG, Schwerpunktprogramms "SPPES").
More about the SPI project on the official SPI homepage.
New approaches in embedded system modeling focus on reconfigurable and adaptable systems.
Therefore, we propose a hierarchical model of embedded systems, capturing alternatives of the required behavior as well as alternatives of the underlying architecture of this system.
More information about recent research in the field of reconfigurable systems will be available on:
Synthesis and Analysis of Embedded Systems
System synthesis is the task of constructing an implementation of an embedded system while regarding all requirements of a given specification.
In general, we have to determine an allocation of hardware components, a binding of task to these allocated resources, and a scheduling of tasks in time.
Furthermore, while analyzing an embedded system, we prove or disprove asserted properties of this system.
Here, we use a graph-based model as described above for the synthesis ad analysis of embedded systems.
Both, synthesis and analysis are essential for the next step, the design space exploration.
Design Space Exploration
The goal of design space exploration is to find all optimal implementation for a given specification of an embedded system.
Due to the multi-dimensional nature of this optimization problem, we are not only interested in a single optimal solution, but in the set of all so-called Pareto-optimal solutions.
The large complexity of the design space of embedded systems yields heuristic optimization techniques for this task.
Special Evolutionary Algorithms (EA) called MOEAs (Multi-Objective Evolutionary Algorithms) have been found valuable in design space exploration.
In recent approaches, we extended design space exploration towards hierarchically specified systems, leading to
- an approximation of the Pareto-optimal solutions by only exploring the subsystems,
- uncertain objectives during system synthesis, and
- a dramatic reduction of the search space.
|
|
