=Paper=
{{Paper
|id=Vol-1643/paper-04
|storemode=property
|title=Search Space Reduction for E/E-Architecture Partitioning
|pdfUrl=https://ceur-ws.org/Vol-1643/paper-04.pdf
|volume=Vol-1643
|authors=Andreas Ettner
|dblpUrl=https://dblp.org/rec/conf/date/Ettner16
}}
==Search Space Reduction for E/E-Architecture Partitioning==
https://ceur-ws.org/Vol-1643/paper-04.pdf
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
Search Space Reduction for E/E-Architecture
Partitioning
Andreas Ettner
Robert Bosch GmbH, Corporate Reasearch,
Robert-Bosch-Campus 1, 71272 Renningen, Germany
andreas.ettner@de.bosch.com
Abstract. As the design of electrical/electronic (E/E)-architectures is
becoming more complex, multi-objective optimization algorithms such
as evolutionary algorithms (EAs) have been proposed for generating
resource optimized architectures. In this paper we extend existing ap-
proaches by excluding infeasible solutions from the search space and
thereby enhance the quality and runtime behavior of the optimization.
Keywords: E/E-Architecture Partitioning, Design Space Reduction, Evo-
lutionary Algorithm
1 Introduction
Due to the introduction of new safety and comfort functions related to advanced
driver assistance, highly automated driving, and car-to-x connectivity, the num-
ber and interconnections of functions in vehicles has been growing over the last
decades and is going to grow further over the next years. As a result, distributed
vehicle system architectures consisting of heterogeneous computing resources be-
come more complex and power consuming. Thereby, also the complexity of the
allocation task problem is growing, which is defined as assigning functions to
Electronic Control Units (ECUs) while fulfilling various design constraints, such
as safety requirements and resource restrictions (see Figure 1).
In recent years, several optimization methods with the aim of supporting
engineers in power and resource aware design of E/E-architectures have been
proposed. While Walla [6] presented a mixed-integer linear programming (MILP)
approach to optimize function partitioning with respect to energy efficiency,
EAs have proven useful for concurrent optimization of multiple objectives, such
as performance, cost, and reliability [1], [3], [4]. However, when increasing the
number of design constraints, EAs might fail in producing feasible solutions and
in converging toward a global maximum. Common approaches to overcome this
problem have been compared by Moser [5] and the results showed that repairing
infeasible solutions is superior to penalizing and constrain-dominance methods.
Yet, the search space still contains all infeasible solutions for each of which the
repair function would be invoked. In order to overcome this drawback and to
decrease the amount of infeasible solutions, we present an approach to reduce
the search space in advance of the optimization run. Thereby, we enhance the
quality and runtime behavior of the optimization.
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
2 Search Space Reduction for E/E-Architecture Partitioning
Fig. 1. Function Allocation
2 Concept
2.1 Models and Representation
Figure 1 exemplary shows the two input models to the optimization. The function
model consists of a set F of functions with inter-dependencies being represented
by directed edges. The architecture is modelled by a set E of ECUs connected
by bus structures. Properties describe the available resources on the ECUs and
the resource demands as well as functional requirements of the functions. For
example, the computing requirements for each function are represented by rf
and the available computing resources for each ECU by re , respectively.
The allocation of vehicle functions to the ECUs is represented by a mapping
vector m indicating for each function fi the corresponding ECU identifier ej .
By default, each function can be allocated to each ECU, such that the set of all
possible ECUs for fi is M = {e1 , ..., eJ } and the number of possible solutions is
S = |E||F | .
2.2 Objective Functions and Constraints
In our approach, we optimize three objective functions: network communication,
safety, and the collection of functions with certain properties on a minimum
number of ECUs. As the search space reduction is independent of the objective
functions, we will concentrate on the constraints in the following:
– Location constraints either define a set of ECUs CI,i - where function fi will
be mapped to one element of this set - or exclude a set of ECUs CE,i .
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
Search Space Reduction for E/E-Architecture Partitioning 3
– Colocation constraints either forbid two functions to be allocated to the same
ECU (Cban : e(fi ) 6= e(fj )) or force two functions to reside on the same ECU
(Cf orce : e(fi ) = e(fj )).
– Some functions demand certain components or functional requirements reqf,
which have to be provided by the corresponding ECU (reqe ). Therefore,
function fi can only be allocated to one ECU of the set Creq,i = {e|reqe ≥
reqf }.
– Some resources, such as the memory and computing units, P are shared among
all functions allocated to the ECU. Therefore, re,j ≥ rf,i with (e(fi ) = ej )
has to hold for each ECU.
2.3 Genetic Algorithm
For the optimization, we use the NSGA-II algorithm presented by Deb [2]. Its
structure is shown in Figure 2. During initialization, a population of solutions is
generated by assigning one element of set M to each of the functions resulting
in one mapping vector for each solution. Afterwards, the population iteratively
improves by creating new solutions, evaluating these solutions with regard to
the constraints and the objective functions (see Fig. 3), and finally selecting the
best solutions for the next generations based on Pareto-optimality.
Fig. 2. Structure of Evolutionary Algorithm
New solutions are generated by variation operators such as mutation, which
assigns an element of set M to a random number of functions. Thereby, a huge
amount of solutions violating the constraints defined in chapter 2.2 might be
generated that would have to be either repaired or discarded. As an approach
to reduce this number, we reduce the sets Mi for each function fi in advance of
the optimization by analyzing the design constraints and use those sets during
initialization and mutation to generate new individuals.
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
4 Search Space Reduction for E/E-Architecture Partitioning
Fig. 3. Evaluation of individuals
2.4 Search Space Reduction (SSR)
Figure 4 presents the SSR for each function. In a first step, the sets Mi are
initialized with either the ECUs defined in CI,i (1a) or, in case CI,i is not defined,
with all ECUs from M (1b). Afterwards, Mi is reduced by CE,i (2), by the ECUs
that do not fulfil the constraints on functional requirements (3), and by the ECUs
that do not provide sufficient resources for function fi (4). Step (5) ensures that
the sets Mi and Mj of two functions to be forced together contain the same ECU
elements. Finally, if functions to be banned from fi are already allocated to a
certain ECU, this ECU is removed from Mi (6).
Fig. 4. Reduction sequence
3 CASE STUDY AND RESULTS
Table 1 and Table 2 exemplary show the property values for the optimization
problem presented in Figure 1.
f1 f2 f3 f4 f5 f6 e1 e2 e3 e4 e5
rf 6 2 3 1 2 3 re 10 10 5 10 10
f reqf 8 0 4 4 2 1 f reqe 8 4 8 2 1
Table 1. Function requirements Table 2. ECU properties
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
Search Space Reduction for E/E-Architecture Partitioning 5
original (1) (2) (3) (4) (5) (6)
15,625 9,375 7,500 810 405 243 162
100 % 60 % 48 % 5.2 % 2.6 % 1.6 % 1%
Table 3. Size of search space after each reduction step
Furthermore, let CI,2 = {e1 , e2 , e3 }, CE,5 = {e1 }, and consider f orce(f5 , f6 )
and ban(f1 , f2 ). Applying SSR to the optimization problem results in M1 = {e1 },
M2 = {e2 , e3 }, M3 = {e1 , e2 , e3 }, M4 = {e1 , e2 , e3 }, M5 = {e2 , e3 , e4 } and
M6 = {e2 , e3 , e4 }. As shown in Table 3, the search space could be pruned to about
1 % of its original size. This has also an impact on the number of generations for
finding the optimal solutions. With a population size of 10, we commonly find the
five Pareto-points after 15 generations, whereas an EA with repair mechanism
needs 150 generation and an EA without repair function and mapping sets more
than 5000 generations. For a larger use case with 32 functions, 10 ECUs, location
constraints on 28 functions, and a population size of 50, Figure 5 shows the mean
hypervolume values over 25 optimization runs. Whereas the standalone NSGA-II
finds first feasible solutions after 60 generations and then slowly increases, the
NSGA-II with SSR converges after 140 generations.
Fig. 5. Hypervolume with SSR (black) and without (blue)
References
1. Blickle, Tobias, Jrgen Teich, and Lothar Thiele. ”System-level synthesis using evo-
lutionary algorithms.” Design Automation for Embedded Systems 3.1 (1998): 23-58.
2. Deb, Kalyanmoy, et al. ”A fast and elitist multiobjective genetic algorithm: NSGA-
II.” Evolutionary Computation, IEEE Transactions on 6.2 (2002): 182-197.
3. Hardung, Bernd. Optimisation of the allocation of functions in vehicle networks.
Shaker, 2006.
4. Moritz, Ralph, Tamara Ulrich, and Lothar Thiele. ”Evolutionary exploration of
e/e-architectures in automotive design.” Operations Research Proceedings 2011.
Springer Berlin Heidelberg, 2012. 361-366.
5. Moser, Irene, and Sanaz Mostaghim. ”The automotive deployment problem: A prac-
tical application for constrained multiobjective evolutionary optimisation.” Evolu-
tionary Computation (CEC), 2010 IEEE Congress on. IEEE, 2010.
6. Walla, Gregor, et al. ”An automotive specific MILP model targeting power-aware
function partitioning.” Embedded Computer Systems: Architectures, Modeling, and
Simulation (SAMOS XIV), 2014 International Conference on. IEEE, 2014