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

Objectives Space Design Space

Pareto
Solutions

F 2 X 2

Search
Windows

F 1 X 1

Fig. 3.4 Search windows idea in the APRS algorithm

￿ Pareto : the starting points of each iteration of the algorithm are the current Pareto

solutions (found up to previous iteration) where the search windows are centered
on.

￿ Random search : the new configurations to be evaluated are randomly selected

within those windows.

The idea behind the algorithm is simple and it is based on iterative local search in
the neighborhood of good points: the current Pareto set (see Fig. 3.4 ). Moreover,
as for temperature in Simulated-Annealing strategies, the algorithm has a parameter
represented by the search-window size that reduces the dynamism of the algorithm
during the optimization life-time. In particular, the search-window size centered on
each Pareto point is reduced whenever no better solutions are found in the iteration.
More in detail, the general structure of the algorithm is the following:

1. Creation of an initial set of solutions selected within the entire DS by using a DoE
2. Initial solutions evaluation ( S )
3. Identification of the Pareto solutions ( P = ParetoFilter ( S ))

4. While the termination condition is not met
(a) Use the Pareto set as initial set for each iteration S< P

−

P )
i) Randomly select a configuration within the reduced DS delimited by the
search window centered on the pareto point ( W ( p ))
ii) Evaluate the selected configuration s ( S

(b) For each point in the Pareto set ( p ∈

s )
(c) If the Pareto set is not changed from the previous iteration (i.e. if P

= S +

==

| W |=| W |∗ α )
(d) Otherwise, Identification of the new Pareto set ( P = ParetoFilter ( S ))

ParetoFilter ( S )), reduce the search window (

The algorithm exposes three parameters, the initial set | S | size, the initial size of

the windows and the windows reduction coefficient α . APRS was completely

designed by POLIMI for the MULTICUBE project and has been implemented in
Multicube Explorer.

| W |