3DD 1e Salomone
21
Politecnico di Milano Politecnico di Milano Salomone - Allocazione e Scheduling per la progettazione di sistemi embedded riconfigurabili- 27 Luglio, 2006 27 Luglio, 2006 Milano Milano Marco Maggioni – Matricola 653729 - [email protected]
Transcript of 3DD 1e Salomone
Politecnico di MilanoPolitecnico di Milano
Salomone- Allocazione e Scheduling per la progettazione di sistemi
embedded riconfigurabili-
27 Luglio, 200627 Luglio, 2006MilanoMilano
Marco Maggioni – Matricola 653729 - [email protected]
DRESD ProjectDRESD Project
OutlineOutline
ObiettiviAllocazione e OrdinamentoTest su specifiche reali
Riconfigurazione dinamicaAllocazione e Ordinamento
Progettazione di sistemi riconfigurabili
Analisi specificaValidazione e sintesi su FPGA
SalomoneGrafo dei conflittiColorazione del grafoOrdinamento
Flusso per specifiche reali
PandAPartizionamentoCalcolo latenze
BenchmarksBB - JpegRicorrenze - Jpeg
Conclusioni
Sviluppi futuri
DRESD ProjectDRESD Project
ObiettiviObiettivi
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Sviluppo di uno strumento per la risoluzione dei problemi di allocazione (placement) e ordinamento (scheduling) inerenti all’esecuzione di un sistema dinamicamente riconfigurabile.
Creazione di un flusso automatico di lavoro per fornire in ingresso a tale strumento specifiche di sistema reali.
DRESD ProjectDRESD Project
Riconfigurazione DinamicaRiconfigurazione Dinamica
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Logiche riconfigurabili = circuiti in grado di cambiare la loro funzionalità
Partial + Dynamic
RiconfigurazioneParzialeDinamica
DRESD ProjectDRESD Project
Allocazione e OrdinamentoAllocazione e Ordinamento
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Problemi dell’esecuzione riconfigurabile…
Le configurazioni saranno eseguite…
…su quale parte dell’area...?
…con quale ordine…?
Allocazione
Ordinamento
DRESD ProjectDRESD Project
Progettazione di sistemi Progettazione di sistemi riconfigurabili riconfigurabili
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Metodologia… dalla specifica al sistema implementato su logica riconfigurabile…
SpecificationDynamic
Reconfiguration
TreeStructure
Graph
Partitioning
Analysis
PlacementScheduling
Salomone
Validation
Simulation
Modules Description
Synthesis
Synthesis
DRESD ProjectDRESD Project
Fase di analisi della specifica…
» Compilazione e produzione della struttura tree
» Costruzione del grafo DFG a livello di statement
» Partizionamento del sistema e produzione del grafo delle partizioni o TDG
Fase di analisi Fase di analisi
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
DRESD ProjectDRESD Project
Fase di validazione e sintesi Fase di validazione e sintesi
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Fase di validazione…
» Validazione del sistema attraverso la simulazione
Fase di sintesi…
» Descrizione delle partizioni in linguaggio sintetizzabile
» Sintesi e implementazione su FPGA del sistema riconfigurabile
DRESD ProjectDRESD Project
Salomone Salomone
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Un’applicazione che si occupa di adattare il sistema al reconfigurable computing…
Allocazione Ordinamento
DRESD ProjectDRESD Project
Salomone Salomone
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Metodologia… dal grafo delle partizioni alle SCoNo (Same Colored Node)
Calcolo Mobilità
Grafo dei Conflitti
Merge GrafoTDG/CG
Colorazione Grafo
Ordinamento
DRESD ProjectDRESD Project
Grafo dei Conflitti Grafo dei Conflitti
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Fase di analisi grafo per raccolta informazioni utili all’allocazione e all’ordinamento…
0
1
3
54
2
6
2
1
31
4 2
3
» Calcolo ASAP e ALAP…
» Scoperta dei cammini critici e dei nodi di mobilità…
» Calcolo del grafo dei conflitti minimo…
0 02
3 3
2 2
4 4
2 5
8 8
4 64
DRESD ProjectDRESD Project
Colorazione del grafo Colorazione del grafo
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Il problema di allocazione si risolve con l’utilizzo la colorazione del grafo…
0
1
3
54
2
6
» Merging tra grafo TDG e CG…
» Colorazione del grafo con algoritmo ADJ Coloring…
» Possibilità di BackTracking…
DRESD ProjectDRESD Project
Ordinamento Ordinamento
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Ordinamento dei nodi contenuti nelle SCoNo utilizzando un algoritmo specifico…
» Nelle valutazioni si tiene conto delle tempistiche e del data path…
» Si privilegiano i nodi nel cammino critico…
» I restanti nodi vengono ordinati cercando di non modificare la latenza…
» Problemi principali… anticipo nodo non critico e nodi paralleli…
» In uscita le SCoNo ordinate…
2
0
6
1
5
2
4
1
2
2 1
3
1
3
DRESD ProjectDRESD Project
Flusso di lavoro per specifiche realiFlusso di lavoro per specifiche reali
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Flusso di lavoro per la produzione di grafi partizionati delle specifiche di sistema…
Compilatore GCC
PandA
PartizionatoreBB / Ricorrenze
C/C++/SystemC
DRESD ProjectDRESD Project
PandaPanda
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Strumento che analizza la specifica del sistema e ricava informazioni utili…
DRESD ProjectDRESD Project
PartizionatorePartizionatore
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Raggruppa operazioni elementari del grafo DFG secondo metriche opportune…
Metriche orientate al Basic Block…
Metriche orientate alle ricorrenze…
In uscita, un grafo che rappresenta il sistema partizionato…
DRESD ProjectDRESD Project
Calcolo latenzeCalcolo latenze
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Latenza delle configurazioni non direttamente disponibili…
» Si utilizzano informazioni sulla tecnologia per ricavare la latenza delle operazioni elementari…
» Si computa la latenza del cammino critico contenuto nel sottografo della partizione…
DRESD ProjectDRESD Project
BenchmarksBenchmarks
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Specifica del sistema di compressione JPEG con diversi tipi di partizionamento…
Basic Blocks Ricorrenze Gupta
DRESD ProjectDRESD Project
ConclusioniConclusioni
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Salomone permette di adattare l’esecuzione di un sistema alla riconfigurazione dinamica…
L’implementazione del flusso di lavoro per il test di Salomone su specifiche reali fornisce indizi positivi sulla realizzabilità del flusso di progettazione…
DRESD ProjectDRESD Project
Sviluppi FuturiSviluppi Futuri
Obiettivi
Ric. Dinamica
ProgettazioneSistemi Ric.
Salomone
Flusso x Specifiche Reali
Benchmarks
Conclusioni
Sviluppi
Inserimento di valutazioni sull’occupazione d’area…
Valutazione limiti FPGA…Allocazioni precise…Latenze…Tempi di riconfigurazione…
Sfruttamento del concetto di ricorrenza…
DRESD ProjectDRESD Project
Domande…?Domande…?
![[D&D 1e - ITA] - [Avventura] - La Spada Di Grartz](https://static.fdocumenti.com/doc/165x107/55cf8f0e550346703b987c0d/dd-1e-ita-avventura-la-spada-di-grartz.jpg)
