Optimization Algorithms for Design Space Exploration of Embedded Systems - Multi-objective Design Space Exploration of Multiprocessor SoC Architectures - page 53

The optimization algorithms implement the mathematical strategies, or heuristics ,
which are designed in order to obtain a good approximation of the actual Pareto
frontier. Real-world optimization problems are solved through rigorously proven
converging methodologies only in an extremely few cases since the high number of
input parameters and the low smoothness of objective functions limit the possible
usage of classical algorithms. Therefore a wide catalogue of heuristics have been
designed trying to achieve a good balance between exploration of the design space
and exploitation of the information carried by the best solutions found so far.
The Design of Experiments (DOE) usually precedes the optimization stage. The
aim of a DOE is to test specific configurations regardless the objectives of the op-
timization run but rather considering their pattern in the input parameters space. It
provides an a priori exploration and analysis which is of primary importance when
a statistical analysis has to be performed: for example, a reduced factorial DOE can
be the basis for a principal components analysis , since it avoids correlations among
input parameters and therefore it highlights input-output relationships. Moreover,
almost all optimization algorithms require a starting population of designs to be con-
sidered first and the DOE can provide it, eventually generating random input values
if no other preference has emerged yet.
The Post Processing analysis could represent the starting point for a new attempt
of optimization, but at the same time it conveys a deep insight into the problem
structure. Starting from a correlation matrix, for example, it is possible to recognize
if some objectives are conflicting or if they are correlated and there is no need to
involve all of them in the optimization process.
A comprehensive list of publications on this topic is out of the aim of this introduc-
tion. The description of the algorithms listed in Sect. 3.3 will include the references
necessary to understand them. The theoretical structure of multi-objective optimiza-
tion as well as classical methods are deeply investigated in the topic by Miettinen [ 10 ].
The paper by Erbas et al. [ 5 ] describes in details a MPSoC design problem solved
with genetic algorithms (GA) and it introduces important concepts like evaluation
metrics and repair mechanisms.
The innovation of the algorithms developed within the MULTICUBE project can-
not be correctly evaluated without considering the whole picture: it is mathematically
proven that it is not possible to rank optimization algorithms on the basis of their
performance over all possible problems. On the contrary, it is possible to specialize
an optimization strategy in order to solve “better” (later in this chapter the concept of
quality for a multi-objective solution set will be addressed more precisely) a defined
class of problems. The work done by MULTICUBE partners generated in a very sat-
isfactory trade-off between applicability and accuracy which is the true achievement
of the project. Not only algorithms contributed to this result and this is the reason
why this chapter also introduces some features of the software framework contain-
ing them and an anticipation of the validation procedure necessary for an industrial
knowledge transfer.
This chapter is organized as follows: Sect. 4.2 presents the problem description
and the software framework while Sect. 4.3 introduces the design space exploration
algorithms used throughout the project. Section 4.4 presents a detailed descriptions
of validation strategy while Sect. 4.5 summarizes the main content of this chapter.