Implementazione dell'algoritmo di compressione vocale G.723.1 su un microprocessore ricon gurabile

2 Introduzione
Nel corso degli ultimi anni si e` registrato uno sviluppo sempre crescen-
te di architetture per l’elaborazione digitale dei segnali che hanno con-
sentito la realizzazione di dispositivi in grado di coniugare i vari aspetti
dell’elaborazione quali prestazioni elevate, in termini di velocita`diese-
cuzione, ed contenimento dei consumi energetici. Inoltre, il tempo di
sviluppo necessario alla progettazione di un nuovo dispositivo (o servi-
zio offerto) puo` decretarne o meno il successo data l’importanza odierna
del time-to-market, evitando quindi una obsolescenza dei prodotti troppo
rapida.
Le principali architetture sviluppate per avere a disposizione una ele-
vata complessita` computazionale si sono orientate verso lo sfruttamento
del parallelismo a livello di istruzione e quindi su architetture di calco-
lo internamente parallele quali i processori superscalari e i VLIW (Very
Long Instruction Word) che posso eseguire piu` istruzioni contemporanea-
mente. Questi dispositivi sono di frequente integrate in complessi System-
on-Chip (o SoC) che possono integrare in un unico chip un maggior nu-
mero di dispositivi quali, ad esempio, processori, memorie, o dispositi-
vi di calcolo dedicato a specifiche funzioni, riducendo l’overhead della
comunicazione fra i componenti del sistema.
Allo scopo di ridurre i tempi di progettazione, e quindi i costi che vi
sono associati, sono stati realizzati sistemi flessibili, cioe` in grado di essere
riprogrammabili, consentendo di ammortizzare gli elevati costi inziali in
virtu` di un maggiore tempo di vita del prodotto. In questo senso i micro-
processori sono i dispositivi ideali in quanto presentano grande flessibilita`,
ma, per contro, risultano spesso meno efficienti in quanto sviluppano nel
tempo operazioni complesse (ad esempio una radice quadrata) non pre-
senti tra le istruzioni supportate, tanto da essere considerati inadeguati per
applicazioni ad elevata complessita`. I DSP (Digital Signal Processing) so-
no processori ottimizzati per l’elaborazione dei segnali e sono in grado di
colmare, anche se solo parzialmente, questo divario in quanto dispongono
di unita` di calcolo specifiche per l’applicazione di riferimento.
L’esigenza di introdurre un elevato grado di flessibilita` associato a pre-
stazioni paragonabili a quelle dei circuiti dedicati, ha portato all’utilizzo
Introduzione 3
in questo ambito di FPGA (Field Programmable Gate Array), dispositivi
che sono in grado di fornire prestazioni vicine a quelle degli ASIC e, allo
tempo stesso, con la capacit di essere riprogrammati (o riconfigurati) co-
me i processori per svolgere diverse attivita`. Come naturale evoluzione,
si e` assistito alla nascita di un modello architteturale che si pone in una
posizione intermedia fra quello deiprocessoriequellodeiFPGA:ipro-
cessori riconfigurabili. Essi fanno interagire un processore, tipicamente
general purpose, con uno o pi FPGA (o dispositivi simili), con l’obbiettivo
di ottimizzare l’escuzione di algoritmi critici sfruttando la riconfigurabi-
lita` e l’efficienza di calcolo degli FPGA e, mantenendo, allo stesso tempo,
la struttura tradizionale di un microprocessore al quale si continuano a
fare eseguire la operazioni di controllo del flusso di esecuzione.
La complessita` di un algoritmo e` spesso associata ad una piccola por-
zione di codice eseguita un numero elevate di volte e questa considerazio-
ne trova applicazione pratica in un modello architteturale in cui si possa
realizzare un dispositivo hardware che implementi in modo efficiente la
porzione di codice critica e la restante porzione di codice venga realizzata
utilizzando un supporto di tipo generale. Un modello di questo tipo trova
corrispondenza nelle richieste di contrazione dei tempi di sviluppo e quin-
di concentrazione degli sforzi, e quindi dei costi, sulle porzioni critiche
dell’applicazione stessa. La necessita` di dover utilizzare un supporto fles-
sibile rende quindi il processore riconfigurabile un modello architteturale
molto interessante e promettente. Per contro, i processori riconfigurabili
richiedono competenze sia di programmazione software che di descrizio-
ne hardware, rendendosi poco accessibili per utenti abituati allo sviluppo
su processori o DSP. L’ambiente di sviluppo di algoritmi su processori ri-
configurabili riveste dunque un ruolo molto importante ed, in particolare,
un alto livello di integrazione fra il flusso di programmazione software e
il flusso di configurazione hardware rappresenta un obiettivo auspicabile,
se non necessario, al fine di consentire un facile utilizzo per un suppor-
to dalle potenzialita` elevate, ma di impatto non immediato sul generico
utilizzatore.
Questa tesi si inserisce nell’ambito dello sviluppo, presso il centro di
4 Introduzione
ricerca ARCES dell’Universita` di Bologna, del processore riconfigurabile
XiRisc che associa un processore RISC di tipo VLIW ad una unita` ricon-
figurabile chiamata PiCoGA che si occupa di rendere piu` efficienti i nu-
clei di calcolo piu` critici. Questi ultimi vengono descritti attraverso DFG
(data-flow graph) utilizzando un linguaggio C semplificato e costituisco-
no una estensione al set di istruzioni standard del processore, che cosı`si
adatta alle esigenze computazionali dell’algoritmo oggetto di implemen-
tazione. In particolare, nel corso di questa tesi, ci si e` posti l’obiettivo di
realizzare sul processore riconfigurabile XiRisc l’algoritmo di compressio-
ne vocale G.723.1, utilizzato nelle moderne comunicazioni audio di ter-
za generazione come standard per il servizio di VoIP (Voice over IP) ov-
vero trasmissione vocale su canale dati (Internet) e nelle applicazioni di
videoconferenza.
Dopo una analisi, nel primo capitolo, delle architetture di calcolo ed
una descrizione del processore XiRisc, verra` analizzato, nel corso del se-
condo capitolo, l’algoritmo di compressione vocale utilizzato nello stan-
dard G.723.1 che fa utilizzo di tecniche di analysis by synthesis, ovvero
tecniche in cui la compressione viene ottenuta analizzando il meccanismo
di produzione del segnale vocale e sintetizzando lo stesso segnale in fase
di decodifica. Nel terzo capitolo verra` affrontato il tema dell’implementa-
zione di nuclei di calcolo critici sull’architettura riconfigurabile e verranno
inoltre esposte le tecniche di ottimizzazione utilizzate nel corso di questa
tesi, quale ad esempio il software pipelining. Infine, nel quarte ed ultimo
capitolo, verranno esposti i risultati ottenuti simulando il vocoder G.723.1
su XiRisc.
Capitolo 1
Architetture riconfigurabili
La richiesta pressante nel mercato dell‘elettronica di consumo, di prdotti
portabili e ad alta fedelta` per quanto riguarda il trattamento del signale
audio e dell‘immagine, implica il trattamento di un volume importante di
dati ed operazioni aritmetiche da effettuare in tempo reale.
Per rispondere a questi vincoli, e` nata una nuova classe di architettura,
i processori riconfigurabili, che risultano piu` promettenti per affrontar le
esigenze di tale settore mercato dei semicondutori. In questa ottica verra`
fatta una una presentazione di alcuni modelli architetturali e delle loro
caratteristiche. In particolare verra` descritto il processore XiRisc, la sua
struttura ed il contesto nel quale si inserisce.
1.1 Modelli computazionali
Una generica computazione puo`, in generale essere rappresentata simboli-
camente come una combinazione di un grafo di flusso di dati o DFG (Data
Flow Graph) e di un grafo di flusso di controllo o CFG (Control Flow Gra-
ph), i cui nodi e archi rappresentano rispettivamente operazioni primitive
e collegamenti fra i vari nodi.
Il nodo identifica una funzione tra gli ingressi, rappresentati dagli archi
entranti, e le uscite rappresentate dagli archi uscenti, che puo` essere com-
putata solo quando tutti i dati di ingresso sono disponibili. Ad ogni nodo
e` inoltre associato uno specifico tempo di esecuzione in termini di unita`di
5
6 Architetture riconfigurabili
++
*
 
+
Figura 1.1: Esempio di Data Flow Graph
tempo normalizzato. I rami del grafo rappresentano il percorso dei dati
(datapath) fra i vari nodi e a ciascun ramo e` associato un ritardo non nega-
tivo.
Nei sistemi digitali sincroni l‘unita` di tempo normalizzata e`ilperiodo
di clock e per ogni nodo e` specificato a priori il numero di dati campionati
e prodotti per ogni unita` di tempo. Questi casi rappresentano una sotto-
classe dei DFG nota in letteratura come SDFG (Synchronous Data Flow
Graph).
Per un DFG le operazioni piu` comuni sono quelle di tipo aritmetico e i dati
sono generalmente parole (word) costituite da un numero consistente di
bit (da un minimo di un byte fino a 64 bit e oltre). Per i CFG, invece, sono
prevalenti operazioni logiche generiche che interessano un limitato nume-
ro di bit, tipicamente 1 o 2, in quanto un CFG ha il compito di produrre i
segnali che regolano la computazione del DFG.
`
E quindi evidente che la granularita` offerta della logica riprogramma-
bile sara` un importante parametro per valutare l’efficienza dell’implemen-
tazione.
Ogni grafo si caratterizza essenzialmente in base alle seguente caratte-
ristiche:
1.1 Modelli computazionali 7

il numero totale di nodi

la profondita`, cioe` numero di nodi attraversati dal percorso piu`lun-
go

il livello di parallelismo, cioe` il numero di operazioni indipendenti
che possono essere svolte in contemporanee

la presenza o l’ assenza di cicli
Il primo punto interessa principalmente la quantita`dirisorsedicalcolo
richieste, mentre il secondo e il terzo le prestazioni. La presenza di cicli e`
una caratteristica importante in molte classi di algoritmi, perche´proprio
nei cicli viene impiegata la maggior parte del tempo di esecuzione. Dato
che la rappresentazione di una computazione tramite grafi non e` unica,
per mezzo di tecniche di rielaborazione, come il retiming, e` possibile otte-
nere, in una certa misura, grafi con le caratteristiche desiderate.
Ai fini della realizzazione di un dispositivo hardware in grado di va-
lutare un DFG, si puo` fare riferimento a DFG strutturati in modo da mo-
dellare il funzionamento di una logica digitale sincrona : quindi si assume
che che ogni ramo del DFG non introduca ritardi e che ogni nodo completi
la propria esecuzione in una unita` di tempo. Per rappresentare nodi o ra-
mi con ritardi superiori ad uno puo` essere esplicitamente inseriti dei nodi
di ritardo fittizi che rappresenteranno in hardware altrettanti registri.
Un fattore molto importante nella valutazione di un DFG, e` il grado di pa-
rallelismo insito nella computazione. Esistono sostanzialmente tre gradi
di parallelismo esprimibile in un algoritmo:

parallelismo fra thread indipendenti di elaborazione, ognuno dei
quali realizza distinti flussi di dati;

parallelismo fra iterazioni successive di uno stesso ciclo di calco-
lo, quando non vi e` dipendenza fra i dati di iterazioni di calcolo
successive;
8 Architetture riconfigurabili

parallelismo a livello di istruzioni (ILP): coinvolge operazioni conte-
nute all‘interno di un singolo thread, come ad esempio in un singolo
ciclo.
1.1 Modelli computazionali 9
L’analisi del parallelismo che si puo` presentare nell’ambito di un DFG
e` utile per comprendere la distinzione fondamentale fra i due modelli
computazionali che si orientano verso direzioni distinte:
Modello a computazione nello spazio : esprime l‘intenzione di sfruttare
il massimo parallelismo contenuto in un grafo utilizzando nello spa-
zio un numero di risorse di calcolo tali da raggiungere la massima
efficienza computazionale.
Modello a computazione nel tempo : tende alla massima riusabilita`de-
gli elementi necessari per il calcolo, distribuendo nel tempo l‘elaborazione
al fine di realizzare un‘architettura il piu` generale possibile, avente
un numero di risorse limitato.
Le pecularita` nei due approcci sono schematizzabili per il modo in cui si
manifestano sui vari blocchi funzionali necessari per eseguire una compu-
tazione :

Unita`dicalcolo
- Nel modello a computazione nello spazio, come caso limite, ad
ogni nodo del grafo puo` corrispondere una specifica unita`di
calcolo, che puo` quindi essere dimensionata esattamente in base
al numero ed alle dimensioni degli operandi.
- Nel modello a computazione nel tempo si utilizzano un nume-
ro ristretto di unita` di calcolo che di volta in volta vengono ri-
programmate, per realizzare l‘operatore corrispondente ad un
nodo del DFG, itroduisando cosı` una piu` ampia riusabilita`nel
tempo delle unita` funzionali. Per la massima generalita`, le unita`
di calcolo presenti realizzano direttamente solo un numero limi-
tato di funzionalita`, mentre le operazioni piu` complesse sono
implementate attraverso un‘opportuna sequenza di operazioni
elementari.

Comunicazione dati
10 Architetture riconfigurabili
- Nel modello a computazione nello spazio i valori intermedi del-
l’elaborazione, che corrispondono agli archi interni del DFG,
sono direttamente passati dall’unita` funzionale che li genera
all‘unita` che li consuma. In questo modello deve quindi esse-
re presente un numero adeguato di bus di comunicazione di
dimensioni opportune.
- Nel modello a computazione nel tempo, la comunicazione fra
le unita` funzionali avviene nel tempo, nel senso che ad ogni ci-
clo devono essere resi disponibili tutti gli ingressi necessari per
un singolo passo dell‘elaborazione; quindi e` necessario dotare
il modello di una memoria centralizzata in grado di contenere i
risultati parziali di cui si avra` bisogno nei prossimi cicli.

Controllo
- Con la computazione nello spazio la logica di controllo e` ridotta
al minimo necessario per realizzare il CFG. Poiche´ ogni unita`di
calcolo svolge direttamente la particolare computazione richie-
sta dal DFG, non sono richiesti segnali di controllo che varino
durante la computazione dell‘algoritmo. Nel caso si utilizzi-
no risorse non completamente specializzate, puo`alpi`urendersi
necessaria una configurazione locale della risorsa computazio-
nale che ne specifichi il comportamento (es. sommatore che puo`
fungere anche da sottrattore).
- Con la computazione nel tempo il controllo risulta molto piu`
complesso perche´ di volta in volta si deve specificare sia la fun-
zionalita` sia il percorso dei dati coinvolti. Nella memoria cen-
tralizzata dovranno quindi risiedere istruzioni che descrivono
univocamente il comportamento della macchina.
Le logiche programmabili possono essere classificate sulla base del mo-
dello di computazione a cui fanno riferimento, ma anche in base ad altre
caratteristiche piu` proprie del dispositivo: ad esempio la granularita`con
cui e` possibile riprogrammare l’hardware e` uno dei parametri fondamen-
1.2 Logiche Programmabili 11
tali nella scelta del dispositivo, oltre ovviamente alla capacita` del sistema
in termini di gate equivalenti disponibili.
1.2 Logiche Programmabili
1.2.1 Processori
I processori sono architetture di calcolo che adottano il modello basato
sulla computazione nel tempo e che si pongono come obiettivo l’eleva-
ta riusabilita` delle unita` funzionali nonche´ un ambito applicativo di tipo
general-purpose. Lo sviluppo nel tempo del calcolo si manifesta serializ-
zando la computazione dell’algoritmo di partenza ed emulando le unita`
funzionali non previste attraverso l’iterazione di altre istruzioni elemen-
tari. Ad esempio, una moltiplicazione puo` essere effettuata sia attraver-
so una risorsa specifica, quale un moltiplicatore hardware, sia attraverso
una serie di operazioni di somma eseguite utilizzando una ALU. Un al-
tro aspetto del processore e` la rigidita` che mostra rispetto alle dimensioni
dei dati, che tipicamente e` fissata dalla dimensione dei registri. Questa
rigidita` si mostra come un limite forte in tutti quegli algoritmi basati sulla
manipolazione di entita` di piccole dimensioni in cui si ha una bassa den-
sita` di sfruttamento effettivo della logica di cui e` composto il processore.
Ne segue che il consumo di energia, comunque richiesto, non e` propor-
zionato al numero di bit significativi elaborati. La riconfigurabilita`av-
viene a tempo di esecuzione a livello di task eseguito e con un overhead
trascurabile nello switching fra applicazioni.
La computazione nel tempo basata su microprocessore risulta, inoltre,
particolarmente inefficiente per DFG che richiedono frequentemente ope-
razioni complesse non implementate direttamente in hardware da unita`
funzionali specifiche. Un moltiplicatore occupa molta area, ma e`pi`uve-
loce e dissipa meno della sua versione iterativa basata su addizioni. Per
questo motivo, e` nata in passato una nuova classe di processori, i DSP
(Digital Signal Processors), che essendo rivolti ad applicazioni specifiche,
l’elaborazione dei segnali digitali, hanno incluso unita` funzionali di uso
12 Architetture riconfigurabili
frequente come i moltiplicatori, MAC (Multiply and ACcumulate), shifter
e altro ancora.
I DSP introducono parzialmente nel modello a computazione nel tem-
po dei processori general purpose, principi del modello a computazio-
ne nello spazio, utilizzando lo spazio disponibile nei chip per migliorare
l‘efficienza.
Un altro limite, significativo nell’ambito delle applicazioni real-time,del
modello computazionale nel tempo e` rappresentato del mancato sfrutta-
mento dei livelli di parallelismo insiti nella computazione: questo limite si
fa via via piu` stringente a fronte dell’aumento di complessita` degli algorit-
mi in quanto obbliga, nella sostanza, a far fronte alle inefficienze compu-
tazionali aumentando la frequenza di funzionamento. Quest’ultimo fatto
porta con se` almeno due aspetti negativi: un aumento della potenza dissi-
pata e la necessita` di processi tecnologici sempre piu` evoluti e quindi costi
conseguentemente piu` elevati.
Un tentativo di fare fronte a queste inefficienze e` rappresentato dalle
architetture superscalari o VLIW (Very Long Instruction Word)incuisi
rende disponibile un modello architetturale in cui unita` funzionali di tipo
diverso sono rese disponibili per essere utilizzate in parallelo: e` possibi-
le quindi sfruttare il parallelismo a livello di istruzione presente nel DFG
ed eventualmente quello a livello di iterazioni successive (attraverso ope-
razioni di unrolling). L’unrolling e` una tecnica che consente di trasferire
parallelismo a livello di iterazione in parallelismo a livello di istruzione:
questo e` possibile grazie allo sviluppo di un loop di dimensione finita nel-
la sequenza delle computazioni richieste dall’esecuzione statica del ciclo.
In questo modo si trasferisce una computazione nel tempo in una nello
spazio in cui il parallelismo a livello di istruzione e` limitato dalle sole
dipendenze di dato e non dalla struttura di controllo. Questa tecnica e`
volta al raggiungimento dei limiti di parallelismo imposti dall’algoritmo
e dall’architettura del processore. Per un funzionamento soddisfacente di
queste architetture si rende necessario l‘utilizzo di un adeguato sistema