venerdì 19 luglio 2013

FPGA: Alla scoperta dello spazio soluzioni del Fitter

Con l’aumentare delle risorse delle FPGA lo spazio delle soluzioni che deve affrontare il fitter cresce ad un ritmo incredibilmente veloce, ad esempio un dispositivo Cyclone IV EP4CE22 contiene 22.320 LEs (senza contare la memoria integrata, i blocchi M9K, etc..).

Se proviamo ad adattare un design di 1 solo registro (occupante quindi 1 LE) ci troviamo davanti 22.320 differenti soluzioni al problema. Un design di 2 soli registri aumenta questo numero a 22.320 x 22.319 = 498.160.080 soluzioni

Il fitter deve quindi esplorare rapidamente un grande numero di soluzioni per trovare un buon risultato, l’esplorazione completa è in generale non fattibile e questo aiuta a spiega perché una piccola modifica in una porzione del design causa risultati diversi sulle altre parti. Non appena il fitter esegue uno spostamento diverso, si ritroverà in un’area completamente diversa dello spazio soluzioni.

I criteri principali col quale il fitter determina la qualità delle soluzioni sono le prestazioni (slack) e la facilità di instradamento (routability).

Vediamo un esempio semplificato di uno spazio soluzioni con questi criteri:

solspace

Con questo enorme numero di soluzioni come fa il fitter a convergere ad una soluzione? Quartus II utilizza un algoritmo basato sul Simulated Annealing (http://it.wikipedia.org/wiki/Simulated_Annealing) che tra le origini da un’algoritmo utilizzato per simulare il raffreddamento dei metalli.

annealing-furnace (1)

Come spiegazione semplificata inizialmente il fitter getta tutto nel dispositivo in posizioni legali che saranno completamente non instradabili e con tempistiche terribili. A questo punto la soluzione è estremamente ”calda” ed il fitter inizierà a muovere gli elementi intorno, sempre mantenendo posizioni legali, mentre la soluzione si “raffredda” ed il posizionamento migliora

solfit2

La linea verde rappresenta i movimenti del fitter nello spazio soluzioni. Il fitter cerca costantemente una punto più basso nel grafico (soluzione migliore). Nell’immagine converge ad un punto di minimo locale seppur non il minimo globale. Lo spazio soluzioni è così esteso che è praticamente impossibile trovare il minimo assoluto.

Una nota, la linea verde si muove verso l’alto, il fitter accetta quindi risultati peggiori prima di procedere. Questa è un’interessante proprietà dell’algoritmo in quanto permette di uscire dai primi minimi locali trovati per cercare soluzioni migliori. Questa proprietà è anche chiamata temperatura

Un esempio pratico da una prospettiva di posizionamento sul dispositivo potrebbe essere un design ottimale nell’angolo basso a sinistra del chip ma inizialmente posizionato in alto a destra. Muovendo un singolo elemento in basso a sinistra, il risultato totale può essere peggiore, in quanto il nodo è sempre collegato con gli altri elementi in alto a destra. Ma a mano a mano che gli altri nodi saranno spostati in basso a sinistra il fitter sarà in grado di uscire dal minimo locale per arrivare a soluzioni migliori.

La temperatura determina quanto spesso il fitter accetta risultati peggiori, inizialmente, quando il dispositivo è caldo, il fitter accetta maggiormente risultati peggiori, quando il dispositivo si raffredda accetterà meno spesso questo tipo di risultati.

In Quartus è possibile modificare parte della temperatura tramite l’impostazione Placemente Effort Multiplier ed Router Effort Multiplier sotto il menu Assignments / Settings / Fitter Settings / More Settings.

temp

Mano a mano che il valore viene incrementato il fitter procederà dal caldo al freddo più gradualmente, i tempi di compilazione però aumenteranno così come le possibilità di trovare soluzioni migliori.

Potenziali fonti di variazione nel fitting del progetto sono:
- Tutti i files di design es. VHDL, Schematici, EDIF, etc..
- Tutte le constraints nei file .sdc (il calcolo dei tempi per motivi di performance si basa su stime approssimative anziché sull’esecuzione completa di TimeQuest)
- Tutti gli assegnamenti nei file .qsf
- La versione di Quartus II
- Il sistema operativo
- Qualcosa che mi sono sicuramente scordato

La più piccola variazione (anche cambiare il nome di una rete nel design) può produrre risultati completamente diversi, ricompilando però i soliti file senza cambiare nessuna fonte di variazione si ottiene il solito risultato, per ottenere diversi risultati senza modifiche fittizie (che in realtà non servono) è possibile modificare il parametro Seed (letteralmente seme) del fitter

fittersettings

Non esiste però un valore migliore di un’altro per il Seed, uno strumento utile che ci può venire in aiuto per trovare la soluzione migliore è il Design Space Explorer accessibile tramite il menù Tools / Launch Design Space Explorer

menu

E’ richiesta l’impostazione preventiva di constraints nel progetto, ad esempio delle frequenza di clock che si vuole ottenere. Tramite TimeQuest è disponibile un’interfaccia grafica per la creazione del file .sdc necessario

Design Space Explorer permette di provare diversi semi ed esplorare soluzioni diverse del fitter in maniera automatica mantenendo la migliore in base ai parametri impostati.

AlteraDesignSpaceExplorer

L’utilizzo del programma è molto intuitivo, semplicemente premendo il pulsante Explore Space (accessibile anche dal menù Processing) in un semplice design visto nei precedenti articoli si è potuto migliorare il periodo di clock massimo da 4.438 ns (225 MHz) a 2.54 ns (394 MHz) in circa 6 minuti, design complessi possono però richiedere tempi di calcolo molto elevati.

explore

I calcoli vista la loro mole sono distribuibili su più processori in sistemi multi-core o su diverse macchine (in base alla licenza che si ha a disposizione).

Abbiamo in questo articolo visto un po’ di teoria e come sfruttare in pratica la varianza del fitter per cercare il risultato migliore tramite il tool Design Space Explorer, molto utile soprattutto quando i requisiti del progetto non sono soddisfatti per una manciata di picosecondi, qualche compilazione con variazione del seme porterà probabilmente al risultato sperato.

Nessun commento:

Posta un commento