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

3.4 Validation Strategies

The so called no-free-lunch theorem for optimization [ 18 ] is a rigorous mathematical
theorem which states the impossibility of ranking algorithms on the basis of their
performance: averaging on all possible problems, every algorithm will obtain results
exactly equal to all the others. A direct corollary is that if one algorithm appears better
than another one in solving a specific problem, there must exist another problem in
which the original algorithm appears worse than the other.
This theorem implies that an optimization algorithm is as important as the valida-
tion strategy which may reveal its ability in solving a specific set of problems. This
issue is not a mere academic question, but it has relevant effects on the industrial
exploitation of the achievement obtained. It is of primarily importance to build confi-
dence on the proposed algorithmic strategies and to prove their robustness. This is the
main achievement of the researches carried on by the MULTICUBE project, whose
partners agreed on the need of a validation step in order to transfer the (possibly
academic) high quality knowledge to the industrial world.
This section focuses on the first two steps performed in this direction within the
project. The first one consists in showing that all the algorithm described in Sect. 3.3
can solve a benchmark problem of SoC design in a satisfactory manner. The second
step is to show the advantages of an automatic optimization process with respect
to a traditional approach. The combination of these two results can guarantee the
reliability of the proposed approach. At the same time, the validation process must
be intended as an iterative process which follows but at the same time precede the
development of new optimization strategies.

3.4.1 Algorithm Comparison

The problem selected as benchmark for the algorithms validation is based on the
SP2 low-power processor use case delivered by STM-China described in Chap. 8. In
this paragraph, we compare the previously introduced algorithms to identify the most
suitable for the architecture under consideration. The executable model for the design
space exploration is the sp2sim simulator, which models the SP2 microprocessor
design. The benchmark application selected is the 164.gzip application, based on the
popular gzip application.
The design space consists of 11 configuration parameters, 7 system metrics
and 3 objectives. The configuration parameters are grouped in three categories:
out-of-order execution parameters, cache system parameters and branch prediction
parameters, as shown in Table 3.1 . The system metrics are grouped in three cate-
gories: performance, power dissipation and area occupation metrics, as shown in
Table 3.2 . The three objectives to be minimized have been selected from each one
of the metrics group: total_cycle, power_dissipation and area.
In order to compute optimization metrics that provide a reasonable measure of
quality of the algorithms, it is necessary to compare the Pareto fronts obtained by