Sviluppo di una metodologia per la riconfigurabilità dinamica
-
Upload
hope-walker -
Category
Documents
-
view
22 -
download
0
description
Transcript of Sviluppo di una metodologia per la riconfigurabilità dinamica
Politecnico di MilanoPolitecnico 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
5 Settembre 2005 Gerardo Gallucci 2
SommarioSommario
• 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 3
Riconfigurabilità DinamicaRiconfigurabilità Dinamica
• FPGA
• Logica Riprogrammabile
• Scrittura del codice
• Sintesi
• Implementazione
• Infinite riconfigurazioni
• Tempi di riconfigurazione interna molto ridotti
5 Settembre 2005 Gerardo Gallucci 4
Earendil: visione d'insiemeEarendil: visione d'insieme
• Earendil: framework che realizza l'implementazione dei meccanismi di riconfigurabilità dinamica.
5 Settembre 2005 Gerardo Gallucci 5
Introduzione a SalomoneIntroduzione a Salomone
Grafo ricevuto
da Astinus
Gli SCONO schedulati sono
passati a Caronte
Costruzione TCG
Algoritmo ADJ
Schedulazione ed Allocazione
5 Settembre 2005 Gerardo Gallucci 6
Thread Conflict GraphThread 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 7
Graph Coloring ProblemGraph 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 8
Same Colored NOdesSame 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 9
Black BoxBlack Box
• Livello Salomone: Definizione SCONO
• Livello EDK: Definizione BB
• Livello FPGA: Architettura Caronte
5 Settembre 2005 Gerardo Gallucci 10
Scheduling & Allocation Scheduling & Allocation AlgorithmAlgorithm
• 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 11
Risultato S&A AlgorithmRisultato S&A Algorithm
• Analizzando tutti i nodi del TDG si ottiene:
• SCONO Schedulati e nodi pronti per essere allocati
5 Settembre 2005 Gerardo Gallucci 12
Conclusioni e Sviluppi futuriConclusioni 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 13
FINE PRESENTAZIONE