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

same time the number of evaluated points must be kept low and the algorithm has to
converge rapidly to the Pareto set.
Elitism in MOGA-II works in this direction. The elite set usually contains a few
points in early stages of the optimization. Moreover, these points belong to the last
generation with a high probability. Hence only a fraction of them will enter the next
parents population promoting exploration. As long as new generations are created,
the elite set grows and the probability of finding out a new elite point decreases.
Therefore in the updated population there will be many points coming from the elite
set exploiting their features.
In order to save simulation time, steady evolution was preferred against the clas-
sical generational evolution in MOGA-II. In almost any industrial application, the
computational time spent in evaluating a point is much larger than the time employed
by the optimization algorithm to prepare and request a new evaluation. A genera-
tional algorithm would keep a significant part of computational resources idle (in a
cluster or grid systems), since before every generation is created, the algorithm needs
to get the results of the evaluation of all the individuals of the previous generation.
Within a steady evolution, the child point replaces its parent immediately. Every
time an evaluation ends, a new one is requested choosing randomly a parent from
the actual population and applying the chosen operators. The elitism procedure is
scheduled with the same frequency as in the case of a generational evolution, but it
can be performed while some points are still being evaluated, using the information
stored so far. This introduces a little delay in the propagation of the information, but
it prevents delays in the computational grid or cluster system. The negative effects of
this issue increase with the dimension of the population, but decrease as the number
of requested generations increases. This algorithm is proprietary of ESTECO and it
was provided by modeFRONTIER from early releases.

3.3.2 Enhanced Algorithms

Literature reports a continuous improvement of available methods since multi-
objective optimization is a research field constantly pressed by new applications.
New applications require new and better answers. In this section we considered as
enhanced algorithms the implementations of well known algorithms which have
been rewritten within the MULTICUBE project in order to better adapt to the SoC
design problem. Indeed, specific operators have been designed for treating categori-
cal variables and a careful attention has been addressed to the problem of optimizing
also the computing resources needed for design evaluation.

3.3.2.1 Enhanced-MOSA

The Simulated Annealing (SA) method for optimization was introduced by Kirk-
patrick [ 6 ], on the basis of a thermo-dynamical analogy.
The evolution of such a system is controlled by an external parameter called
temperature. A related energy can be assigned to every possible configuration of the