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

system. When an initial configuration is perturbed, the difference in energy between
the two states is responsible for the evolution of the system: if the new state is
favorable, i.e. if it decreases the energy, then the new configuration is accepted. If
this is not the case, the new state is accepted or rejected according to a probability
distribution derived by Boltzmann. This distribution is a function of the temperature
and when the temperature is high, the probability of accepting an unfavorable state
is larger (see Metropolis et al. [ 9 ]).
The energy for the MOSA algorithm is (a suitable function of) the non-dominated
ranking already described for NSGA-II. Hence a new point is always accepted if
it is non-dominated by its parent. It will be also accepted in the opposite situation
depending on a temperature-based probability distribution.
Temperature is simply a parameter, initially user-defined, which evolves during
the optimization. MOSA starts with a hot phase accepting many points in order to
explore the design space. Afterwards, a cold phase, during which only the best points
survive, represents the exploitation part of the algorithm.
The creation of a child configuration from a parent one in the original formulation
of the algorithm is a directional perturbation. A random direction versor represents
the direction of the perturbation, while its length is predicted by a schedule similar
to the temperature one: starting from a specified upper bound, the value decreases
during the hot phase and it reaches the imposed lower bound in the cold phase. If the
perturbation vector brings the point out of variables space boundaries, a bouncing
routine will maintain the feasibility of the samples. This procedure also helps in
differentiating and enhancing the exploration and the exploitation capabilities of the
algorithm.
The concept of direction has no meaning working with categorical variables. The
enhanced version of MOSA takes in account this problem keeping at the same time
the idea of a tunable perturbation. Every categorical variable at each iteration has a
probability to change its value depending on a law similar to the one applied to the
temperature and perturbation length. If the value has to be changed, a new value is
chosen randomly from the available list.
A lifespan counter is introduced in order to compensate for the uncontrolled ran-
domness in the search for the best values for categorical variables. Especially during
the hot phase there could be sequences of parents and children moving towards dom-
inated regions of the objective space because of the Metropolis acceptance criterion.
If the number of subsequent unwanted increasing in energy exceeds a threshold,
Enhanced-MOSA replaces the child with its better-fitting parent.
A steady state evolution is a second enhancement of the algorithm. The procedure
is very similar to the evolution implemented in MOGA-II with the obvious change of
the updating schedule: there is no elite set to be updated, but instead Enhanced-MOSA
changes the value of the temperature, the perturbation length and the probability of
replacement for categorical variables.
The standard implementation of MOSA is available in modeFRONTIER from
early releases and it has also been implemented in Multicube Explorer. The described
enhancements were developed for the MULTICUBE project and were implemented
in modeFRONTIER.