Il processo di progettazione di un sistema embedded può essere con- siderato come un problema di ottimizzazione multi-obiettivo che cerca di individuare una soluzione ottimale per quanto riguarda gli obiettivi come il tempo, l’area, la potenza e i costi. Al fine di individuare le implementazioni ottimale è necessario valutare e considerare una serie di varianti in quello che viene comunemente chiamato con il nome di design space. Questo com- pito, noto come Design Space Exploration (DSE) [55] [56], risulta di fon- damentale importanza per raggiungere a quella che è l’implementazioni ottimale.
3.5.1 Ottimizzazione Multi-Obiettivo
Il problema di identificare la soluzione ottimale può essere considerato come un problema di ottimizzazione multi-obiettivo. Tale problema può essere formalizzato nel seguente modo:
dove f(x) definisce un vettore avente k > 2 funzioni obiettivo contra- stanti fi: Rn→ R, i = 1..k.
Il vettore di decisione x=(x1,...,xn)T appartiene alla regione di accetta-
zione S ⊂ Rn(vedi figura 3.3 ).
X3 X1 X2 f2 f1 Regione Valida Regione Possibile x f(x) Vincolo
Figura 3.3: Esempio di un’ottimizzazione multi-obiettivo
A causa della presenza di vincoli di sistema il vettore di decisione po- trebbe non essere valido. Quindi possono esistere un insieme di vincoli bi
come superficie massima, tempo di risposta massimo, o il consumo di po- tenza massima. Tali vincoli possono essere raggruppate in un vettore b = (b1,..., bn)T, definendo un insieme di disuguaglianze.
x6 b (3.4)
Di seguito sono riportati le possibili relazioni tra due vettori di decisioni x1e x2:
• x1 x2(dominante) se f (x1) < f (x2)
• x1 x2(debole dominanza) se f (x1) 6 f (x2)
CAPITOLO 3. CONCETTI TECNOLOGICI 34
Come affermato in precedenza, non è possibile trovare una soluzione unica che ottimizzi contemporaneamente tutti gli obiettivi, per tale pro- blema si utilizza il principio di Pareto. Pareto afferma che: un vettore x1 è
un punto chiamato ”Pareto ottimale” se non esiste un altro vettore x2 tale
che x2 x1. L’insieme dei punti “Pareto ottimale“ costituisce la frontiera di
Pareto ovvero quell’insieme di soluzioni dove ogni componente non può essere migliorato senza deteriorare almeno un degli altri componenti.
Matematicamente, tutti i punti di ”Pareto ottimali” sono soluzioni ugual- mente accettabili. La dominanza di Pareto per un obiettivo coincide con il classico approccio di ottimizzazione e definisce un gruppo di soluzioni efficienti. Frontiera di Pareto
Area
Tempo
X
3Vincolo
Vincolo
X
4X
2X
5X
6X
1Figura 3.4: Esempio di design space
punto di “Pareto ottimale” e domina x2, x3, e x4 in altre parole x1 x2, x1
x3, x1 x4. Il punto x3è un punto indifferente a x4in altre parole x3∼ x4. Il punto x2è un punto debolmente dominante a x4in altre parole x2 x4. I
punti x5e x6risultano essere invalidi poiché non rispettano i vincoli.
3.5.2 Popolazione del Design Space
Nel raccogliere nuovi dati per la modellazione multi-obiettivo al fine di popolare il design space, si dovrebbe prestare attenzione ai seguenti criteri:
• ottenere più informazioni da un minor numero di esperimenti; • raccogliere solo le informazioni che sono veramente necessarie.
Uno degli strumenti più utilizzati per ottenere le informazioni è Design Of Experiments (DOE) [57] [58]. Tale strumento mostra i significati stati- stici che, un particolare fattore, ha su una variabile analizzata. DOE è una strategia per acquisire conoscenze empiriche, ossia la conoscenza sulla base dell’analisi dei dati sperimentali e non su modelli teorici. Esso può essere applicato nell’ambito delle indagini su un fenomeno, al fine di ottenerne la comprensione o migliorarne le prestazioni.
Costruire un design significa scegliere accuratamente un piccolo numero di esperimenti che devono essere eseguiti in condizioni controllate. Ci sono quattro fasi nella costruzione di un design:
• definire l’obiettivo delle indagini: ad esempio, capire meglio o risol- vere importanti variabili o trovare le condizioni ottimali;
• definire le variabili che saranno controllate durante l’esperimento (va- riabili di progetto), ed i loro livelli o intervalli di variazione;
• definire le variabili che saranno misurate per descrivere il risultato dell’esperimento (variabili di risposta), ed esaminare la loro precisio- ne;
CAPITOLO 3. CONCETTI TECNOLOGICI 36
• scegliere tra i modelli standard quello che è compatibile con l’obiet- tivo, il numero di variabili di progetto e la precisione delle misure, considerando i costi.
Un’attenta selezione del campione aumenta la possibilità di estrarre informazioni utili dai dati.
Sono disponibili diversi modi di selezione dei punti all’interno di un design space, la loro scelta è determinata dagli obiettivi della sperimenta- zione e lo stato attuale delle conoscenze circa l’ambiente sperimentale. I principali tipi sono [59] [60]:
X3 X2
X1
(a) Full Factorial
X3 X2 X1 (b) Fractional Factorial X3 X2 X1 (c) Central Composite X3 X2 X1 (d) Box Behnken
Full Factorial Studia gli effetti delle variabili di progetto indipendente-
mente dalle altre (vedi figura 3.5(a)).
Fractional Factorial Il numero delle variabili di progetto può essere gran-
de, l’obiettivo è di scoprire con un piccolo numero di esperimenti le variabili che devono essere ulteriormente analizzate (vedi figura 3.5(b)).
Central Composite Trova il livello ottimale delle variabili di progetto con
l’aggiunta di alcuni esperimenti aggiunti al full factorial design. Tut- te le variabili di progetto devono variare continuamente (vedi figura 3.5(c)).
Box Behnken Un’alternativa al central composite design è la tipologia Box
Behnk, utilizzata quando la risposta ottimale non si trova agli estremi della regione sperimentale o non benefica dei risultati estrapolati da fractional design. Tutte le variabili di progetto deve variare continua- mente (vedi figura 3.5(d)).
DOE risulta essere un utile complemento alla analisi multi-obiettivo dei dati poiché genera un insieme di dati catalogabili in tabelle strutturate, os- sia tabelle di dati che contengono una quantità importante di dati relativi alle possibili soluzioni adottabili. Questa struttura sarà poi utilizzata co- me base per la modellazione multi-obiettivo, che garantirà modelli stabili e robusti.