L'efficienza e le prestazioni degli FPGA a virgola mobile sono state limitate da latenze elevate e congestione del routing. Inoltre, il flusso di progettazione tradizionale degli FPGA, basato sulla scrittura di descrizioni hardware a livello di registro in Verilog o VHDL, non è adatto all'implementazione di algoritmi complessi a virgola mobile.
Altera ha sviluppato un nuovo flusso di progettazione in virgola mobile che mira a semplificare l'implementazione di algoritmi di elaborazione del segnale digitale in virgola mobile su FPGA Altera, consentendo a questi progetti di raggiungere i massimi livelli di prestazioni ed efficienza finora ottenuti. Invece di costruire un percorso dati costituito da operatori elementari in virgola mobile (ad esempio, moltiplicazione seguita da addizione seguita da elevamento al quadrato), il compilatore in virgola mobile genera un percorso dati che combina gli operatori elementari in un'unica funzione o percorso dati. Ciò elimina le ridondanze presenti nei tradizionali progetti FPGA in virgola mobile. Inoltre, il flusso di progettazione di Altera è un flusso di progettazione di alto livello, basato su modelli, che utilizza Altera DSP Builder Advanced Blockset con MATLAB e MathWorks Simulink. Altera prevede che questo approccio di alto livello consentirà ai progettisti di FPGA di implementare e verificare algoritmi complessi in virgola mobile più rapidamente rispetto alla progettazione tradizionale basata su HDL.
BDTI ha condotto un'analisi indipendente del flusso di progettazione DSP a virgola mobile di Altera. L'obiettivo di BDTI era comprendere le prestazioni ottenibili con le FPGA di Altera per applicazioni DSP a virgola mobile di alto livello e valutare l'usabilità del flusso di progettazione DSP a virgola mobile di Altera. Questo articolo presenta i risultati di BDTI, insieme a informazioni di base e dettagli sulla metodologia utilizzata.
1. Introduzione
Due esempi di progettazione in virgola mobile
I progressi nei chip digitali consentono l'utilizzo di algoritmi complessi, precedentemente limitati alla ricerca, in applicazioni di elaborazione embedded comuni. Ad esempio, l'algebra lineare (e in particolare la soluzione di sistemi che coinvolgono simultaneamente grandi insiemi di equazioni lineari) è stata utilizzata per molti anni principalmente nella ricerca, dove sono disponibili risorse di calcolo su larga scala e generalmente non sono richiesti calcoli in tempo reale. La risoluzione di sistemi di grandi dimensioni richiede l'inversione di matrici o qualche tipo di decomposizione di matrici. Oltre ai requisiti di capacità computazionale, queste tecniche possono soffrire di instabilità numerica se non viene utilizzato un intervallo dinamico sufficiente. Pertanto, l'implementazione efficiente e accurata di questi algoritmi è praticabile solo su dispositivi in virgola mobile.
Altera ha recentemente introdotto funzionalità di calcolo in virgola mobile nel suo toolkit DSP Builder Advanced Blockset per semplificare l'implementazione di algoritmi DSP in virgola mobile su FPGA Altera e migliorare le prestazioni e l'efficienza dei progetti in virgola mobile rispetto alle tecniche di progettazione FPGA tradizionali. In un precedente articolo [1], BDTI ha analizzato e valutato le prestazioni e l'efficienza del toolkit software Quartus II v11.0 di Altera su un'implementazione di esempio del risolutore Cholesky a virgola mobile a canale singolo, sintetizzato per le FPGA Stratix IV e Arria IV a 40 nm.
In questo articolo valutiamo l'efficacia della soluzione proposta da Altera utilizzando la nuova versione 12.0 del software Quartus II ed esploriamo le capacità delle FPGA Stratix V e Arria V a 28 nm di Altera. Per eseguire questa valutazione, BDTI si è concentrata sulla risoluzione di un elevato numero di equazioni lineari simultanee utilizzando due tipi di decomposizione: una decomposizione di matrice di Cholesky multicanale e una decomposizione QR con il processo di Gram-Schmidt. Queste decomposizioni, insieme alle sostituzioni in avanti e all'indietro, forniscono una soluzione per il vettore x in un sistema di equazioni lineari della forma Ax = B.
La decomposizione di matrici è utilizzata in numerose applicazioni radar militari, come l'elaborazione adattiva spazio-temporale (STAP), e in vari problemi di stima nelle comunicazioni digitali. La decomposizione QR è comunemente utilizzata su qualsiasi matrice A di dimensioni m x n, mentre la decomposizione di Cholesky è l'algoritmo più diffuso per matrici quadrate, simmetriche e definite positive, grazie alla sua elevata efficienza computazionale. Entrambe le decomposizioni impiegano algoritmi computazionalmente intensivi che richiedono un'elevata precisione dei dati, rendendo necessarie operazioni in virgola mobile. Inoltre, i due esempi discussi in questo articolo utilizzano prodotti scalari e cicli annidati all'interno dell'algoritmo, operazioni prevalenti in un'ampia gamma di applicazioni di elaborazione del segnale digitale relative all'algebra lineare e ai filtri a risposta impulsiva finita (FIR).
Gli esempi descritti in questo articolo risolvono sistemi simultanei di equazioni lineari di dati complessi utilizzando entrambi i metodi e presentano i risultati. Utilizzando il risolutore QR, come spiegato nella Sezione 4, un FPGA Altera Stratix V è in grado di eseguire 315 decomposizioni di matrici al secondo di dimensioni 400x400, a una velocità di 203 MHz, raggiungendo 162x10⁹ operazioni in virgola mobile al secondo (GFLOPS).
I due esempi di progettazione valutati in questo articolo fanno parte del software DSP Builder v12.0 o possono essere ordinati da [
Flusso di progettazione in virgola mobile:
le FPGA non sono state generalmente la piattaforma di scelta per le applicazioni in virgola mobile di alto livello. Sebbene i fornitori di FPGA offrano librerie di primitive in virgola mobile, le prestazioni delle FPGA in tali applicazioni sono state fortemente limitate. L'inefficienza dei tradizionali progetti FPFA in virgola mobile è in parte dovuta alla natura altamente segmentata e alle strutture aritmetiche degli operatori in virgola mobile, che creano un'elevata latenza del percorso dati e congestione del routing. A loro volta, queste latenze creano problemi difficili da gestire nei progetti dipendenti dai dati. Il risultato finale è spesso un progetto con una bassa frequenza operativa.
Il flusso di lavoro dello strumento DSP Builder Advanced Blockset di Altera affronta questi ostacoli sia a livello di architettura che di progettazione di sistema. Il compilatore in virgola mobile di Altera combina ampie sezioni del percorso dati in un'unica funzione in virgola mobile, anziché generarle componendo operatori in virgola mobile elementari. Questo risultato si ottiene analizzando la crescita dei bit nel percorso dati e scegliendo la normalizzazione di input ottimale per allocare una precisione sufficiente lungo il percorso dati, in modo da eliminare il maggior numero possibile di passaggi di normalizzazione e denormalizzazione, come mostrato in Figura 1. Il formato IEEE 754 viene utilizzato solo ai confini del percorso dati; larghezze della mantissa maggiori vengono utilizzate nel percorso dati stesso per aumentare la gamma dinamica e ridurre la necessità di passaggi di normalizzazione e denormalizzazione tra operatori successivi. Le funzioni di normalizzazione e denormalizzazione utilizzano shifter a barile veloci con una larghezza fino a 48 bit per un numero in virgola mobile a singola precisione. Ciò consuma una quantità significativa di risorse logiche e di routing ed è il motivo principale per cui le implementazioni in virgola mobile basate su FPGA non sono state efficienti. La metodologia del percorso dati combinato elimina un numero significativo di shifter a barile veloci. Le moltiplicazioni della mantissa a precisione più elevata utilizzano la modalità moltiplicatore a 27 bit x 27 bit di Altera sui dispositivi Stratix V e Arria V. La Figura 1(b) confronta la metodologia del percorso dati combinato per il caso semplice di una stringa con due sommatori e l'implementazione tradizionale mostrata nella Figura 1(a). Il percorso dati combinato nella Figura 1(b) elimina la ridondanza tra operatori sopprimendo la denormalizzazione dell'output del primo sommatore e la normalizzazione dell'input del secondo sommatore. L'eliminazione della logica e del routing aggiunti, insieme all'uso di moltiplicatori hardware, rende prevedibili i tempi e la latenza per percorsi dati complessi. Gli algoritmi in virgola mobile IEEE 754 a singola e doppia precisione sono implementati con meno risorse logiche e prestazioni superiori. Altera afferma che un percorso dati combinato riduce le risorse logiche e la latenza del 50% rispetto al percorso dati equivalente implementato utilizzando operatori elementari [2]. Inoltre, come risultato di una rappresentazione più ampia dei dati interni, la precisione dei dati è generalmente superiore a quella ottenuta da una libreria che utilizza operatori in virgola mobile IEEE 754 elementari.
Il flusso di lavoro di progettazione DSP a virgola mobile di Altera integra il software Altera DSP Builder Advanced Blockset e Quartus II, oltre a MATLAB e MathWorks Simulink. L'ambiente Simulink consente al progettista di lavorare a livello di comportamento algoritmico per descrivere, eseguire il debug e verificare sistemi complessi. Funzionalità di Simulink come la propagazione dei tipi di dati e l'elaborazione di dati vettoriali sono integrate in DSP Builder Advanced Blockset, consentendo al progettista di esplorare rapidamente lo spazio di progettazione algoritmica.
Per valutare l'efficienza e le prestazioni del flusso di progettazione in virgola mobile di Altera, BDTI ha utilizzato lo strumento DSP Builder Advanced Blockset per validare due esempi, entrambi relativi alla risoluzione di un sistema di equazioni lineari simultanee utilizzando tipi di dati complessi in una rappresentazione in virgola mobile a singola precisione. Una soluzione è stata ottenuta utilizzando la decomposizione di Cholesky, mentre l'altra ha impiegato la decomposizione QR tramite il processo di Gram-Schmidt. La Sezione 2 di questo articolo descrive l'implementazione dei due esempi in virgola mobile. La Sezione 3 illustra l'esperienza di BDTI con il flusso di progettazione e il toolkit. La Sezione 4 presenta le prestazioni dell'implementazione utilizzando due FPGA Altera: lo Stratix V 5SGSMD5K2F40C2n di fascia alta e di medie dimensioni e l'Arria V 5AGTFD7K3F40I3N di fascia media. Infine, la Sezione 5 presenta le conclusioni di BDTI.
2. Informazioni di base
sull'implementazione
Numerose applicazioni coinvolgono sistemi di equazioni lineari della forma Ax = b. Che si tratti di un problema di ottimizzazione che coinvolge i minimi quadrati lineari, un filtro di Kalman per la previsione di un problema o la stima in un canale di comunicazione MIMO, il problema consiste comunque nel trovare una soluzione numerica per un sistema di equazioni lineari della forma Ax = b. Per una matrice generica di dimensioni m x n, dove m è l'altezza della matrice e n la sua larghezza, la decomposizione QR può essere utilizzata per risolvere il vettore x. L'algoritmo decompone A in una matrice ortonormale Q di dimensioni m x n e una matrice triangolare superiore R di dimensioni n x n. Poiché Q è ortonormale, QTQ = I e Rx = QTb. Poiché R è una matrice triangolare superiore, x può essere facilmente risolto tramite sostituzione all'indietro senza nemmeno la necessità di invertire la matrice A originale. Nell'esempio QR di questo articolo, lavoriamo con matrici sovradeterminate dove m ≠ n.
Quando la matrice A è simmetrica e definita positiva, come nel caso delle matrici di covarianza che si presentano in molti problemi, si utilizzano comunemente la decomposizione di Cholesky e il relativo algoritmo. L'algoritmo trova l'inversa della matrice A, risolvendo così il vettore x come x = A⁻¹b. La decomposizione di Cholesky è almeno due volte più efficiente della decomposizione QR, a seconda degli algoritmi di decomposizione utilizzati. Poiché questi algoritmi di decomposizione sono di natura ricorsiva e includono la divisione, è necessario un ampio intervallo dinamico numerico all'aumentare delle dimensioni della matrice. Nella maggior parte dei casi, anche per matrici di dimensioni ridotte come 4x4, ad esempio nella stima del canale MIMO, vengono eseguite operazioni in virgola mobile. Per sistemi più grandi che richiedono prestazioni superiori, come nelle applicazioni militari, la velocità in virgola mobile è spesso proibitiva per i sistemi embedded. I progettisti spesso abbandonano completamente l'algoritmo alla ricerca di una soluzione meno ottimale o ricorrono a processori in virgola mobile ad alte prestazioni, con il conseguente aumento dei costi e dello sforzo di progettazione.
Autore:
A cura del team di Berkeley Design Technology, Inc. Ottobre 2012
(Continua a febbraio)
