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

not uniform itself, since the problem is highly discrete both in the search space and
in the objective space: notwithstanding the real values achievable by the objective
functions, it is observed the formation of clusters of points with a cylindrical shape.
Only some tips belong to the Pareto front and the distance between two nearby
solution points is relatively large.
Extent metric gives some insight into the evolution of the non-dominated front.
Some algorithms (MOPSO, MOSA, and APRS) span a wider range than others. This
is due to a sharper division between exploration and exploitation phase. Indeed, the
higher values of

-metric are achieved when the local front contains points which
will be dominated by the following generations. These designs may span a wider
area in the objective space resulting in a higher value of the extent metric.
The analysis of the metrics values obtained offers a deep insight into the algorithms
structure in addition to the comparison information. Efficiency assessments can be
drawn in terms of ADRS metric and number of Pareto points found. Under this per-
spective, all algorithms behave in a satisfactory manner on the proposed benchmark
problem: as remarked before, starting from 30% of the design space exploration, all
scored less than 0.02 in ADRS metric. The worst score in the achievement of Pareto
points can be taken as an indicator of the reliability of the proposed algorithms: ES
found 15.6 points which however corresponds to 86.6% coverage of the true Pareto
front. Since in real-world problems the solution set is unknown, this percentage is
clearly a good guarantee that the algorithms will reach at least a significant part of
the Pareto front.

∇

3.4.2 The Complete Optimization Problem

The problem proposed for algorithms comparison can be very useful for validating
the whole optimization process as well. The procedure followed for obtaining the
subspace of points for the comparison can be summarized as:

￿ simulate an initial set of 5,000 random points;

￿ perform statistical analysis on the sample in order to detect the most significant

variables and the most appropriate values for the remaining ones;

￿ simulate all the configurations (full factorial exploration, 9,216 points) obtained

varying the selected variables;

￿ extracting the non-dominated set.

The approximated Pareto set obtained counts 18 designs and it costs about 14,000
simulations. This procedure is similar to a manual optimization, which however in
most of the cases would have produced only a reduced number of pseudo-optimal
designs. The idea is to perform a first exploration in order to extract useful information
about the problem. The second step is the analysis of the data obtained and their
consequent exploitation through a second exploration phase, this time limited on a
restricted and affordable search space.
The sequence exploration-exploitation-exploration is exactly the same hypothe-
sized by the elitism operator of MFGA algorithm in Sect. 3.3 . However that algorithm