Politecnico di Milano
Sviluppo di una metodologia per la
riconfigurabilità dinamica
Relatore:
Prof. Fabrizio FERRANDI
Correlatore: Ing. Marco D. SANTAMBROGIO
Tesi di Laurea di:
Gerardo Gallucci
A.A. 2003/2004
Sommario
• Riconfigurabilità dinamica
• Earendil: visione d'insieme
• Introduzione a Salomone
• Costruzione TCG
• Algoritmo ADJ
• Schedulazione ed Allocazione
• Conclusioni e Sviluppi futuri
5 Settembre 2005
Gerardo Gallucci
2
Riconfigurabilità Dinamica
• FPGA
• Logica Riprogrammabile
• Scrittura del codice
• Sintesi
• Implementazione
• Infinite riconfigurazioni
• Tempi di
riconfigurazione interna
molto ridotti
5 Settembre 2005
Gerardo Gallucci
3
Earendil: visione d'insieme
• Earendil: framework che realizza l'implementazione
dei meccanismi di riconfigurabilità dinamica.
5 Settembre 2005
Gerardo Gallucci
4
Introduzione a Salomone
Costruzione
TCG
Grafo
ricevuto
da
Astinus
Algoritmo
ADJ
Gli SCONO
schedulati sono
passati a Caronte
5 Settembre 2005
Schedulazione
ed Allocazione
Gerardo Gallucci
5
Thread Conflict Graph
• Conflict Graph: grafo dei conflitti ottenuto mediante
informazioni fornite da ASAP e Mobilità
• Minimum Conflict Graph:
CG con minor numero di archi
• Il TCG è ottenuto dall'unione
del TDG iniziale con
il MCG trovato
• Graph Coloring Problem
5 Settembre 2005
Gerardo Gallucci
6
Graph Coloring Problem
• GCP: dato un grafo, per ogni nodo bisogna trovare
un colore tale che nessuno dei nodi adiacenti abbia
lo stesso colore
• Algoritmo ADJ
5 Settembre 2005
Gerardo Gallucci
7
Same Colored NOdes
• SCONO: insieme di nodi identificati dallo stesso colore
• Colore = Blackbox : Porzione di FPGA
• Meno Colori = Minore spazio = Maggiori prestazioni
5 Settembre 2005
Gerardo Gallucci
8
Black Box
• Livello Salomone:
Definizione SCONO
• Livello EDK:
Definizione BB
• Livello FPGA:
Architettura Caronte
5 Settembre 2005
Gerardo Gallucci
9
Scheduling & Allocation
Algorithm
• Devono essere rispettate le Dipendenze indicate dal
TDG, ma questo implica decremento di Performance
Temporali (si deve attendere il completamento del
nodo precedente).
• S&A Algorithm si occupa
di ordinare i nodi
appartenenti allo
stesso SCONO,
rispettando il TDG
e il Critical Path
dello stesso.
5 Settembre 2005
Gerardo Gallucci
10
Risultato S&A Algorithm
• Analizzando tutti i nodi del TDG si ottiene:
• SCONO Schedulati e nodi pronti per essere allocati
5 Settembre 2005
Gerardo Gallucci
11
Conclusioni e Sviluppi futuri
• Caronte può effettivamente iniziare la sua
computazione, occuparsi degli SCONO schedulati
passati dall'Algoritmo S&A di Salomone, e mapparli
sulla FPGA.
• Possibili sviluppi:
• Implementare un nuovo algoritmo di colorazione per la
computazione statica degli SCONO;
• Ottimizzare l’algoritmo ADJ per riuscire a decrementare la
sua percentuale di errore, e senza peggiorare troppo le sue
performance temporali;
• Migliorare l’algoritmo del CGG.
5 Settembre 2005
Gerardo Gallucci
12
FINE PRESENTAZIONE
5 Settembre 2005
Gerardo Gallucci
13