Politecnico di MilanoPolitecnico di Milano

Cosa sto facendo???Cosa sto facendo???

Chiara Fornoni

(l’altra.... Quella che mangia durante le riunioni di DRESD....)

Chiara Fornoni

IndiceIndice

• Obiettivi

• Pip (Articolo 6)

• Articolo 5

• Articolo 3+4

Chiara Fornoni

ObiettiviObiettivi

• Definire un algoritmo di partizionamento per un grafico generico in input che rappresenti il sistema voluto

• Garantire le migliori prestazioni per un’implementazione su Yara (architettura riconfigurabile)

• Sfruttare le caratteristiche “positive” di algoritmi realizzati da altre università, minimizzando le caratteristiche “negative”

Chiara Fornoni

Pip – elementi fondamentaliPip – elementi fondamentali

• Direct Acyclic Graph (DAG)

• Node-Induced Subgraph

• Task Graph

Chiara Fornoni

Pip – estrazione strutture Pip – estrazione strutture regolariregolari

•Isomorphic DFG

•Isomorphic Subgraphs

P problem

NP compleet

NP problems

Chiara Fornoni

Pip – fasi del flussoPip – fasi del flusso

DAGSTS

MINCAT

TSS

Φ(t), Φ%(t)

CTSS

Oggetto

LFFPHTG

Chiara Fornoni

Pip – parametri della scelta del Pip – parametri della scelta del templatetemplate

•Scelta del template

TSS: insieme di t che sono soluzione

Φ(t): Posto occupato dalla frame per ogni t

Φ%(t)

TSSΦ%(t): TSS ordinato secondo Φ%(t)

dt: soglia di dimensione (riduzione TSSΦ%(t))

dt%

CTSS = TSS – PS : spazio soluzione del template

Chiara Fornoni

Pip – parametri dello sviluppo del Pip – parametri dello sviluppo del templatetemplate

template

oggetti

+ politica di partizionamento

Chiara Fornoni

Pip – parametri della Candidate Pip – parametri della Candidate EvaluationEvaluation

•HTG (Hierarchical Template Graph)

< tempo di configurazione

bitstream + piccolo

•Morphing time

Chiara Fornoni

Pip – nuove frontiere 1Pip – nuove frontiere 1

• Minimizzare tempo di esecuzione tramite possibili disposizioni dei template

O1 O2

O4

O1 O3

O1 O4

O2

O1 O3vs

Chiara Fornoni

Pip – nuove frontiere 2Pip – nuove frontiere 2

• Evoluzione delle politiche di creazione dei template

Chiara Fornoni

Analisi di altri metodiAnalisi di altri metodi

• Altri metodi: articoli 3+4 (motomura), articolo 5

• Valutazione altri parametri -> costo di Comunicazione

Chiara Fornoni

Articolo 5 – metodologiaArticolo 5 – metodologia

Estrazione path più lungo (?)

Chiara Fornoni

Articolo 5 – metodologiaArticolo 5 – metodologia

Tutti i possibili legami tra operazioni e cstep

scelta non-crossing (ottima ?)

Chiara Fornoni

Articolo 5 - metodologiaArticolo 5 - metodologia

Grafico cartesiano operazioni/cstep

Dominanza

Chiara Fornoni

Articolo 5 – metodologiaArticolo 5 – metodologia

Catena pesata massima

Chiara Fornoni

Algoritmo 5 - Algoritmo 5 -

• Confronto con altri metodi

Chiara Fornoni

Algoritmo 3+4 - algoritmoAlgoritmo 3+4 - algoritmo

Chiara Fornoni

Algoritmo 3+4 - algoritmoAlgoritmo 3+4 - algoritmo

Chiara Fornoni

Cosa devo fare io???Cosa devo fare io???

• Valutazione parametri di ogni metodo/algoritmo

• Valutazione prestazioni

• Estrazione caratteristiche “ottime”

• Test(?)