È possibile ridurre il fabbisogno di spazio di un albero di operazioni binarie su un FPGA a scapito della larghezza di banda di un fattore inferiore a 2?

Question

Ho un circuito in cui ad ogni ciclo di clock sono presenti N ingressi a 32 bit per il calcolo. Ho un'operazione binaria che prende due input a 32 bit e produce un output a 32 bit. Questa operazione è associativa e vorrei applicarla a tutti gli ingressi N a 32 bit per ottenere un output a 32 bit. Attualmente sto raggiungendo questo obiettivo implementando un albero binario pipeline di operazioni.

Per un esempio concreto, supponendo N = 4 e ho ingressi {a, b, c, d} allora farei il seguente:

a op b => reg1 
c op d => reg2 
reg1 op reg2 => result 

Quando una fase nella struttura non è divisibile per 2, inserisco un'operazione fittizia che richiede solo 1 input e restituisce 1 output con la stessa latenza.

Il problema che ho è che mi interessano alcune dimensioni di N ingressi {9, 25, 49, 81, 121}. La dimensione maggiore di N, 121, richiede il 110% di lute nel mio tessuto FPGA, mentre tutte le altre dimensioni si adattano facilmente. L'albero di queste operazioni binarie è di gran lunga il più grande consumatore di luts nel mio design.

Sono consapevole che potrei ridurre l'utilizzo di luts di quasi la metà dimezzando il numero di circuiti op presenti sulla mia scheda e multiplexando i loro ingressi. Sfortunatamente, ciò significherebbe solo ottenere un risultato ogni altro ciclo di clock e dimezzare la larghezza di banda.

Poiché un albero completo richiede solo il 10% di risorse in più rispetto a quanto offre la scheda, una riduzione del 50% della larghezza di banda sembra troppo significativa per un successo. Esiste un'architettura in cui posso fare il trade di una riduzione di dimensioni più fini per una riduzione della larghezza di banda a grana fine?

Answer 1

Ok, ho preso il tuo esempio con 9 ingressi e ho cercato di risolvere il problema del tuo albero binario con il 75% degli operatori binari.

Denominare gli ingressi a,b,c,d,e,f,g,h,i. Per distinguere i valori di input nel tempo, aggiungerò un segno di spunta dopo a.

a' = a at time 1 
a''' = a at time 3 
(ab)' = result of a' and b' 

9 ingressi richiedono 8 operazioni binarie. Limito il mio schema di elaborazione a 6 operatori, quindi utilizza il 75% degli operatori necessari. Ogni riga nel seguente schema rappresenta un operatore.

time 1  time 2   time 3   time 4    | time 1+4 
a'b'  (abcd)'(efgh)' (ab)''(cd)''  e'''f'''   | a'b' 
c'd'  (abcdefgh)'i' (ef)''(gh)''  g'''h'''   | c'd' 
e'f'  a''b''   (abcd)''(efgh)'' (ab)'''(cd)'''  | e'f' 
g'h'  c''d''   (abcdefgh)''i'' (ef)'''(gh)'''  | g'h' 
(ab)'(cd)' e''f''   a'''b'''   (abcd)'''(efgh)''' | (ab)'(cd)' 
(ef)'(gh)' g''h''   c'''d'''   (abcdefgh)'''i''' | (ef)'(gh)' 

Dopo 4 cicli, lo schema si ripete. Quindi l'elaborazione di 3 set di input richiede 4 cicli:
=> 33% di overhead.

Questo schema può essere ordinato, in modo che ogni riga elabori solo 2 input diversi:
=> l'input può essere sottoposto a controllo da un multiplexer 2: 1.

time 1  time 2   time 3   time 4    | time 1+4 
a'b'  a''b''   a'''b'''   (ab)'''(cd)'''  | a'b' 
c'd'  c''d''   c'''d'''   (ef)'''(gh)'''  | c'd' 
e'f'  e''f''   (ab)''(cd)''  e'''f'''   | e'f' 
g'h'  g''h''   (ef)''(gh)''  g'''h'''   | g'h' 
(ab)'(cd)' (abcd)'(efgh)' (abcd)''(efgh)'' (abcd)'''(efgh)''' | (ab)'(cd)' 
(ef)'(gh)' (abcdefgh)'i' (abcdefgh)''i'' (abcdefgh)'''i''' | (ef)'(gh)' 

Se ho commesso errori, questa dovrebbe essere la rete di operazione:

(cliccabile)

Answer 2

Hai pensato di usare 3, 4 operatori, 5, o 6 di ingresso? Le LUT negli attuali FPGA Altera e Xilinx sono 6 input. Se i tuoi operatori sono veramente semplici (cioè AND, OR, XOR) potresti sprecare un sacco di LUT nella tua attuale implementazione usando solo una funzione di input 2 invece di una funzione di input 6 (supponendo che tu registri ogni fase della pipeline). Questo trasformerebbe il tuo albero binario in un albero k-ario di operazioni. Con i numeri sarebbe sprecare molte LUT a seconda della scelta di N.

Qui ci sono le scelte di K che avrebbe senso:

N | K | LUTs/bit | LUTs | LUTs/bit @k=2 | LUTs @k=2 
-----|---|----------|------|---------------|----------- 
9 | 3 |  4 | 128 |  11  | 352 
25 | 5 |  6 | 192 |  25  | 800 
49 | 5 | 13 | 416 |  50  | 1600 
81 | 6 | 18 | 576 |  75  | 2400 
121 | 6 | 26 | 832 |  123  | 3936