4/12/98Cristina Silvano - CEFRIEL1 Il problema dello scheduling Cristina Silvano CEFRIEL -...

4/12/98 Cristina Silvano - CEFRIEL 1

Il problema dello scheduling

Cristina Silvano

CEFRIEL - Politecnico di MilanoElectronic Design Automation (EDA) Area

Via Fucini 2, I-20133 Milano (Italy)

Ph.: +39-2-23954-325 Fax: +39-2-23954-254

e-mail: [email protected]

mailto:[email protected]






Introduzione

• Obiettivo: assegnare le operazioni del DFG ai passi di controllo in modo da minimizzare una data funzione obiettivo e al tempo stesso soddisfare un insieme di vincoli imposti.

• La funzione obiettivo può includere il numero di passi di controllo, il ritardo, il consumo di potenza, le risorse hardware.

• Vincoli per sistemi sincroni: ogni modulo può essere utilizzato solo una volta durante un singolo passo di controllo.

• Entro un passo di controllo per eseguire ogni operazione si deve utilizzare una corrispondente e separata unità funzionale.

• Un passo di controllo corrisponde ad uno stato della FSM controllante.


Introduzione (cont.)

• Il numero totale di unità funzionali richieste in un passo di controllo corrisponde direttamente al numero di operazioni previste (scheduled) nel passo.

• Realizzazione con pochi passi di controllo (più veloce) implica che in ogni passo di controllo siano attive più unità funzionali distinte (richiede più area).

• Realizzazione con riduzione del numero di operazioni in ogni passo di controllo minor costo (richiede meno area) ma un numero di passi di controllo più alto (più lenta).

• Lo scheduling implica quindi un bilancio fra costi e prestazioni.


Introduzione (cont.)

• Il numero di passi di controllo può essere ulteriormente ridotto eseguendo operazioni ordinate nello stesso passo di controllo (chaining delle operazioni).

• Il bilancio non è solo fra il numero di passi di controllo e il numero di risorse hardware, ma coinvolge anche la lunghezza del passo di controllo.

• Se si ricorre al chaining per ridurre il numero di passi di controllo, la lunghezza del passo di controllo (cioè il numero di operazioni che devono essere compiute in serie dalla logica combinatoria) aumenta, e quindi aumenta il tempo di ciclo.

• Si suppone che le varie fasi di esecuzione non si sovrappongano, cioè si è escluso il pipelining.


Assunzioni

• Le descrizioni comportamentali non contengono costrutti condizionali o cicli.

• Ogni operazione può essere eseguita esattamente in un passo di controllo.

• Ogni tipo di operazione può essere eseguita da un solo tipo di unità funzionale.

• Si fa riferimento ad un clock ad una sola fase e all’uso di registri master-slave.


Possibili strategie

• Si assume assegnata una libreria di unità funzionali e registri con caratteristiche note e definita la lunghezza del passo di controllo.

• Approcci time-constrained o fixed-latency: minimizzano il numero di risorse rispettando un vincolo relativo al massimo numero dei passi di controllo.

• Approcci resource-constrained: minimizzano il numero di passi di controllo rispettando un vincolo relativo al numero di risorse massime disponibili (in termini di unità funzionali e registri).


Notazione

• Gli algoritmi di scheduling operano su grafi di flusso dei dati (Data Flow Graph - DFG) nei quali:

• Ogni vertice vi rappresenta un’operazione oi nella corrispondente descrizione comportamentale;

• Esiste un lato orientato eij da vi a vj se i dati prodotti dall’operazione oi vengono consumati dall’operazione oj vi è un predecessore immediato di vj;

• Ogni operazione oi può essere eseguita in Di passi di controllo: per il momento si assume Di = 1.


• Slide 7.6


Estrazione del DFG

• Per estrarre il DFG corrispondente ad una descrizione comportamentale occorre rilevare che:

• Gli operatori ammessi sono esclusivamente operatori elementari ad uno o due operandi le espressioni complesse vanno spezzate nella composizione di più operazioni elementari;

• In tutti i casi in cui non esistono dipendenze di dati le operazioni possono essere eseguite in parallelo da nodi indipendenti.


Vincoli di dipendenza dei dati nel DFG

• Sia Pred_vi = insieme dei nodi immediati predecessori di vi

• Pred_v1 = Ø

• Pred_v2 = Ø

• Pred_v3 = Ø

• Pred_v4 = Ø

• Pred_v5 = {v1, v2 }

• Pred_v6 = {v3 }

• Pred_v7 = {v5 }

• Pred_v8 = {v6, v7 }

• Pred_v9 = {v4 }

• Pred_v10 = Ø

• Pred_v11 = {v10 }


Algoritmi di scheduling

• IL DFG mette in rilievo il parallelismo presente nel progetto: esiste quindi una certa flessibilità nell’associare un nodo del DFG ad uno specifico passo di controllo.

• Alcuni algoritmi di scheduling valutano i limiti estremi entro i quali un’operazione può essere assegnata.

• Algoritmo As Soon As Possible (ASAP): dopo aver ordinato le operazioni in base alle dipendenze dei dati, ogni operazione viene assegnata al primo passo di controllo disponibile.

• Algoritmo As Late As Possible (ALAP): dopo aver ordinato le operazioni in base alle dipendenze dei dati, ogni operazione viene assegnata all’ultimo passo di controllo disponibile.


Algoritmo ASAP

for each node vi V doif Pred_vi = Ø then

Ei = 1;V = V - {vi};

elseEi =0;

endif;endfor;

while V Ø dofor each node vi V do

if ALL_NODES_SCHED ( Pred_vi, E ) thenEi = MAX ( Pred_vi, E ) + 1;V = V - {vi};

endif;endfor;

endwhile;


Algoritmo ASAP

• L’algoritmo assegna un’etichetta ASAP (cioè l’indice del passo di controllo) Ei a ogni node del DFG, assegnando così la corrispondente operazione al primo passo di controllo possibile.

• La funzione ALL_NODES_SCHED restituisce valore vero se tutti gli immediati predecessori di vi sono stati assegnati ad un passo di controllo ( hanno quindi un’etichetta E non nulla).

• La funzione MAX fornisce l’indice del nodo con il massimo valore di E fra gli immediati predecessori di vi.

• Il ciclo for dell’algoritmo assegna tutti i nodi che non hanno predecessori allo stato s1 e gli altri nodi allo stato s0 (indeterminato).

• Ad ogni iterazione, il ciclo while determina quali nodi abbiano tutti i predecessori già assegnati e li assegna al primo stato possibile. Il calcolo viene fatto incrementando di 1 il valore restituito dalla funzione MAX perché si ipotizza che ogni operazione abbia un ritardo di un passo di controllo.


Slide 7.9


Algoritmo ALAP

• Algoritmo duale rispetto al precedente: per ogni nodo calcola l’ultimo stato cui può essere assegnato.

• Si assegnano innanzitutto i nodi che non hanno successori ( e che vanno assegnati sicuramente nell’ultimo stato possibile) e poi si risale con gli stati i cui successori hanno tutti trovato un assegnamento.


Confronto algoritmi ASAP e ALAP

• Fissato lo scheduling, si calcola il numero di unità funzionali necessarie per realizzare il progetto: il numero massimo di operazioni in un qualsiasi stato indica il numero di unità funzionali per quel particolare tipo di operazione.

• Per la soluzione ASAP occorrono:• 4 moltiplicatori, 1 addizionatore/sottrattore e 1 comparatore.

• Per la soluzione ALAP occorrono:• 2 moltiplicatori, 1 addizionatore, 1 sottrattore e 1 comparatore.

• Nell’esempio considerato:• La versione ALAP è meno costosa in termini di risorse.

• Il numero di passi di controllo richiesto dalle due soluzioni è identico (pari a 4) e pertanto le prestazioni ottenute sono uguali.

• In generale gli algoritmi ASAP e ALAP non forniscono risultati ottimi sotto il profilo delle prestazioni (cioè non minimizzano il numero di passi di controllo), ma sono facili da realizzare.


Mobilità degli operatori

• Siano sEk e sLk i passi di controllo ai quali è stata assegnata l’operazione ok rispettivamente con gli algoritmi ASAP e ALAP.

• Chiaramente Ek Lk cioè ok deve iniziare l’esecuzione in un passo di controllo che non può precedere sEk e non può seguire sLk.

• Numero dei passi di controllo tra sEk e sLk = mobility range dell’operazione ok

m_range (ok) = {sj | Ek j Lk}

• Ad esempio: m_range (o4) = {s1, s2, s3} dati E4 = 1 e L4 = 3


• Slide 7.12 senza il titolo


Algoritmi di scheduling

• ASAP

• ALAP

• Algoritmi TIME-CONSTRAINED: minimizzano il numero di risorse fissato il numero di passi di controllo

• Integer Linear Programming (ILP)

• Force-Directed Scheduling ( Euristica costruttiva senza back-tracking)

• Iterative Refinement (Raffinamenti iterativi)

• Algoritmi RESOURCE-CONSTRAINED: minimizzano il numero di passi di controllo fissato il numero di risorse

• List-Based Scheduling

• Static-List Scheduling


Algoritmi Time-Constrained

• Importanti per sistemi dedicati ad applicazioni real-time

• Obiettivo: minimizzare il numero di risorse richieste (area), fissato il numero di passi di controllo.

• Tecniche:• Programmazione matematica (ILP): conduce alla soluzione ottima, ma a costo di

un’elevata complessità computazionale.

• Euristiche costruttive (Force-Directed Scheduling): non garantiscono l’ottimalità della soluzione.

• Metodi iterativi: migliorano la qualità di uno scheduling generato con un algoritmo qualunque.


Metodo della Programmazione Intera Lineare (ILP)

• Questo metodo trova una soluzione ottima mediante ricerca branch-and-bound che coinvolge del back-tracking: alcune decisioni prese nei passi iniziali possono essere riesaminate man mano che la ricerca prosegue.

• Notazione usata:• OP = { oi | 1 i n } insieme delle operazioni nel DFG;

• ti = tipo dell’operazione oi;

• T = { tk | 1 i m } insieme dei possibili tipi;

• OPtk = operazioni in OP di tipo tk;

• INDEXtk = insieme degli indici di operazioni in OPtk;

• Ntk = numero di unità che compiono operazioni di tipo tk;

• Ctk = costo unità di tipo tk;

• S = { sj | 1 j r } insieme dei passi di controllo disponibili per lo scheduling delle operazioni;

• xij variabili logiche ( = 1 se l’operazione oi è prevista per il passo j).



• Formulazione ILP del problema di scheduling:

Min k=1,…, m (Ctk Ntk)

i, 1 i n, ( Ej j Lj xij =1)

j, 1 j r, k, 1 k m, ( j INDEXtk xij Ntk)

i, j, oi Pred_oj ( Ei k Li ( k xjk ) - Ei l Li ( l xjk ) -1)



• La funzione obiettivo minimizza il costo totale delle unità funzionali necessarie:

• La prima condizione richiede che ogni operazione sia eseguita in uno e un solo passo di controllo fra i limiti imposti dagli algoritmi ASAP e ALAP;

• la seconda condizione garantisce che in nessun passo di controllo compaiano più di Ntk operazioni di tipo tk;

• La terza garantisce che tutti i predecessori di una qualsiasi operazione vengano eseguiti in un passo di controllo precedente.

• Nell’esempio occorrono 4 tipi di unità funzionali (un moltiplicatore un addizionatore, un sottrattore e un comparatore).

• La formulazione del problema di assegnare il DFG su 4 passi di controllo diventa:

• min ( Cm Nm + Ca Na + Cs Ns + Cc Nc)

• Soluzione ottenuta supponendo che addizionatori, sottrattori e comparatori abbiano costo pari a 1 e moltiplicatori costo pari a 2.



• Il costo dell’algoritmo cresce molto rapidamente con il numero delle variabili e dipende dalla struttura del DFG.

• Metodo computazionalmente molto costoso.

• Si usano delle varianti in cui si elimina il back-tracking sostituendo delle euristiche che assegnano le operazioni una alla volta invece di tentare un assegnamento simultaneo.


Es slide 7.16


Force-Directed Scheduling

• Obiettivo: ridurre il numero totale di unità funzionali usate, e viene ottenuto distribuendo le operazioni dello stesso tipo uniformemente in tutti gli stati disponibili.

• Tale distribuzione garantisce che le unità funzionali allocate in un passo di controllo vengano usate in modo efficiente in tutti gli altri passi di controllo porta ad un miglior rapporto di utilizzazione.

• Si parte dal calcolo del mobility range per ogni operazione.

• Si assume che ogni operazione oi abbia probabilità uniforme di essere assegnata ad un qualunque passo del campo ammissibile e probabilità zero di essere assegnata a qualsiasi altro passo di controllo.

• Per uno stato sj tale che Ei j Li, la probabilità che l’operazione oi sia assegnata allo stato sj è data da:pj (oi) = 1 / (Li - Ei + 1)


Force-Directed Scheduling (cont.)

• Rappresentando per ogni tipo di operatore la probabilità con dei rettangoli la cui ampiezza è proporzionale al valore per lo stato corrispondente, si costruisce un diagramma a barre che rappresenta il costo previsto per l’operatore (EOC) nel rispettivo stato.

• Per lo stato sj il costo dell’operatore ti tipo k è dato da:• EOC jk = ck i, sj mrange (oi) pj (oi)

• dove oi è un’operazione di tipo k, ck è il costo dell’unità funzionale che la esegue.

• Esempio: • EOC 1, mult = cmult (p1 (o1) + p1 (o2) + p1 (o3) + p1 (o4) ) =

cmult (1 + 1 + 0.5 + 0.33) = cmult 2.83


Slide 7.20



• A questo punto si cerca di bilanciare il valore di EOC per tutti i tipi di operazione.

• Ad ogni operazione si calcola il costo per assegnare ogni operazione non ancora assegnata entro il suo campo.

• Una volta assegnata un’operazione ad un passo di controllo, non si modifica più l’assegnamento effettuato (no back-tracking).

• Esempio: Si assegna o3 al passo s2 e si minimizza l’EOC per la moltiplicazione (Max (pj) scende da 2.83 a 2.33) e si ottiene il nuovo diagramma a barre per la moltiplicazione.


Slide 7.21



• Ad ogni iterazione dell’algoritmo si assegna un’operazione ad un passo di controllo.

• L’algoritmo si dice costruttivo perché costruisce una soluzione senza mai fare back-tracking.

• Il risultato può non essere ottimo: si può raffinare il suo valore ricorrendo a tecniche di raffinamento iterativo in cui si ammette di riassegnare un’operazione già assegnata sulla base di opportune strategie.


Slide 7.23


Algoritmi Resource-Constrained

• Importanti per sistemi con vincoli in area o consumo di potenza.

• Obiettivo: minimizzare il numero di passi di controllo (prestazioni) entro il vincolo di risorse assegnate.

• Si costruisce uno scheduling assegnando un’operazione per volta, in modo da non superare i vincoli di risorse e non violare le dipendenze dai dati.

• I vincoli sulle risorse si soddisfano garantendo che il numero totale di operazioni assegnate ad un passo di controllo non superi i vincoli imposti.

• I vincoli di dipendenza possono essere verificati garantendo che tutti i predecessori di un nodo siano stati assegnati prima di assegnare il nodo.

• Tecniche:• List-Based Scheduling

• Static-List Scheduling


List-Based Scheduling

• Generalizzazione dell’algoritmo ASAP: in assenza di vincoli sulle risorse produce gli stessi risultati.

• L’algoritmo mantiene una lista di nodi ready, cioè dei nodi i cui predecessori siano già stati assegnati.

• Ad ogni iterazione si assegnano le operazioni all’inizio della lista fino a quando le risorse disponibili in quello stato non sono esaurite.

• La lista viene ordinata secondo una funzione di priorità, che risolve possibili conflitti sull’uso di una risorsa.

• L’assegnamento di un’operazione ad un passo di controllo può rendere ready operazioni che non lo erano e che vengono inserite nella lista secondo il loro livello di priorità.

• Si mantiene un a lista PList per ogni tipo di operatore contenente i nodi ready, cioè i nodi con predecessori già assegnati (al primo passo nella lista ci sono solo i nodi senza predecessori).

• La mobilità costituisce una buona funzione di priorità.


Slide 7.12


List-Based Scheduling (cont.)

• Prima iterazione: nella lista dei nodi ready ci sono solo i nodi corrispondenti ad operazioni senza predecessore: o1, o2, o3, o4, o10 che vengono inserite nella lista delle diverse operazioni secondo la funzione di priorità:

• Plist*: 1 <0>, 2 <0>, 3 <1>, 4 <2>

• Plist+: 10 <2>

• Plist- : NIL

• Plist<: NIL

• L’unica addizione o10 viene assegnata al passo s1, mentre nell’ipotesi di avere disponibili solo due moltiplicatori si assegnano ad s1 le operazioni o1 e o2 che hanno mobilità più bassa e quindi priorità più alta.


Slide 7.13


List-Based Scheduling (cont.)

• Seconda iterazione: nella lista dei nodi ready si aggiungono o5 e o11 i cui nodi predecessori sono stati tutti assegnati e si tolgono i nodi assegnati al passo precedente.

• Le operazioni presenti nella lista vengono riordinate secondo la funzione di priorità:

• Plist*: 5 <0>, 3 <1>, 4 <2>

• Plist+: NIL

• Plist- : NIL

• Plist<: 11<2>

• L’unico confronto o11 viene assegnata al passo s2, mentre nell’ipotesi di avere disponibili solo due moltiplicatori si assegnano ad s2 le operazioni o5 e o3 che hanno mobilità più bassa e quindi priorità più alta.

• In totale nell’esempio servono 4 iterazioni.


Slide 7.14


Rilascio delle ipotesi semplificatrici

• In particolare si ammettono ora:

• Unità funzionali con tempi di esecuzione diversi;

• Unità multi-funzione;

• Descrizioni comportamentali che non si limitino a codice lineare.


Unità funzionali con ritardi diversi

• Le unità funzionali reali spesso hanno ritardi diversi, dipendenti dal loro progetto e dalla loro complessità.

• Non si può quindi supporre che qualsiasi operazione venga completata in un solo passo di controllo: tale ipotesi porterebbe a usare un periodo di clock troppo lungo per ospitare l’operazione più lenta.

• Si deve ammettere che esistano unità funzionali con ritardo variabile e che queste non vengano più eseguite in un solo ciclo di clock.

• Unità funzionali con ritardi variabili:• Multicycling

• Chaining

• Pipelining


Slide 7.25


Multicycling

• Si dimensiona il ciclo di clock sulla durata dell’operazione più veloce.

• Le operazioni più lunghe (operazioni multiciclo) richiedono allora due o più passi di controllo.

• Occorre introdurre latch d’ingresso sul fronte delle unità multiciclo per conservare gli operandi fino a che i risultati non siano disponibili diversi cicli più avanti.


Chaining

• L’aumento del numero di passi di controllo richiede una maggiore complessità dell’unità di controllo.

• Un’alternativa per aumentare l’utilizzazione delle unità funzionali consiste nel consentire che due o più operazioni vengano eseguite ordinatamente in serie in un solo passo: chaining.

• Tale approccio richiede collegamenti diretti fra le unità funzionali oltre a quelli già esistenti fra registri e unità funzionali.


Pipelining

• Per aumentare il parallelismo di esecuzione si può ricorrere al pipelining: quando si usa un’unità dotata di pipelining, lo scheduler deve calcolare in modo diverso le risorse richieste.

• Si consideri l’impiego di un moltiplicatore pipelined a due stadi per eseguire due moltiplicazioni consecutive.

• Le due moltiplicazioni possono condividere lo stesso moltiplicatore perché ognuna usa un diverso stadio del moltiplicatore e quindi risulta sufficiente un solo moltiplicatore invece di due.


Unità multi-funzionali

• Le unità multi-funzionali costano in genere meno di un insieme di unità ognuna a funzione singola che coprano lo stesso insieme di funzioni: ad esempio un addizionatore-sottrattore costa solo il 20% in più di un addizionatore e molto meno di un addizionatore e un sottrattore.

• La libreria dei componenti può offrire diverse implementazioni fisiche per una data unità con diverse caratteristiche di area e di ritardo.


Costrutti condizionali

• I costrutti condizionali corrispondono ad un insieme di percorsi mutuamente esclusivi: in esecuzione, un solo percorso viene eseguito, sulla base della valutazione della condizione.

• Il comportamento non può essere rappresentato attraverso un DFG puro: si deve ricorrere ad un CDFG che rappresenti sia dipendenze dei dati sia dipendenze di controllo.

• Un algoritmo di scheduling efficiente condivide le risorse tra operazioni mutuamente esclusive.


Costrutti ciclici

• In genere, l’ottimizzazione del corpo del ciclo migliora le prestazioni del progetto.

• Esiste un parallelismo potenziale tra le diverse iterazioni del ciclo, che può essere sfruttato eseguendo in parallelo diverse iterazioni del ciclo.


Slide 7.26


Costrutti ciclici (cont.)

• Si consideri un ciclo di 12 iterazioni, lo scheduling può avvenire in 3 modi diversi.

• Esecuzione sequenziale in b passi di controllo; il tempo totale di esecuzione è pari a 12b passi di controllo.

• Srotolamento parziale del ciclo (Partial Loop Unrolling):• Si srotolano alcune iterazioni del ciclo e ne risulta un corpo del ciclo più lungo ma

meno iterazioni. Esempio: si srotolano 3 iterazioni in una super-iterazione che richiede u passi di controllo. Se u < 3b il tempo totale di esecuzione (4u) è migliorato.

• Loop Folding: iterazioni successive vengono sovrapposte con tecnica pipeline.

• Se il corpo del ciclo richiede m passi di controllo, l’esecuzione di una nuova iterazione inizia ogni p passi di controllo (p < m). Tempo totale di esecuzione m+ (n-1) p passi di controllo.

• Il loop unrolling è applicabile solo se il numero di iterazioni del ciclo è noto a priori; il loop folding è applicabile anche quando tale numero non è noto.


Esempio di costrutti ciclici

• Ciclo composto da 17 operazioni identiche che richiedono ognuna un passo di controllo.

• Gli archi tratteggiati indicano dipendenze dei dati tra diverse iterazioni.

• Confrontiamo le tre tecniche di scheduling secondo le seguenti cifre di merito:

• Rapporto di utilizzazione delle risorse (percentuale del numero di stati nei quali le unità sono usate per compiere un’operazione)

• Costo del controllo, misurato con il numero di parole di controllo diverse richieste all’unità di controllo.


Esempio di costrutti ciclici (cont.)

• Scheduling Sequenziale: 6 passi di controllo e 3 unità funzionali.

• Partial Loop Unrolling srotolando due copie del ciclo: 9 passi di controllo e 4 unità funzionali.

• Loop Folding con iterazioni successive che partono dopo 3 passi di controllo: 9 passi di controllo (3 per la testa, 3 per il corpo del ciclo e 3 per la coda) e 6 unità funzionali.


Slide 7.27 e 7.28


Confronto

No. FU RapportoUtilizzaz.

Tm esecuz.per iteraz.

Costo delcontrollo

Sequential 3 17/18 6 6

Partial Loop Unrolling 4 17/18 4.5 9

Loop Folding 6 17/18 3 9


Bibliografia

• D. Gajski, N. Dutt, A. Wu and S. Lin, “ High-Level Synthesis: Introduction to Chip and System Design” Kluwer Academic Press, 1992.

• G. De Micheli, “Synthesis and Optimization of Digital Circuits”, McGraw-Hill, 1994.

• M. Sami, “Hardware-Software Co-Design ”, Memorie della Scuola Nazionale del Gruppo Italiano di Ingegneria Informatica, Pavia, 3-13 Settembre, 1996.

4/12/98Cristina Silvano - CEFRIEL1 Il problema dello scheduling Cristina Silvano CEFRIEL -...

Documents

Transcript of 4/12/98Cristina Silvano - CEFRIEL1 Il problema dello scheduling Cristina Silvano CEFRIEL -...