SVILUPPO DI COMPONENTI PER SISTEMI DEDICATI...

POLITECNICO DI M ILANO

FACOLTA DI INGEGNERIA

CORSO DILAUREA IN INGEGNERIA INFORMATIVA

SVILUPPO DI COMPONENTI PER SISTEMIDEDICATI TRAMITE EDK: IL CASO DELLA DFT

Relatore: Prof. Fabrizio FERRANDI

Correlatore: Ing. Marco Domenico SANTAMBROGIO

Tesi di Laurea di:Vincenzo RANAMatricola n. 654968

ANNO ACCADEMICO 2003-2004

Tesi di Laurea

Vincenzo Rana

Luglio 2004

Indice

1 Definizioni 5

1.1 FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 EDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

1.2.1 Xilinx Platform Studio. . . . . . . . . . . . . . . . . . . 10

1.2.2 Importazione di un IP core. . . . . . . . . . . . . . . . . 16

1.3 Architettura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.3.1 Definizione dell’architettura di riferimento. . . . . . . . 21

1.3.2 Architettura finale . . . . . . . . . . . . . . . . . . . . . 24

1.4 DFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

1.5 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2 Presentazione della metodologia 29

2.1 L’esempio della DFT. . . . . . . . . . . . . . . . . . . . . . . . 30

2.2 Implementazione originaria. . . . . . . . . . . . . . . . . . . . . 32

2.3 Realizzazione dell’implementazione. . . . . . . . . . . . . . . . 33

2.3.1 Rappresentazione dei numeri. . . . . . . . . . . . . . . . 34

2.3.2 Rappresentazione delle funzioni trigonometriche. . . . . 35

2.3.3 Problemi relativi alla prima implementazione. . . . . . . 36

2.4 Implementazione finale. . . . . . . . . . . . . . . . . . . . . . . 37

2.5 Implementazioni alternative. . . . . . . . . . . . . . . . . . . . 39

2.6 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Descrizione delle implementazioni 43

3.1 Implementazione originaria. . . . . . . . . . . . . . . . . . . . . 44

i

3.1.1 Contatore. . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.2 MemoriaCampioni. . . . . . . . . . . . . . . . . . . . . 46

3.1.3 Twiddle . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.1.4 Sommatoria finale. . . . . . . . . . . . . . . . . . . . . 48

3.2 Implementazione finale. . . . . . . . . . . . . . . . . . . . . . . 51

3.2.1 DFT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2.2 DFTmodule . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2.3 Calcolo . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.3 Implementazioni alternative. . . . . . . . . . . . . . . . . . . . 55

3.4 Gestione software dei componenti. . . . . . . . . . . . . . . . . 60

3.4.1 Configurazione del componente. . . . . . . . . . . . . . 61

3.4.2 Lettura del risultato. . . . . . . . . . . . . . . . . . . . . 62

3.4.3 Codice d’esempio. . . . . . . . . . . . . . . . . . . . . . 65

3.5 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4 Dati e conclusioni 67

4.1 Dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .68

4.2 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Bibliografia 79

Elenco delle figure

1 Virtex 2 Pro Evaluation Board. . . . . . . . . . . . . . . . . . . 3

1.1 Schema di una FPGA. . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Blocco logico di base. . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Schema di una FPGA. . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Schermata iniziale di XPS. . . . . . . . . . . . . . . . . . . . . 11

1.5 Selezione file PBD. . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6 Schema del file PBD. . . . . . . . . . . . . . . . . . . . . . . . 12

1.7 Selezione del file UCF. . . . . . . . . . . . . . . . . . . . . . . 13

1.8 Sezione Applications. . . . . . . . . . . . . . . . . . . . . . . . 13

1.9 Codici sorgente. . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.10 Headers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.11 Barra degli strumenti. . . . . . . . . . . . . . . . . . . . . . . . 15

1.12 Voce Import Peripheral Wizard. . . . . . . . . . . . . . . . . . . 16

1.13 Select flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.14 Percorso di importazione. . . . . . . . . . . . . . . . . . . . . . 17

1.15 Inserimento nome e versione. . . . . . . . . . . . . . . . . . . . 18

1.16 Opzione per la selezione dei files. . . . . . . . . . . . . . . . . . 19

1.17 Selezione bus. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.18 Visualizzazione delle connessioni delle porte. . . . . . . . . . . 20

1.19 Visualizzazione dei parametri. . . . . . . . . . . . . . . . . . . . 21

1.20 Schema dell’architettura di riferimento. . . . . . . . . . . . . . . 23

1.21 Schema del MicroBlaze. . . . . . . . . . . . . . . . . . . . . . . 24

1.22 Schema dell’architettura finale. . . . . . . . . . . . . . . . . . . 25

iii

1.23 Configurazionde del componente. . . . . . . . . . . . . . . . . . 25

1.24 Schema di un sistema LTI. . . . . . . . . . . . . . . . . . . . . . 26

2.1 Shift e troncamento di un valore. . . . . . . . . . . . . . . . . . 35

2.2 Quadranti della circonferenza trigonometrica. . . . . . . . . . . 36

2.3 Mappatura degli angoli. . . . . . . . . . . . . . . . . . . . . . . 36

3.1 Schema della prima implementazione. . . . . . . . . . . . . . . 45

3.2 Descrizione in linguaggio VHDL del blocco contatore. . . . . . 46

3.3 Descrizione in linguaggio VHDL del blocco MemoriaCampioni. 48

3.4 Prima parte della descrizione in linguaggio VHDL del blocco twid-

dle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

3.5 Seconda parte della descrizione in linguaggio VHDL del blocco

twiddle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.6 Descrizione in linguaggio VHDL della sommatoria finale. . . . . 50

3.7 Architettura del componente. . . . . . . . . . . . . . . . . . . . 51

3.8 Schema dello spazio di indirizzamento. . . . . . . . . . . . . . . 53

3.9 Schema dei registri in fase di ingresso. . . . . . . . . . . . . . . 54

3.10 Schema dei registri in fase di uscita. . . . . . . . . . . . . . . . . 54

3.11 Prima parte della descrizione in linguaggio VHDL del blocco di

calcolo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56

3.12 Seconda parte della descrizione in linguaggio VHDL del blocco

di calcolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.13 Calcolo degli angoli nella DFT32 . . . . . . . . . . . . . . . . . 58

3.14 Calcolo degli angoli nella DFT16 . . . . . . . . . . . . . . . . . 58

3.15 Riduzione degli angoli nella DFT32 . . . . . . . . . . . . . . . . 58

3.16 Riduzione degli angoli nella DFT16 . . . . . . . . . . . . . . . . 59

3.17 Costrutto case nella DFT32 . . . . . . . . . . . . . . . . . . . . 59

3.18 Costrutto case nella DFT16 . . . . . . . . . . . . . . . . . . . . 60

3.19 Funzioni del file function.c. . . . . . . . . . . . . . . . . . . . . 61

3.20 Funzione scrivi . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.21 Funzione leggi . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.22 Funzione calcola. . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.23 Codice per la configurazione del componente. . . . . . . . . . . 65

3.24 Codice per l’elaborazione dei dati. . . . . . . . . . . . . . . . . 66

4.1 Dati relativi alla DFT32 . . . . . . . . . . . . . . . . . . . . . . 69

4.2 Dati relativi alla DFT16 . . . . . . . . . . . . . . . . . . . . . . 69

4.3 Dati relativi alla DFT8 . . . . . . . . . . . . . . . . . . . . . . . 70

4.4 Dati relativi alla DFT1 . . . . . . . . . . . . . . . . . . . . . . . 71

4.5 Relazione tra cicli e blocchi di calcolo. . . . . . . . . . . . . . . 73

4.6 Relazione tra gate e blocchi di calcolo. . . . . . . . . . . . . . . 74

4.7 Relazione tra cicli e gate. . . . . . . . . . . . . . . . . . . . . . 75

4.8 Relazione tra costo e blocchi di calcolo. . . . . . . . . . . . . . 76

Introduzione

Le FPGA, Field Programmable Gate Array, sono i dispositivi riconfigurabili at-

tualmente piu diffusi sul mercato e vengono utilizzati sia come strumento per

la progettazione prototipale, sia come alternativa riprogrammabile degli ASIC,

Application Specific Integrated Circuits [2].

Le prestazioni in termini di velocita di esecuzione e di spazio occupato rap-

presentano i principali vantaggi degli ASIC; questi sono, infatti, circuiti pensati

per adempiere ad uno specifico compito, pertantoe possibile realizzarli utilizzan-

do solo i componenti strettamente necessari ed ottimizzando le connessioni tra

questi.

Al contrario le FPGA sono essenzialmente delle matrici di componenti base,

collegati tra loro attraverso una logica riprogrammabile, e quindi possiedono le

caratteristiche di flessibilita ed adattabilita che sono invece completamente as-

senti negli ASIC;e possibile, infatti, successivamente alla fase di realizzazione

fisica, configurarle programmando la loro logica, in modo da utilizzarle per im-

plementare la soluzione di una vasta gamma di problemi con un unico dispositi-

vo, invece di dover utilizzare un singolo e diverso ASIC per ognuno di essi; ma

questi vantaggi sono controbilanciati dal peggioramento delle prestazioni sia in

termini di tempo di esecuzione che di spazio occupato, poiche la tecnologia uti-

lizzata per la realizzazione dei componenti e della logica riprogrammabile non

permette di eguagliare la velocita degli ASIC e comporta la possibilita che, in

certe configurazioni, alcuni componenti base rimangano inutilizzati, e quindi pos-

sano essere considerati sprecati quando vengono considerate quelle determinate

configurazioni.

1

La configurazione delle FPGA, pertanto, rappresenta il cuore delle potenzialita

di questi dispositivi;e dunque importante cercare di sfruttare questa caratteristica

trovando il giusto compromesso tra il numero di componenti utilizzati per real-

izzare un IP core, Intellectual Property core, e la sua velocita di esecuzione. Tali

variabili sono legate da un rapporto di proporzionalita inversa: ottimizzare il nu-

mero di componenti utilizzati, cioe ridurlo al minimo, significa necessariamente

peggiorare i tempi di esecuzione, e viceversa.

Utilizzare un maggior numero di componenti, ovviamente, riduce il tempo

di esecuzione di un IP core mappato sulla FPGA, ma riduce il numero di IP

core che vi si possono contemporaneamente mappare; questa ottimizzazione delle

prestazionie limitata dalla quantita dei componenti presenti sul dispositivo. Vi-

ceversa, per permettere alla FPGA di contenere contemporaneamente un mag-

gior numero di IP core,e necessario ridurre il numero di componenti utilizza-

ti da ciascuno di essi, con un conseguente peggioramento delle loro prestazioni

temporali.

Lo sviluppo di un IP core e l’analisi della ricerca di un compromesso tra gli

aspetti appena presentati rappresenta lo scopo di questo documento.

Nel primo capitolo verra presentato lo scenario all’interno del quale si svilup-

pa il progetto e verranno esposte le principali caratteristiche delle FPGA, con-

frontandone gli aspetti salienti con gli altri dispositivi della famiglia delle logiche

programmabili e con le ASIC; successivamente si passera alla presentazione di

EDK, Embedded Development Kit, uno strumento che permette di sviluppare ar-

chitetture per configurare le FPGA; in particolare si prendera in considerazione la

FPGA presente sulla scheda Virtex 2 Pro della Xilinx, mostrata in Figura1. Verra

successivamente definita l’architettura di riferimento e sara descritto il proces-

so per la realizzazione dell’architettura finale che risultera essere un’architettura

completa e mappabile su FPGA; infine verra descritta la DFT, Discrete Fourier

Transform, che verra presa come esempio per l’implementazione di un IP core

all’interno di un’architettura.

Nel secondo capitoloverra trattato nello specifico l’esempio della DFT, Dis-

crete Fourier Transformate, presentandone le caratteristiche che la rendono adatta

2

Figura 1: Virtex 2 Pro Evaluation Board

ad essere presa in considerazione come IP core da sviluppare ed ottimizzare. Si

passera poi alla descrizione della prima implementazione, basata su una scom-

posizione in blocchi funzionali, e dei problemi introdotti da questo approccio,

procedendo con la successiva implementazione che risolve i problemi riscontrati

durante la prima fase di sviluppo. Infine verranno presentati gli aspetti concettuali

delle varie implementazioni alternative, realizzate nell’ottica di offrire una com-

parazione tra gli aspetti relativi alle prestazioni temporali ed all’occupazione di

area all’interno della FPGA.

Nel terzo capitolo verranno passate in rassegna tutte le differenti implemen-

tazioni realizzate, presentando e commentando, per ognuna di esse, le descrizioni

VHDL ed i dettagli di implementazione della DFT.

Nel quarto capitolo verranno esposti i dati relativi alle architetture per il cal-

colo della DFT, e verranno confrontati i risultati, mettendo in risalto le principali

differenze generate dalle diverse scelte implementative, analizzando quindi come

queste abbiano influito, positivamente o negativamente, sulle prestazioni dell’IP

core implementato. Verranno infine tratte le conclusioni sui risultati ottenuti, ricer-

cando le relazioni che intercorrono tra i vari aspetti analizzati.

3

Capitolo 1

Definizioni

5

1.1. FPGA

Lo sviluppo di componenti per sistemi dedicati si colloca nell’ambito della

configurazione dei dispositivi a logica riprogrammabile, il cui principale espo-

nente, come gia accennato,e rappresentato dalle FPGA; in questo capitolo ver-

ranno presentate le loro caratteristiche principali e verranno effettuati confronti

con gli ASIC e con gli altri dispositivi appartenenti alla famiglia delle logiche

riprogrammabili.

Verranno inoltre presentati i tratti generali di XPS, lo strumento di EDK uti-

lizzato per realizzare le architetture all’interno delle quali sono state importate le

descrizioni in linguaggio VHDL degli IP core. Oltre alla realizzazione delle ar-

chitetture ed all’importazione di componenti, XPS permette di creare il bitstream

relativo alle architetture e di effettuarne il download sulla FPGA, consentendo,

quindi, di effettuarne la configurazione.

Verra poi presentata l’architettura di riferimento, nella quale sono di fonda-

mentale importanza il soft-processor MicroBlaze ed il modulo di divisione, e

sara descritto il procedimento attraverso il quale si arrivera alla realizzazione

dell’architettura finale da mappare sulla FPGA.

Lo specifico componente, realizzato come esempio, permette di effettuare il

calcolo della DFT; sara dunque oggetto di conclusione l’introduzione dei concetti

fondamentali che sono alla base dell’algoritmo utilizzato per il calcolo della DFT.

1.1 FPGA

Le FPGA (Field Programmable Gate Arrays) sono dei dispositivi programma-

bili un numero qualsiasi di volte direttamente dall’utente e sono costituiti da una

matrice di blocchi logici collegabili tra loro, come mostrato in Figura1.1[2].

Questi dispositivi sono programmabili nel senso che le funzioni che imple-

mentano sono definite da una configurazione definita dall’utente finale e non dal

loro produttore; a seconda del tipo di dispositivo questa configurazione puo es-

sere memorizzata permanentemente o semi-permanentemente, oppure puo essere

caricata da una memoria esterna ad ogni accensione.

Il blocco logico base di una FPGAe rappresentato da una lookup table, LUT,

6

1.1. FPGA

Figura 1.1: Schema di una FPGA

che riceve quattro bit in ingresso e restituisce un bit in uscita, come mostrato in

Figura1.2.

Figura 1.2: Blocco logico di base

7

1.1. FPGA

Attraverso la configurazione delle LUTe possibile realizzare qualsiasi fun-

zione a quattro bit.

Vari studi hanno permesso di considerare il dimensionamento delle LUT a quattro

ingressi come il miglior compromesso tra le loro prestazioni, il potere espressivo

del blocco, ed il loro utilizzo, la frazione del loro potere effettivamente sfruttata.

LUT a piu bit avrebbero permesso di implementare fuzioni logiche molto comp-

lesse utilizzando meno blocchi logici, ma l’implementazione di funzioni piu sem-

plici avrebbe comportato un notevole spreco della loro capacita di calcolo, poiche

per ogni LUT ne sarebbe stata sfruttata solo una minima porzione.

LUT a meno bit, viceversa, avrebbero avuto un potere espressivo molto ridotto,

e quindi sarebbe stato necessario un elevato numero di blocchi logici per rap-

presentare le funzioni complesse, con un conseguente aumento delle connessioni

necessarie.

Le FPGA, come mostrato in Figura1.3, sono costituite da altri tre elementi: i

componenti logici, i blocchi di input/output e le interconnessioni.

• i componenti logici, quali, per esempio, porte logiche, Flip-flop, Buffer,

Adder e Shifter, rappresentano la collezione di funzionalita che la FPGA

mette a disposizione dell’utente; questa collezione puo venire sfruttata an-

che solo in parte.

Questi componenti si suddividono in due differenti categorie: quella che

comprende componenti molto complessi e quella con componenti poco com-

plessi.

I primi permettono di individuare delle funzionalita molto articolate, con

un conseguente miglioramento delle prestazioni in termini di velocita di es-

ecuzione e diminuzione delle connessioni necessarie, ma a discapito della

flessibilita, essendo componenti molto specifici, e quindi utilizzabili solo in

determinati casi particolari.

Al contrario i componenti logici poco complessi permettono un notevole au-

mento della flessibilita, essendo componenti molto generici, ma comportano

un aumento delle connessioni necessarie.

8

1.1. FPGA

Figura 1.3: Schema di una FPGA

• i blocchi di input/output consentono l’interfacciamento tra i contatti del

dispositivo e le linee dei segnali interni.

• le linee di interconnessione permettono di connettere i blocchi logici tra loro

e con i blocchi di input/output; possono essere distribuite o locali, ovvero

corte o lunghe; le prime sono essenzialmente condivise da pochi elementi

logici e quindi interessano solo una parte ridotta del dispositivo, permetten-

do il contenimento dei ritardi e della potenza utilizzata, mentre le secon-

de possono essere di varia lunghezza e sono utili per ottenere un’elevata

flessibilita.

Nella famiglia dei dispositivi programmabili possiamo trovare, oltre alle FP-

GA, i PLD (Programmable Logic Device), come ROM, PAL e PLA, e le MPGA

(Mask Programmable Gate Array), che sono matrici di elementi che possono es-

sere connessi tra loro secondo le specifiche dell’utente nella fase finale del pro-

9

1.2. EDK

cesso di fabbricazione. Le FPGA, all’interno di questa famiglia, rappresentano il

miglior compromesso tra flessibilita e prestazione.

Se confrontate con le ASIC (Application Specific Integrated Circuit), le FPGA

hanno lo svantaggio di avere prestazioni ridotte, ma presentano altre caratteristi-

che piu vantaggiose rispetto alle ASIC, tra cui il costo per unita piu basso per

bassi volumi di produzione, il costo ed il tempo di avvio alla produzione inferiori

e soprattutto consentono di utilizzare lo stesso dispositivo, in momenti differenti,

con diverse configurazioni che realizzano applicazioni differenti e quindi hanno

un’elevata flessibilita.

Le FPGA possono, inoltre, essere considerate dispositivi capaci di supporta-

re lo sviluppo di interi sistemi dedicati, perdendo il ruolo di dispositivi che im-

plementano unicamente le sezioni hardware e spostandosi anche verso la realiz-

zazione delle sezioni software.

1.2 EDK

EDK, Embedded Develompent Kit,e un ambiente di sviluppo che offre la pos-

sibilita di definire e realizzare architetture per diverse piattaforme prodotte dal

Xilinx, tra cui le FPGA della famiglia Virtex-II e Virtex-II Pro, in modo veloce ed

intuitivo, grazie ad un’interfaccia grafica che permette di avere una visione di alto

livello dell’intero progetto.

Di questo pacchetto applicativoe stato utilizzato lo strumento Xilinx Platform

Studio, XPS, descritto nel seguente paragrafo. Successivamente viene descritta la

procedura guidata per l’importazione di un IP core, che verra poi utilizzata nel

capitolo1.3.2.

1.2.1 Xilinx Platform Studio

Xilinx Platform Studioe uno strumento che permette di realizzare architetture per

sistemi dedicati [1]. All’apertura di un’architettura, attraverso il file con estensione

.xmp, si ottiene la schermata mostrata in Figura1.4.

10

1.2. EDK

Figura 1.4: Schermata iniziale di XPS

La finestra contrassegnata dalla lettera Ae suddivisa in piu sezioni; la prima

sezione,System, presenta l’elenco dei componenti dell’architettura, una serie di

file di sistema ed alcune opzioni del progetto; la sezioneApplications, che con-

tiene l’elenco dei file che costituiscono il software dell’architettura, verra analiz-

zata in dettaglio successivamente; la sezioneOptionspresenta una serie di opzioni

di carattere generale e la sezioneComponentsvisualizza la lista degli IP core che

possono essere aggiunti al sistema.

La finestra indicata dalla lettera B rappresenta l’area di lavoro, nella quale

verranno aperti i file che consentono di lavorare al progetto.

La finestra di output contrassegnata dalla lettera C serve per visualizzare i

messaggi generati dal programma.

Selezionando la vocePBD File: system.pbddalla sezione Applications (Figu-

ra 1.5), viene visualizzato lo schema grafico dei componenti presenti all’interno

dell’architettura, mostrato in Figura1.6, attraverso il qualee possibile gestire ogni

singolo componente visualizzato oppure aggiungerne di nuovi, eventualmente col-

legandoli agli opportuni bus, selezionandoli dall’elenco dei componenti riportato

sulla sinistra; piu avanti nella trattazione si descrivera comee possibile importare

un nuovo componente in EDK, in modo da renderlo disponibile insieme a quelli

11

1.2. EDK

Figura 1.5: Selezione file PBD

Figura 1.6: Schema del file PBD

di default nell’elenco dei componenti. La versione testuale della struttura grafica

mostrata dal file con estensione.pbdsi trova nel file con estensione.mhs.

Successivamente all’inserimento ed alla configurazione dei componenti desiderati,

si passa alla stesura del file UCF, User Constraints File; selezionando la voceUCF

File: data/system.ucfdal menu delle opzioni (Figura1.7), viene aperto il file con

estensione.ucf, all’interno del qualee possibile specificare le corrispondenze tra i

12

1.2. EDK

Figura 1.7: Selezione del file UCF

pin logici dell’architettura con i pin fisici della scheda.

Figura 1.8: Sezione Applications

Per la scrittura del codice eseguito dal processore (nel caso preso in conside-

razione si tratta di un MicroBlaze soft-processor, cioe un componente descritto in

VHDL che realizza le funzionalita di un processore) basta selezionare la sezione

Applications dal menu delle opzioni (Figura1.8), dopodichee possibile importare

13

1.2. EDK

Figura 1.9: Codici sorgente

Figura 1.10: Headers

i sorgenti con estensione.c (Figura1.9) e quelli con estensione.h (Figura1.10),

necessari per la realizzazione della parte puramente software.

Dopo aver sviluppato l’architettura desideratae possibile compilarla ed effet-

tuarne il download sulla scheda; per eseguire questi processi si ricorre alle seguenti

operazioni, le cui icone sono mostrate in Figura1.11:

14

1.2. EDK

Figura 1.11: Barra degli strumenti

• Generate Libraries, indicata dalla lettera A, che genera e compila le librerie

necessarie alla compilazione dei driver.

• Compile Program Source, indicata dalla lettera B, che compila i file conte-

nenti il codice che verra eseguito dal processore.

• Generate Netlist, indicata dalla lettera C, che crea, utilizzando il sintetiz-

zatoreXST, la rete dei collegamenti tra i componenti, generando i file con

estensione.ngc, Generic Native Database.

• Generate Bitstream, indicata dalla lettera D, che genera, basandosi sulla

rete dei collegamenti creata precedentemente, il bitstream necessario al-

la configurazione della FPGA, ovvero il file con estensione.bit (nel caso

considerato il filesystem.bit).

• Update Bitstream, indicata dalla lettera E, che consente di unire la sezione

software, cioe le librerie ed i file eseguibili, con quella hardware, rappre-

sentata dal file con estensione.bit creato dalGenerate Bitstream; in uscita

viene generato un ulteriore file con estensione.bit, il file download.bit, che

rappresenta l’architettura da mappare sulla FPGA.

• Download, indicata dalla lettera F, che effettua la configurazione della FP-

GA tramite la connessione JTAG, basandosi sul filedownload.bitgenerato

dall’Update Bitstream.

15

1.2. EDK

1.2.2 Importazione di un IP core

Per arricchire la libreria dei componenti, EDK mette a disposizione degli utenti

una procedura di importazione di nuovi componenti; per avviarlae sufficiente

selezionare la voceImport Peripheral Wizarddal menuToolsdella barra dei menu,

come mostrato in Figura1.12.

Figura 1.12: Voce Import Peripheral Wizard

La prima schermatae la presentazione del wizard; dopo aver cliccato sul pul-

santeNextviene proposta una scelta, mostrata in Figura1.13, ovvero se si desidera

creare un template per un nuovo componente oppure importare un componente gia

esistente.

Successivamente viene richiesto il percorso completo dell’architettura all’in-

terno della quale il componente verra importato, come indicato in Figura1.14.

16

1.2. EDK

Figura 1.13: Select flow

Figura 1.14: Percorso di importazione

Si giunge cosı ad una finestra, mostrata in Figura1.15, nella quale si devono

inserire i dati relativi al componente che si sta inserendo, quali il suo nome, che

deve necessariamente corrispondere al nome dell’entita presente nella descrizione

in linguaggio VHDL del componente da importare, e la sua versione.

17

1.2. EDK

Figura 1.15: Inserimento nome e versione

Proseguendo attraverso la procedura guidata si deve selezionare, all’interno

della successiva schermata, la voceHDL Source Files (*.vhd, *.v), che specifica

che il linguaggio di descrizione dell’hardware utilizzatoe il VHDL, e poi la voce

Browse to your HDL source and dependent library files (*.vhd, *.v) in next step,

come mostrato in Figura1.16, che permette di selezionare, successivamente, i files

VHDL necessari per la descrizione del componente da importare.

La schermata seguente, mostrata in Figura1.17, permette di selezionare il tipo

di iterfaccia con il bus che viene utilizzata dal nostro componente.

I bus standard supportati sono quattro:

• OPB: On-chip Peripheral Bus

• PLB: Processor Local Bus

• DCR: Device Control Register

• LMB: Local Memory Bus

Le interfacce supportate sono sei: una per il bus LMB, una per quello DCR

e due sia per il bus OPB che per il bus PLB, a seconda che il componente da

importare sia di tipo Master o Slave.

18

1.2. EDK

Figura 1.16: Opzione per la selezione dei files

Figura 1.17: Selezione bus

La descrizione dettagliata dei tipi di bus verra presentata successivamente, nel

capitolo relativo all’architettura di riferimento.

Il bus utilizzato dal componente per il calcolo della DFTe il bus OPB, come

indicato dalle specifiche.

Le schermate successive permettono di visualizzare le connessioni effettuate

19

1.3. ARCHITETTURA

da EDK tra il bus di riferimento ed il componente stesso (Figura1.18) e di im-

postare laMinimum size of address window(Figura 1.19), che rappresenta lo

spazio di indirizzamento riservato alla periferica.

Figura 1.18: Visualizzazione delle connessioni delle porte

Dopo aver effettuato queste operazioni, la procedura guidera l’utente verso

la conclusione dell’operazione, fino al raggiungimento della schermata che no-

tifica all’utente il successo dell’importazione del componente in EDK. A questo

puntoe possibile inserire il componente all’interno dello schema dell’architettura

semplicemente selezionandolo all’interno dell’elenco dei componenti di EDK.

1.3 Architettura

Il componente per il calcolo della DFTe stato sviluppato appositamente per es-

sere inserito all’interno di un’architettura che verra mappata sulla FPGA.

Viene ora introdotta questa architettura di riferimento e viene descritto il procedi-

mento seguito per la realizzazione dell’architettura finale, cioe quella contenente

l’IP core sviluppato.

20

1.3. ARCHITETTURA

Figura 1.19: Visualizzazione dei parametri

Quest’ultima architettura sara quella mappata effettivamente sulla FPGA e costi-

tuira dunque un’architettura completa di un sistema dedicato.

1.3.1 Definizione dell’architettura di riferimento

Ogni architetturae composta da vari componenti di tipologia differente; le tre

grandi classi in cui questi ultimi si possono suddividere sono:

• i processori, adibiti alla gestione dell’intera architettura e permettono di

eseguire il codice software.

• i componenti, le interfacce delle periferiche, che rappresentano gli elementi

di contatto tra la FPGA ed il mondo esterno, oppure i componenti interni al

sistema, come l’IP core realizzato per il calcolo della DFT.

• i bus, le linee di connessione consentono di connettere gli elementi prece-

denti in modo da permettere la comunicazione tra loro.

Per quanto riguarda i bus,e importante introdurre l’IBM Core Connect, un tipo di

bus sviluppato dall’IBM per ottenere elevate prestazioni [4].

L’architettura dei bus del Core Connect comprende:

21

1.3. ARCHITETTURA

• il PLB, Processor Local Bus.

Il bus PLBe utilizzato dal processore per accedere alle periferiche di mag-

giore velocita. Ha una dimensione di 32 bit per gli indirizzi e di 64 bit per i

dati e le istruzioni.

• l’OPB, On-chip Peripheral Bus.

Il processore accede alle risorse piu lente attraverso il bus OPB. Quest’ul-

timo e stato creato per limitare il traffico sul bus PLB ede un bus sincrono

che funziona indipendentemente, con un diverso livello di gerarchia rispetto

al processore.

Questo bus si compone di un bus da 32 bit per i dati ed uno da 32 bit per

l’indirizzamento. Il bus OPB ha l’importante caratteristica di poter gestire

piu componenti master contemporaneamente collegati ad esso. Per que-

sta caratteristica il bus dati ed il bus indirizzi sono implementati come un

multiplexer distribuito.

• il PLB to OPB bridge, un bridge tra i due bus appena presentati.

Il processore puo accedere ai componenti slave collegati al bus OPB at-

traverso un particolare componente chiamatoPLB to OPB bridge. Attraver-

so questo componente le periferiche che sono master sul bus OPB possono

accedere alla memoria presente sul bus PLB.

• il DCR bus,Device Control Registerbus.

Il bus DCRe stato progettato per trasferire dati dai registri di uso comune

del processore GPR (General Purpose Register) ed i registri di controllo dei

componenti connessi con il bus DCR stesso. Questo bus fornisce un bus

indirizzi da 10 bit ed un bus dati da 32 bit.

La struttura dell’architettura di riferimento, ovvero lo schema grafico riportato

dal file con estension.pbd, e mostrato in Figura1.20.

L’architettura mostrata in Figura1.20contiene un soft-processor MB, MicroB-

laze, indicato dalla lettera A, il cui schema con la relativa memoriae riportato in

Figura1.21.

La presenza del MicroBlaze all’interno dell’architettura comporta una maggiore

22

1.3. ARCHITETTURA

Figura 1.20: Schema dell’architettura di riferimento

occupazione di area, cosa che non avviene per il processore PPC; questo punto

verra analizzato piu avanti durante l’analisi dei problemi di spazio dell’architet-

tura originaria.

Oltre al soft-processor, questa architettura contiene anche il componente dcmmodule,

indicato dalla lettera B in Figura1.20, che serve per diminuire la frequenza alla

quale lavora il processore MicroBlaze, dividendola per un numero intero.

Quest’ultimo componente permette di realizzare degli IP core che possano lavo-

rare ad una frequenza inferiore ai 100 MHz imposta dal processore PPC, Power

PC, presente sulla scheda; questa caratteristica risulta fondamentale poiche none

possibile, come verra spiegato in dettaglio piu avanti, far lavorare il componente

per il calcolo della DFT alla frequenza di 100 MHz e dunque si rendera necessario

ridurre notevolmente la frequenza.

Il componente per il calcolo della DFT verra inserito nell’architettura attraverso il

collegamento con il bus OPB, chee indicato dalla lettera C in Figura1.20.

23

1.3. ARCHITETTURA

Figura 1.21: Schema del MicroBlaze

1.3.2 Architettura finale

Dopo aver importato l’IP core all’interno di EDK, come descritto precedente-

mente,e possibile inserirlo nell’architettura di riferimento attraverso lo schema

grafico presentato dal file con estensione.pbd.

L’architettura contenente il componente DFTe mostrata in Figura1.22, nella

qualee evidenziato l’IP core per il calcolo della DFT; la linea orizzontale che lo

unisce all’architettura rappresenta il suo collegamento con il bus OPB.

Dopo aver inserito il componente all’interno dell’architetturae necessario pas-

sare alla sua configurazione. Cliccando col tasto destro del mouse sul componente

e selezionando la voceObject Properties..., si accede alla finestra mostrata in figu-

ra 1.23. Questa schermata permette di modificare il nome e la versione del com-

ponente e di impostare i valori delBase Addresse delHigh Address, che rappre-

sentano lo spazio di indirizzamento del’IP core all’interno del bus; i valori inseriti

sono stati selezionati in modo da non entrare in conflitto con gli altri componenti

collegati al bus OPB, cioe in modo che ciascun IP core collegato allo stesso bus

abbia uno spazio di indirizzamento disgiunto dagli altri.

24

1.3. ARCHITETTURA

Figura 1.22: Schema dell’architettura finale

Figura 1.23: Configurazionde del componente

Dopo aver effettuato queste operazionie necessario compilare il codice sor-

gente per la gestione del componente, come descritto piu avanti, e sintetizzare

l’architettura finale per poterla mappare sulla FPGA.

25

1.4. DFT

1.4 DFT

La Trasformata Discreta di Fourier (DFT, Discrete Fourier Transformate)e uno

strumento utile in tutte quelle applicazioni che operano nel campo della gestione

dei segnali, in quanto consente la loro analisi in frequenza [1][3].

Si definisce risposta in frequenza di un segnale la funzione della frequenza

che descrive come vengono modificate ampiezza e fase di un esponenziale com-

plesso quando passa attraverso un sistema lineare tempo-invariante (LTI). Quando

l’ingresso di un sistema LTIe un esponenziale complesso l’uscita sara ancora un

esponenziale complesso con la stessa frequenza ma con ampiezza e fase modifi-

cate (vedi Figura1.24).

x(t) = Aej(2π f0t+ρ)

Figura 1.24: Schema di un sistema LTI

y(t) = Bej(2π f0t+Θ)

Il segnale y(t) puo essere rappresentato come somma integrale di impulsi (h(t)

e la risposta all’impulso del sistema):

y(t) =∮

Aej(2π f0(t−τ)+ρ)h(τ)dτy(t) = Aej(2π f0t+ρ) ∮

h(τ)e− j(2π f0τ+ρ)dτy(t) = Aej(2π f0t+ρ)H( f )

L’integrale e chiamato trasformata di Fourier, e viene indicata dal simbolo

26

1.5. CONCLUSIONI

H(f). Rappresenta la risposta in frequenza del sistema ede chiaramente indipen-

dente dal tempo;e una funzione complessa della frequenza che dipende esclusi-

vamente dalla risposta all’impulso del sistema h(t).

H( f ) =∮

h(τ)e− j(2π f0τ+ρ)dτ

La funzione che rappresenta H(f)e quindi pari, mentre quella che rappresen-

ta la sua fasee dispari. La DFT risulta essere un modello accurato per la rap-

presentazione dello spettro del segnale quando l’intervallo di campionamentoe

abbastanza largo (almeno 32 campioni).

1.5 Conclusioni

Sulla base dei concetti e delle conoscenze esposte precedentemente in questo capi-

tolo e dunque possibile procedere all’implementazione di un componente attraver-

so il linguaggio VHDL, per poi passare alla sua integrazione all’interno di EDK;

successivamente all’importazionee possibile inserire il componente all’interno

dell’architettura di riferimento, collegandolo con il bus, configurarlo in modo da

renderlo compatibile con l’intera architettura ed infine scrivere il codice eseguibile

necessario per farlo funzionare, in modo da ottenere un’architettura completa per

sistemi dedicati.

Sfruttando le informazioni relative alla DFTe inoltre possibile sviluppare un

componente che ne implementi l’algoritmo per poi utilizzarlo per effettuare il

procedimento precedentemente descritto.

Le motivazioni per cui il calcolo della DFTe stato selezionato come esempio e

la descrizione dei principali percorsi seguiti per le sue differenti implementazioni

sono oggetto del prossimo capitolo.

27

Capitolo 2

Presentazione della metodologia

29

2.1. L’ESEMPIO DELLA DFT

Vengono ora introdotte le principali motivazioni che hanno portato a conside-

rare l’algoritmo base per il calcolo della DFT come esempio ideale per descrivere

il processo di sviluppo di componenti per sistemi dedicati; partendo dall’analisi

delle sue caratteristiche fondamentali, si procede verso l’analisi della sua com-

plessita sia spaziale che temporale, fino a giungere ai dettagli implementativi delle

sequenze di istruzioni matematiche che sono alla sua base.

Si passa, successivamente, alla descrizione teorica dell’implementazione ori-

ginaria, ponendo risalto alla scomposizione in blocchi funzionali, alla rappresen-

tazione dei numeri e delle funzioni trigonometriche.

Nel paragrafo successivo si analizzano i problemi riscontrati durante lo svilup-

po della prima implementazione, quali la frequenza troppo elevata, il superamento

dei limiti di spazio disponibile sulla FPGA presa in considerazione ed i proble-

mi di sincronizzazione rilevati; vengono dunque proposte le possibili soluzioni ai

problemi presentati e, basandosi su queste, viene esposta una possibile implemen-

tazione alternativa.

Viene infine presentata la serie di implementazioni sviluppate per analizzare

il processo di ricerca del miglior compromesso tra spazio occupato e velocita di

esecuzione, focalizzando l’attenzione sulle conseguenze, in termini prestazionali,

delle scelte architetturali effettuate.

2.1 L’esempio della DFT

La realizzazione di un componente in grado di effettuare il calcolo della DFT

e stata presa come esempio per lo sviluppo di componenti per sistemi dedicati

essenzialmente per i seguenti motivi.

In primo luogo l’algoritmo base per il calcolo della DFTe noto e consta di un

numero finito di passi, che sono rappresentati da calcoli matematici effettuati sui

valori in ingresso per la produzione del risultato finale come somma dei risultati

parziali, ottenuti nelle fasi intermedie del processo; quindi questo algoritmo pre-

senta tutte le caratteristiche che lo rendono un ottimo candidato per essere imple-

30

2.1. L’ESEMPIO DELLA DFT

mentato attraverso un linguaggio di descrizione dell’hardware come, ad esempio,

il VHDL.

In secondo luogo le complessita spaziali e temporali relative all’implemen-

tazione dell’algoritmo base per il calcolo della DFT sono abbastanza elevate, e

quindi risulta sensato, se non addirittura essenziale, intraprendere un percorso che

miri all’ottimizzazione di questi due aspetti, per permettere da un lato di non oc-

cupare un’area troppo elevata della FPGA e dall’altro di eseguire il calcolo nel

minor lasso di tempo possibile.

La complessita spaziale risulta essere la somma dei registri e dei componenti

base necessari per gestire i 32 campioni, a cui si sommano, ovviamente, i com-

ponenti base utilizzati per il calcolo dei risultati intermedi che, nel caso migliore,

possono consistere nella logica che lavora su un singolo campione, effettuando

quindi questo calcolo per 32 volte consecutive, ogni volta su un campione di-

verso, e nel caso peggiore possono consistere nella logica sfruttata per effettuare

contemporaneamente i calcoli relativi ai 32 campioni, che occupa, quindi, un’area

circa 32 volte maggiore della precedente.

La complessita temporale, invece, risulta essere la somma dei tempi di elabo-

razione dei segnali, che nel caso migliore puo consistere nel tempo necessario ai

calcoli relativi ad un campione; cio avviene quando tutti i segnali vengono pro-

cessati in parallelo. Nel caso pessimo, viceversa, la complessita temporale risulta

essere la somma dei 32 tempi relativi ai calcoli effettuati in serie per i 32 segna-

li; in questo caso la complessita temporale ottenuta risulta, considerando uguali i

tempi per il calcolo dei singoli segnali, 32 volte la complessita rilevata preceden-

temente. Ovviamente il miglioramento di un aspetto comporta, inevitabilmente, il

peggioramento dell’aspetto duale.

Infine, come gia precedentemente evidenziato, questo algoritmo consiste nel-

l’effettuare determinati calcoli matematici sui 32 campioni in ingresso; poiche i

calcoli sono esattamente gli stessi per ogni campione (varia, ovviamente, il valore

del campione e, di conseguenza, il risultato finale, ma le formule applicate sono

le medesime), si puo pensare a varie implementazioni alternative dell’algoritmo,

ognuna delle quali si focalizzi su un determinato compromesso tra le due com-

31

2.2. IMPLEMENTAZIONE ORIGINARIA

plessita, quella spaziale e quella temporale, e percio l’algoritmo stesso si presta

ad essere utilizzato come esempio di esplorazione dello spazio delle soluzioni.

2.2 Implementazione originaria

La DFT e un algoritmo relativamente semplice per la creazione dello spettro di

frequenza (X[k]) di una sequenza discreta di campioni (x[n]), ede rappresentata

dalla formula [1]:

X(k) = ∑x(n)WknN

X(k) = ∑x(n)(cos(2πknN )− j sin(2πkn

N ))

dove:

k = 0−→ N−1

n = 0−→ N−1

WknN = e

2πnkN

dove kN rappresenta la frequenza.

Il risultato della DFT sono due vettori di dimensione N che rappresentano i

coefficienti di Fourier; in particolare nel primo vettore avremo valori reali che rap-

presenteranno l’ampiezza dello spettro di frequenza, mentre nel secondo avremo

valori immaginari che rappresenteranno la fase.

L’obiettivo da raggiungeree quello di implementare un dispositivo che mo-

dellizzi una DFT su una FPGA: tale dispositivo deve quindi essere in grado di

elaborare una sequenza discreta in ingresso fornendo una serie di valori attendibili

in uscita.

L’approccio inizialee stato quello di realizzare una rappresentazione modulare

32

2.3. REALIZZAZIONE DELL’IMPLEMENTAZIONE

della DFT, ossia di scomporre in piu blocchi distinti i vari processi necessari alla

realizzazione di tale algoritmo.

Il problema della realizzazione della DFTe stato separato in quattro blocchi

distinti:

• Blocco 1: contatore

• Blocco 2: memoria per i campioni

• Blocco 3: modulo per il calcolo del twiddle

• Blocco 4: modulo per il calcolo della sommatoria finale

1. Il contatoree basato su di un conteggio a log2(N) bit, necessario per fornire

agli altri moduli il valore corrente din. E’ regolato da un clock esterno, il

quale delimita i limiti di velocita dell’insieme delle operazioni.

2. Il blocco di memoriae un modulo sincrono nel quale sono memorizzati i 32

valori precampionati del segnale che si sta prendendo in considerazione. In

base al valoren fornito dal contatore restituisce il corrispondente campione.

3. Il terzo blocco prende in ingresso il valore del campione in uscita dalla

MemoriaCampioni, il valoren in uscita dal contatore, il valore d’ingressok

e calcola la parte reale e immaginaria di x[n].

4. Il blocco per il calcolo della sommatoria finale effettua appunto la somma-

toria fra tutti i valori reali e tutti i valori immaginari associati ai 32 campioni

in uscita dal blocco twiddle. Il valore della sommatoria viene restituito solo

quando il valore di ne 31.

2.3 Realizzazione dell’implementazione

Nella realizzazione di un sistema che modellizzi la DFT ci si rende subito conto

della presenza di diversi fattori che impongono delle regole da seguire durante la

fase di sviluppo, in modo da evitare l’insorgere di una serie di problematiche, per

33


esempio la rappresentazione dei numeri reali o delle funzioni trigonometriche e la

loro implementazione [3].

Un secondo problema consiste nel fatto che un’implementazione relativamente

semplice come quella proposta nel paragrafo precedente none facilmente imple-

mentabile con un linguaggio come il VHDL. Questo perche molti moderni com-

pilatori VHDL tendono a creare una netlist complessa se le specifiche VHDL non

sono ben scritte. La traduzione di un programma dal linguaggio C al linguaggio

VHDL non e un compito banale e per portarlo a termine correttamente si rende

necessario seguire gli accorgimenti descritti nei paragrafi seguenti.

Due ulteriori aspetti che verranno presi in considerazione, e che saranno an-

ch’essi discriminanti fondamentali nel raggiungimento dell’obiettivo finale, sono

la velocita del componente e la sua dimensione.

2.3.1 Rappresentazione dei numeri

Uno dei limiti principali che si incontra quando si sviluppa un progetto con tec-

nologie FPGA riguarda la gestione dei numeri reali [3].

Al fine di ottenere un adeguato livello di precisionee necessario manipolare i

valori reali con cui si avra a che fare attraverso operazioni di scalatura e tronca-

mento. Basta pensare ad esempio che il termineWknN (della formula della DFT) ha

valore compreso tra -1 e 1, mentre il termine X(k) appartiene a R. Non essendo

possibile utilizzare direttamente i numeri reali in virgola mobile, poiche la loro

sintesie troppo complessa, tutti i valori reali sono rappresentati in virgola fissa

tramite numeri interi, che richiedono operazioni di scalatura e troncamento.

Per rappresentare seno e coseno di un angolo verranno utilizzati 8 bit. Per

prima cosa il risultato delle due funzioni trigonometriche verra shiftato a sinistra

di 8 bit e quindi troncato, come mostrato in Figura2.1; in questo modo si ottiene

una rappresentazione basata su numeri interi del valore a virgola fissa delle due

funzioni. Il valore, prima di essere restituito come uscita, verra quindi shiftato di 8

bit verso destra. Nell’esempio precedente l’errore che si compie nel manipolare il

valoree attorno allo 0,2%. E’ possibile pero osservare che per valori dell’angolo

che si avvicinano a 0◦ e 90◦ l’errore che si riscontrera risultera piu elevato.

34


Figura 2.1: Shift e troncamento di un valore

2.3.2 Rappresentazione delle funzioni trigonometriche

I valori del seno e del coseno fra 0◦ e 90◦ con incremento di mezzo grado sono

memorizzati all’interno di due vettori nel blocco numero 3 al fine di diminuire la

complessita del sistema [3].

Il problema consiste, quindi, nel mappare correttamente un angolo con il cor-

retto valore del suo seno e del suo coseno. La rappresentazione degli angoli avviene

tramite la formula del termineWknN gia discussa in precedenza:

Θ = cos−1bReWknN crads

Il valore delπ e pero difficile da rappresentare accuratamente in un ambiente

che non fa uso della virgola per la rappresentazione dei numeri, e quindi la rap-

presentazione degli angoli in gradie data da:

Θ = 360◦knN

dove

360◦ rappresenta 2πkN rappresenta la frequenza

n rappresenta il numero del campione

Il valore dell’angoloe alla base del nostro algoritmo. La divisione per N dara

pero un risultato sicuramente non intero, e per questa ragione il valore dovra essere

moltiplicato per un determinato valore in base al numero di decimali presente in

35


Θ. Nel nostro caso, una DFT a 32 campioni,Θ=11,25kn. Cio significa che per

eliminare i decimalie sufficiente una moltiplicazione per 4, ossia effettuare uno

shift verso sinistra di due bit.

Figura 2.2: Quadranti della circonferenza trigonometrica

Una volta calcolato il valore dell’angolo, e dopo aver individuato quale il

suo quadrante corrispondente per definire il segno (vedi Figura2.2), esso viene

mappato in un angolo del primo quadrante (0◦-90◦), come mostrato in Figura2.3,

in modo da semplificare il calcolo del seno e del coseno.

Figura 2.3: Mappatura degli angoli

2.3.3 Problemi relativi alla prima implementazione

Durante lo sviluppo della prima implementazione si sono verificati principalmente

due problemi:

36

2.4. IMPLEMENTAZIONE FINALE

1. la sincronizzazione dei blocchi generava dei conflitti, compromettendo quin-

di il corretto funzionamento del componente, in quanto la frequenza del

clock (100 MHz) dell’architettura in cui era stato inizialmente inserito era

troppo elevata;

2. la periferica superava i limiti di spazio disponibile sulla FPGA, e non era

quindi possibile mapparla su quest’ultima per la sua eccessiva dimensione.

Il primo problema derivava essenzialmente dai percorsi critici (critical paths),

ovvero dei percorsi dell’architettura che non era possibile percorrere nel lasso di

tempo imposto dal ciclo di clock; per risolvere questoe stato necessario cambiare

l’architettura di riferimento per l’utilizzo della periferica; sie quindi passati da

un’architettura con un processore PowerPc ad una con un processore MicroBlaze

(un soft-processor) ed un modulo che permettesse di dividere la frequenza del

clock del nuovo processore, in modo da rallentarlo permettendo alla periferica di

funzionare correttamente, e quindi di soddisfare i vincoli posti dai percorsi critici.

Questa soluzione, pero, ha comportato l’utilizzo di un soft-processor, il Mi-

croBlaze, e, dunque, un’ulteriore occupazione di area sull’FPGA, aggravando

il problema relativo alla dimensione della periferica, che eccedeva lo spazio a

disposizione.

Questo problemae legato essenzialmente all’utilizzo della Virtex-II Pro Eval-

uation Board della Avnet come supporto.

Per la risoluzione dell’ultimo problema, cioe il superamento dei limiti di spazio,

si e passati allo sviluppo di architetture alternative della periferica, nel tentati-

vo di renderle completamente compatibili con l’architettura basata su processore

MicroBlaze.

2.4 Implementazione finale

Avendo riscontrato che la prima implementazione della periferica presentava un’ec-

cessiva occupazione d’area, sie tentato, nelle successive implementazioni, di ridurre

al minimo tutte le componenti della periferica stessa [1].

37


Questa fase di progettazione ha portato allo sviluppo dell’implementazione

finale, le cui principali differenze con l’implementazione originaria sono:

• il calcolo della DFT viene effettuato per un singolo valore della frequenza

alla volta; questo valore viene fornito in ingresso e quindi viene delegata

parte della logica applicativa, cioe quella relativa all’incremento del valore

della frequenza per effetuare il calcolo di tutti i campioni della DFT, alla

parte software dell’architettura.

• i campioni del segnale da trasformare non sono memorizzati nella descrizione

VHDL ma vengono letti dai registri dalblocco DFTmodule, e dunque

vengono forniti come ingresso al componente.

• i calcoli vengono effettuati da un unico blocco, ilblocco calcolo, che riceve

in ingresso dalblocco DFTmodulei valori dei campioni e della frequenza

per la quale calcolare la DFT ed al quale restituisce come uscita i valori

della parte reale e di quella immaginaria della DFT calcolata.

A questo punto si prospettavano due possibili soluzioni:

1. implementare l’intero processo in modo che tutti i calcoli (compresa la som-

matoria finale) fossero eseguiti tutti in serie all’interno di un singolo ciclo

del clock;

2. implementare il processo in modo che ad ogni ciclo di clock venisse ela-

borato un singolo segnale ed infine, con un ulteriore ciclo di clock, venisse

effettuata la sommatoria dei valori precedentemente calcolati.

La prima possibilita sarebbe stata la migliore in termini di prestazioni della

periferica poiche l’intero calcolo sarebbe avvenuto con un singolo ciclo del clock.

Il problema, pero, era che la frequenza dei due processori (100 MHz per il PPC

e 100MHz, ma divisibili per un numero intero compreso tra 2 e 12, per il Mi-

croBlaze) era comunque troppo elevata per permettere di effettuare tutti i calcoli

in serie in un singolo ciclo di clock.

38

2.5. IMPLEMENTAZIONI ALTERNATIVE

La seconda possibilita, completamente duale alla prima, consiste nello svol-

gere all’interno di ogni ciclo di clock i calcoli relativi ad un singolo campione del

vettore di ingresso. Le operazioni da svolgere all’interno del ciclo di clock sono

compatibili con una frequenza inferiore ai 10 MHz, e quindi la periferica cosı

ottenuta puo essere utlilizzata soltanto nell’architettura contenente il processore

MicroBlaze ed il modulo di divisione.

L’ultimo passo per arrivare all’implementazione finale della DFTe quello di

separare il modulo di calcolo dalDFT module.

2.5 Implementazioni alternative

Successivamente alla separazione del modulocalcolo dal DFT modulesi e pas-

sati all’analisi delle possibili scelte implementative per quanto riguarda la paral-

lelizzazione dei calcoli relativi ai campioni; per ogni singolo campione, infatti,

l’algoritmo per il calcolo della DFT prevede una serie di calcoli matematici la cui

unica variabilee rappresentata dal valore del campione preso in esame (la fre-

quenza viene considerata costante poiche rimane invariata dall’inizio alla fine per

tutti i campioni) e solo dopo lo svolgimento di queste operazioni per tutti i cam-

pioni viene eseguita la somma di tutti i risultati parziali ottenuti che, ovviamente,

dipende da questi ultimi.

Essendo dunque ogni blocco di calcolo (per blocco di calcolo si intende l’in-

tero processo di elaborazione effettuato per ogni campione in ingresso) dipen-

dente unicamente dal campione preso in esame, e quindi completamente indipen-

dente dagli altri blocchi di calcolo, appare evidente che effettuare l’esecuzione dei

blocchi di calcolo in serie o in paralleloe una scelta che dipende unicamente dal

compromesso tra tempo e spazio che si desidera conseguire.

L’esecuzione in serie dei blocchi di calcolo richiede la presenza di compo-

nenti base sufficienti per la realizzazione di un singolo blocco di calcolo, poiche

quest’ultimo verra sfruttato per ogni campione; i campioni, infatti, vengono pro-

cessati uno alla volta tramite il singolo blocco di calcolo, e il risultato parziale

viene memorizzato sommato ai precedenti risultati parziali ottenuti. In questo

39


modo, percio, si riduce l’area occupata sulla FPGA, ma il tempo necessario per

l’esecuzione risulta essere pari a 32 volte il tempo che richiede l’elaborazione di

un singolo segnale, e quindi la velocita del componente risulta essere di modesta

entita.

L’esecuzione in parallelo dei blocchi di calcolo, invece, richiede per l’ese-

cuzione totale del calcolo della DFT un tempo pari a quello necessario per l’ese-

cuzione di un singolo blocco di calcolo, e quindi la velocita del componente risulta

molto elevata. D’altro canto, pero, diventa indispensabile utilizzare un’area tale

da rendere possibile la realizzazione di 32 blocchi di calcolo differenti, quin-

di lo spazio richiesto dal componente diventa 32 volte lo spazio richiesto nella

configurazione precedente.

Sono state implementate 6 differenti tipologie di componente, ognuna basata

su un preciso rapporto tra area occupata e tempo di esecuzione.

L’implementazione originaria consiste nell’esecuzione in serie dei blocchi di

calcolo, e ricade quindi nel primo dei due casi precedentemente riportati.

Si e poi considerata un’implementazione che, utilizzando 2 blocchi di calcolo,

permette di effettuare l’elaborazione parallela di 2 segnali per volta, richiedendo

quindi 16 cicli per ottenere il risultato finale; i 2 campioni elaborati in parallelo

sono selezionati considerando il campionen-esimo(n dispari compreso tra 1 e 31)

ed il campione in posizionen+1.

Successivamente sie sviluppata un’implementazione avente 4 blocchi di cal-

colo e che, ovviamente, consente di processare 4 campioni contemporaneamente,

richiedendo 8 cicli per passare in rassegna tutti i campioni in ingresso; i 4 cam-

pioni sono individuati dalle posizionin (n compreso tra 1 e 29, conn+3 multiplo

di 4), n+1, n+2, n+3.

Un ulteriore sviluppo ha portato all’utilizzo di 8 blocchi di calcolo, con la

conseguente parallelizzazione di 8 campioni per volta, e la necessita di 4 cicli per

portare a termine il lavoro; gli 8 campioni elaborati parallelamente sono collocati

nelle posizionin (n compreso tra 1 e 25, con n+7 multiplo di 8),n+1, n+2, n+3,

n+4, n+5, n+6, n+7.

La penultima implementazionee caratterizzata dalla presenza di 16 blocchi

40

2.6. CONCLUSIONI

di calcolo, e dunque richiede l’esecuzione di solo 2 cicli, poiche in ogni ciclo

processa la meta dei campioni in ingresso (ovvero 16); durante il primo ciclo

vengono presi in considerazione i campioni nelle posizioni comprese tra la 1 e la

16, mentre durante il secondo ciclo quelli nelle posizioni comprese tra la 17 e la

32.

L’ultima implementazione, infine, ha 32 blocchi di calcolo, e dunque ricade

esattamente nel secondo caso descritto all’inizio del paragrafo, ovvero quello della

completa parallelizzazione dell’elaborazione dei campioni.

2.6 Conclusioni

Dopo aver analizzato tutti gli aspetti concettuali relativi alle varie implemen-

tazioni possibili ed aver chiarito le motivazioni che sono alla base delle decisioni

prese, si passa alla descrizione dettagliata dei codici che realizzano fisicamente le

implementazioni fin qui presentate.

Il prossimo capitolo pone cosı l’attenzione sui dettagli di progettazione, per

evidenziare in modo preciso quali percorsi sono stati realmente intrapresi per re-

alizzare le descrizioni in linguaggio VHDL del componente per il calcolo della

DFT.

41

Capitolo 3

Descrizione delle implementazioni

43


In questo capitolo viene preso in considerazione l’aspetto implementativo sot-

to il punto di vista dei dettagli di progettazione.

Si analizza dapprima l’implementazione originaria basata sulla scomposizione

in blocchi funzionali; viene fornita una breve descrizione e viene commentato il

codice nelle sue parti piu interessanti per ogni singolo blocco, partendo dal blocco

contatore, passando al blocco MemoriaCampioni proseguendo col blocco twiddle,

per finire la trattazione con il blocco dedicato alla sommatoria finale.

Viene, in seguito, presentata l’implementazione composta da un singolo bloc-

co di calcolo, che risolve i problemi generati dall’implementazione precedente,

e vengono descritti i blocchi per il suo interfacciamento con il bus OPB dell’ar-

chitettura base considerata, ovvero ilDFT moduleed il DFT.

Successivamente vengono descritte nel dettaglio le differenze sostanziali tra

le successive implementazioni del componente, ovvero vengono mostrate e com-

mentate le parti del codice che permettono di realizzare la parallelizzazione del-

l’elaborazione dei campioni, e che quindi consentono di modificare il rapporto

tra l’area occupata sul dispositivo programmabile e la velocita di esecuzione del

componente mappato su di esso.

Viene infine commentato il codice per la gestione software del componente

DFT; vengono presentate e descritte le funzioni per la lettura dai registri e per la

scrittura sugli stessi, oltre alla funzione utilizzata per gestire il calcolo della DFT e

viene presentato il codice che effettua le chiamate alle funzioni precedentemente

citate per gestire nel complesso il processo che porta all’elaborazione della DFT.

3.1 Implementazione originaria

Il sistema puo essere schematizzato come mostrato in Figura3.1[3].

L’implementazione originariae composta pertanto da quattro blocchi distinti:

• blocco contatore

• blocco memoriaCampioni

• blocco twiddle

44


Figura 3.1: Schema della prima implementazione

• blocco sommatore

Questi blocchi vengono descritti in dettaglio nei seguenti paragrafi, all’interno dei

quali viene riportato e commentato la loro descrizione in linguaggio VHDL.

3.1.1 Contatore

Il blocco contatorericeve in ingresso un segnale diclock, unenablee restituisce i

valori di n ek.

Ad ogni fronte di salita delclock, solo nel caso in cui il segnale dienablesia

alto, il valore din (contatore del sistema) viene incrementato di 1.

Quandon e pari a 32 il suo valore viene azzerato mentre viene incrementato il

valore della variabilek. Cio significa che tutti i 32 campioni sono stati analizzati,

il risultato e stato calcolato, e si passa quindi all’analisi del segnale ad una nuova

frequenza (definita appunto dalla variabilek).

L’unico problema relativo al modulo contatoree dovuto al fatto chen viene

incrementata solo in relazione ad un fronte di salita delclock: durante la simula-

zione del componente con Modelsim ci si rende conto che cio non avviene durante

il primo ciclo proprio perche il clockparte gia alto.

Basta quindi associare an il valore iniziale -1, in modo che il ciclo che viene

perso risulta essere un ciclo inutile per i nostri calcoli. La scelta di far terminare

45


il ciclo del contatore pern uguale a 32, cioe dopo 33 cicli (34 se si considera il

primo ciclo superfluo),e dovuta ad una motivazione pratica legata al calcolo della

sommatoria finale e verra spiegata nel dettaglio nel paragrafo relativo alblocco 4.

La descrizione in linguaggio VHDL relativa alblocco contatoree riportata in

Figura3.2.

Figura 3.2: Descrizione in linguaggio VHDL del blocco contatore

3.1.2 MemoriaCampioni

Il blocco MemoriaCampioniriceve in ingresso il valore corrente din in uscita dal

contatore, e restituisce il corrispondente campione del segnale ed il valoren in

ingresso.

46


Questo modulo ha un comportamento piuttosto semplice: al suo interno i 32

campioni del segnale sono memorizzati in un vettore.

Quando viene ricevuto un nuovo valore din in ingresso, esso viene utilizza-

to come indice del vettore e il corrispondente valore del campione viene inviato

all’uscita.

La scelta di mettere in uscita anche il valoren ricevuto in ingresso senza che

questo venga modificatoe necessaria per problemi di sincronizzazione.

Come si puo notare dallo schema iniziale il valoren passa dalblocco 1al

blocco 3solo dopo aver attraversato ilblocco 2: la scelta piu logica sarebbe quella

di farlo passare dalblocco 1direttamente sia alblocco 2che alblocco 3. Questa

seconda soluzione porta pero ad un problema dovuto al fatto che nel momento in

cui il blocco 3riceve il valore din e inizia ad operare, ilblocco MemoriaCampioni

non ha ancora inviato in uscita il nuovo campione. I calcoli effettutati dalblocco

3 risultano quindi errati in quanto effettuati con il valore del vecchio campione.

La descrizione in linguaggio VHDL relativa alblocco MemoriaCampionie

riportata in Figura3.3.

3.1.3 Twiddle

Il blocco twiddlericeve in ingresso il valore corrente del contatoren, il campione

corrispondente, il valore dik e restituisce il valore della parte reale e immaginaria

relativa.

Puo essere considerato il blocco principale del dispositivo, in quanto al suo

interno vengono eseguiti la maggior parte dei calcoli.

Una volta ricevuti i valorin e k, attraverso una serie di procedure gia spiegate

in precedenza, viene calcolato l’angolo corrispondente.

All’interno del blocco i valori del coseno e del seno sono gia memorizzati

all’interno di un vettore:e sufficiente quindi utilizzare l’angolo calcolato come

indice del vettore per avere a disposizione il valore del corrispondente seno o

coseno. Moltiplicando il campione per il seno e per il coseno si ottengono la parte

immaginaria e quella reale: prima di essere inviato all’uscita il risultato viene con-

47


Figura 3.3: Descrizione in linguaggio VHDL del blocco MemoriaCampioni

vertito in binario non piu pero su 8 bit ma su 9, in quanto quello piu significativo

e usato per rappresentare il segno.

La descrizione in linguaggio VHDL relativa al processo principale delblocco

twiddlee riportata in Figura3.4ed in Figura3.5.

3.1.4 Sommatoria finale

Il blocco sommatoriariceve in ingresso la parte reale e immaginaria calcolata dal

blocco twiddle, il valore del contatoren e, al termine dell’analisi dei 32 campioni,

restituisce la somma di tutte le parti reali e quella di tutte le parti immaginarie.

Questo blocco ha un comportamento relativamente semplice, anche se la ge-

stione dei valori comporta un problema fondamentale. I valori della parte reale e

di quella immaginaria vengono ricevuti come binari; effettuare le somme parziali

48


Figura 3.4: Prima parte della descrizione in linguaggio VHDL del blocco twiddle

Figura 3.5: Seconda parte della descrizione in linguaggio VHDL del blocco

twiddle

con i binari risulta problematico in quanto il nono bit non viene interpretato come

bit di segno, e quindi i valori attesi sono ben diversi da quelli reali. Per questo

49


motivo e necessario tradurre i binari in interi (facendo attenzione al bit di segno),

effettuare la sommatoria e riconvertire il risultato in binario.

Un ulteriore difficolta nella realizzazione di quest’ultimo moduloe dovuta al

fatto che nel calcolo della sommatoria totale non viene presa in considerazione la

parte reale e immaginaria relativa all’ultimo campione. Questo perche, una volta

arrivati all’ultimo ciclo (n=31), nel momento esatto in cui il blocco sommatoria

riceve i valori reali e immaginari relativi all’ultimo campione invia immediata-

mente all’uscita le due sommatorie senza averle prima aggiornate con i due nuovi

valori. Il problema puo essere risolto aggiungendo un nuovo ciclo superfluo per

n=32: nell’ultimo ciclo utile (n=31) le due sommatorie vengono quindi aggior-

nate, mentre il trentaduesimo cicloe utilizzato esclusivamente per inviare i valori

finali alle uscite.

La descrizione in linguaggio VHDL relativa alblocco sommatoriae riportata

in Figura3.6.

Figura 3.6: Descrizione in linguaggio VHDL della sommatoria finale

50


3.2 Implementazione finale

L’implementazione finale consta di un componentecalcoloutilizzato nelDFT module

[1].

Il DFT modulelegge dai registri i valori dik (la frequenza alla quale calcolare

la DFT), dei 32 campioni e del segnale distart, e li passa alblocco di calcoloin-

sieme alclock, ed ilblocco di calcologli restituisce i valori (reale ed immaginario)

della DFT alla frequenzak ed il valore del segnaleok.

L’implementazione finale della periferica, dunque,e composta da tre blocchi:

1. blocco DFT

2. blocco DFTmodule

3. blocco calcolo

3.2.1 DFT

Figura 3.7: Architettura del componente

Il blocco DFTpermette di interfacciare ilblocco DFTmodulecon il bus OPB,

grazie al componentepselect, e di definire le principali funzioni standard che per-

mettono ad una qualunque periferica collegata al bus OPB di funzionare corretta-

51


mente, come le funzioni di indirizzamento e quelle per la sincronizzazione della

lettura e della scrittura sul bus. L’architettura risultantee mostrata in Figura3.7.

Il componentepselectserve per abilitare un determinato componente (periph-

eral select), ovvero attivarlo per renderlo sensibile ai segnali provenienti dal bus,

in modo da evitare i conflitti che si potrebbero generare data la condivisione da

parte di piu componenti di un unico bus.

Una possibile architettura alternativa puo essere realizzata sostituendo il com-

ponentepseletccon l’ipif ; quest’ultimo componente risulta pero essere piu com-

plesso del precedente e poiche le sue caratteristiche aggiuntive non sono di inte-

resse nell’ambito in cui si sta operando sie preferito utilizzare il piu sempliceps-

elect, che risulta sufficiente a soddisfare le necessita di interfacciamento richieste

dall’IP core realizzato

3.2.2 DFT module

Il blocco DFTmodulesvolge effettivamente tutte le operazioni di lettura e scrit-

tura riguardanti i registri.

Lo spazio di indirizzamento del componentee mostrato in Figura3.8, nella

quale vengono precisate le funzioni di ingresso o di ingresso/uscita relative ad

ogni indirizzo; l’indirizzo assoluto viene calcolato sommando alBase Address

l’indirizzo relativo riportato sulla destra.

In particolare ilblocco DFTmoduleassocia il valore scritto sui registri ai se-

gnali corrispondenti; questi registri sono relativi alla frequenza alla quale si vuole

calcolare la DFT, ai 32 campioni in ingresso ed al segnale distart, che permette

di avviare l’esecuzione dei calcoli, per impostare i relativi se. La mappatura dei

registri in fase di ingresso con i rispettivi indirizzie mostrata in Figura3.9.

Tutti questi segnali, oltre al segnale diclock, vengono passati alblocco cal-

colo, che restituisce alblocco DFTmodulei valori della sommareale e della

sommaimmaginaria, che costituiscono il valore reale ed immaginario della DFT

alla frequenza desiderata, ed il segnaleok, che segnala il termine del processo di

calcolo da parte delblocco calcolo. Il blocco DFTmodule, infine, si occupa di

52


Figura 3.8: Schema dello spazio di indirizzamento

scrivere sui registri, che vengono mappati agli indirizzi mostrati in Figura3.10, il

valore di questi tre segnali di uscita.

3.2.3 Calcolo

Il componente dicalcoloconsta di un unico processo attivato dal segnale diclock,

che opera nel seguente modo: finche il segnale distart resta basso (tutti i bit di

53


Figura 3.9: Schema dei registri in fase di ingresso

Figura 3.10: Schema dei registri in fase di uscita

start sono 0) si limita a tenere il contatoren al valore 0, a leggere e memorizzare

il valore della frequenza dal registro e ad impostare al valore di default (tutti i bit

54


a 0) i segnali di uscita (sommareale, sommaimmaginariaeok).

Quandostart risulta essere diverso da 0 (almeno 1 bit diverso da 0), sul fronte

di salita del primo ciclo delclock inizia il processo di calcolo relativo al primo

campione in ingresso; terminato questo processo viene memorizzata la somma

parziale dei valori calcolati (sia dei reali che degli immaginari) e viene incre-

mentaton in modo che al seguente ciclo del clock venga processato il campione

successivo; una volta processato il trentaduesimo campione, e calcolata la somma

totale (reale e immaginaria), vengono settati i segnali di uscita con i relativi valori

calcolati e viene alzato il segnaleok (tutti i bit a 1) per indicare il termine del

processo di calcolo.

Il blocco calcoloe il cuore della periferica essendo il blocco che effettivamente

si incarica di calcolare il valore della DFT.

In Figura3.11ed in Figura3.12viene riportato la descrizione in linguaggio

VHDL del processo principale delblocco calcolo, per evidenziarne le differenze

con la prima implementazione (l’implementazione modulare).

3.3 Implementazioni alternative

Successivamente alla realizzazione del componente descritto nel paragrafo prece-

dente, si passa alla stesura del codice relativo alle implementazioni alternative.

Per quanto riguarda queste ultime, non vengono apportate modifiche ne al

blocco DFT, ne alblocco DFTmodule, poiche i cambiamenti riguardano sostanzial-

mente il processo di calcolo, cioe il metodo utilizzato per effettuare l’elaborazione

matematica dei campioni in ingresso, e quindi ilblocco calcolo.

Non viene alterata, invece, tutta la parte del componente utilizzata per la gestione

dei segnali di input/output e per l’interfacciamento col bus.

Viene mostrato, in questo modo, il vantaggio di separare il componente in tre

blocchi, che si dedicano ad aspetti concettualmente differenti, in modo che una

variazione di un singolo aspetto non si ripercuota su tutta la struttura, ma riman-

ga, al contrario, confinato all’interno del blocco considerato; questa trasparenzae

molto utile anche dal punto di vista della gestione esterna del componente, poiche

55


Figura 3.11: Prima parte della descrizione in linguaggio VHDL del blocco di

calcolo

le differenze tra le implementazioni non influenzano il codice software che le uti-

lizza, che puo, dunque, essere scritto, come evidenziato nel paragrafo3.4, senza

preoccuparsi delle specifiche caratteristiche di calcolo dell’implementazione con

la quale verra associato.

Per comodita chiameremo le differenti implementazioni con il prefisso DFT

al quale si aggiunge il numero di cicli necessari per portare a termine il calcolo

totale; quindi l’implementazione con un solo blocco di calcolo si chiama DFT32,

quella con 2 blocchi di calcolo si chiama DFT16, quella con 4 blocchi di calcolo

si chiam DFT8, quella con 8 blocchi di calcolo si chiama DFT4, quella con 16

blocchi di calcolo si chiama DFT2 ed infine quella con 32 blocchi di calcolo si

chiama DFT1.

All’interno del blocco calcoloe possibile notare le prime differenze gia nel-

la fase di dichiarazione delle variabili; la DFT32 presenta il minor numero di

56


Figura 3.12: Seconda parte della descrizione in linguaggio VHDL del blocco di

calcolo

variabili, in accordo con la sua peculiare ottimizzazione spaziale.

Osservando le variabili dichiarate nella DFT16, si nota immediatamente la

duplicazione dicosvalue, sin value, campione, theta, tempdiv real, tempdiv imag,

flag cos, flag sin e sign; viene inoltre aggiunta la variabilet per semplificare le

operazioni del calcolo dell’angolo (i dettagli verrano presentati piu avanti nel

capitolo).

Questa duplicazione avviene anche nelle successive implementazioni, ognuna

delle quali raddoppiera il numero delle variabili sopracitate presenti nell’imple-

mentazione precedente, fino a giungere alla DFT1 che presentera una variabile

per ogni campione in ingresso, e dunque 32 variabili di ogni tipo;e da notare

che nella DFT1 viene a mancare la variabilen, che rappresenta il contatore,

e che ovviamente non viene utilizzato quando tutti i campioni sono processati

contemporaneamente.

57


Successivamente si passa al calcolo degli angoli, che nella DFT32 viene

effettuato come mostrato in Figura3.13.

Figura 3.13: Calcolo degli angoli nella DFT32

Nella DFT 16, invece, viene utilizzato il codice riportato in Figura3.14.

Figura 3.14: Calcolo degli angoli nella DFT16

Il numero delle istruzioni necessarie per il calcolo degli angoli aumenta pro-

porzionalmente al numero di campioni processati in parallelo e viene percio rad-

doppiato ad ogni passaggio all’implementazione successiva.

In tutte le implementazioni, tranne la DFT32, e presente la variabilet, che

viene utilizzata per effettuare un’unica volta il calcolo della moltiplicazione dik

per 45, termine che viene successivamente utilizzato per calcolare tutti gli angoli

necessari.

Nella parte di codice rimanente, tutti i costrutti vengono replicati per permet-

tere il calcolo di tutte le variabili parziali necessarie, facendo attenzione a non

replicare i cicli for, ma inserendo tutte le operazioni all’interno di un unico ciclo.

Viene preso ad esempio il costrutto della DFT32 mostrato in Figura3.15.

Figura 3.15: Riduzione degli angoli nella DFT32

Lo stesso costruttoe presente nella DFT16 ede mostrato in Figura3.16.

Un’ultima importante differenza risiede nel costruttocase, che nella DFT32

si presenta come mostrato in Figura3.17.

58


Figura 3.16: Riduzione degli angoli nella DFT16

Figura 3.17: Costrutto case nella DFT32

Nella DFT 16 il costruttocaseviene modificato come indicato in Figura3.18.

Nelle successive implementazioni ogni sezionewhenviene espansa in mo-

do da contenere 4, poi 8 poi 16 campioni, rispettivamente nella DFT8, nella

DFT 4 e nella DFT2, fino ad arrivare alla DFT1 nella quale none piu pre-

sente il costruttocase, non essendo piu necessaria la selezione del campione, o

dei campioni, da elaborare, proprio perche i campioni sono tutti processati con-

temporaneamente all’interno del primo ciclo e quindi, avendo a disposizione 32

varibili, ogni campionee memorizzato in una singola variabile.

59

3.4. GESTIONE SOFTWARE DEI COMPONENTI

Figura 3.18: Costrutto case nella DFT16

3.4 Gestione software dei componenti

Nel paragrafo precedente sie discusso il tema della trasparenza dell’implemen-

tazione del blocco calcolo per quanto riguarda la stesura del codice per la gestione

del componente.

Viene presentato ora il driver (il filefunction.c) per la gestione del compo-

nente, senza una precisa indicazione dell’implementazione di riferimento, essendo

esso stesso valido per ognuna di esse; nella sezione A indicata in Figura3.19

vengono mostrate le funzioni di interesse per la gestione dell’input/output del

componente, contenute nel filefunction.c.

Il processo per il calcolo della DFT si puo suddividere nelle due seguenti fasi:

60


Figura 3.19: Funzioni del file function.c

• la configurazione del componente, che serve per impostare i valori di tutti i

segnali di ingresso, compreso il segnale per l’avvio del calcolo;

• la lettura del risultato, che serve per ottenere il valore della DFT calcola-

to, ovviamente dopo essersi assicurati che il componente abbia terminato

l’esecuzione del calcolo.

La descrizione di queste due fasi, la spiegazione del codice necessario per

portarle a termine e la presentazione di alcuni esempi sono oggetto dei paragrafi

seguenti.

3.4.1 Configurazione del componente

Per configurare il componentee necessario impostare i registri con i valori desiderati;

questi valori riguardano la frequenza alla quale si vuole calcolare la DFT, i valori

dei 32 campioni in ingresso ed il segnale distart, che serve per avviare l’ese-

cuzione del calcolo della DFT e dunque deve essere impostato per ultimo. Suc-

cessivamente all’avvio dell’esecuzionee possibile interromperla, eventualmente

dopo aver letto il risultato in uscita, riportando il segnale distart a 0 (tutti i bit

impostati a 0), modificare i dati che si desidera variare, ad esempio il valore del-

61


la frequenza alla quale si vuole calcolare la DFT, ed infine avviare nuovamente

l’esecuzione per effettuare un nuovo calcolo basato sui nuovi dati e su quelli che

sono rimasti invariati dall’esecuzione precedente.

Per la scrittura dei dati in ingresso sui registrie necessario conoscere l’indi-

rizzo al quale si deve effettuare la scrittura e disporre di una funzione che effettui

la scrittura del dato all’indirizzo desiderato; gli indirizzi, relativi allo spazio di in-

dirizzamento del componente (offset), dei diversi registri in fase di ingresso sono

indicati in Figura3.9, mentre la funzione per la scritturae la funzionescrivi del

file function.c.

Figura 3.20: Funzione scrivi

In Figura3.20viene evidenziata la funzionescrivi che, come sottilineato dal

suo nome, serve per poter scrivere dati in un determinato registro del compo-

nente DFT. Questa funzione ha come parametri di ingresso due interi senza se-

gno,data e offset, e non presenta alcuna uscita; il parametrodata rappresenta il

dato che si desidera memorizzare nello spazio di indirizzamento della periferica,

e piu precisamente nella posizione indicata dal parametrooffset, che rappresenta

la variazione di indirizzo rispetto all’indirizzo base della periferica; la funzione

scrivi e composta da un’unica istruzione, oltre all’istruzione di return, che uti-

lizza un’ulteriore funzione, ovvero laXGpio mWriteRegper scrivere all’indirizzo

rappresentato dal parametroXPARDFT 1 BASEADDR(l’indirizzo base del com-

ponente DFT) con unoffsetrappresentato dal parametrooffset, i dati rappresentati

dal parametrodata.

3.4.2 Lettura del risultato

Per effettuare la lettura del risultatoe necessario controllare il valore del registro

per la segnalazione del termine dell’esecuzione; quando il valore di questo registro

risulta essere diverso da 0 (tutti i bit impostati a 0), significa che il componente

62


ha terminato il calcolo e quindi si puo passare alla lettura dei registri contenenti il

valore reale e quello immaginario della DFT.

Per la lettura di questi 3 registri di uscitae necessario conoscere l’indirizzo al

quale si deve effettuare la lettura e disporre di una funzione che effettui la lettura

del dato contenuto nel registro all’indirizzo desiderato; gli indirizzi, relativi allo

spazio di indirizzamento del componente (offset), dei diversi registri in fase di

uscita sono indicati in Figura3.10, mentre la funzione per la letturae la funzione

leggidel file function.c.

Figura 3.21: Funzione leggi

La funzioneleggi, indicata in Figura3.21, serve per leggere il contenuto di un

determinato registro del componente DFT. Questa funzione riceve come parametro

in ingresso un intero senza segno,offset, che rappresenta la variazione di indiriz-

zo rispetto all’indirizzo base della periferica, e restituisce un intero senza segno

rappresentante il contenuto del registro selezionato tramite l’offset. Anche questa

funzionee composta da un’unica istruzione, e piu precisamente dalla chiamata alla

funzioneXGpio mReadReg, alla quale viene passato il valore dell’indirizzo base

del componente DFT,XPARDFT 1 BASEADDR, e l’offsetrelativi al registro di

cui leggere il valore.

Viene ora presentata la funzionecalcola che, pur non aggiungendo nessuna

funzionalita ripetto alle precedenti, ne semplifica l’utilizzo, incorporando una se-

rie di istruzioni di uso comune; questa funzione, infatti, si basa sulle due prece-

denti funzioni per effettuare il calcolo della parte reale e della parte immaginaria

della DFT per un determinato valore della frequenza: prende in ingresso due interi

senza segno,d edn, e non presenta alcuna uscita;n rappresenta il numero che si

vuole visualizzare come indice dei risultati nel momento in cui verranno stam-

pati a video la parte reale e la parte immaginaria della DFT, mentred rappresenta

il valore della frequenza alla quale si vuole calcolare la DFT. La prima riga di

codice di questa funzione serve per dichiarare due variabili intere senza segno che

63


Figura 3.22: Funzione calcola

verranno utilizzate piu avanti all’interno della funzione; le successive istruzioni,

ovvero le tre chiamate alla funzione scrivi, servono per resettare il segnale distart

del componente DFT, per impostare il valore della frequenza in base al valore di

d ed infine per settare il segnale distart. Dopo l’esecuzione di queste istruzioni,

il componente DFT comincia il processo di calcolo, e la funzione leggi si mette

in attesa che il componente setti il segnaleok, ovvero segnali la terminazione del

calcolo; questa attesa viene effettuata tramite il ciclo:

os=0x00; while(leggi(os)==0x00000000)

Nel momento in cui il componente termina la sua esecuzione, e di conseguenza

setta il segnaleok, la funzione calcola esce dal loop e, attraverso le due successive

chiamate alla funzione leggi, accede ai registri contenenti i risultati relativi alla

parte reale ed a quella immaginaria della DFT per leggerne e stamparne a video il

valore, ed infine esegue l’istruzione di return per tornare alla procedura chiamante.

64


3.4.3 Codice d’esempio

All’interno del file system0.csono effettuate delle chiamate dirette alle funzioni

scrivi e calcoladel file function.c, mentre la funzioneleggi e chiamata indiretta-

mente dalla funzionecalcola.

Figura 3.23: Codice per la configurazione del componente

In Figura3.23viene mostrata la configurazione del componente per predispor-

lo ad effettuare il calcolo della DFT; vengono memorizzati nei registri i valori dei

32 campioni in ingresso ed il valore della frequenza alla quale si vuole calcolare

la DFT.

In Figura 3.24 vengono mostrate le chiamate alla funzione calcola, ognuna

effettuata ad una frequenza differente; in questa sezione del codice vengono effet-

tuate 32 chiamate a tale funzione, in modo da stampare a video i 32 valori reali ed

i 32 valori immaginari della DFT calcolata per 32 differenti valori della frequenza

(ovviamente ciascuna coppia di valori reali ed immaginarie calcolata per ciascun

differente valore della frequenza).

In questo modoe possibile calcolare i 32 campioni (ognuno dei quali compo-

65

3.5. CONCLUSIONI

Figura 3.24: Codice per l’elaborazione dei dati

sto da una parte reale ed una immaginaria) che costituiscono la DFT del segnale

rappresentato dai 32 campioni di ingresso.

3.5 Conclusioni

Dopo aver descritto i dettagli tecnici delle implementazioni, avendo mostrato le

differenze dal punto di vista della programmazione tra l’implementazione origina-

ria e quelle successive, ed aver proposto un esempio di codice per gestirle, si pas-

sa, nel prossimo capitolo, alla presentazione dei dati ricavati dalla compilazione

delle architetture in EDK, per evidenziare le differenze prestazionali in termini

quantitativi, in aggiunta alla visione qualitativa finora offerta.

66

Capitolo 4

Dati e conclusioni

67

4.1. DATI

In questo capitolo vengono riportati i dati relativi a tutte le architetture realiz-

zate; le informazioni su cui si pone attenzione sono quelle relative all’occupazione

di area sulla FPGA e quelle relative ai tempi di esecuzione che variano a seconda

dell’architettura considerata.

Poiche la realizzazione di tutte le architetture ha avuto inizio dall’architettura

di riferimento presentata precedentemente e l’unica differenza nel loro sviluppo

consiste nell’utilizzo di un differente IP core per ognuna di esse,e logico consi-

derare i dati che variano da un’architettura all’altra come dati strettamente dipen-

denti dai componenti inseriti nelle diverse architetture.

Per questo motivo le architetture considerate nel presente capitolo verranno indi-

cate col nome del particolare componente che le caratterizza.

Partendo da questi dati si effettueranno confronti prestazionali in termini quan-

titativi, per dare al lettore un’idea piu precisa dei costi da sostenere per poter

utilizzare l’architettura contenente il componente per il calcolo della DFT.

L’analisi di queste informazioni conduce alla formulazione di alcune conside-

razioni conclusive, che sono oggetto della parte finale di questo capitolo.

4.1 Dati

Vengono ora presentati i dati relativi all’occupazione di area sulla FPGA ed alla

massima frequenza del clock sostenibile per ogni architettura realizzata.

Le informazioni esposte in questo paragrafo riguardanti le dimensioni delle

architetture vertono principalmente attorno al numero di componenti base della

FPGA necessari in rapporto ai componenti base messi a disposizione dalla scheda

Virtex 2 Pro, considerando unicamente i dati dipendenti dall’IP core considerato

e tralasciando quelli che rimangono costanti al variare dell’implementazione.

I dati relativi alla DFT32 sono mostrati in Figura4.1. Dall’analisi di questi

dati si deduce che l’architettura presa in esame occupa piu della meta (57%) del-

la FPGA; questo dato conferma l’ipotesi considerata nel terzo capitolo, secondo

la quale la complessita spaziale raggiunta sarebbe stata abbastanza elevata. La

percentuale di utilizzo dei componenti critici (cioe quelli dipendenti dall’imple-

68

4.1. DATI

Figura 4.1: Dati relativi alla DFT32

mentazione considerata) si attesta tra il 47% ed il 51% per i 4 input LUT e sul 13%

per i MULT18x18; tutti questi valori sono, quindi, ampiamente inferiori rispetto

alla soglia della disponibilita offerta dalla FPGA.


In Figura4.2sono invece riportati i dati relativi alla DFT16. La percetuale di

69

4.1. DATI

occupazione della scheda risulta notevolmente aumentata rispetto al caso prece-

dente, ovvero 87% in confronto al precedente 57%, mae ancora sufficientemente

bassa da permettere la mappatura dell’intera architettura sulla FPGA. Anche la

percentuale di utilizzo dei componenti critici subisce una variazione seguendo la

medesima tendenza, infatti si raggiungono i valori compresi tra il 74% e l’80% per

i 4 input LUT e del 20% per i MULT18x18, valori ancora entro i limiti imposti

dal dispositivo.


Per quanto riguarda la DFT8, al contrario, i dati, mostrati in Figura4.3, in-

dicano chiaramente il superamento di alcune soglie limite (segnalato dalla parola

overmapped). La percentuale di spazio occupato viola il massimo del 100%, ar-

rivando ad un valore del 129%; cio significa che l’architettura realizzata non puo

essere contenuta nella FPGA presa in considerazione poiche l’IP core inserito

risulta avere dimensioni troppo elevate. La percentuale dei componenti critici su-

pera il 100% per quanto riguarda i 4 input LUT, il cui valore si aggira tra il 117%

ed il 126%, mentre rimane inferiore per i MULT18x18 (36%).

Le successive architetture hanno dimensioni maggiori della DFT8 e percio

nemmeno loro possono essere contenute nella FPGA; la percentuale di occu-

pazione della scheda per la DFT4 raggiunge il 214%, la percentuale di utilizzo

70

4.1. DATI

dei 4 input LUT e compresa tra il 196% ed il 210%, mentre quella relativa ai

MULT18x18 e del 68%; la percentuale di occupazione della scheda per la DFT2

raggiunge il 378%, quella dei 4 input LUT si attesta tra i 346% ed il 370%, mentre

quella dei MUL18x18 raggiunge i 131%.


Si riportano a titolo esemplificativo i dati relativi alla DFT1, mostrati in Figu-

ra 4.4; quest’ultima architettura raggiunge il picco di occupazione di area col

735%. Anche le percentuali di utilizzo dei componenti critici raggiungono va-

lori enormi, compresi tra il 674% ed il 711% per quanto riguarda i 4 input LUT e

del 150% per i MUT 18x18.

Per quanto riguarda l’analisi della massima frequenza del clock che ciascu-

na architettura, e dunque ciascun IP core, puo sostenere, va precisato che nella

precedente trattazione sie parlato della velocita di esecuzione di un IP core in

termini di numero di cicli effettuati; in effetti l’unita di misura presa in considera-

zione, ovvero il singolo ciclo del clock, non ha una durata equivalente per tutte le

implementazioni.

All’aumentare di componenti base utilizzati, e quindi al crescere dello spazio

richiesto dall’IP core sulla FPGA, infatti, la frequenza del clock deve essere via via

71

4.2. CONCLUSIONI

diminuita poiche il crescere delle dimensioni comporta l’aumento della comples-

sita della netlist, e quindi un leggero peggioramento delle prestazioni temporali.

Limitandoci ad analizzare i dati relativi alle architetture che riescono ad es-

sere fisicamente mappate sulla FPGA, ovvero la DFT16 e la DFT32, si puo co-

munque osservare che l’approssimazione precedentemente utilizzatae accettabile

con un limitato margine d’errore. Il periodo minimo compatibile con la DFT16,

calcolato automaticamente da EDK, risulta essere di 204.796 ns (quindi la mas-

sima frequenza del clocke di 4.883 MHz), mentre quello della DFT32 soltanto

187.104 ns (quindi la frequenza del clock puo essere aumentata fino a 5.345 MHz).

Da questi dati si puo evincere che il tempo di esecuzione richiesto dalla DFT16

e di circa 3.28 us (calcolato effettuando la moltiplicazione tra il numero di cicli di

clock necessari per l’elaborazione di tutti i segnali, ovvero 16, e la durata di cia-

scun ciclo, equivalente al periodo del clock), mentre quello richiesto dalla DFT32

risulta essere 5.99 us (calcolato effettuando la moltiplicazione tra il numero di ci-

cli di clock necessari per l’elaborazione di tutti i segnali, ovvero 32, e la durata di

ciascun ciclo, equivalente al periodo del clock).

Utilizzando come unita di misura il numero di cicli, la DFT16 risulta avere

una velocita esattamente doppia rispetto alla DFT32, poiche la prima necessita

di 16 cicli di clock, mentre la seconda di 32.

Utilizzando come unita di misura il tempo effettivo necessario ai due IP core,

la DFT 16 risulta essere 1,83 volte piu veloce della DFT32; questo risultatoe

stato ottenuto effettuando il rapporto tra i due tempi di esecuzione.

I risultati ottenuti attraverso l’analisi effettuata utilizzando i cicli come unita

di misura, dunque, presentano un errore legato all’approssimazione inferiore al

10% (l’errore relativo percentuale vale circa 9,3%), e quindi l’approssimazione

effettuata risulta ampiamente accettabile.

4.2 Conclusioni

La stima della variazione della complessita spaziale di un’architettura puo essere

effettuata, in prima analisi, utilizzando come unita di misura il numero di bloc-

72

4.2. CONCLUSIONI

chi di calcolo presenti nel componente per il calcolo della DFT in essa presente;

e proprio questa variabile, infatti, che viene modificata per generare le diverse

implementazioni del componente ede, quindi, responsabile dell’aumento o della

diminuzione dello spazio occupato dall’intera architettura.

Per quanto riguarda le prestazioni temporali, invece, come dimostrato nel para-

grafo precedente,e possibile basarsi sul numero di cicli effettuati, considerando

costante, in prima approssimazione, la durata dei differenti cicli.

Figura 4.5: Relazione tra cicli e blocchi di calcolo

La relazione tra le due grandezze appena introdottee mostrato dal grafico in

Figura 4.5, che raffigura l’andamento di un ramo di iperbole, per indicare che

il numero di blocchi utilizzati ed il numero di cicli richiesti per l’esecuzione

sono inversamente proporzionali tra loro, ovvero all’aumentare del primo valore

il secondo tende a diminuire e viceversa.

73

4.2. CONCLUSIONI

Figura 4.6: Relazione tra gate e blocchi di calcolo

Una misura piu raffinata dell’occupazione di spazio sulla FPGAe rappresen-

tata dal numero di gate equivalenti; questo dato puo essere ricavato per ogni im-

plementazione dal precedente paragrafo; la relazione tra questa misurazione spe-

rimentale e quella approssimata, il numero di blocchi,e mostrato in Figura4.6;

la relazione esistente tra queste due variabilie di proporzionalita diretta, ovvero

l’aumento della prima comporta l’aumento della seconda; questo fatto confer-

ma l’ipotesi secondo la quale il numero di blocchi puo essere considerato, con

un’approssimazione accettabile, come indice della complessita spaziale.

Dai risultati ottenuti dalle due precedenti osservazioni si puo dedurre che la

relazione tra il numero di cicli ed il numero di gate equivalenti dovrebbe essere

simile a quella esistente tra il numero di cicli ed il numero di blocchi di calcolo;

il grafico riportato in Figura4.7, infatti, assomiglia ad un ramo di iperbole equi-

74

4.2. CONCLUSIONI

Figura 4.7: Relazione tra cicli e gate

latera, a dimostrazione della proporzionalita inversa esistente tra le due variabili

considerate.

Prima di analizzare il costo totale di ogni implementazione in base al nu-

mero di blocchi utilizzatie necessario stabilire un criterio per determinare come

valutarlo.

Nel caso in cui si ponesse l’attenzione sulle dimensioni del componente, il

costo sarebbe quello indicato dalla linea A della Figura4.8, ovvero l’implemen-

tazione ottimale sarebbe quella col minor numero di blocchi di calcolo, cioe la

DFT 32, che ne utilizza soltanto 1.

Considerando come criterio base per il calcolo del costo unicamente la velocita

del componente, invece, ci si dovrebbe soffermare sulla linea B della Figura4.8;

in questo caso, infatti, l’implementazione migliore sarebbe quella contenente il

75

4.2. CONCLUSIONI

Figura 4.8: Relazione tra costo e blocchi di calcolo

maggior numero di blocchi, la DFT1, poiche permette di eseguire il calcolo nel

minor numero di cicli, ovvero soltanto 1.

Per ottenere una visione globale delle caratteristiche del componente, e dunque

dell’architettura nella qualee inserito, risulta interessante utilizzare come criterio

di costo la somma tra il numero di cicli ed il numero di blocchi, eventualmente

moltiplicati per delle costanti per assegnargli pesi differenti; utilizzando un peso

sbilanciato verso il numero di blocchi si ricadrebbe nel caso della linea A, mentre

con un peso sbilanciato verso il numero di cicli la linea degenererebbe nella linea

B.

La linea C della Figura4.8 mostra il costo calcolato come somma dei due

fattori aventi la stessa costante di peso; in questo caso si nota che il componente

ideale ricade all’interno della gamma di IP core realizzati, e non alle estremita

76

4.2. CONCLUSIONI

come nei casi precedenti; si puo dunque affermare che, utilizzando questo criterio

di costo, il miglior compromesso tra le prestazioni spaziali e quelle temporali si

trova nelle implementazioni DFT4 e DFT8, che utilizzano rispettivamente 8 e 4

blocchi di calcolo.

77

Bibliografia

[1] Leonardo Mino, Fabio Rizzato, Massimo Ratti e Vincenzo Rana.Realiz-

zazione di una periferica per il calcolo della trasformata discreta di Fourier.

Politecnico di Milano - Laboratorio di Micro Architetture, 2004.

[2] Marco Domenico Santambrogio.A methodology for dynamic reconfigurabil-

ity in embedded system design. Politecnico di Milano - Laboratorio di Micro

Architetture, 2004.

[3] Steve R. Jones and Scott BezanScalable implementation of an n-point dis-

crete Fourier Transform using a sequential design. McMaster University,

Hamilton, Ontario, Canada - 2003

[4] Diego Nichetti e Stefano OrlandiRealizzazione di un componente per un

sistema dedicato: sviluppo dell’algoritmo di crittografia RC6 a 128 bit.

Politecnico di Milano - Laboratorio di Micro Architetture, 2004.

79

SVILUPPO DI COMPONENTI PER SISTEMI DEDICATI...

Documents

Transcript of SVILUPPO DI COMPONENTI PER SISTEMI DEDICATI...