Sviluppo di una metodologia per la riconfigurabilità dinamica

13
Politecnico di Milano 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

description

Relatore: Prof. Fabrizio FERRANDI Correlatore: Ing. Marco D. SANTAMBROGIO. Sviluppo di una metodologia per la riconfigurabilità dinamica. Tesi di Laurea di: Gerardo Gallucci. A.A. 2003/2004. Sommario. Riconfigurabilità dinamica Earendil: visione d'insieme - PowerPoint PPT Presentation

Transcript of Sviluppo di una metodologia per la riconfigurabilità dinamica

Page 1: 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

Page 2: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 3: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 4: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

5 Settembre 2005 Gerardo Gallucci 4

Earendil: visione d'insiemeEarendil: visione d'insieme

• Earendil: framework che realizza l'implementazione dei meccanismi di riconfigurabilità dinamica.

Page 5: Sviluppo  di una metodologia per la 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

Page 6: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 7: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 8: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 9: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

5 Settembre 2005 Gerardo Gallucci 9

Black BoxBlack Box

• Livello Salomone: Definizione SCONO

• Livello EDK: Definizione BB

• Livello FPGA: Architettura Caronte

Page 10: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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.

Page 11: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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

Page 12: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

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.

Page 13: Sviluppo  di una metodologia per la riconfigurabilità  dinamica

5 Settembre 2005 Gerardo Gallucci 13

FINE PRESENTAZIONE