METODOLOGIA DI PROGETTO PER LA TRADUZIONE DI … · riguardanti il design digitale ed inoltre...

POLITECNICO DI M ILANO

FACOLTA DI INGEGNERIA

CORSO DILAUREA IN INGEGNERIA INFORMATICA

METODOLOGIA DI PROGETTO PER

LA TRADUZIONE DI SPECIFICHE

AD ALTO LIVELLO IN VHDL

Relatore: Prof. Fabrizio FERRANDI

Correlatore: Ing. Marco Domenico SANTAMBROGIO

Tesi di Laurea di:Paola MUSSIDAMatricola n. 650995Marco LOSITOMatricola n. 653814

ANNO ACCADEMICO 2003-2004

Alle nostre care Famiglie

Indice

Introduzione 1

1 Stato dell’Arte 3

1.1 Le Macchine a Stati Finiti. . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Macchine di Mealy. . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Macchine di Moore. . . . . . . . . . . . . . . . . . . . . 6

1.1.3 Macchine a Stati Finiti con Datapath. . . . . . . . . . . . 7

1.1.4 Diagrammi ASM. . . . . . . . . . . . . . . . . . . . . . 9

1.1.5 Blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Grafi e Cammino Critico. . . . . . . . . . . . . . . . . . . . . . 14

1.2.1 I Grafi: Notazione e Nomenclatura. . . . . . . . . . . . . 14

1.2.2 Gli Activity Networks . . . . . . . . . . . . . . . . . . . 19

1.2.3 Il Cammino Critico. . . . . . . . . . . . . . . . . . . . . 24

2 Metodologia 31

2.1 Introduzione. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Preliminari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3 Prima Fase: Traduzione dell’algoritmo di partenza in un diagram-

ma ASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.1 State box. . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.2 Decision box. . . . . . . . . . . . . . . . . . . . . . . . 37

2.3.3 Condition box . . . . . . . . . . . . . . . . . . . . . . . 39

2.3.4 Macrostrutture. . . . . . . . . . . . . . . . . . . . . . . 41

ii

2.3.5 Blocchi ASM, o ASM blocks . . . . . . . . . . . . . . . 41

2.4 Seconda Fase: Traduzione del diagramma ASM in specifica VHDL

sintetizzabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.4.1 Traduzione dastate boxa VHDL . . . . . . . . . . . . . 45

2.4.2 Traduzione dadecision boxa VHDL . . . . . . . . . . . . 47

2.4.3 Traduzione da Condition Box a VHDL. . . . . . . . . . 50

2.4.4 Testing della periferica, scrittura del driver e integrazione

della periferica . . . . . . . . . . . . . . . . . . . . . . . 51

3 Caso di Studio: Il Cammino Critico 52

3.1 Aree Applicative . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2 Strumenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.3 Fasi del Progetto. . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.1 Studio del Problema. . . . . . . . . . . . . . . . . . . . 56

3.3.2 Formalizzazione del Codice C. . . . . . . . . . . . . . . 57

3.3.3 ASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.3.4 VHDL e Verifica . . . . . . . . . . . . . . . . . . . . . . 65

3.3.5 Integrazione. . . . . . . . . . . . . . . . . . . . . . . . . 71

4 Verifica e Conclusioni 74

A Diagrammi ASM 78

Ringraziamenti 82

Bibliografia 84

Elenco delle figure

1.1 Una macchina Sequenziale generica (di Mealy o di Moore). . . . 4

1.2 Macchina a stati finiti rappresentata tramite un diagramma degli

stati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Calcolo della parita tramite una Macchina di Moore. . . . . . . . 6

1.4 Schema di Finite State Machine with Datapath. . . . . . . . . . . 8

1.5 Esempio di blocchi di un diagramma ASM.. . . . . . . . . . . . 12

1.6 Ciclo costituito da un solo blocco. . . . . . . . . . . . . . . . . . 13

1.7 Esempio generico di grafo non diretto. . . . . . . . . . . . . . . 15

1.8 Esempio di grafo orientato o diretto. . . . . . . . . . . . . . . . 17

1.9 Esempio di grafo orientato con un ciclo. . . . . . . . . . . . . . 18

1.10 Esempio di grafo aciclico e orientato (DAG) . . . . . . . . . . . . 19

1.11 Livelli dell’ordinamento topologico di un grafo. . . . . . . . . . 20

1.12 Esempio di grafoActivity Networks . . . . . . . . . . . . . . . . 22

1.13 Grafo diretto e aciclico con pesi sugli archi e cammino critico. . 25

1.14 Frammento di algoritmo relativo al calcolo del tempo minimo. . 28

1.15 Frammento di algoritmo relativo al calcolo del tempo massimo. . 28

1.16 Algoritmo relativo al calcolo del cammino critico. . . . . . . . . 30

2.1 Flusso della Metodologia Proposta. . . . . . . . . . . . . . . . . 33

2.2 Due possibili alternative nella creazione di State box. . . . . . . 37

2.3 Livelli di operazioni effettuate. . . . . . . . . . . . . . . . . . . 38

2.4 Esempio di traduzione del costrutto:finche condizione ripeti. . . . 39

2.5 Esempio di traduzione di ciclo.. . . . . . . . . . . . . . . . . . . 42

2.6 Esempio di blocco generico. . . . . . . . . . . . . . . . . . . . . 43

iv

2.7 Esempio di blocco. . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.1 Flusso di sviluppo del progetto. . . . . . . . . . . . . . . . . . . 53

3.2 Porzione di codice C relativo al calcolo del tempo minimo. . . . 59

3.3 Parte del codice relativa all’acquisizione del grafo da file. . . . . 61

3.4 codice in cui si evidenzia la gestione delloscheduling. . . . . . . 61

3.5 Frammento di codice in cui vengono settati il nodo origine e quel-

lo finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.6 Dettaglio del codice sul calcolo del tempo minimo. . . . . . . . . 62

3.7 Frammento di codice in cui viene determinato il sotografo critico. 62

3.8 Diagrammi della parte di codice relativa al calcolo del percorso

minimo e massimo . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.9 Esempio di codice C dell’algoritmo che viene tradotto in diagram-

mi ASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.10 Esempi di box derivanti dalla traduzione del codice di Figura3.9 . 65

3.11 Esempio di uno stato della FSM, derivante dalla traduzione del

codice di Figura3.9 . . . . . . . . . . . . . . . . . . . . . . . . 66

3.12 Foto della Virtex-II Pro Evaluation Board. . . . . . . . . . . . . 69

3.13 Verifica tramite strumenti software. . . . . . . . . . . . . . . . . 71

3.14 Integrazione dell’IP core in una architettura. . . . . . . . . . . . 72

A.1 Diagramma ASM che descrive l’algoritmo che calcolaTMax e

TMin di unDAG . . . . . . . . . . . . . . . . . . . . . . . . . . 79

A.2 Diagramma ASM che descrive l’algoritmo che ricava daTMaxe

TMin il sottografo critco di unDAG . . . . . . . . . . . . . . . . 80

A.3 Diagramma ASM che descrive l’algoritmo che trova i percorsi

critici dato un sottografo critico. . . . . . . . . . . . . . . . . . . 81

Elenco delle tabelle

1.1 Tipi fondamentali di box in un diagramma ASM, con esempio. . 10

1.2 Condition Box, con esempio. . . . . . . . . . . . . . . . . . . . 11

1.3 Attivita del progetto in esempio. . . . . . . . . . . . . . . . . . . 21

1.4 Matrice di adiacenza del grafo di Figura1.12, derivante dalla

Tabella 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1 Tipi di box in un diagramma ASM con esempio. . . . . . . . . . 35

2.2 Lo spostamento di unaboxda un blocco all’altro. In questo modo

la state boxdiventa unacondition box . . . . . . . . . . . . . . . 45

3.1 Esempio di dichiarazione del grafo, affiancato dalla rappresen-

tazione del grafo stesso.. . . . . . . . . . . . . . . . . . . . . . . 60

3.2 Esempio di traduzione distate box . . . . . . . . . . . . . . . . . 69

3.3 Esempio di traduzione didecision box . . . . . . . . . . . . . . . 70

3.4 Esempio di traduzione dicondition box . . . . . . . . . . . . . . 70

vi

Introduzione

L’obiettivo principalee giungere ad un chiaro metodo che mira a semplificare e

formalizzare il passaggio da un algoritmo ad una specificaVery high speed inte-

grated circuits Hardware Description Language(VHDL). Tale ricercae stimola-

ta dalla volonta di applicare teorie affermate per creare una metodologia nuova

riguardante alcune fasi dello sviluppo hardware.

Nel primo capitolo vengono mostrate le basi teoriche che rappresentano le

fondamenta del metodo esposto. Si prendono in analisi alcune teorie esistenti

riguardanti ildesigndigitale ed inoltre vengono fornite tutte le conoscenze neces-

sarie alla comprensione della metodologia proposta e del caso di studio presentato.

Una volta fornite queste basi, nelcapitolo 2 si propone una nuova metodologia

di traduzione da specifiche ad alto livello in VHDL. Nel corso del capitolo si il-

lustra dettagliatamente la metodologia proposta, analizzandola fase per fase, par-

tendo dalla specifica ad alto livello fino ad arrivare alla specifica VHDL. Nella

descrizione fornita vengono mostrati singolarmente il modo di operare e le moti-

vazioni delle scelte effettuate.

Nel 3o capitolo si presenta la reale implementazione in hardware, tramite l’appli-

cazione della metodologia proposta, di un IP core dedicato al calcolo del cammino

critico in un grafo. Nel capitolo, partendo da una specifica iniziale inC, si cerca di

approfondire l’aspetto implementativo della metodologia, illustrando in dettaglio

le fasi della traduzione in VHDL per la creazione di un IP core. L’obiettivoe

quello di illustrare in modo piu dettagliato la metodologia tramite l’analisi critica

di tutte le scelte implementative effettuate per lo specifico caso di studio.

I risultati riportati nelCapitolo 4 mostrano una metodologia snella, che facen-

1

Introduzione

do uso di nozioni semplici, permette uno sviluppo lineare e rapido di descrizioni

VHDL. Vengono presentati i test effettuati sull’implementazione risultante dal

caso di studio e, basandosi sul loro esito, si valida la metodologia. Si accennano

quindi possibili lavori futuri derivanti dal lavoro svolto.

2

Capitolo 1

Stato dell’Arte

Il presente capitolo mira a fornire tutte le informazioni e le conoscenze di base

utili alla lettura ed alla comprensione di questo lavoro di tesi. Principalmente la

descrizione si articola su tre sezioni. La prima di queste, relativa alle macchine a

stati finiti, Finite State Machineso FSM, ed alle macchine a stati finiti con data-

path,Finite State Machines with Datapatho FSMD, rappresenta la base per la

seconda, riguardante idiagrammi Algoritmic State Machine o ASM, presentati

in [2]. Infine l’ultima di questee dedicata alla presentazione delle definizioni utili

alla comprensione del caso di studio.

3

CAPITOLO 1. STATO DELL’ARTE

1.1 Le Macchine a Stati Finiti

Una macchina, o automa, a stati finiti,e un semplice modello operazionale che

permette di risolvere una certa gamma di problemi1 e per questo rappresenta

una delle basi teoriche fondamentali della metodologia proposta in questa tesi.

Poiche le FSM sono particolarmente affini a quello che sara il risultato defini-

tivo in hardware, esse diventano una delle strutture fondamentali descritte nella

specifica VHDL risultante.

Le FSM sono definite tramite una tripletta< Q, I , δ > dove:

• Q e un insieme finito di statiq0, q1, q2, q3 , . . . ;

• I e un insieme finito di ingressii0, i1, i2, . . . detto alfabeto;

• δ e una funzione (parziale), detta funzione di transizione, che permette di

calcolare lo stato prossimo dallo stato corrente e dall’ingresso. Q× I → Q.

Uno schema per una generica macchina sequenzialee illustrato in Figura1.1.

Figura 1.1: Una macchina Sequenziale generica (di Mealy o di Moore).

Un’utile rappresentazione delle FSMe il cosı dettodiagramma degli stati2

[3],[4]. Un diagramma degli statie un grafo orientato che specifica gli stati, rapp-

resentati come nodi, e la funzione di transizione tra essi, rappresentata dagli archi,1Per un’analisi dei problemi risolvibili tramite una FSM si veda [1].2Si noti, che questa rappresentazione graficae soltanto una delle molteplici utilizzate per le

FSM. Come ulteriori esempi di rappresentazioni molto utilizzate si citano: letabelle degli stati,

4


Figura 1.2: Macchina a stati finiti rappresentata tramite un diagramma degli stati.

di una FSM. Ogni arco ha un’etichetta corrispondente all’ingresso cuie associata

la transizione tra gli stati congiunti dall’arco. Un esempio di FSM rappresentata

tramite grafoe visibile in Figura1.2.

Esistono in letteratura varie estensioni alla definizione di FSM proposta in

precedenza, ma sie deciso di adottare da qui in poi le macchine definite dalla

sestupla< Q, I , U, δ, λ, q0 >. Queste differiscono dalla precedente definizione

per l’aggiunta opzionale di uno stato iniziale3 q0 rappresentante lo stato in cui si

trova la macchina al partire dell’esecuzione, di un insieme di simboli U detto al-

fabeto di uscita e di una funzione parzialeλ detta funzione di uscita.

Queste estensioni vengono aggiunte per far sı che la FSM possa rappresentare due

differenti macchine, semanticamente equivalenti tra loro, ma che differiscono per

la funzione di uscitaλ. Si tratta della macchina di Mealy e della macchina di

Moore4 , che vengono descritte nei due paragrafi seguenti.

le tabelle delle transizioni, e le tabelle delle eccitazioni. Per una trattazione piu approfondita si

vedano [3] e [4].3Detto anche stato di reset.4Una macchina di Mealy puo sempre essere trasformata in una macchina di Moore, e viceversa

5


1.1.1 Macchine di Mealy

Nella macchina di Mealy, l’uscita U in un determinato istante, dipende sia dallo

stato corrente, sia dell’ingresso. Cioe λ e definita come:

λ : Q× I →U (1.1)

Questa macchina viene rappresentata nel diagramma degli stati precedente-

mente descritto inserendo lo stato inizialeq0 e l’uscita. Il primo viene indicato

con un arco entrante recante l’etichettareset, mentre le uscite sono rappresentate

accodando il testo dell’uscita al testo dell’ingresso sugli archi che le determinano.

1.1.2 Macchine di Moore

A differenza della macchina di Mealy, nella macchina di Moore, l’uscita dipende

unicamente dallo stato corrente, cioe λ e definita come:

λ : Q→U (1.2)

La rappresentazione delle macchine di Moore nel diagramma degli stati aggiunge

alla descrizione di una FSM lo stato inizialeq0 , proprio come nel caso della

macchina di Mealy. L’uscitae invece indicata nello stato che la provoca. Un

esempio di grafo di questo tipoe illustrato dalla Figura1.3.

Figura 1.3: Calcolo della parita tramite una Macchina di Moore.

6


.

L’ampia letteratura riguardante la formalizzazione degli automi [1], che af-

fonda le sue basi nella logica matematica,e stata estesa tramite un datapath dagli

studi di Daniel D. Gajski [2].

1.1.3 Macchine a Stati Finiti con Datapath

Il trattamento di informazione tramite le semplici FSM puo incontrare varie diffi-

colta dovute alla specifica natura di queste macchine. Per esempio, non vie altra

memoria se non i registri di stato (come si puo vedere dalla Figura1.1), per cui

e difficile memorizzare dati in grande quantita. Inoltre, e difficile capire come

far compiere operazioni matematiche all’automa tramite le sole transizioni. Per

ovviare a questi ed altri problemi il modello delle FSM viene esteso5 tramite un

datapath. Si giunge dunque alle macchine a stati finiti con datapath. L’esten-

sione in questione prevede di aggiungere un datapath, inclusivo di registri, il cui

contenuto viene elaborato e confrontato da una logica combinatoria.

Formalmente la FSMDe quindi definita [2] come una FSM, cui si aggiungono:

• Un insieme di variabiliV, che definisce lo stato del datapath, specificando

tutti i valori di tutte le variabili.

• Expr(V) = K ∪ V ∪{(ei � ej) | ei , ej ∈ Expr, dove� e un operatore

accettabile} (abbiamo definito le espressioni computabili dal datapath sui

dati dei suoi registri)

• STAT= {statk = ei 4 ej | ei , ej ∈ Expr(V), dove4 e un comparatore

valido, ossia4 ∈ { <, >, ≤, ≥, =, 6= }}. In pratica abbiamo definito

i confronti eseguibili dal datapath sui dati contenuti nei suoi registri, detti

segnali di stato.

Si e dunque definito un formalismo che permette implicitamente di specifi-

care macchine nelle quali una FSM controlla le operazioni da eseguire su una

5Cio e dovuto a Gajski. Si veda [2]

7


Figura 1.4: Schema di Finite State Machine with Datapath.

memoria. Si noti che le operazioni eseguite sui dati non vengono descritte nel

dettaglio. Questo tipo di progettazione, detta ancheregister transfert design, non

si concentra infatti sui dettagli deldesignlogico, bensı sulla funzionalita.

Detto questoe possibile suddividere la FSMD, nelle sue due componenti prin-

cipali: il controllore ed il datapah (si veda Figura1.4), per ognuna delle quali

si separano gli ingressi dalle uscite e le funzioniδ e λ tra le due componenti.

Formalmente questa suddivisionee operata nel seguente modo:

• I = Ic × Id , doveIc sono gli ingressi del controllore eId sono gli ingressi

del datapath.

• U = Uc × Ud , doveUc sono le uscite del controllore eUd sono le uscite

del datapath

Data la funzionei stato prossimoλ: (Q x V) x I → Q × V otteniamo

• λc : Q × Ic × STAT → Q, dove STAT sono i Segnali di Stato

• λd : Q × V × Id → V ( ed λd := λDi : V × Id → V : Vj = ej |Vj ∈ V, ej ∈ Expr(V × Id))

Data la funzione di uscitaδ:

8


• δc : Q × Ic × STAT → Oc

• δd : Q × V × Id → Od

Questa macchinae stata quindi divisa in due parti distinte, datapth e con-

trollore. Il datapath opera, a richiesta del controllore, operazioni aritmetiche o

logiche sui dati contenuti nei registri. Quando calcola funzioni, scegliendole in

base aisegnali di controllo, sfrutta una parte di logica (multiplexers e demulti-

plexers rispettivamente MUX e DEMUX) che gli permette di leggere e scrivere

nel registro corretto. Quando invece opera confronti su variabili, utilizzando sem-

pre multiplexers, compara i dati corretti e segnala il risultato al controllore.

Il controllore invece comanda il datapath mediantesegnali di controllo, ricevendo

risposte tramite i segnali di stato.

In sintesi il controllore istruisce il datapath sulle operazioni da effettuare sui dati,

calcolando mediante una FSM quali operazioni sono opportune.

Si fa notare chee possibile utilizzare architetture con piu di un controllore e

datapath, e chee anche possibile riscrivere il controllo in dati e viceversa, ovvero

la distinzione Dati/Controlloe sempre opzionale.

Fissata questa formalizzazione, si necessita di un metodo descrittivo per le

FSMD. La descrizione di algoritmi tramite ASMe la soluzione a questa necessita.

1.1.4 Diagrammi ASM

Gli Algoritmic State Machine charts(o diagrammi ASM) sono uno strumento ca-

pace di descrivere il designregister transfert, astraendo dalla suddivisione in con-

trollore e datapath. Una volta creato un diagramma ASM, partendo da un algo-

ritmo e poi possibile estrarre da questo un cosiddettodiagramma a blocchi, che

permette di separare controllore e datapath, ed individuare gli stati del primo.

Un diagramma ASM fa uso di due fondamentali tipi di box6, piu uno opzionale,

connessi da frecce, che rappresentano il flusso di esecuzione.

6Viene utilizzato il termineboxin quanto il terminebloccopuo creare confusione con i blocchi

delblock diagram

9


Tipo di Box Rappresentazione della Box

State

Decision

Tabella 1.1: Tipi fondamentali di box in un diagramma ASM, con esempio

I due tipi fondamentali di box sono lestate boxe ledecision box, illustrate in

Tabella1.1.

Le state boxeseguono incondizionatamente una o piu operazioni. Sono rapp-

resentate da un rettangolo contenente le istruzioni da eseguire, dal quale esce una

ed una sola freccia, in quanto labox da eseguire successivamentee fissata. E’

permesso eseguire un numero arbitrario di operazioni contemporanee, a patto di

rispettare la regola dell’assegnamento singolo, ossia:

Un registro puo essere assegnato soltanto una volta in una stessa

state box.

Le decision box7 servono a scegliere quale box sara eseguita successivamente

basandosi sull’ingresso e sullo stato presente. Queste box si rappresentano come

un rombo, all’interno del quale presente il TEST da eseguire, con due frecce

etichettate con T ed F che rappresentano i possibili risultati del test.E possibile

utilizzare solamente lo stato e l’ingresso presente al ciclo corrente. Oltre alla rap-

presentazione riportata in Tabella1.1, che equivale ad un test a risultato binario,

sono (piu raramente) utilizzate anchedecision boxche rappresentano il costrutto

CASE, per cui hanno piu di due frecce uscenti. In questo caso, laboxe rappresen-

tata tramite un esagono. Nel presente lavoro di tesi non si fara pero uso didecision

boxa piu uscite.

7La notazione alternativaconditional, riportata da alcuni testi, non sara utilizzata in quanto

crea confusione con leconditional output box.

10


Le duebox descritte fin’ora sono quelle necessarie e sufficienti a descrivere

correttamente una macchina di Moore. Le macchine di Mealy invece, fanno uso di

un’ uscitacondizionata, ovvero possono eseguire o no operazioni in un certo stato

in base all’ingresso della macchina (e non solo allo stato stesso). Per supplire a

questa mancanza, i diagrammi ASM introducono le cosiddetteconditional output

box, o condition box, rappresentate in Tabella1.2.


Condition

Tabella 1.2: Condition Box, con esempio

In questebox, a cui si applica la stessa restrizione dell’assegnamento singolo

valida per lestate box, le istruzioni vengono eseguite soltanto nel caso si trovino

nel ramo di uscita attivo della decision box8 presente9 nello stesso stato. Sono

rappresentate tramite un rettangolo dagli angoli smussati, con una ed una sola

freccia di uscita.

La box iniziale e quella finale di un diagramma ASM formalmente non ven-

gono indicate con nessuna notazione particolare, infatti si possono dedurre dal

contenuto delleboxe dalla topologia del grafo, in quanto l’esecuzione in genere

viene rappresentata come un fluire discontinuo dall’alto verso il basso. Labox

iniziale puo essere indicata tramite una freccia entrante portante l’etichettareset,

ma nella definizione di Gajski questae omessa introducendo unadecision box

nella quale viene testato il valore di una variabileStart. Nel caso iltestdia esi-

to negativo si rimane in questa stessabox, chee anche quella in cui si giunge

al termine dell’esecuzione. Sebbene questa rappresentazione sia utile per la suc-

cessiva traduzione in quantoe piu aderente al VHDL, per non appesantire trop-

po i diagrammi presenti, e per renderli piu facilmente leggibili, si usera un’altra

8Nel caso si tratti di un albero didecision box, si richiede che laconditionalsia a valle di un

cammino che abbia tutti gli archi attivi9Una decision box, come vedremo nelCapitolo 2 puo esistere solo se l’ultima box prima di

quella in questionee unadecision box

11


notazione. Labox iniziale sara indicata dalla freccia portante l’etichettareset,

mentre lo stato finale sara indicato tramite un cerchio contenente una×. Visto

che sie operata questa scelta in modo arbitrario, si consiglia, una volta compre-

sa la metodologia di traduzione, di adottare la notazione di Gajski. Per maggiori

dettagli sulla notazione formale si rimanda in ogni caso a [2].

1.1.5 Blocchi

Una volta terminato il disegno del diagramma ASM e’ possibile tracciare attorno

alleboxdei blocchi, altrimenti dettiblocks, rappresentati da rettangoli tratteggiati,

che permettono innanzitutto di distinguere la parte di controllo dalla parte di data-

path, e secondariamente individuano esattamente gli stati del controllore. Grazie

a queste caratteristiche i blocchi facilitano la traduzione del diagramma ASM in

VHDL. Il tracciamento dei blcchi porta ad un grafo chee talvolta chiamatoblock

diagram.

Figura 1.5: Esempio di blocchi di un diagramma ASM.

12


Quest’operazionee sottoposta ad alcuni vincoli, che fanno sı che la suddivi-

sione in blocchi abbia senso.

• Il grafo deve rappresentare un unico stato prossimo dato uno stato, ed un

insieme di condizioni.

• Ogni percorso, definito dalla rete di Conditional box, deve portare ad un

altro stato.

Da notare che, in base alla seconda condizione si giunge alla regola:

Non e possibile avere retroazione all’interno di un blocco.

Cio significa che non si possono avere cicli all’interno di un blocco, anche se si

possono avere cicli costituiti da un blocco solo, come nell’esempio di Figura1.6.

Figura 1.6: Porzione del diagramma ASM costituita da un ciclo, costruito mediante un

solo blocco.

13


In base alle regole appena enunciatee possibile raggruppare una o piu box al-

l’interno di un blocco. Questi blocchi individuano esattamente gli stati della FSM

inclusa nel controllore. Definito questoe possibile individuare in modo semplice

la distinzione tra controllore e datapath. Questo procedimento sara discusso nel

dettaglio nelCapitolo 3.

Seguono cenni di teoria dei grafi, necessari alla comprensione di vari argo-

menti trattati nel presente elaborato di tesi.

1.2 Grafi e Cammino Critico

Per comprendere il concetto di cammino criticoe utile chiarire l’idea di grafo, piu

precisamente si vuole specificare perche sia necessario, per il calcolo del Critical

Path, l’avere un grafo aciclico, orientato, che abbia un unico nodo iniziale ed un

unico nodo finale. Seguono pertanto le definizioni su cui si basera la trattazione

del caso di studio(Capitolo 4). Saranno inoltre presentate due differenti teorie

che si basano sui grafi: quella della lettereratura tradizionale e quella relativa agli

activity netkorks. Poiche il caso di studio si basa principalmente sulla seconda,

si e preferito sviluppare e approfondire maggiormente questo argomento, anche

supportandolo tramite un esempio.

1.2.1 I Grafi: Notazione e Nomenclatura

Un grafo, ad esempio quello mostrato in Figura1.7, e costituito da un insieme di

nodi (rappresentati come cerchi) collegati da archi (linee che congiungono i nodi).

Se il grafoe orientato, ogni arcoe descritto come una freccia che collega il nodo

di origine al successivo. Piu formalmente:

14


Un grafo, G = (N; A),e una coppia di insiemi: Ne un insieme

finito e non vuoto di elementi, Ae un insieme finito di coppie di ele-

menti distinti di N.

N e detto insieme dei nodi (o vertici), e usualmente viene indicato

mediante i primi n= | N | numeri naturali : N = { 1, 2, ..., n}.

L’insieme A, detto insieme degli archi,e in generale indicato con

A = { a1, a2, ..., am} ( m=| A | ); ogni arco individua una coppia

di nodi, definiti adiacenti. Considerando n come numero dei nodi e m

come numero degli archi, vale la relazione:

0 ≤ m < n2

Figura 1.7: Esempio generico di grafo indiretto.

15


Una sequenza di nodin1, n2, n3, ..., nn forma uncamminodi lunghezza

n− 1 10 se esistono gli archi davi a vi+1 per 1≤ i < n. Un camminoe

semplicese tutti i vertici che lo costituiscono sono distinti.

Ci sono molti tipi di grafi, contradistinti da particolari caratteristiche, in generale

un grafoe :

• sparsose ha pochi archi;

• densose ha molti archi;

• completose ha tutti i possibili archi;

• diretto o orientato (Figura1.8e Figura1.9)

Un grafoorientato, anche detto diretto (D-Graph), viene definito come una

coppia di insiemi:D = (N; A), ove N rappresenta l’insieme dei nodi ed A

quello degli archi fra due vertici per cui vale:

A = (x, y) | x, y ∈ N

• indiretto se none diretto Figura1.7);

• aciclicose non contiene cicli;

• aciclico-diretto o DAG (illustrato in Figura1.10e descritto in seguito).

In un grafo orientato un camminon1, n2, . . . , nn costituisce unciclo se

n ≥ 1 e n1 = nn . Il ciclo e semplice sen2, . . . , nn sono distinti, mentre si

tratta di un autoanello sen = 1 . Per un esempio di grafo con ciclo semplice si

veda la Figura1.9, in cui e evidenziato il ciclo fra i nodi recanti etichette A, C, e

B.

Si definisce unsottografo S= (NS, AS) di un grafoG = (N, A) quando gli

insiemi dei vertici e degli archi archi sono inclusi, rispettivamente, nell’insieme

dei vertici e degli archi del grafo G( NS ⊆ N ∧ AS⊆ A ) e tutti i vertici di

ogni lato presente inAS si trovano inNS.

10Si osservi che la lunghezza del cammino equivale, piu semplicemente, al numero dei nodi

coinvolti

16


Figura 1.8: Esempio di un generico grafo orientato (o diretto).

Un grafo aciclico e orientato, D-A-Graph (DAG), come quello

mostrato in Figura1.10, e un grafo diretto in cui non esistono au-

toanelli o cicli, per cui partendo da qualsiasi nodo none mai possibile

ritornare sullo stesso dopo un numero arbitrario di passi [12].

Qualsiasi tipo di grafo puo esser rappresentato in vari modi. La rappresen-

tazione tramitematrice di adiacenzadi un grafoe costituita da un array bidimen-

sionaleN × N , dove N rappresenta il numero dei nodi del grafo. Ogni elemento

dell’array contiene un valore booleano che indica se l’arco (x, y)11 appartiene al

grafo.

Dato un DAG ed un suo nodo, detto nodo origine,e possibile calcolare il cosid-

dettoTopological Sorto ordinamento topologico. L’ordinamento topologicoe

un modo di creare una partizione all’interno dell’insieme dei nodi. I sottoinsiemi

creati nell’insieme dei nodi rappresentano quelli che vengono definitilivelli del

grafo. Il numero del livello a cui appartiene un nodoe la massima distanza in

11Questa notazione indica un arco generico, specificando la coppia corrispondente al nodo di

partenzax ed il nodo di arrivoy

17


Figura 1.9: Esempio di un generico grafo orientato contenente un ciclo semplice.

archi del nodo in questione dal nodo origine.

Piu approfonditamente, come si puo osservare in Figura1.11 l’unico nodo ap-

partenente al livello 0e il nodo di origine, i nodi appartenenti al livello 1 sono i

nodi che sono figli del nodo origine, e non sono figli di nessuna altro nodo. Ap-

partengono al livello 2 i nodi figli di nodi appartenenti solamente ai livelli 0 ed

1, cioe che hanno almeno un padre appartenente al livello 1, un numero arbitrario

anche nullo di padri del livello 0, e nessun padre appartenente ad altri livelli. Ap-

partengono al livello 3 i nodi con almeno un padre appartenente al livello 2, un

numero arbitrario di padri appartenenti ai livelli 0 ed 1, e nessun padre apparte-

nente ad altri livelli.

Tale procedimento puo essere ripetuto per tutti i nodi del grafo, ossia un nodo

appartiene al livello x se e solo se:

• ha almeno un padre al livellox−1 12

12Per una trattazione piu formale si veda [1].

18


Figura 1.10: Esempio di un generico grafo aciclico e orientato (DAG).

• non ha padri a livelli superiori o uguali ad x

Questa visione dei grafi, frequentemente utilizzata nella progettazione hard-

ware, considera gli archi senza peso di percorrenza, ma solo come unione dei

nodi ede solo una delle possibili visioni che si hanno dei grafi stessi, a seconda

degli usi previsti.

1.2.2 Gli Activity Networks

Un altro punto di vista, sviluppato soprattutto nell’ambito della ricerca operativa,

ma molto frequente anche nella gestione aziendale, prevede di assegnare i valori

delle attivita agli archi che congiungono i nodi. I nodi rappresentano quindi degli

stadi intermedi (fatta eccezione per il nodo iniziale e quello finale) che servono

esclusivamente a definire le precedenze.

Considerando ad esempio gliActivity Networks 13, si ottiene ilgrafo delle prece-

denze delle attivita, in cui:

13Gli Activity Networks sono grafi, utilizzati in economia, nei quali gli archi rappresentano le

attivita da compiere per concludere un progetto. I nodi si chiamano eventi e rappresentano l’inizio

o la fine di una attivita . L’inizio del progetto coincide col nodo iniziale, mentre la fine con il nodo

finale.

19


Figura 1.11: Esempio di livelli del grafo ordinati secondo un ordinamento topologico .

• I vertici rappresentano eventi, cioe istanti in cui accade qualcosa (es. inizio

o fine di un’attivita);

• Gli archi rappresentano le attivita del progetto;

• Gli archi tratteggiati rappresentano attivita fittizie, cioe di durata nulla (con

peso zero, ndr) che vengono introdotte per rappresentare delle precedenze;

• Il vertice iniziale indica l’inizio del progetto, il vertice terminale, la fine.

Si consideri ad esempio un progetto definito da quattordici attivita (da A a P), le

cui durate sono definite nella Tabella1.3, insieme alle relazioni di precedenza tra

le varie attivita stesse.

20


Attivit a Durata Predecessori

A 1 -

B 3 -

C 1 -

D 3 A

E 5 B

F 10 B

G 1 C

H 2 C

I 3 H

L 5 D, E

M 1 D, E

N 5 F, G

O 5 I

P 7 L, O

Tabella 1.3: Attivita del progetto in esempio

Utilizzando le convenzioni degli Activity Networks,e possibile disegnare il

grafo delle precedenze fra attivita, come mostrato in Figura1.12, appunto par-

tendo dalla tabella in esame.

Questa nuova rappresentazione rende un’ampia visione d’insieme ede facilmente

comprensibile. Si osserva infatti che il nodo0 e iniziale, il nodo9 e finale e rapp-

resenta la conclusione del progetto, da cui deriva che l’ultima attivita completata

sara appunto laP, mentree necessario svolgere innanzitutto le attivita A, B e C

che possono esser eseguite anche contemporaneamente, in quanto sono del tutto

indipendenti fra loro.

21


Figura 1.12: Esempio di unActivity Networks, corrispondente ai valori della Tabella1.3.

Infine, dal grafo (cosı come dalla tabella delle precedenze)e comunque pos-

sibile visualizzare lamatrice delle adiacenze14, Tabella1.4, per gli activity net-

works. A differenza della tradizionale matrice di adiacenza, ogni elemento del-

l’array non contiene un valore booleano, bensi’ il reale peso dell’arco sotteso fra

i due nodi corrispondenti. Si usa poi uno speciale carattere (nell’esempioe : ’-’)

per indicare l’assenza degli archi.

L’importanza degli Activity Networks, soprattutto nel campo gestionale-ma-

nageriale, risulta molto evidente anche per la relazione di questi con le tecniche di

programmazione applicate ai progetti per la gestione dei tempi, come i diagrammi

di Gantt e Pert.14La matrice di adiacenzae solo una delle possibilita di rappresentare un grafo.E nota infatti

anche lalista di adiacenza, in cui ad ogni nodo viene associata la lista dei successori, per un grafo

diretto. Questa risulta comunque piu efficiente per grafi sparsi, in quanto memorizza solo gli archi

realmente occupati.

22


0 1 2 3 4 5 6 7 8 9

0 - 1 3 1 - - - - - -

1 - - - - 3 - - - - -

2 - - - - 5 - - 10 - -

3 - - - - - - - 1 2 -

4 - - - - - 5 - - - 1

5 - - - - - - - - - 7

6 - - - - - 5 - - - -

7 - - - - - - - - - 5

8 - - - - - - 3 - - -

9 - - - - - - - - - -

Tabella 1.4: Matrice di adiacenza del grafo di Figura1.12, derivante dalla Tabella1.4

Il diagramma di Gantt e uno strumento di scheduling e di controllo, in cui ven-

gono rappresentate le attivita che costituiscono il progetto attraverso delle barre

aventi lunghezza proporzionale alla durata della singola attivita. Queste attivita

vengono disposte parallelamente all’asse orizzontale, il quale rappresenta il ca-

lendario di progetto.

Il diagramma di Pert e invece una tecnica di modello reticolare che consente

di costruire un modello operativo di un progetto e cerca di sopperire alle lacune

del diagramma di Gantt. La conversione di un progetto in un diagramma di Pert si

basa sulla stesura dell’elenco delle attivita , ordinato con criteri di precedenza sulla

loro analisi a seconda che precedano o seguano immediatamente un determinato

lavoro oppure che possano avvenire in parallelo. In quanto modello reticolare,

il diagramma di Pert esplicita quindi le relazioni di interdipendenza fra le oper-

azioni elementari, solitamente basandosi sulla tipologia15 Finish to Startper cui

15Le relazioni di dipendenza precedenza possono essere di quattro differenti tipologie: Finish to

Start, Finish to Finish, Start to Start e Start to Finish, in cui il primo termine si riferisce all’attivita

23


l’attivit a di partenza deve finire prima di iniziare quella di arrivo. In particolare il

diagramma di Pert evidenzia tutti gli eventi e le attivita, posti in sequenza logica

e visualizzati tramite una rete, e permette di focalizzare gli sforzi principali e di

valutare l’effetto di eventuali cambiamenti sul progetto. Nel diagramma di Pert,

proprio come negli Activity Network, i rami (o linee) rappresentano le attivita ,

mentre i nodi (o cerchi) gli eventi. [10]

1.2.3 Il Cammino Critico

La ricerca del percorso massimoe un problema chee stato ampiamente studia-

to, insieme al suo duale, nell’ambito della ricerca operativa, ede disponibile

un’ampia trattazione teorica con la rispettiva documentazione.

Il cammino critico, o Critical Pathe l’insieme dei nodi critici (cioe quei nodi

che vincolano il tempo di esecuzione16) che costituiscono uno dei possibili per-

corsi di un grafo. Esso viene spesso utilizzato per determinare la durata minima

di un progetto. Visto che al completamento del progetto, tutte le attivita devono

esser state eseguite, nel rispetto delle precedenze, ogni cammino dal nodo di inizio

del progetto al nodo di fine determina una durata al di sotto della quale il proget-

to non puo essere completato. Il metodo del cammino critico individua quindi il

cammino piu lungo del grafo, cioe che possiede la piu alta sommatoria dei pesi

degli archi.

Per calcolare il cammino critico si richiede in genere la precondizione che il

grafo in esame non contenga cicli ne autoanelli, in quanto gli algoritmi di anal-

isi su tali grafi potrebbero non terminare mai, cosı comee necessario che ogni

grafo sia caratterizzato da un solo inizio e da una sola fine, congiunte in modo

sequenziale attraverso vari cammini fra i nodi intermedi17. Questi cammini pos-

di partenza, mentre il secondo a quella di arrivo.16Per una definizione piu rigorosa di cosa sia un nodo critico si faccia riferimento al paragrafo

successivo.17Teoricamentee possibile separare un grafo con piu uscite e/o ingressi in piu grafi distinti e

successivamente calcolare il cammino critico dei sottografi risultanti, oppure aggiungere due nodi

al grafo per unire eventuali inizi o fini multiple, ma queste possibilita , in modo conforme con gli

24


sono essere fra i piu svariati, mae sempre possibile suddividere l’intero grafo in

livelli. Ogni nodo puo quindi essere eseguito se e solo se sono state risolte tutte

le sue precedenze e il nodo terminale sara l’ultimo ad esser svolto. Queste prece-

denze forniscono anche un’idea del tempo di esecuzione: i nodi di un livello (ad

eccezione del nodo radice) possono cominciare la loro esecuzione solamente se

sono stati completati tutti i loro padri, ossia tutti i nodi che li precedono, situati

nei livelli precedenti.

In Figura1.13e illustrato il grafo aciclico e orientato di Figura1.10, a cui vengono

aggiunti i pesi sugli archi e su cui viene evidenziato il cammino critico.

Figura 1.13: Grafo aciclico e orientato (Figura1.10) a cui sono stati aggiunti i pesi sugli

archi e su cuie evidenziato il camino critico.

E innanzitutto necessario precisare che ogni grafo deve avere almeno un nodo

critico, tre, se si contano anche il nodo di inizio ed il nodo di fine, e puo anche

avere tutti i nodi critici. Dualmente, esiste almeno un cammino critico per ogni

grafo, ma la cardinalita puo esser anche maggiore, fino al caso limite di grafi nei

quali ogni percorso dall’inizio alla finee critico, Viene per questo motivo indivi-

duato ilsottografocostituito esclusivamente dai nodi critici, cosicche sia possibile

activity list, non verranno analizzate.

25


estrarre successivamente tutti i percorsi.

Data un’attivita, per ridurre il tempo di esecuzione, ovvero per aumentare le

prestazioni di ogni rete basata su grafi,e necessario individuare il percorso piu

lento, chiamato appunto percorso critico , in quanto solo diminuendo il tempo

di esecuzione del cammino critico diminuisce il tempo di esecuzione dell’intero

grafo.

26


Ricerca del Cammino Critico

I nodi critici, ossia i nodi che appartengono al sottografo critico, sono tutti

quei nodi in cui il tempo massimo di esecuzione coincide con il tempo minimo.

Risulta quindi necessario determinare entrambi i tempi di esecuzione per ogni

nodo. Loscheduling e l’operazione che determina l’istante in cui parte l’ese-

cuzione delle attivita in un dato grafo diretto. Piu formalmente, dato un grafo

orientato D=(N; A), la soluzione del problema del calcolo del valore di schedu-

ling richiede che il tempo d’inizio di un’operazioneti sia almeno lungo quanto

il tempo di inizio t j di ognuno dei suoi predecessori diretti, piu il suo ritardo di

esecuzione, cosı come mostra la seguente relazione:

ti − t j + di j , ∀ i, j | (ni , n j) ∈ N

in cui ti e il tempo del nodo che rappresenta l’evento inizio di una determinata

attivita, t j rappresenta il tempo necessario affinche sia teminata l’esecuzione del-

l’attivit a precedente, mentredi j indica la durata dell’attivita intermedia che con-

giunge i due vertici i e j presi in analisi.

Il metodo per la ricerca del sottografo critico opera in due fasi:

• nella prima si etichettano i vertici a partire dal nodo di origine, seguendo la

direzione delle precedenze, per individuare l’istante minimo di ogni evento,

quindi l’istante minimo di inizio di ogi attivita , da qui detto comeTMIN

(Tempo Minimo);

• nella seconda fase si etichettano i vertici a partire dalla fine del proget-

to, seguendo gli archi nel verso opposto delle precedenze, per determinare

l’istante massimo di accadimento di ogni evento, cioe l’istante massimo di

completamento delle attivita, da quiTMAX (Tempo Massimo).

Entrambe le fasi etichettano quindi i nodi che rappresentano il termine di un’attiv-

ita o l’inizio di quella successiva, assegnando ad ognuno due valori: sia il tempo

minimo che quello massimo. In altri termini, il tempo minimo indica il tempo

necessario che permette l’inizio dell’attivita , al di sotto del quale none possibile

scendere in quanto non sono state ancora risolte tutte le precedenze. Esso viene

determinato dal seguente algorimo (Figura1.14):

27


Figura 1.14: Frammento di algoritmo relativo al calcolo del tempo minimo nella ricerca

del cammino critico.

Il tempo massimo, che rappresenta il problema duale, determina invece il mas-

simo intervallo di tempo dopo di cui non puo piu cominciare l’attivita senza creare

ritardi nel progetto stesso. L’algoritmo relativo al tempo massimoe il seguente

(Figura 1.15):

Figura 1.15: Frammento di algoritmo relativo al calcolo del tempo massimo nella ricerca

del cammino critico.

Si definiscemobilit a di un nodo l’intervallo di tempo derivato dalla differen-

za fra il tempo massimo e il tempo minimo. Un’attivita puo incominciare in un

qualsiasi istante compreso nell’intervallo di tempo fra il tempo minimo che la

caratterizza e il rispettivo tempo massimo, quindi per tutto l’arco di tempo defini-

to dalla mobilita, senza che venga modificata la durata del progetto. Quando la

28


mobilita e nulla, ossia quando i due valori TMin e TMax coincidono, si tratta di

un’attivita il cui nodo che indica l’evento inizialee critico.

29


Algoritmo CPM ( N, A, n0, nN, d, tMin, tMax, LC)

ingresso: grafoDAG=(N, A); nodo origine n0; nodo finale nN;

durate di j≥ 0,∀(i, j) ∈ A;

uscita: istanti minimoemassimodi accadimento di ogni evento;

lista contenente inodi critici LC;

Figura 1.16: Algoritmo relativo al calcolo del cammino critico.

30

Capitolo 2

Metodologia

Nel presente capitolo si presenta dettagliatamente la metodologia proposta, sud-

dividendo le operazioni da compiere in due fasi distinte. Le fasi vengono quindi

analizzate mostrando come, partendo dalla specifica ad alto livello ed utilizzando

la prima, sia possibile tradurre la specifica stessa in un diagramma ASM, e come

applicando la seconda fase sul diagramma ASM ottenuto si operi una traduzione

per giungere fino alla descrizione VHDL. Quest’analisi viene compiuta mostrando

approfonditamente il modo di operare e le specifiche scelte metodologiche.

2.1 Introduzione

Sfruttando studi di Gajski[2] si e sviluppata una metodologia che cerca di forma-

lizzare e semplificare lo sviluppo di Sistemi Embedded. Attraverso la metodologia

trattata si divide lo sviluppo di un IP core nelle due seguenti fasi:

• Traduzione dell’algoritmo dal linguaggio di alto livello in un diagramma

ASM;

31

CAPITOLO 2. METODOLOGIA

• Traduzione del diagramma ASM in VHDL.

La linea di demarcazione tra le due fasie piuttosto netta, cio significa che, una

volta tracciato il diagramma ASM e passati alla seconda fase, none piu necessario

tornare sui propri passi e modificare l’algoritmo di partenza. Questo a patto di

non aver compiuto sostanziali errori durante la definizione dell’algoritmo di alto

livello o nella prima fase di traduzione. Il flusso di progetto proposto, chee una

versione semplificata e riadattata del flusso a cascata di sviluppo del software,e

chiarito dalla Figura2.1.

2.2 Preliminari

La creazione di un IP core parte da una specifica1 del problema da risolvere, sulla

quale sia stata fatta una analisi di fattibilita. Questa fase esula dalle tematiche

del presente testo, e pertanto non verra affrontata. Si puo dire quindi che la base

per l’applicazione della metodologiae una definizione di qualche tipo dell’algo-

ritmo da tradurre. I requisiti per questo algoritmoe che sia corretto e definito

in modo preciso e possibilmente formale. Queste necessita sono dovute al fatto

che una cattiva definizione(o ancor peggio l’utilizzo di un algoritmo scorretto),

se diagnosticata in modo tardivo, porta ad un grave costo in termini di tempo di

sviluppo. Per avere buone probabilita di soddisfare le caratteristiche richieste si

consiglia di definire l’algoritmo tramite un linguaggio di programmazione a pro-

pria scelta. Sie infatti rilevato che questo, formalizzando l’algoritmo, facilita

lievemente l’applicazione della metodologia.

I diagrammi ASM rappresentano un passaggio fondamentale intermedio della

1Per quanto riguarda la formalizzazione di specifiche si rimanda ai testi di informatica

teorica[1].

32


Figura 2.1: Flusso della metodologia di traduzione proposta nel presente elaborato.

33


metodologia, situandosi tra la specifica in linguaggio di alto livello, o ancor peggio

in pseudocodice o linguaggio naturale e il livello della descrizione in VHDL.

La traduzione di un algoritmo corretto, preciso e ben formalizzatoe un’opera-

zione semplice che permette di costruire diagrammi ASM partendo direttamente

dallo (pseudo)codice dell’algoritmo dato.

2.3 Prima Fase: Traduzione dell’algoritmo di parten-

za in un diagramma ASM

Rileggendo sequenzialmente il codice ed analizzandolo in un’ottica di basso li-

vello si incontrano sempre tre tipi di strutture, chiamate ASM box:

• state box;

• decision box;

• condition box.

Esempi diASM boxriportati in Tabella2.1.

Le ASM boxillustrate, che sono strutture sufficienti a descrivere qualunque

algoritmo computabile, corrispondono nei diagrammi ASM ad altrettante box.

Quindi la semplice ma delicata fase di stesura del diagramma ASM equivale ad

una approfondita analisi dell’algoritmo, la quale riconosca queste box all’interno

dell’algoritmo. E’ cioe necessario analizzare lo (pseudo)codice di partenza, e

trasformarlo in una rete composta unicamente dalle semplicissime treASM box

rappresentate in Tabella2.1. I tre paragrafi presentati di seguito spiegano come

tradurre strutture algoritmiche inASM box.

2.3.1 State box

Una qualunque parte di codice che esegua operazioni o assegnamenti, e non in-

cluda alcun test o confronto (come{ <, >, ≤, ≥, =, 6= })fa uso dellestate box.

E dunque semplice inserire le istruzioni presenti nell’algoritmo nel diagramma

34



State

Decision

Condition

Tabella 2.1: Tipi di box in un diagramma ASM con esempio

ASM, in quanto l’unico vincolo presentee la regola dell’Assegnamento Singolo,

che riportiamo:

Un registro puo essere assegnato soltanto una volta in una stessa

state box.

E da notare comunque che, per quanto si possa scrivere un qualunque numero

di istruzioni da eseguire contemporaneamente in unastate box, e spesso sconsi-

gliabile inserirne un numero eccessivo. Infatti spesso inserirestate boxcompren-

denti molte istruzioni, magari ciascuna composta di molte operazioni elementari2

nel diagramma ASM puo generare alcuni poblemi di traduzione in seguito. Questo

puo essere ovviato nella seconda fase proposta dalla metodologia (che fornisce un

metodo per tradurre il diagramma ASM in VHDL) riadattando leggermente il

diagramma ASM dividere le istruzioni presenti in una sola box tra piu box distin-

te. Nonostante questoe possibile eliminare il problema a monte suddividendo in

modo critico le istruzioni nellestate box. Bisogna quindi ricordare che esistono

2Operazioni elementari possono essere, ad esempio,+, −, ×, ÷, oppure il valore assoluto

35


vincoli non stretti a cio chee consigliabile inserire in un singolostate box, dettati

da considerazioni riguardanti l’hardware che viene in seguito prodotto.

Eseguiren operazioni semplici in parallelo richiede che sia disponibile fisica-

mente l’hardware necessario ad eseguiren operazioni. Questo aumenta le presta-

zioni temporali del dispositivo (si ha un tempo di esecuzionen volte inferiore al

tempo necessario ad eseguire len operazioni in serie) ma spesso, per diminuire

l’area necessaria a realizzare il dispositivo (e quindi il suo costo di produzione),

si preferisce utilizzaren volte lo stesso hardware. Eseguire invece istruzioni

complesse, come ad esempio il calcolo di una espressione composta da molti

operatori algebrici (oltre a necessitare dello spazio necessario ad implementare

tutte le operazioni in hardware), fa sı che il tempo necessario ad eseguire l’oper-

azione sia pari al tempo di esecuzione del percorso critico del grafo corrispondente

all’espressione algebrica.

Volendo implementare in unostate boxle seguenti istruzioni, e ponendo per

semplicita il costo (temporale e spaziale) dell’implementazione di ogni operatore

pari ad1

a = (b×5)+(c/(d×e))

h = 3+b

otteniamo il diagramma in Figura2.2(riquadroA), cui corrispondono le seguen-

ti caratteristiche:

• Un tempo di esecuzione pari a 3 (cioe il numero di livelli del grafo che

rappresenta l’equazione piu complessa).(Si veda Figura2.3)

• Un costo spaziale pari a 5, cioe pari al numero di operatori utilizzati:×, +, /, ×, +.

Scorporando invece lostate Boxin piu state boxsemplici, come mostrato nel

riquadroB della Figura2.2Possiamo avere:

• un tempo di esecuzione pari a 5 (cioe pari al numero di operazioni elemen-

tari da eseguire).

36


Figura 2.2: Due delle possibili alternative nella creazione di State box.

• Un costo spaziale pari a 3, cioe pari al numero di operatori differenti utiliz-

zati (+ ,∗ ,/ ), infatti si ipotizza di riutilizzare gli operatori.

In conclusione, per quanto inserire istruzioni dell’algoritmo di partenza nelle

state boxpossa sembrare estremamente semplice, per generare un diagramma

ASM eccellentee necessario saper guardare oltre la traduzione meccanica, tenen-

do conto delle problematiche della futura implementazione in hardware. Questo

puo significare anche mettere mano ad alcune scelte precedenti, cioe potrebbe

essere necessario rivedere leggermente la specifica di alto livello, per adattarla.

2.3.2 Decision box

Le strutture algoritmiche che comprendono test generano decision box. Portia-

mo come esempio due strutture, tra le piu comuni nella descrizione di algo-

ritmi: la struttura secondizione allora. . . altrimenti. . . e la strutturafinche

condizione ripeti . . ..

secondizione allora . . . altrimenti . . .

Facendo riferimento alla seconda riga in Tabella2.1, dovee presentata una

decision box, si puo notare chee immediato tradurre un costruttose condizione

37


Figura 2.3: Livelli di operazioni effettuate.

. . . allora in una condition box. Infatti l’esempio riportatoe la traduzione in

diagrammi ASM dello pseudocodice seguente:

se (jncnr>0) allora

"segui il ramo in basso"

altrimenti

"segui il ramo a destra"

end se

finchecondizione ripeti . . .

Se la traduzione del costruttosecondizione . . . allora e banale, anche volen-

do tradurre la porzione di pseudocodice seguente, corrispondente ad un costrutto

finche condizione ripeti . . . non si incontrano comunque grandi difficolta.

Infatti:

finch e (z=0) ripeti

codice

end finch e

viene tradotto nella parte di diagrammi ASM in Figura2.4.

38


Figura 2.4: Esempio di traduzione del costrutto:finche condizione ripeti. . . .

Risulta chiaro che osservando l’algoritmo, ed inserendo una decision box, ogni

qual volta si incontra un test, si puo costruire la struttura del grafo ASM.

2.3.3 Condition box

Le condition boxsono un particolare tipo distate box, le quali sono inserite in

cascata adecision box. Quindi conditione state boxricoprono lo stesso ruolo, e

le condition boxsono opzionali. Lecondition boxsono necessarie per avere una

corrispondenza forte tra diagrammi ASM e macchine di Mealy ed inoltre, come

sara spiegato successivamente, servono a ridurre il numero degli stati del control-

lore3. Se non vengono usate maiconditional box, la macchina risultante sara una

macchina a stati di Moore, altrimenti, se nee presente almeno uno, risultera una

macchina a stati di Mealy4.

In generale, volendo descrivere un algoritmo con una macchina di Mealy,e

consigliabile inserire in unacondition boxle istruzioni che nell’algoritmo ad alto

3Come detto nel Capitolo 1, i blocchi che vengono successivamente tracciati nel diagramma

ASM rappresentano gli stati del controllore4Ogni macchina di Mealy, puo essere trasformata in una di Moore (e viceversa). Risulta quindi

di semplice comprensione il fatto che si possa fare a meno di utilizzareconditional boxper la

descrizione di un qualsiasi algoritmo

39


livello seguono unadecision box, in quanto questo facilita l’applicazione delle fasi

successive descritte nel presente capitolo.

40


Viene illustrato brevemente un esempio di come tradurre alcune strutture (che

verranno chiamate d’ora in poimacrostrutture), presenti in descrizioni in alto

livello di algoritmi, le quali generano nel diagramma AMS reti composte da un

discreto numero dibox.

2.3.4 Macrostrutture

Per mostrare in modo piu approfondito la traduzione, si descrive dettagliatamente

come tradurre una struttura comunemente usata nella descrizione di algoritmi (sia

tramite linguaggi di programmazione sia in descrizioni meno formali, come lo

pseudocodice): il ciclo per i da a a b ripeti . . . (in vari linguaggi viene chia-

mato for ). Una struttura di questo tipo (considerandoa e b costanti) necessita

di:

• Un variabile (o registro) per memorizzare il valore dell’indicei

• Un assegnamento del valorea ad i all’inizio dell’esecuzione, da tradurre in

unastate box.

• Un confronto da eseguirsi ogni ciclo per controllare il che il valorei sia tra

gli estremia eb, da tradurre in unadecision box.

• Un operatore di incremento (++) che modifichi il valore dii, da tradurre in

unastate box.

Inserendo questi elementi in maniera opportuna si ottiene il diagramma ASM

di Figura2.5.

2.3.5 Blocchi ASM, o ASM blocks

Una volta creato il diagramma ASM posizionando le varie box in modo corretto,

e necessario passare ad una successiva fase nella quale si opera una partizione

dell’insieme delle box, raggruppando le box inblocchi(o blocks). Questi blocchi,

dotati di una struttura generale fissa illustrata in seguito, permettono di individuare

gli stati del controllore.

41


Figura 2.5: Esempio di traduzione di ciclo.

La struttura dei blocchi

Come illustrato in Figura2.6, la prima box che puo presentarsi in un blocco,e

unastate box. La presenza di unastate boxall’ingresso di un bloccoe opzionale, e

non vi puo mai esserne piu di una in ogni blocco.5 Collegata alla freccia uscente

dallastate box(se presente), o come primabox(nel caso non vi sia unastate box)

vi puo essere unadecision box. Questa puo essere seguita in cascata da una rete

di altredecision box. In uscita alla la rete didecision box(se presente), per ognuna

delle frecce uscenti dalla rete puo esserci una ed una solacondition box.

Queste erano le regole di disposizione dellebox per un blocco valido, oltre a

queste, esiste una regola che riguarda le frecce.

Non possono esserci frecce che entrano nel blocco se non nella

primabox.

In base a questo non puo esserci retroazione all’interno di una box, cioe una

5Se infatti ne fosse presente piu di una si potrebbero avere piu assegnamenti concorrenti alla

stessa variabile, il che none consentito, in quanto lo stato della variabile assegnata in questa

situazione sarebbe sconosciuto.

42


Figura 2.6: Esempio di blocco generico

freccia che parte da una Box del blocco deve necessariamente uscire dal blocco

stesso6.

In base a queste regole, e cercando di diminuire il piu possibile il numero dei

blocchi (per diminuire la complessita del controllore),e possibile individuare tutti

i blocchi di un diagramma ASM. Come esempio di blocco si veda Figura2.7 ,

per un esempio di diagrammi ASM in cui sono stati individuati i blocchi, si veda

l’Appendice. E da notare che in questa fasee possibile decidere, per alcune con-

figurazioni di grafo, se incorporare unastate boxin un blocco precedente (come

ordine di esecuzione), trasformandola in unacondition box, o viceversa. Questo

spostamentoe illustrato nella Tabella2.2

Effettuate le operazioni descritte nella Sezione precedente si ha un diagramma

(il diagramma ASM), che descrive in modo facilmente interpretabile l’algoritmo

6Al massimo puo rientrare nellaprima boxdel blocco

43


Figura 2.7: Esempio di blocco costituito da trebox, corrispondente allo stato S3

dal quale sie partiti. Nonostante la sua semplicita, si vedra in questa sezione come

il diagramma ASM comprenda nella sua descrizione alcuni dettagli dai quali si

puo facilmente dedurre la specifica VHDL.

2.4 Seconda Fase: Traduzione del diagramma ASM

in specifica VHDL sintetizzabile

Una volta creato il diagramma ASMe necessario analizzarlo e comprendere come

verra implementata la rete logica che lo realizza. Il diagramma ASM, corrisponde

ad una rete composta da tre parti fondamentali.

• Un controllore, che gestisce lo stato corrente, include ledecision boxe

calcola lo stato prossimo in base allo stato corrente e agli ingressi.

• Un processo, che cambia lo stato presente nello stato prossimo.

• Uno o piu processi7 che eseguono le computazioni necessarie, ed imple-

mentano glistateed idecision box.

7Questi processi rappresentano il datapath.

44


Tabella 2.2: Lo spostamento di unabox da un blocco all’altro. In questo modo lastate

boxdiventa unacondition box

2.4.1 Traduzione dastate boxa VHDL

Ogni state boxviene tradotta in una rete logica combinatoria che fa parte di un

processo (o costituisce lei stessa un processo) e viene eseguita solo e soltanto in

funzione dello stato corrente. La descrizione VHDL avra quindi una struttura fissa

di questo tipo:

Datapath1 : process (clk)

begin

if (clk’event AND clk=’1’) then

case current_state is

when Q0 =>

<codice>

when Q1 =>

45


<codice>

when others =>

<codice>

end case;

end if;

end process Datapath1;

Processo che esegue a seconda dello stato corrente, le istruzioni contenute nella

state box opportuna.

Questo processo controlla le operazioni da effettuare a seconda dei vari stati.

E possibile inizialmente creare un numero di processi pari al numero di variabili

utilizzate. Cosı si ha un processo per ogni variabile che si occupa degli asseg-

namenti ad essa. Non c’e mai pericolo di assegnamenti concorrenti alla stessa

variabile perche gli assegnamenti sono tutti all’interno dei rami di uncasebasato

sullo stato del controllore.

In seguito si puo ottimizzare il codice scritto in tre modi differenti. Due o piu

variabili potrebbero essere usate in intervalli di tempo disgiunti. In questo caso

e possibile assegnare alla stessa memoria variabili diverse, avendo l’accortezza

di ricordare che queste zone di memoria avranno un contenuto con un significato

diverso a seconda dell’istante di tempo in cui sono lette. Questa ottimizzazione,

che viene effettuata talvolta anche nella programmazione software,e dettaregister

sharing, ede stata utilizzata nel caso di studio. Osservando i diagrammi ASM in

Appendice B si puo notare che nel calcolo diTmaxla variabilei, viene utilizzata

con due significati diversi negli stati daS1adS8e daS9aS11.

Una ulteriore ottimizzazione si puo attuare nel caso alcuni dei processi effet-

tuino operazioni solamente durante parte degli stati del controllore. Se gli stati

in cui due o piu processi operano sono disgiunti,e possibile unirli in un unico

processo. Questoe utile a ridurre il numero dei processi, ma puo anche ridurre

46


il la dimensione della parte combinatoria se si riescono a raggruppare processi

che eseguono la stessa operazione su variabili diverse. In questo caso lo strumen-

to di sintesi dovrebbe istanziare una sola copia della rete necessaria a svolgere il

calcolo in questione, e dei multiplexers per scegliere le variabili su cui operare.

Questo permette di ridurre drastiacamente la dimensione della rete logica risul-

tante, e provoca solamente un modesto calo di prestazioni temporali dovuto alla

presenza del multiplexer in serie alla logica operazionale.

2.4.2 Traduzione dadecision boxa VHDL

Le decision box, che corrispondono ad un test, sono incluse nel controllore. I due

effetti possibili di questeboxsono: possono decidere lo stato prossimo e/o attivare

o meno alcuneconditional box. In ogni caso la Decision Box serve a decidere

quale tra due o piu percorsi intraprendere in un diagramma ASM (ovvero: quale

sequenza di operazioni eseguire successivamente). Per la precisione unadecision

box, a differenza delle altre box, oltre ad avere una o piu frecce entranti, ha piu

di una freccia uscente. Ledecision boxdescrivono indirettamente il controllore

della FSMD. Il controlloree un ottimo esempio di FSM, ede composto da due

processi. Il piu semplice dei due,e di questo tipo:

refresh_state : process (clk,reset, start_in)

begin


if (reset = ’1’) then

current_state<= RESETstate;

elsif (start_in = ’1’) then

current_state <= STARTstate;

else

current_state <= next_state;

end if;

47


end if;

end process refresh_state;

Processo che aggiorna lo stato di una FSMD.

Questo processo fa sı che la macchina a stati del controllore rimanga in uno

stato di reset fino all’invio di un segnale di start (startin), dopodiche fa eseguire

alla macchina ad ogni ciclo di clock la transizione da uno stato allo stato suc-

cessivo. A decidere quale sia lo stato successivoe l’altra parte del controllore.

Si ricordi che i segnali che il controllore invia al datapath dipendono unicamente

dallo stato corrente (se non vi sonoconditional box) e dai segnali dienableche

il controllore setta per pilotare le porzioni di codice derivanti daicondition box.

L’altro processo del controllore ha una struttura del tipo:

48


controller : process(...)

begin

enable_1 <= ’0’;

enable_2 <= ’0’;

enable_3 <= ’0’;


when Q0 =>

next_state <= Q2;

when Q1 =>

if i = 0 then

enable_1 <= ’1’;

next_state <= Q2;

else

next_state <= Q0;

end if;

[........]

when Q2 =>

if A = 0 then

next_state <= Q2;

else

next_state <= Q0;

end if;

end case;

end process controller;

Specifica VHDL di un controllore.

49


Questa parte di codice, a seconda dello stato e della configurazione delle varia-

bili, calcola lo stato prossimo ed i valori dienableper pilotarle; alcune di queste

frecce possono giungere in unaconditional box, che viene dunque eseguita. Per

tradurre tutto questo in VHDL, sempre che si voglia far uso delleconditional box,

si puo semplicemente far alzare un flag di del controllore quando l’uscita dellade-

cision boxporta nellaconditional. Scrivendo poi il processo corrispondente alla

condition box, e sufficiente inserire all’esecuzione la clausola di avere il corrispon-

dente flag di enable alto (ed inserirlo nella sensitivity list). Il processo controllore

e costituito da un costrutto case che, in base allo stato corrente, sceglie quali test8 eseguire, ed in base ai risultati dei test sceglie lo stato prossimo. Inoltre, sempre

in base ai risultati delledecision box, sceglie se e qualicondition boxattivare e

per far sı che vengano eseguite alza i segnali dienable.

2.4.3 Traduzione da Condition Box a VHDL

La traduzione dellecondition box, come accennato,e assai simile a quella delle

state box, solo che esse vengono eseguite non solo in base allo stato corrente, ma

anche in base al segnale (flag) di enablecorrispondente. In questo modo si ottiene

proprio cio che si cercava di implementare: delle istruzioni eseguite in base al

risultato di un test. Segue un esempio di processo di unacondition box.

Sum_a_b : process (clk)

begin



when Q0 =>

sum <= 0;

when Q1 =>

8corrispondenti alle decision box

50


if enable_1 = ’1’ then

Sum <= a + b;

Else Sum <= 0;

end if;

when others =>

sum <= 0;

end case;

end if;

end process Sum_a_b;

Esempio di traduzione di condition box in VHDL.

2.4.4 Testing della periferica, scrittura del driver e integrazione

della periferica

La metodologia proposta mira alla stesura di una specifica VHDL facilmente

sintetizzabile da strumenti software automatici. Una volta giunti a questo, la

metodologia non prosegue oltre: le procedure per la simulazione tramite software

dell’IP core ottenuto, quelle per la scrittura del relativo driver, ed infine quelle per

l’integrazione, sono operazioni che esulano dagli scopi della presente tesi. La-

sciamo ad altri la trattazione di questi argomenti, che oltre ad essere fuori tema, se

inseriti nel presente elaborato, lo vincolerebbero agli specifici strumenti utilizzati.

51

Capitolo 3

Caso di Studio: Il Cammino Critico

Nel corso di questo capitolo si presenta, tramite l’applicazione della metodolo-

gia proposta nelCapitolo 2, la reale implementazione in hardware di un IP core

dedicato al calcolo del cammino critico in un grafo. Nel capitolo, partendo da

una specifica iniziale inC, si cerca di approfondire l’aspetto implementativo del-

la metodologia, illustrando in dettaglio le fasi della traduzione in VHDL per la

creazione di un IP core. L’obiettivoe quello di illustrare in modo piu dettagliato

la metodologia tramite l’analisi critica di tutte le scelte implementative effettuate

per lo specifico caso di studio

In Figura (Figura3.1) si mostrano le fasi principali che caratterizzano il pro-

getto relativo al calcolo del camino critico su un grafo aciclico e orientato. Nel

seguito si presenteranno le aree aplicative, gli strumenti utilizzati e le scelte che

hanno caratterizzato ogni fase del progetto stesso, al fine di fornire un ulteriore

supporto alla spiegazione della metodologia proposta.

52

CAPITOLO 3. CASO DI STUDIO: IL CAMMINO CRITICO

Figura 3.1: Flusso di sviluppo del progetto del calcolo del cammino critico.

3.1 Aree Applicative

Come validazione della metodologia proposta sie scelto di creare una periferica

per il calcolo del cammino critico. Il problema del calcolo del percorso criticoe

di interesse generale, e trova applicazione in un vasto numero di aree, tra cui molti

problemi di ricerca operativa.

Durante lo sviluppo dell’IP core, sie scelto di concentrarsi principalmente in due

aree applicative: una legata agli activity networks, e l’altra riguardante lo svilup-

po hardware. Piu in dettaglio,e stata approfondita la possibilia di sviluppare il

progetto per applicazioni in ambito di gestione dei progetti e per l’ottimizzazione

53


di reti logiche.

Per quanto riguarda la prima area si procede utilizzando la convenzione degliAc-

tivity Networks, i quali rappresentano uno dei principali strumenti utilizzati nella

pianificazione di qualsiasi genere di progetto, specialmente di carattere gestionale-

manageriale.

Per quanto riguarda invece l’ottimizzazione di una rete logica, chee una fase

importante della realizzazione della stessa, si deve tener conto di due principali

problematiche: leprestazioni del dispositivo e il suocostoin termini di area oc-

cupata. I due parametri indicatori fondamentali per quanto riguarda le prestazioni

dipendono direttamente dal cammino critico e sono iltempo impiegatodalla rete

per elaborare gli ingressi (nel caso di una rete combinatoria), o lefrequenze(nel

caso di una rete sequenziale). Il costo del dispositivo in termini di area occupata, a

parita di processo realizzativo e tecnologia utilizzata,e normalmente valutato nel

numero di porte logiche, in quanto da questo dipende l’area del chip.

L’ottimizzazione delle prestazioni di una rete combinatoria mira a ridurre il tempo

in cui i segnali in ingresso alla rete stessa vengono posti in uscita, in seguito alla

computazione avvenuta. Questo tempoe pari al tempo impiegato dal percorso

della rete logica che viene completato nel tempo maggiore. Infatti non ha sen-

so aspettarsi il risultato in un tempo minore, in quanto l’uscita (o le uscite)e il

risultato dato dall’intera rete. Quindi, per ridurre il tempo di esecuzione, ovvero

per aumentare le prestazioni di ogni rete combinatoria,e necessario individuare

il percorso piu lento, ossia il cammino critico. Una volta individuato, si puo poi

procedere a ridurre il suo tempo di esecuzione, dettotempo critico o critical time,

chee pari alla durata della computazione della rete.

L’implementazione tramite FPGA di algoritmi di ricerca del cammino criti-

co, oltre a produrre un dispositivo embedded che puo risolvere questo algoritmo

(il quale e computazionalmente costoso per reti estese) in tempi brevi, puo rien-

trare anche nell’area applicativa della Riconfigurazione Dinamica delle FPGA [5]

stesse.

54


3.2 Strumenti

Il progettoe stato svolto principalmente nel laboratorio di Microarchitetture del

Dipartimento di Elettronica e Informazione presso il Politecnico di Milano. Questo

ha consentito l’uso di vari strumenti, soprattutto per quando riguarda la traduzione

del codice C in VHDL tramite i diagrammi ASM e la conseguente integrazione in

un’archittettura.

Si e scelto come linguaggio base per la specifica iniziale, un linguaggio di alto

livello: il C. Questoe stato utilizzato per la traduzione formale delle specifiche

iniziali, con l’obiettivo di rendere l’elaborazione successiva il piu semplice possi-

bile.

Si e deciso di utilizzare il linguaggio C poiche si e visto che opportune scelte

implementative possono facilitare (fino quasi a render automatica) la successi-

va formazione dei diagrammi ASM. Per quanto riguarda l’implementazione della

specifica nel linguaggio C sie fatto uso dei seguenti strumenti:

• kwrite come editor di testo;

• gcc 3 per la compilazione;

• Doxygen 1.3.7 per la documentazione.

Dopo la scrittura del codice C si sono prodotti alcuni diagrammi, che de-

scrivono l’algoritmo implementato. Come presentato nelCapitolo 2, i diagram-

mi ASMsono dei diagrammi a se stanti, che non richiedono quindi un particolare

software per lo sviluppo. Essi vengono progettati manualmente, partendo da un

linguaggio di alto livello, come proposto nella metodologia in esame. Per questo

motivo, in questa fase della progettazionee stato utilizzato solo uno strumento per

disegnare grafi, schemi, diagrammi, etc.:Dia 0.92.

Nella fase successiva, che parte dai diagrammi ASM e giunge alla descrizione

in VHDL, per la traduzione del diagramma in un linguaggio di descrizione hard-

ware, che nel caso in esamee il VHDL, si e utilizzato unambiente integrato di

55


sviluppo hardwareche mette a disposizione svariati strumenti utili per la pro-

gettazione di IP core. Si tratta di un prodotto dellaXilinx ed e l’ Integrated

Software Environment (Xilinx ISE ).

La verifica della specifica VHDLe stata effettuata mediante l’uso di un soft-

ware simulatore che consente di verificare il corretto funzionamento del codice

stesso, in modo da rispettare le specifiche richieste. Per questa fasee stato uti-

lizzatoModelSim che ha consentito una visualizzazione delle uscite sia tramite i

valori finali, ma soprattutto come propagazione dei segnali durante tutta la simu-

lazione effettuata.

Infine, per l’introduzione dell’IP core in un’architetturae necessario utiliz-

zare un software che permetta di manipolare architetture hardware. Per il caso

di studio sie utilizzato quello fornito dallaXilinx : l’ Embedded Development

Kit (Xilinx EDK ), indispensabile quindi per integrare l’IP core (o gli IP core,

a seconda del progetto) sviluppato precedentemente in VHDL in un’architettura.

L’ EDK si occupa anche della gestione dei drivers, che consentono la gestione del-

l’IP core stesso e che solitamente sono sviluppati in C.

3.3 Fasi del Progetto

Il presente paragrafo fornisce una dettagliata descrizione del flusso presentato nel-

la Figura3.1.

Si illustrano quindi nel dettaglio le fasi in cui si articola il progetto.

3.3.1 Studio del Problema

Una volta scelto di affrontare il problema del calcolo del cammino critico si sono

fatte delle valutazioni generali sull’algoritmo. Ci si domanda innanzitutto se il

problema di computare il cammino critico di un grafo sia ben posto. Natural-

56


mente, come gia e stato specificato, le caratteristiche richieste normalmente ai

grafi per la ricerca del cammino critico riguardano l’orientamento degli archi e

l’assenza di cicli, e per queste tipologie di grafi il problema in esamee deciso, in-

fatti esistono algoritmi in grado di risolverlo.E necessario inoltre considerare che

si tratta di un algoritmo caratterizzato da un’elevata complessita, sia temporale

sia spaziale1. Per quanto riguarda la complessita spaziale si passa ad analizzare

la dimensione del grafo: l’ideale sarebbe riuscire a garantire il corretto funzion-

amento dell’IP core per grafi il piu estesi possibile. Pero, in vista della futura

traduzione in VHDL, la dimensione del grafo stessoe un parametro critico. Infat-

ti, se a livello software le limitazioni relative all’occupazione di memoria hanno

gia un’importanza ragguardevole, a livello hardware diventano ancor piu rilevanti.

Infatti, per operare sul grafoe necessario disporre della matrice delle adiacenze,

che per quanto concerne gliActivity Networks, racchiude tutte le informazioni

caratterizzanti il grafo: gli archi presenti, la loro durata, etc. . . Se da una parte

la matrice delle adiacenze consente di conoscere ed effettuare tutto quanto possi-

bile del grafo, il suo principale difetto risiede pero nell’occupazione di memoria.

Come gia e stato illustrato, si tratta di una matrice quadrata, la cui occupazione di

memoriae proporzionale al quadrato del numero di nodi.

3.3.2 Formalizzazione del Codice C

Nelle prime 210 righe di codicee stata sviluppata la parte relativa alla dichiarazione,

acquisizione, inizializzazione e visualizzazione della matrice di adiacenza del

grafo fornito. Segue la parte piu interessante e relativa al vero calcolo deltempo

minimo e massimo, che viene brevemente riassunta nelle seguenti linee.

Riassunto Generale dell’Algoritmo

Piu in dettaglio il ciclo esterno scorre un array, quello discheduling, ed individua

il nodo che deve esser schedulato, appunto. Per quanto concerne la parte di algo-

ritmo relativa altempo minimo, il nodo che deve esser schedulatoe individuato

1Per la definizione di decidibilita e di complessita si rimanda a [1].

57


sull’array in base alla posizione che contiene lo 0. Infattie necessario siano stati

analizzati tutti i predecessori del nodo che verra schedulato; e questoe rappre-

sentato nell’algoritmo come un array contenente il numero dei predecessori da

analizzare per ogni nodo (si tratta di una notazione posizionale). Partendo dalla

radice quindi bisogna schedularla e decrementare in modo unitario il numero dei

predecessori corrispondente ai suoi successori. Detto questo, il passo successivo

consiste nel cercare a il nodo da schedulare e settare a−1 il valore del nodo in

analisi nell’array stesso (il che significa che il nodoe stato schedulato). L’array

tmin e gli array dischedulingvengono tenuti sempre nella memoria dell’hard-

ware permettendo libero accesso alla periferica. A questo punto ci si occupa dello

schedulingvero e proprio e viene analizzata, per ogni successore, la somma del

costo del cammino che lo congiunge a questo e il valore gia presente relativo al

successore in esame. Nel caso venga trovato un valore minore si aggiorna il tMin.

Dopo aver considerato tutti i successori del nodo, questoe da ritenersi schedu-

lato deve quindi essere trovato un nuovo nodo da schedulare ed analizzare. La

parte relativa al calcolo deltempo massimoe , come gia precedentemente detto,

completamente duale , quindi presenta solo lievissime differenze nell’implemen-

tazione. Nella Figura seguente (3.2) e riportato il codice in cui si ricava iltempo

minimo:

Analisi Dettagliata dell’Algoritmo Sviluppato in C

Nella parte iniziale vengono impostate le strutture su cui si opera successivamente

e viene riempita la matrice delle adiacenze, partendo da un grafo contenuto in un

files (3.1) secondo le seguenti convenzioni:

• la prima riga contiene il numero dei nodi e il numero degli archi, separati

da uno spazio

• segue un numero di righe pari al numero degli archi presenti nel grafo. Og-

nuna di queste contiene rispettivamente tre numeri (ancora separati da spazi)

che indicano il nodo di partenza dell’arco, il nodo di arrivo e la durata.

58


Figura 3.2: Porzione di codice C relativo al calcolo del tempo minimo.

Nella Tabella (3.1) viene riportato un grafo con il relativo file che la rappre-

senta.

La scelta di non passare l’intera matricee motivata dalla ricerca di un metodo

piu breve e meno impegnativo per l’utente, ipotizzando di lavorare solitamente con

grafi sparsi, senza quindi troppi archi, ma si posticipa la gestione dell’interazione

con l’utente solo in un secondo momento, dando la precedenza alcuore del codice.

Vengono quindi inizializzati tutti i valori necessari alloscheduling, come il

numero dei genitori di ogni nodo per il successivo calcolo del tempo minimo

oppure, dualmente, il numero dei figli di ogni nodo per il calcolo del tempo mas-

simo. Questo consente di verificare che siano risolte tutte le dipendenze di ogni

nodo prima che venga analizzato. Infatti, ogni volta che si analizza un vertice del

59


Grafo File di Inizializzazione

Tabella 3.1: Esempio di dichiarazione del grafo, affiancato dalla rappresentazione del

grafo stesso.

grafo, viene decrementato ogni contatore relativo al nodo a cui collegato, sia in

quanto padre (tMin) che in quanto figlio (tMax). In seguito, vengono analizzati

i nodi in cui il contatore ha valore nullo, ossia per cui sono state risolte tutte le

precedenze.

I nodi iniziali a partire dai quali vengono calcolati iltempo massimoe il

tempo minimosono rispettivamente, il nodo iniziale e quello finale, preceden-

temente individuati come i nodi caratterizzati da valori nulli subito in seguito

all’inizializzazione della matrice3.5.

Nel dettaglio, l’analisi di ogni nodoe costituita dalle seguenti operazioni:

• si scorrono tutti i nodi e fra questi vengono scelti quelli in relazione con il

nodo in esame, a cui sono collegati quindi, tramite un arco;

60


Figura 3.3: Parte del codice relativa all’acquisizione del grafo da file.

Figura 3.4: codice in cui si evidenzia la gestione delloscheduling.

• si valuta la condizione caratteristica per il calcolo del tempo richiesto, che

nel caso si tratti di tempo minimoe la seguente:ti ≥ t j + di j , ∀ i, j| (ni ,n j) ∈ N.

Se la condizionee verificata, allora avviene la sostituzione;

• ad ogni modo viene decrementato il contatore del nodo scelto e si pas-

sa ciclicamente all’analisi di un altro vertice chee in relazione al nodo

considerato in partenza.

Infine, dopo che sono stati individuati sia il tempo minimo che quello massi-

mo, in modo del tutto indipendente, vengono confrontati i due valori di ogni nodo

Figura 3.5: Frammento di codice in cui vengono settati il nodo origine e quello finale.

61


Figura 3.6: Dettaglio del codice sul calcolo del tempo minimo.

al fine di individuare i vertici critici che appartengono quindi al sottografo critico:

Figura3.7

Figura 3.7: Frammento di codice in cui viene determinato il sotografo critico.

A questo punto,e necessario individuare tutti i possibili percorsi effettuabili

dai nodi che appartengono al sottografo critico. In quanto si tratta di una parte

molto complessa, ma poco attinente allo studio della metodologia, si rimanda il

lettore particolarmente interessato all’appendice del volume, in cui si trova tutto

il codice C generato e documentato con Doxygen.

3.3.3 ASM

Alcune scelte effettuate in funzione di una futura traduzione durante la fase di

sviluppo dell’algoritmo in C, possono semplificare la stesura dei diagrammi ASM.

Ad esempio, frammentando il codice in alcune parti distinte ed indipendenti si

aiuta pesantemente questa stesura, in quanto risulta ben visibile la possibilita di

62


scelta relativa a quali di questi frammenti di codice vadano effettivamente reim-

plementati in hardware. Cio ha permesso di far calcolare TMAX e TMIN dallo

stesso hardware, riutilizzando la maggior parte della logica. Osservando infatti i

diagrammiASM dei due frammenti di codice (Figura3.8), relativi al calcolo del

tempo minimo e di quello massimo,e facilmente osservabile come questi due si

assomiglino e siano addirittura identici in molte parti.

Seguendo quanto proposto si sono creati quattro distinti ASM. Due di questi

rappresentano gli algoritmi per il calcolo ditMin e di tMax , come mostra la

Figura 3.8, mentre gli altri due rappresentano ilcalcolo del sottografo critico

(ovvero di nodi ed archi critici) ed ilcalcolo di tutti i cammini critici. La creazione

di questi grafi, attraverso l’uso del programma Diae avvenuta in due fasi distinte.

In un primo momento sie percorso tutto il codice precedentemente scritto e, si

sono trascritte le istruzioni C utilizzando le tre box dei diagrammi ASM, della

Figura 2.1. Una volta eseguita questa prima fase, sie cercato di raggruppare

le box in blocchi, al fine di individuare in modo univoco gli stati del controllore

della FSMD. Raggruppate le box si sono ottenuti i grafi di tMin e di tMax, visibili

rispettivamente nelle Figure3.8, .

Un esempio significativo di questo lavoro di traduzionee osservabile nelle

seguenti Figure3.9e3.10:

Partendo dal codice C dell’algoritmo presentato in Figura3.9si sono estratti

il secondo ed il terzo dei Box in Figura3.10

Una volta disegnati i tre box sie evidenziato come, applicando le regole

descritte nelCapitolo 2, possano essere raggruppati a formare un unico bloc-

co. Questo blocco corrisponde esattamente con lo stao S4 del controllore, come

mostrato in Figura3.11. Questo significa, tra le altre cose, chee possibile eseguire

i tre Box in un unico ciclo di clock dell’IP core.

Una volta effettuate tali operazioni per tutto il sorgente C, e sviluppati i dia-

grammi ASM,e possibile passare alla fase successiva della metodologia, ovvero

alla traduzione dei diagrammi ASM in VHDL.

63


Figura 3.8: Diagrammi della parte di codice relativa al calcolo del percorso minimo e

massimo.

64


Figura 3.9: Esempio di codice C dell’algoritmo che viene tradotto in diagrammi ASM.

Figura 3.10: Esempi di box derivanti dalla traduzione del codice di Figura3.9.

3.3.4 VHDL e Verifica

Dopo aver formalizzato l’algoritmo a partire da un sorgente C e volendolo trasferire

su una periferica hardware sie applicata la metodologia per ottenere un diagram-

ma ASM. Dopo aver scelto di utilizzare una scheda dotata di una FPGA sie pas-

sati alla fase successiva della metodologia: la traduzione da diagrammi ASM a

VHDL.

Problematiche Affrontate Prima della Trasformazione del diagramma ASM

in una descrizione VHDL

Prima di iniziare a realizzare la specifica in VHDL sie analizzato a fondo il dia-

gramma ASM, per poter riflettere sulle possibili scelte implementative. Sie cosı

presentata la non banale scelta relativa a quali parti di codice andassero trasferite

65


Figura 3.11: Esempio di uno stato della FSM, derivante dalla traduzione del codice di

Figura 3.9.

a livello hardware e quali sarebbero diventate software e quindi driver delle per-

iferiche. Le prime, descritte in VHDL permettono di sintetizzare una rete logica

con vantaggi relativi alla velocita di esecuzione. Le parti rimaste in C vengono poi

eseguite dal processore presente nella FPGA, sia esso unMicroBlaze o unPPC

405, e costituiscono il driver della periferica descritta in VHDL.

La differenza trahardwareesoftwaree che la parte implementata inhardware

e estremamente piu efficiente in termini di prestazioni temporali della stessa im-

plementazione insoftware, ma la quantita di codice trasferibile inhardwaree, ad

esempio, limitata dalle disponibilita fisiche della FPGA presente sulla scheda uti-

lizzata. Si pensi, ad esempio, la sola rappresentazione in memoria del grafo, me-

diante matrice di adiacenza, puo occupare una porzione consistente dello spazio

fisico presente nell’FPGA a disposizione. Per questi motivi il primo passo verso

la traduzionehardwaree stato quello di decidere quali parti implementare e in che

modo andassero sviluppate e tradotte.

Posto questo, bisogna rendere indipendente il calcolo diTMAX e TMIN ,

per poter quindi avere aperta la strada a due scelte differenti. Nel caso l’FPGA

66


sia in grado di contenere due periferiche differenti, una volta implementate si

sviluppa un driver che le sfrutti entrambe in contemporanea (cioe in parallelo).

Questoe vantaggioso in quanto permette di ottimizzare il tempo di esecuzione,

che diventa pari al tempo di esecuzione maggiore tra le due periferiche, anziche

la somma dei tempi di esecuzione delle due periferiche. Nel caso invece risulti

impossibile implementare due periferiche, a causa di limitazioni della FPGA, si

crea una periferica unica in grado di calcolareTMIN o TMAX a seconda di un

flag in ingresso. Questo minimizza lo spazio occupato dall’intera struttura, ma

rende impossibile la parallelizzazione, quindi peggiora le prestazioni temporali.

Cosı sono stati leggermente modificati i diagrammi ASM in modo da dividere

il calcolo diTMIN dal calcolo diTMAX .

Ignorando la parte di acquisizione dati e l’inizializzazione, si sono ottenuti due

grafi indipendenti per il calcolo diTMIN eTMAX , e altri due grafi per il calcolo

rispettivamente del sottografo critico e dei cammini critici. Dopo aver individuato

i nodi che costituiscono uno o piu cammini critici, mediante gli algoritmitMin e

tMax si ottiene unsottografo criticoil quale e dimensionalmente molto minore

del grafo di partenza. Questo significa che esso richiederebbe uno sforzo com-

putazionale di analisi decisamente inferiore se si trattasse di matrici allocabili di-

namicamente (discorso valido invece per l’implementazione puramente software),

e quindi sie scelto di svolgere il passaggio successivo (ovvero l’individuazione

dei veri e propri cammini critici) interamente viasoftware. Se invece si decidesse

di implementarlo inhardwarebisognerebbe considerare che none possibile sta-

bilire a priori unupper boundalla dimensione del sottografo critico se non pari

alla dimensione del grafo di partenza. Scelto quindi di non tradurre in VHDL i

due grafi riguardanti il sottografo critico ed i percorsi critici, ci sie concentrati sul

calcolo diTMIN eTMAX .

Posto di avere alcune limitazioni, come quella relativa a fissare a priori le di-

mensioni massime del grafo, risulta ad ogni modo ovvio quanto sia preferibile

trasferire in hardware le sezioni di programma che richiedono uno sforzo com-

putazionale maggiore; a tal finee opportuno valutare la complessita delle singole

67


porzioni di codice per effettuare una scelta oculata.E stato quindi necessario,

prima di procedere, compiere ai seguenti passi:

• approfondire le nostre conoscenze riguardo il linguaggio VHDL

• imparare l’utilizzo degli strumenti ISE e EDK di Xilinx per poter utilizzare

la scheda Avnet del laboratorio di Microarchitetture del Politecnico

• studiare il diagramma ASM per individuare le parti per le quali la descrizione

VHDL avrebbe portato vantaggi significativi

Per questo, in seguito ad un’analisi critica del codice scritto precedentemente

e con un’idea, seppur approssimativa, di come fosse il vero e proprio ambiente di

lavoro, sie cercato di individuare gli scenari piu interessanti per lo sviluppo. Le

teorie piu significative proposte inizialmente sono due, piu una possibile alterna-

tiva prevista per un’ eventuale implementazione futura. Entrambe escludono co-

munque la gestione dell’acquisizione degli ingressi e dell’inizializzazione, scelte

lasciate volutamente alla fine della realizzazione generale.

Analisi delle Scelte Implementative

Come accennato nel paragrafo precedente, la miglior soluzione auspicabile prevede

la totale conversione del codice in hardware, con la conseguente riduzione dei

tempi di elaborazione2. Obiettivo ambizioso, che richiede pero delle restrizioni

relative ai grafi (ad esempio limitando il numero dei nodi del grafo) ed ingen-

ti problematiche nella fase di sintesi, considerando la complessita del codice a

confronto con le capacita della scheda.

Sfruttando la possibilita di riutilizzare i componenti3 all’interno dell’FPGA

(svolgendo cioe in modo sequenzialetMin e tMax), ma soprattutto introducendo

2In realta non si tratta di una certezza matematica. Un’interessante studio previsto prevede

infatti il confronto fra l’algoritmo progettato insoftwaree quello implementato anche a livello

hardware, come in questo caso3Grazie all’uso dei diagrammi ASMe stato possibile riutilizzare alcune porzioni di rete logica

68


Figura 3.12: Foto della Virtex-II Pro Evaluation Board.

l’uso di unaBlock-RAM, BRAM , per la memorizzazione della struttura dati del

grafo,e possibile implementare l’intero algoritmo inhardware.

Si e quindi giunti ad una rete che svolge in modo completamentehardware

tutto l’algoritmo fino al calcolo di TMIN ed TMAX compresi.

Esempi di Traduzione in VHDL

Un esempio di come si sia operato per la traduzione dei diagrammi ASM in una

specifica VHDL,e presente nelle Figure seguente3.2, 3.3e 3.4.

Tabella 3.2: Esempio di traduzione distate box

La state boxmostrata in Figura3.2, composta da due istruzioni da eseguirsi

simultaneamente, viene tradotta in due processi distinti. Entrambi, se la FSM si

trova nello stato corretto, eseguono l’assegnamento indicato. Altrimenti i registri

69


corrispondenti mantengono il valore presente senza modificarlo.

Tabella 3.3: Esempio di traduzione didecision box

Come mostrato nelCapitolo 2 le decision box, una volta tradotte, fanno parte

del controllore di una macchina a stati finiti. Nel caso specifico, unadecision box,

viene tradotta in una condizione della FSM del controllore che decide lo stato

prossimo (cioe implementa la funzione di transizione) in base all’esito del test

effettuato.

Tabella 3.4: Esempio di traduzione dicondition box

Infine,e stata posta lacondition box, di figura3.4. Si vuole che effettui l’asseg-

namento solo se ladecision boxche la precede ha dato esito positivo. In questo

caso dunque si fa alzare al controllore un segnale (enableS4) e il processo che

segue l’assegnamento verifica il valore dell’enable stesso per effettuare o meno

l’operazione. In caso contrario viene mantenuto nel registro il valore precedente.

Si e scelto di presentare un solo esempio di traduzione per ogni tipo di box, in

quanto si ritiene che ogni caso sia poi a se stante, ma una rappresentazione faciliti

molto la comprensione. Resta ad ogni modo possibile vedere i grafi e l’intero

codice in appendice per osservare come si sia operato in questa fase di traduzione.

70


Verifica

E’ possibile verificare che la descrizione VHDL implementi effettivamente l’al-

goritmo voluto, simulando il comportamento della rete logica descritta. Questo

avviene tramite l’uso di simulatori software. Nel nostro progetto in particolare

e stato utilizzato il programmaModelsim, che ha permesso di verificare la cor-

retta progettazione del modulo hardware. Segue in Figura3.13 un’immagine

di una simulazione effettuata durante la fase di sviluppo, a testimonianza del

funzionamento del modulo descritto in VHDL.

Figura 3.13: Verifica tramite strumenti software.

3.3.5 Integrazione

L’ultima fase del progetto consiste nella realizzazione fisica dell’IP core, a par-

tire dal linguaggio VHDL precedentemente scritto. Questa fase, che comprende

la creazione di un driver in linguaggio C per utilizzare la periferica,e un’oper-

71


azione che non presenta particolari difficolta, purche la specifica VHDL da im-

plementare non contenga errori di progettazione.E importante sapere che una

specifica VHDL, pur implementando l’algoritmo voluto, e pur essendo semanti-

camente ineccepibile, puo descrivere un hardware che none realmente sintetiz-

zabile. Questo puo avvenire perche la descrizione VHDL tende ad occupare un

numero diSlicessuperiore alle capacita della FPGA. Un codice che non presenti

simili errori di progettazione, dopo un’adeguata fase di testing, tramite appositi

strumenti di simulazione, permette una non difficile configurazione dell’IP core

in una scheda. Questa motivazione, unita al legame stretto con l’hardware ed il

software utilizzato, motivano la scelta di non trattare questo argomento, per altro

assai lontano come tematiche dallametodologiaproposta.

Figura 3.14: Integrazione dell’IP core in una architettura.

Si rimanda alla bibliografia, ed in particolare al materiale presente su [13] per

72


ulteriori approfondimenti.

Unica nota che viene presentatae l’utilizzo dellaBRAM nell’implementazione

dell’IP core qui presentata. Il suo utilizzo ha permesso di aumentare lo spazio uti-

lizzabile per la reale implementazione dell’algoritmo per il calcolo del cammino

critico, diminuendo drasticamente lo spazio occupato per i dati in memoria.

Uso della BRAM

In seguito a varie verifiche ed analisi sie notato che la memorizzazione della ma-

trice di adiacenza inflip-flop4 non era una possibilita attuabile. Questo perche,

per far sı che l’FPGA inclusa nella scheda disponibile contenesse sia la memoria

sia la rete necessaria ad implementare l’algoritmo, si sarebbe dovuto ridurre fino

a livelli inaccettabili la dimensione massima del grafo sul quale calcolare il cam-

mino critico. Quindi sie scelto di utilizzare nonflip-flops, bensı la Block-RAM

(o BRAM) presente all’interno dell’FPGA. Questa memoria, oltre a non sottrarre

slicesall’FPGA, era per l’FPGA a disposizione, molto piu capiente della memoria

sintetizzabile tramiteslices.

Si e dunque riusciti ad avere spazio di memoria sufficiente a far calcolare all’IP

core il cammino critico su grafi di dimensione considerevole. Questo ha inoltre

fatto sı che il numero dislicesoccupate dell’IP core fosse decisamente limitato. In

conclusione l’utilizzo della BRAM ha portato grandi vantaggi, ede consigliabile

per qualunque IP core abbia bisogno di ingenti quantita di memoria.

4I flip-flopvengono generati utilizzando leslicedella FPGA.

73

Capitolo 4

Verifica e Conclusioni

Le Conclusioni illustrano i risultati della validazione della metodologia mediante

il caso di studio, alcune osservazioni sulla metodologia stessa ed i possibili lavori

futuri derivanti dal lavoro svolto.

L’applicazione della metodologia proposta ad un caso reale ha avuto il triplice

effetto di validarla, farne comprenderne meglio le possibilita, e migliorarla.

Infatti l’applicazione della metodologia al caso della ricerca del cammino critico

ha mostrato ottimi risultati al confronto di altri progetti. L’utilizzo delle teorie su

cui si basa ha reso possibile lo sviluppo della periferica in un minore tempo e con

minori ostacoli rispetto allo sviluppo non metodico. Per quanto si comprenda che

la valutazione dello sforzo, e dell’impegno (o, in termini aziendali, del costo) da

sostenere per sviluppare un piccolo prodotto hardware siano fattori difficilmente

valutabili in maniera quantitativa, il risultato in termini qualitativie stato sicura-

mente positivo. Sono auspicabili in ogni caso ulteriori studi sul reale impatto della

metodologia.

74

CAPITOLO 4. VERIFICA E CONCLUSIONI

Ulteriori studi possibili sull’argomento potrebbero essere l’inclusione nella

metodologia di tecniche avanzate di ottimizzazione, e lo sviluppo di strumenti

informatici a supporto dell’applicazione del metodo.

Per quanto concerne il caso di studio, sono stati effettuati dei test per la va-

lidazione della descrizione VHDL tramite il software di simulazione ModelSim.

Questi hanno reso esito positivo, ovvero, la periferica funziona correttamente. Il

codicee funzionante e la traduzione non ha presentato gravi difficolta , anzi,e

stata portata a termine in tempi brevi, nonostante il tempo dedicato all’analisi

della Metodologia. Inoltre, il codice scritto, una volta sintetizzato, risulta avere

ottime caratteristiche in quanto sia riesce a limitare l’utilizzo di varie strutture

dell’FPGA, sia ottiene buone prestazioni temporali.

Si puo osservare infatti dal seguente rapporto di sintesi come sia stato possibile

realizzare un IP core che utilizzi solamente porzione ridotte delle capacita fisiche

dell’FPGA utilizzata.

Design Summary: Number of errors: 0

Logic Utilization:

Total Number Slice Registers: 778 out of 9,856 7%

Number used as Flip Flops: 746

Number used as Latches: 32

Number of 4 input LUTs: 820 out of 9,856 8%

Logic Distribution:

Number of occupied Slices: 1,276 out of 4,928 25%

Number of Slices containing only

related logic: 1,276 out of 1,276 100%

Number of Slices containing

unrelated logic: 0 out of 1,276 0%

Total Number 4 input LUTs: 1,140 out of 9,856 11%

Number used as logic: 820

Number used as a route-thru: 60

75


Number used for Dual Port RAMs: 210

(Two LUTs used per Dual Port RAM)

Number used as Shift registers: 50

Number of bonded IOBs: 4 out of 396 1%

Number of PPC405s: 1 out of 1 100%

Number of JTAGPPCs: 1 out of 1 100%

Number of Block RAMs: 16 out of 44 36%

Number of GCLKs: 1 out of 16 6%

Number of GTs: 0 out of 8 0%

Number of GT10s: 0 out of 0 0%

Total equivalent gate count for design: 1,092,518

Rapporto di sintesi: area

Inoltre l’IP core permette l’applicazione di una frequenza di clock molto alta (100Mhz),

come mostrato dalla relativa sezione del rapporto di sintesi riportata in seguito.

Timing summary:

---------------

Timing errors: 0 Score: 0

Design statistics:

Minimum period: 9.982ns (Maximum frequency: 100.180MHz)

Rapporto di sintesi: temporizzazione

Riguardo possibili usi dell’IP core derivante dal case study si ricorda che il cal-

colo del Critical Path in hardware potrebbe essere uno spunto per la creazione di de-

76


vices atti alle ottimizzazioni di reti logiche, o, essendo il Critical Path collegato stret-

tamente con la schedulazione, questa affinita potrebbe essere sfruttata dalla nell’ambito

della riconfigurazione dinamica delle FPGA.

Espansioni possibili dell’IP core potrebbero essere l’aumento del numero di nodi

del grafo analizzabile o l’aumento del valore del peso massimo di ogni nodo, entrambi

realizzabili in modo non difficoltoso aumentando la porzione di BRAM utilizzata.

Un argomento correlato potrebbe essere l’implementazione della ricerca del percor-

so minimo. Basandosi sull’IP core prodotto sarebbe infatti possibile implementare, con

scelte simili a quelle effettuate, hardwares dedicati al calcolo del problema duale al cam-

mino critico: il percorso minimo, che puo vantare una sconfinata gamma di applicazioni.

77

Appendice A

Diagrammi ASM

Seguono i diagrammi ASM utilizzati nelCapitolo 3: Caso di Studioper l’applicazione

dellametodologia(proposta nelCapitolo 2) al problema del cammino critico.

78

Appendice A. Diagrammi ASM

Figura A.1: Diagramma ASM che descrive l’algoritmo che calcolaTMax e TMin di un

DAG

79


Figura A.2: Diagramma ASM che descrive l’algoritmo che ricava daTMax e TMin il

sottografo critco di unDAG

80


Figura A.3: Diagramma ASM che descrive l’algoritmo che trova i percorsi critici dato un

sottografo critico81

Ringraziamenti

Vorremmo avere la possibilita, con questa pagina, di ringraziare tutte queste persone in

un modo cosı vivo, che un abbraccio in confronto sembri freddo. Non ci riusciremo.

Ma nonostante questo vogliamo comunque cercare di comunicarvi come senza di voi, se

anche forse questo lavoro sarebbe stato fatto comunque1, la nostra vita, in questi tre anni

di studio al Politecnico, non avrebbe avuto tutti quegli alti che fanno sı che, ripensando al

passato, ci si dimentichi dei bassi.

Vogliamo quindi ringraziare, il prof. Fabrizio Ferrandi, soprattutto per la mastodon-

tica disponibilita mostrata nei nostri confronti, ma anche per numerosi altri motivi, e le

nostre famiglie, non perche tutti le ringraziano, ma per averci sopportato durante gli sforzi

che si sono dimostrati necessari a produrre questo lavoro, e perche ci hanno dimostrato∞

volte di volerci troppo bene.

Inoltre il Santa, per il suo continuo appoggio spirituale, e i nostri amici (colleghi e

non) per la simpatia, l’aiuto, la disponibilita, l’affetto, e troppe altre ragioni. Tra questi

in particolare: Giada & Claudia & Silvia & Laura, Roby, Nicola, Fadi, FedeLATEX & Alice,

Eliseo, Bonzo, Lucy, Shumy, Silvia & Fabio, Fabio, Il Caccia, Il Gringo, Lo’oris, Edo,

1E questoe tutto da dimostrare.

82

Ringraziamenti

Al, gli amici del treno e quelli dell’ISU, Filippo, Tommy, Mathieu, Il Sido, Barbara,

Francesco & Carlo & Paolo, Carlo e Francesco. Infine non dimentichiamo i ragazzi del

µLab, sempre pronti a dare utili, se non indispensabili, suggerimenti.

un bacio a voi tutti,

Marco e Paola

83

Bibliografia

[1] Carlo Ghezzi, Dino Mandrioli. Informatica Teoricaed. Clup, 1989.

[2] Daniel D. Gajski. Principles of Digital Design

[3] Fabrizio Ferrandi. Materiale Per il corso di Reti Logiche A

www.elet.polimi.it/upload/ferrandi/.

[4] ]: F. Fummi, M.G. Sami, C. Silvano. Progettazione DigitaleMcGraw Hill, 2002.

[5] Marco Domenico Santambrogio. A methodology for dynamic reconfigurability in

embedded system design

[6] Sito web Xilinxwww.xilinx.com.

[7] Federico Malucelli. Appunti del corso di Ricerca Operativa presso il Politecnico di

Milano

[8] Mauro dell’Amico. 120 Esercizi di Ricerca OperativaPitagora Editrice

Bologna,1996.

[9] Virtex-II Pro Platform FPGAs: Functional Description (FPGA Data- Sheet

[10] Bocchi. Slides del corso di Gestione Aziendale da http://corsi.metid.polimi.it.

[11] Wayne Wolf. Modern VLSI Design, 2nd edition 1997 Prentice Hall

[12] Clifford A. Shaffer. A pratical Introduction to Data Structures and Algorithm

Analysis - Java Edition

84

BIBLIOGRAFIA

[13] MicroLab - Laboratorio di Microarchitetture del Politecnico di Milano

http://micro.elet.polimi.it

85

Printed the 13 novembre 2004 using LATEX 2ε

METODOLOGIA DI PROGETTO PER LA TRADUZIONE DI … · riguardanti il design digitale ed inoltre...

Documents

Transcript of METODOLOGIA DI PROGETTO PER LA TRADUZIONE DI … · riguardanti il design digitale ed inoltre...