During the development process of complex embedded systems there typically is a large number of architectural decisions that engineers are facing. Each of them can in uence the properties of the end result (i.e.: cost, performance, etc.). A systematic process that supports this decision making is often referred to as Design Space Exploration (DSE). The need for computer-aided DSE methods was recognized by the research community which resulted in a large number of publications in this area. The contribution of this PhD project is two-fold: First contribution is a classi cation of typical DSE problems that arise during the development process of embedded systems. Due their high popularity in this area the focus of this work lies on the model-based approaches. The second contribution is two provide a decomposition approach for complex DSE problems. The decomposition strategy is thereby based on the previously identi ed DSE problem classes.
During the design phase of complex embedded systems engineers are faced with a number of design decisions (i.e. di erent selection or con guration of system components) that may in uence the quality of the system under development. Depending on the size of the system the number of decisions can become very large. The traditional (manual-driven) approaches such as relying on the experience of leading engineers or following the, so-called, best practices do not always produce good results. A systematic and computer-aided approach would be much more preferable. A decision process of searching for design solutions that satisfy certain constraints (i.e.: cost, weight, etc.) within a design space is called Design Space Exploration (DSE).
The need for automated Design Space Exploration techniques was
recognized by industry and academia, which led to a rising number of DSE related
publication in the last decade. The large amount of new publications and their
fragmentation over di erent research communities led to many ad-hoc solutions
(cf. [
Another trend, driven by the increasing computational power of modern
embedded hardware, is the rising complexity of those systems. That also e ects
the complexity of Design Space Exploration problems, that are used during the
design of these systems. Furthermore, during a preliminary study of the related
literature we found that many DSE problems consist of a number of atomic
sub-problems . An example for such a complex DSE problem is the search for
a mapping of software to hardware together with a corresponding schedule (cf.
[
This work is related to two research areas: The rst one deals with the
generalization of DSE approaches and their classi cation. The generalization of DSE is
often tackled by Frameworks, such as: ArcheOpterix [
The second related are to this work is the decomposition of complex problems
into simpler sub-problems. This approach is very popular in computer science
and is widely used in the eld of Constraint Programming, such as Parallel
Constraint Solving (cf. [
Todays embedded systems, such as modern vehicles, are characterized by high
complexity and heterogeneity. Therefore, the development process has to provide
support to the engineers in dealing with these challenges. A popular approach,
that is recommended by many standards and methodologies (cf. AUTOSAR [
In the following sub-sections, we discuss how it is possible to use this separation of the design process, that is dictated by many standards, to (i) de ne Design Space Exploration in this context; (ii) provide a classi cation of typical Design Space Exploration Problems; and (iii) use this classi cation for the decomposition of complex Design Space Exploration tasks. 3.1
Model-based development (MBD) became more and more popular in the area
of embedded systems. It is considered to be a central approach to deal with the
rising complexity in this eld [
As already discussed in this section, separation of concerns is a popular approach in the eld of embedded systems. Therefore, we assume that A can be partitioned into disjunct sub-sets as follows: Assumption 1 A collection of nonempty sets A1; :::; An are partitions of A i
To be able to construct a valid system instance it is though necessary to provide a possibility of assemble those partitions back together. Assumption 2 If Ai 2 A and Aj 2 A are two partitions according to ass. 1, then it is possible to nd a relation R(Ai; Aj ) between those two partitions.
And nally it should be possible to express constraints (i.e.: derived from requirements) towards this system that consists of partitions and their relations. Assumption 3 If Ai and R is a relation between two partitions, then is possible to express constraints of (sub-)partitions C(Ai) and their relations C(R). DSE De nition Using those assumptions, it is now possible to provide a de nition of Design Space Exploration in this particular context.
De nition 1. DSE is a process of systematically nding solutions from a design spaces that satisfy certain constraints. A solution thereby is either a partition, a relation between partitions or a combination of those two. 3.2
Based on the assumptions and de nitions from sec. 3.1 a set of abstract DSE problems is derived. We di erentiate the DSE problems over their constraints. The main di erence thereby is whether the constraint includes elements from one single partition or includes elements from two di erent partitions.
Fig. 1. Design Space Exploration Problem Classes
To illustrate this concept a small example (cf. g. 1) is used. It shows a simpli ed embedded system that consists of a software and a hardware part, where the software is supposed to run on the hardware.
De nition 2. We propose that one class of DSE problems is to select a sub-set from a partition Ai where this sub-set A0 Ai conforms to a set of constraints C. This problem we call selection.
An example for this class is to select features from a feature tree or components from a 150% model (cf. eq. 1). Another example is to select a con guration (or an instance) of a component (i.e. select a camera sensor model from a set). De nition 3. As the second class of DSE problems we propose is the search for a set of valid relations R between two partitions Ai and Aj so that 8r 2 R(Ai; Aj ) ! C(r).
Examples for this operation would be the allocation (cf. eq. 2) of software to hardware (deployment) or the allocation of software onto time slots (scheduling).
We performed a preliminary study of the related literature. Based on the results we can say that most of the DSE operations within these works could be led back to the two operations from def. 2 and 3. The literature search strategy was directed towards nding published papers in journals and conference proceedings that are accessible the widely accepted search engines and databases such as Google Scholar, IEEE XPlore, ACM Digital Library etc. The search words were focused on the scope of the PhD topic, which is Design Space Exploration, model-based Development and embedded Systems.
The idea of the decomposition approach is to divide a DSE problem into subproblems, solve them one after another. Pruning parts of the design-space in each step and thereby reducing the overall complexity of the problem. Often the solution of one problem has an e ect of the solution (or even solvability) of the other problem. If one does not take care of those dependencies it is very probable to prune to much design space during the solution of the rst sub-problems. Consider the DSE problem (P2) from sec. 1: If during the selection of the hardware architecture to much emphasis is put on the cost-e ciency the result may not provide enough resources for a possible deployment of software to this platform in the next step. Even though the generalization of these dependencies is still subject of ongoing work, there are some rst results that can be sketched here using examples. Let consider the DSE problem P2 again, which consists of selection (P2.1 ) and allocation (P2.2 ) according to de nitions from sec. 3.2.
Let us assume that the goal of P2.1 is to nd a hardware con guration so that its cost doesn't exceed a certain value (cf. eq. 1). For P2.2 we assume that each software component consumes a certain amount of memory and each hardware component provides a certain amount of memory. The goal of P2.2 is then to create a mapping between SWCs and HWCs. Thereby it is not allowed to exceed the memory provided by the HWCs(cf. eq. 2). (1) (2) (3)
SW C
X swc >hwc 8hwc 2 HW C : hwc:cost
value 8hwc 2 HW C swc:memory hwc:memory If during the solution of P2.1 we only consider the satisfaction of eq. 1, there is a chance that in the next step (P2.2 ) we will not nd a valid solution, because the cost-e cient hardware architecture does not provide enough memory. A possible way to prevent this is to add a simpli ed version of eq. 2 to the DSE problem P2.1 as follows.
SW C X swc:memory
HW C X hwc:memory This extra constraint ensures that the sum of provided memory is at least as high as the sum of the consumed memory. Vice versa one may conclude that if eq. 3 is not satis ed the problem P2.2 will not have any solutions. 4
This research will provide the following scienti c contributions: 1. DSE Classi cation Framework (a) Set of DSE problem classes that are typical for the design phase of embedded systems (b) Set of requirements(assumptions) a tool or methodology has to ful ll in order to be able to integrate those DSE classes 2. General Decomposition Approach for DSE Problems within Design Phase of embedded Systems (a) Guide of how to decompose complex DSE Problems (b) Tool Support for (semi-)automatic Decomposition of DSE Problems 5
At present time, we already achieved a number of tasks. We performed a literature study over the Design Space Exploration literature of the last 10 years. From that study we derived a preliminary classi cation of DSE problems. This allows us a decomposition of complex problems along the steps of a common development process of embedded systems. Furthermore, we conducted rst experiments that showed us an increase in performance compared to traditional approaches. Using the obtained classi cation, we derived a rst version of a Domain Speci c Language that can describe the identi ed types DSE problems and supports our decomposition approach.
We intend to evaluate the applicability of our approach using an industrial case study. Furthermore, we plan to compare our work with other decomposition approaches and conduct more experiments to show the scalability of our method. Finally, we plan to integrate our work into a state-of-the-art model-based tool as a prototype.