Sintesi architetturale

1) Sintesi architetturale :

Consente di costruire la struttura macroscopica di un sistema digitale a partire dalla sua descrizione comportamentale espressa tramite un grafo sequenziale, un insieme di risorse ed un insieme di vincoli.

 

2) Data path :

Si tratta della interconnessione di risorse e logica di collegamento.

 

3) Classificazione delle risorse:

a)       Risorse funzionali consentono di eseguire operazioni aritmetico logiche, si suddividono in risorse funzionali primitive ossia comuni a molte applicazioni e risorse funzionali specifiche di una determinata applicazione.

b)       Risorse di memoria consentono la memorizzazione dei dati.

c)       Risorse di interfaccia quali i bus che rendono possibile il trasferimento dei dati.

 

4) Tipologie di vincoli :

a)       Vincoli di implementazione richiedono al sistema sintetizzato determinate proprietà, ad esempio spesso si richiede un´area limitata ed un tempo di esecuzione ben determinato.

b)       Vincoli di interfacciamento legati alla necessità di interfacciare il sistema con altri sistemi, è importante a questo riguardo il formato dei dati e la loro sincronizzazione.

 

5) Fasi della sintesi architetturale :

a)       Scheduling delle operazioni

b)       Binding delle risorse

Le limitazioni imposte su una delle due fasi della sintesi si ripercuotono anche sulla altra fase e viceversa.

 

6) Modello per i problemi di scheduling :

Si utilizza un grafo diretto aciclico nel quale le operazioni sono rappresentate dai vertici mentre gli archi rappresentano le dipendenze, ad ogni operazione è poi associato un ritardo di esecuzione d che è nullo solo per il vertice sorgente e per il vertice destinazione, i ritardi sono contenuti in un vettore D mentre il ciclo di clock in cui inizia l´operazione è contenuto in un vettore T e si assume che l´operazione del vertice sorgente inizi al ciclo di clock 1.

 

7) Latenza :

È il tempo che intercorre tra l´inizio della operazione del vertice destinazione e quella del vertice sorgente, essa è pari al più lungo cammino tra sorgente e destinazione.

 

8) Scheduling non vincolato :

Vengono programmati gli istanti di esecuzione delle operazioni senza aver vincoli sulle risorse, sia perché queste possono essere dedicate, sia perché possono essere sfruttate serializzando le operazioni una volta che le risorse sono state fissate. Si tratta di algoritmi utilizzati prevalentemente per ricavare la latenza di problemi con limitazioni.

 

9) Algoritmo ASAP :

As Soon As Possibile, l´operazione viene schedulata non appena tutte le operazioni da cui dipende sono state eseguite.

 

10) Algoritmo ALAP :

As Late As Possibile, l´operazione viene schedulata il più tardi possibile questo al fine di individuare un limite superiore per la latenza.

 

11) Mobilità di un´operazione :

È la differenza m tra la sua schedulazione di un operazione  con la algoritmo ALAP e la schedulazione della stessa con la algoritmo ASAP.

 

12) Scheduling vincolato dal tempo :

Le limitazioni di tempo vengono specificate come limite superiore ed inferiore al tempo di separazione tra due istruzioni, si rappresentano mediante un grafo vincolato che si ottiene dal grafo sequenziale (…pesato con i ritardi di esecuzione delle operazioni) aggiungendo un arco in avanti con peso uguale al limite minimo nel caso vogliamo imporre un limite minimo di tempo tra le due operazioni mentre se vogliamo imporre il limite massimo si inserisce nel grafo un arco all´indietro con peso pari all´opposto del limite massimo. Un possibile criterio di scheduling consiste nel considerare a turno ogni tempo limite massimo e verificare che non vi siano cicli positivi.

 

13) Scheduling vincolato dalle risorse :

Gli algoritmi di scheduling che richiedono di minimizzare la latenza con risorse limitate o di minimizzare le risorse con latenza limitata sono intrattabili, gli algoritmi euristici di list.scheduling ne danno delle soluzioni approssimate. Vengono presentati tre algoritmi :

a)       Minimizzazione della latenza con limite delle risorse

A tutte le operazioni viene associato un ritardo unitario, le risorse sono in numero prestabilito ed il grafico è pesato con le priorità in modo che le operazioni che debbono essere eseguite per prime hanno priorità più elevata, si procede schedulando prima le operazioni a priorità più elevata compatibilmente col numero delle risorse, se poi c´è una risorsa che ad un dato ciclo di clock rimane inutilizzata, le viene assegnata l´operazione attinente avente priorità maggiore.

b)       Minimizzazione delle risorse con limite di latenza

Si ha inizialmente una risorsa per ogni tipo di operazione, vengono schedulate le operazioni con mobilità zero ossia quelle che se non schedulate determinano la violazione del limite sulla latenza, a tal fine se necessario vengono aggiunte delle risorse. Le restanti operazioni vengono schedulate soltanto se non richiedono risorse addizionali.

c)       Force Directed Scheduling

L´intervallo di mobilità di un´operazione individua i cicli nei quali la stessa può essere schedulata, si ricava come differenza tra la sua schedulazione con l´ALAP e con l´ASAP , la probabilità che l´operazione venga schedulata al di fuori di questo intervallo è nulla mentre è costante e inversamente proporzionale alla ampiezza della intervallo al suo interno. Sommando la distribuzione di probabilità per operazioni dello steso tipo si ottiene un grafico della distribuzione di probabilità per ogni tipo di operazione, l´operazione prescelta per essere schedulata su una data risorsa al passo n è prescelta in modo che le forze si oppongano e vinca la più forte.

 

14) Binding delle risorse :

Il binding è volto a far si che più operazioni possano usufruire della medesima risorsa al fine di ridurre la area del circuito, vi sono le seguenti tipologie di binding :

a)       corrispondenza biunivoca tra tipo di operazione e tipo di risorsa

b)       differenti operazioni eseguite sulla stessa risorsa (…ad esempio l´ALU)

c)       una stessa operazione può essere eseguita su più risorse (… sommatori con caratteristiche diverse)

Il problema può essere impostato in termini di colorazione del grafo delle incompatibilità costruito inserendo un arco tra le operazioni che sono incompatibili in quanto richiedono la stessa risorsa nello stesso istante di tempo.

 

15) Condivisione delle risorse non funzionali :

Per risorse non funzionali si intende ad esempio la memoria nella quale vengono memorizzate le variabili che sono caratterizzate da un tempo di vita, evidentemente si può effettuare un binding anche per regolamentarne la condivisione dei registri nei quali sono memorizzate le variabili.