Politecnico di Milano
UNA METODOLOGIA PER LA STIMA
DELLE RISORSE HARDWARE
IN ARCHITETTURE RICONFIGURABILI
Relatore: Prof. Fabrizio FERRANDI
Correlatore: Ing. Marco Domenico SANTAMBROGIO
Tesina di Laurea di
Marco MAGNONE
Matr. 640006
Sommario
Introduzione
Sistemi dedicati
Obiettivi
Framework
PandA
Flusso di sviluppo
Estrazione delle metriche
PDG
Vettore di caratterizzazione
Implementazione
Parametrizzazione delle metriche
Struttura di CLB e slice
Test e risultati
Esempi
Risultati
Conclusioni e sviluppi futuri
DRESD - PandA Project
-2-
Introduzione
Introduzione
Sistemi dedicati
Obiettivi
Framework
PandA
Flusso di sviluppo
Estrazione delle metriche
PDG
Vettore di caratterizzazione
Implementazione delle metriche
Parametrizzazione delle metriche
Struttura di CLB e slice
Test e risultati
Esempi
Risultati
Conclusioni e sviluppi futuri
DRESD - PandA Project
-3-
Sistemi dedicati
Stato:
• Generazione della descrizione
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG.
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
• Creazione del modello
Descrizione a livello di sistema
Analisi
Valutazione del progetto ed esplorazione
dello spazio delle soluzioni sulla base di
prestazioni, dimensioni, consumo e costo
Verifica
Partizionamento HW/SW
Descrizione HW
Descrizione SW
Sintesi HW
Generazione SW
Minimizzazione di una cifra di
merito rispettando i vincoli di
progetto. E’ necessario disporre
di strumenti di stima della
qualità del sistema per la parte
hardware e quella software
Sintesi Interfacce
Tecniche per la sincronizzazione tra hardware e
software (scambi di segnale, schemi in interrupt..)
Integrazione + Valutazione vincoli
Verifica del comportamento del
sistema da un punto di vista
funzionale e di timing sia per
validare la specifica iniziale sia il
partizionamento introdotto
Simulazione + Validazione
Sistema Integrato
DRESD - PandA Project
-4-
Obiettivi
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Ricerca di metriche che permettano una stima affidabile dell’area
occupata e del tempo di esecuzione dei singoli componenti in
un’architettura riconfigurabile utilizzando descrizioni semi formali
quali PDG e SDG
Analisi di varie strutture dati (PDG e FGPDG) e validazione dei
risultati tramite flusso automatico con l’utilizzo di EDK
SVANTAGGI DELLE METRICHE PRESENTI IN
LETTERATURA
• Limitazione a funzioni combinatorie ad un solo ingresso (Nemani e Najm)
• Orientamento ad un solo dispositivo obiettivo, quindi in caso di differente
architettura è necessario rifare tutto (Kulkarni, Najjar, Rinkel)
• Errori medi di stima alti (intorno al 20-25%)
• Sostanziale dipendenza tra implementazione delle metriche e dispositivo
obiettivo scelto
DRESD - PandA Project
-5-
Framework
Introduzione
Sistemi dedicati
Obiettivi
Framework
PandA
Flusso di sviluppo
Estrazione delle metriche
PDG
Vettore di caratterizzazione
Implementazione delle metriche
Parametrizzazione delle metriche
Struttura di CLB e slice
Test e risultati
Esempi
Risultati
Conclusioni e sviluppi futuri
DRESD - PandA Project
-6-
PandA
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
•
Progetto nato all’interno del DEI del Politecnico di Milano che mira a
sviluppare un framework per la progettazione di sistemi dedicati
•
Struttura del progetto modulare, composta da sottoprogetti che
interagiscono tra di loro, raggruppati in varie categorie:
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
1. Livello di gestione di descrizioni comportamentali
2. Livello di gestione di grafi e descrizioni strutturali
3. Livello di sintesi ad alto livello
•
La struttura interna si chiama IR: tree ed è un grafo i cui nodi sono
istanze di classi C++ appartenenti ad un’unica gerarchia, mentre gli
archi sono implicitamente definiti come riferimenti tra coppie di nodi. E’
composto da due sotto-moduli: IR: graph e IR: circuit
Le metriche introdotte verranno implementate all’interno di PandA
considerando il sotto-modulo IR: graph
DRESD - PandA Project
-7-
Flusso di sviluppo
Stato:
Descrizione
ad alto livello
PandA GCC
Parser
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
IR: graph
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Metriche
IR: tree
IR: circuit
bitstream
EDK System
Creator
IP CoreGen
Tool che collega automaticamente il
generico IP-Core e un dato sistema
con architettura EDK-compatibile
DRESD - PandA Project
-8-
Partizionamento
HW/SW
VHDL
C
Tool che crea automaticamente un core
compatibile con EDK partendo da una
generica funzionalità VHDL
Estrazione delle metriche
Introduzione
Sistemi dedicati
Obiettivi
Framework
PandA
Flusso di sviluppo
Estrazione delle metriche
PDG
Vettore di caratterizzazione
Implementazione delle metriche
Parametrizzazione delle metriche
Struttura di CLB e slice
Test e risultati
Esempi
Risultati
Conclusioni e sviluppi futuri
DRESD - PandA Project
-9-
PDG
Stato:
ENTRY
Sa
Sb Sc
S: for(a=ref; a<b; a++)
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
S1: ..........;
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
P
Sa
.:: Framework
> PandA
> Flusso di
sviluppo
Archi di dipendenza di controllo
a,li,o
T
X,Y,Z
Archi di dipendenza dal flusso di dati
X
Variabile interessata alla dipendenza
a,lc,a
a,lc,-
R1
Y
a,lc,o
S1
}
P: ..........;
a,li,-
Sb
{
Sc
Z
li
loop indipendent
lc
loop carried
do
o
a
-
def-order dependency
output dependency
anti-dependency
nessuna delle tre precedenti
R1
DRESD - PandA Project
- 10 -
Nodo regione
Vettore di caratterizzazione
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Il processo di stima esplora progressivamente l’intero grafo per arrivare a
determinare le caratteristiche dell’intera applicazione.
Si considera il PDG di ogni task presente nell’applicazione e si compila una
lista di tutti i tipi di operazioni presenti, determinando un vettore di
caratterizzazione del tipo:
Unità funzionale
Coefficiente
Sommatori – Sottrattori - Contatori
C1-C4
Array Multiplier
C5-C6
Comparatori
C7-C14
Moltiplicatori - Moltiplicatori per costante
C15-C17
Operazioni Logiche
C28-C33
MUX - Shifter
C34-C38
DRESD - PandA Project
- 11 -
Implementazione delle metriche
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
Una volta che il PDG è stimato, si considerano le dipendenze di controllo,
quali loop o branch, e si costruiscono dei macro-nodi fondendo insieme due o
piu’ nodi, e si ripete il procedimento per i nuovi nodi.
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
ENTRY
S
T
S1
ENTRY
ENTRY
S3
T
F
S2
S3
S
S1
T
F
S2
S3
S
S1
F
S2
Allo stesso modo si valutano gli SDG, cioè considerando i singoli PDG come
macro-nodi e valutando le dipendenze che intercorrono tra essi (esecuzione
parallela, sequenziale..)
DRESD - PandA Project
- 12 -
Parametrizzazione delle metriche
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
L’area e il ritardo di propagazione di ogni unità funzionale sono stati ottenuti
attraverso una serie di passi:
1.
Generazione del learning-set
2.
Sintesi del learning-set
3.
Analisi del rapporto di sintesi
4.
Estrazione della metrica dall’analisi del rapporto di sintesi
5.
Validazione della metrica
Per rendere le metriche adattabili ad un certo numero di dispositivi, si sono introdotti dei
parametri, S e L, indicanti rispettivamente il numero di slice e di LUT all’interno di una singola
CLB. Quindi prima di applicare le metriche è necessario ottenere il valore di tali costanti, in
base all’architettura di volta in volta presa in considerazione.
Xilinx FPGA
Virtex II Pro – Virtex II – Virtex IV
Virtex V
Virtex
Spartan 3/3L – Spartan 3E
DRESD - PandA Project
- 13 -
S
L
4
2
2
4
8
8
4
8
Struttura di CLB e slice
Stato:
L’architettura obiettivo di questo lavoro è la Virtex II Pro di Xilinx, che ha all’interno di ogni
CLB 4 slice (S=4) e 4x2=8 LUT (L=8)
COUT
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
Slice
X1Y1
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
LUT
Slice
Switch
Matrix
COUT
G
FF/
CY
X1Y0
SHIFT
Slice
latch
CIN
X0Y1
LUT
F
Slice
CY
FF/
latch
X0Y0
CIN
Ogni CLB è composta da:
•
4 slice
•
2 buffer 3-state
DRESD - PandA Project
Ogni slice è composta da:
• 2 generatori di funzioni logiche (LUT a 4 ingressi)
• 2 elementi di memorizzazione funzionanti in modalità
sincrona (FF) o asincrona (latch)
- 14 -
Test e risultati
Introduzione
Sistemi dedicati
Obiettivi
Framework
PandA
Flusso di sviluppo
Estrazione delle metriche
PDG
Vettore di caratterizzazione
Implementazione delle metriche
Parametrizzazione delle metriche
Struttura di CLB e slice
Test e risultati
Esempi
Risultati
Conclusioni e sviluppi futuri
DRESD - PandA Project
- 15 -
Esempi (1): unità funzionali
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Alcuni esempi di metriche ottenute per la SINGOLA unità funzionale, per le famiglie Virtex II e
Spartan, per le quali il potere espressivo di una CLB equivale ad un byte:
• Sommatori – Sottrattori
CLB=N Slice=S*N LUT=L*N
N dimensione in byte degli addendi
• Moltiplicatori
CLB=
N2/2
[(N1=1), V N2]
N1*N2
[(1<N1<16), V N2] V [N1>16, N2>50]
(N1+N2)
4
2
[(N1>16), (1<N2<50)]
N1, N2 dimensione in byte delle due variabili da moltiplicare
Quindi per l’intero PDG si avranno le seguenti metriche per i sommatori e moltiplicatori:
ASomm[CLB] = C1*C2
C1 num. Sommatori, C2 dim.media addendi
AMol1[CLB] = C15*C16*0.5
C15 num. Molt. con N1=1, C16 dim.media N2
AMol2[CLB] = C17*C18*C19
AMol3[CLB] = C20*(C21+C22)*0.25
AMol4[CLB] = C23*C24*C25
DRESD - PandA Project
- 16 -
Esempi (2): unità funzionali
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Quindi l’area espressa in CLB dell’intero PDG è pari a:
A[CLB] = ASomm + ACont + AArrMul + AComp1 + AComp2 + AComp3 + AComp4 + AMol1 + AMol2+ +
AMol3 + AMol4 + AMolK + AOpLog1 + AOpLog2 + AOpLog3 + AMux
Per quanto riguarda il timing, si è proceduto nello stesso modo e si è ottenuto ad esempio
per gli addizionatori:
TAdd[s] = NumAdd * [(LungMediaAddendo*dr)+dc]
dr e dc sono rispettivamente il ripple line delay e il combinatorial delay e sono ricavabili dal
data sheet della scheda
Quindi il ritardo di propagazione è dato dalla somma dei singoli contributi, pesati da un
fattore empirico 1.5 necessario per tenere in considerazione l’influenza del routing e dal
fattore (1/LP) necessario per pesare la somma dei singoli contributi in relazione alla
struttura del task.
T[s] = (1.5/LP) (TAdd + TMol + TMux + TLog)
Una volta che il PDG è stimato, costituisce un nodo, quindi si considerano le dipendenze
di controllo, si formano i macro-nodi e si combinano le stime di area e tempo. Ad esempio
nel caso di nodi eseguiti in PARALLELO con area (A1,A2) e timing (T1,T2), il macro nodo
risultante ha:
A = A1 + A2
T = MAX (T1,T2)
DRESD - PandA Project
- 17 -
Risultati (1): unità funzionali
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
Errore medio stima
FF sempre nullo
tranne Molt. e MUX
Errore
medio %
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Errore medio stima
tempo di esecuzione al
di sotto del 5%
(problema wiring)
Errore medio
stima CLB
intorno al 2%
Stima
CLB Stima
FF
Stima
tempo
DRESD - PandA Project
- 18 -
Risultati (2): il filtro FIR
Stato:
Il sorgente C del filtro è costituito dalla funzione clear, che pone zeri nella delay line e dalla
funzione fir-basic, che immagazzina i campioni di ingresso e calcola i campioni di uscita.
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
Errore medio
stima CLB tra
il 12% e il 18%
Area [CLB]
100
95
.:: Framework
> PandA
> Flusso di
sviluppo
90
85
80
75
Stima
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
Implementazione
Errore
medio stima
temporale 7%
Frequenza
[Mhz]
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
Stima
Implementazione
DRESD - PandA Project
- 19 -
Conclusioni e sviluppi futuri
Stato:
.:: Introduzione
> Sistemi
dedicati
> Obiettivi
.:: Framework
> PandA
> Flusso di
sviluppo
.:: Estrazione
delle metriche
> PDG
> Vettore di
caratterizzaz.
> Implementaz.
> Parametr.
> CLB e slice
.:: Test e
risultati
> Esempi
> Risultati
> Conclusioni e
sviluppi futuri
• Errori medi di stima per le singole unità funzionali soddisfacenti, intorno
al 2% per le CLB e al 5% per il tempo di esecuzione
• Facilità nell’adattare le metriche ad architetture differenti
• Errori medi di stima per benchmark complessi tra il 12% e il 18%
• Problemi riscontrati con il wiring delay
In futuro..
• Maggiore utilizzo dei PDG a granularità fine
• Integrazione automatica nel flusso di sviluppo delle stime ottenute
• Maggiore indipendenza dai coefficienti di delay nelle stime del tempo di
esecuzione
DRESD - PandA Project
- 20 -