Sommatori veloci - carry-bypass, carry-select e square-root

Il ripple-carry (Sommatori - full adder e ripple-carryLa somma di due bit con riporto in ingresso è realizzata dal full adder: S = A ⊕ B ⊕ C_in, C_out = AB + BC_in + AC_in. Con generate G = AB, propagate P = A ⊕ B (e delete D = Ā B̄) si scrive C_out = G + P·C_in e S = P ⊕ C_in: G e P non dipendono dal riporto in ingresso (fase di set-up), solo C_out ed S ne dipendono. Il sommatore ripple-carry collega N full adder in cascata: il riporto attraversa gli stadi uno dopo l'altro, nel caso peggiore t_add = (N−1) t_carry + t_sum (lineare in N). Il ritardo effettivo dipende dagli operandi: un generate o un delete azzera la catena, un propagate la prolunga; per operandi uguali bit a bit vale t_carry + t_sum.Sommatori - full adder e ripple-carry →) ha $t_{add}=(N-1)t_c+t_s$, lineare in $N$: a $64$ bit il riporto deve attraversare $63$ stadi. Le architetture veloci mantengono lo stesso full adder ma accorciano il cammino critico del riporto con logica aggiuntiva. Notazione: $t_{setup}$ (calcolo di $G$, $P$), $t_{carry}$ (propagazione in uno stadio), $t_{mux}$ (ritardo di un multiplexer), $t_{sum}$.

Carry-bypass (carry-skip)

I $N$ bit si dividono in blocchi di $M$ bit. In ciascun blocco si calcola $BP=P_0P_1\cdots P_{M-1}$. Idea: se tutti i propagate del blocco valgono $1$, il riporto in uscita è uguale al riporto in ingresso ($C_{o,M-1}=C_{i,0}$): un multiplexer comandato da $BP$ lo fa saltare direttamente, senza aspettare che attraversi i $M$ stadi.

Formula (ritardo del carry-bypass e dimensione ottima dei blocchi). Ritardo nel caso peggiore ($N$ bit, blocchi da $M$): il riporto deve (1) essere generato nel primo stadio del primo blocco e attraversare lo stesso blocco ($M\,t_{carry}$), (2) saltare i blocchi successivi attraverso i loro multiplexer ($N/M-1$ multiplexer in totale, uno per ogni blocco dopo il primo), (3) attraversare i $M-1$ stadi dell'ultimo blocco e produrre la somma: $$t_{add}=t_{setup}+M\,t_{carry}+\Big(\frac NM-1\Big)t_{mux}+(M-1)\,t_{carry}+t_{sum}.$$ Il termine in $M$ è $(2M-1)\,t_{carry}$: aumentando $M$ cresce la parte di ripple dentro i blocchi estremi, diminuendo $M$ crescono i multiplexer. Derivando rispetto a $M$: $$M_{opt}=\sqrt{\frac{N\,t_{mux}}{2\,t_{carry}}}.$$

Esempio. Con $N = 32$ e tutti i ritardi uguali a $T$: $M_{opt} = \sqrt{32/2} = 4$ e $t_{add} = T + 4T + 7T + 3T + T = 16\,T$.

Con $M=M_{opt}$ il ritardo cresce come $\sqrt N$ (con $M$ fisso resta lineare ma con un coefficiente molto minore del ripple). In questa architettura il tempo di ritardo per il calcolo della somma finale è determinato principalmente dal tempo di riporto ($t_{carry}$), non da $t_{sum}$ o dal set-up, che compaiono una sola volta.

Carry-select

Per eliminare l'attesa del riporto in ingresso, in ciascun blocco (tranne il primo) si calcolano due volte le somme e i riporti: una assumendo riporto in ingresso $0$ (0-carry) e una assumendo $1$ (1-carry). Quando il riporto vero del blocco precedente arriva, un multiplexer sceglie il risultato corretto (di riporto e di somma). I due calcoli avvengono in parallelo al calcolo del riporto del blocco precedente: la selezione è l'unico lavoro che resta.

Formula (ritardo del linear carry-select e dimensione ottima dei blocchi). Linear carry-select (blocchi tutti da $M$ bit, $N/M$ blocchi): $$t_{add}=t_{setup}+M\,t_{carry}+\frac NM\,t_{mux}+t_{sum},\qquad M_{opt}=\sqrt{\frac{N\,t_{mux}}{t_{carry}}}.$$

Esempio. Con $N = 32$, $M = 8$ e tutti i ritardi uguali a $T$: $t_{add} = T + 8T + 4T + T = 14\,T$.

($M\,t_{carry}$: ogni blocco calcola i suoi riporti in parallelo; poi i multiplexer si propagano in cascata, uno per blocco.) Costo: circa il doppio dei full adder, più i multiplexer.

Caso a dati specifici (tema d'esame): $N=20$ bit, $4$ blocchi da $5$, con $t_{mux}<t_{carry}$, $A=11111\;11111\;11111\;11111$ e $B=10010\;00000\;00000\;00001$ (LSB a sinistra). Il primo blocco è un ripple-carry normale: (1,1) G, (1,0) P, (1,0) P, (1,1) G, (1,0) P: il riporto in uscita è pronto dopo $2\,t_c$ (generate nel quarto bit e un propagate). Nei blocchi $2,3,4$ i riporti per entrambe le ipotesi si calcolano comunque in $5\,t_c$ (i bit sono tutti propagate, con $B=00000$, e la catena di $5$ stadi è completa), cioè più tardi del riporto del primo blocco: il tempo è dominato da $5t_c$. Poi il riporto attraversa i multiplexer dei blocchi $2$ e $3$ e il mux finale che sceglie le somme del blocco $4$: tre multiplexer in cascata (il primo blocco non ne ha), quindi $t_{add}=t_{su}+5t_c+3t_{mux}+t_s$. La formula generale con $N/M=4$ ne conta quattro ed è quindi un limite superiore. (Esercizio 17 · quesiti rapidi sui sommatori con dati numerici (temi d'esame 2025-2026).)

Square-root carry-select

Formula (ritardo del square-root carry-select). Nel linear carry-select il blocco $j$ aspetta il riporto del blocco $j-1$, che arriva un multiplexer dopo il precedente: nel frattempo ha già finito di calcolare le due alternative. Si può quindi dare ai blocchi successivi un bit in più del precedente: ciascuno impiega $t_{mux}$ in più per il riporto, e può quindi elaborare un bit in più in parallelo (con $t_{carry}$ per bit). Blocchi di $M,\,M+1,\,M+2,\dots,M+K-1$ bit: $$N=\sum_{j=0}^{K-1}(M+j)=MK+\frac{K(K-1)}2\ \approx\ \frac{K^2}2\quad(M\text{ piccolo}),\qquad K\approx\sqrt{2N}.$$ $$t_{add}=t_{setup}+M\,t_{carry}+K\,t_{mux}+t_{sum}\ \approx\ t_{setup}+M\,t_{carry}+\sqrt{2N}\,t_{mux}+t_{sum}.$$

Esempio. Con $N = 32$ e $M = 3$: blocchi da $3, 4, 5, 6, 7, 8$ bit ($33$ bit), $K = 6$ e, con ritardi tutti uguali a $T$, $t_{add} = T + 3T + 6T + T = 11\,T$.

Il ritardo cresce come $\sqrt N$ invece che linearmente. Se $t_{carry}=t_{mux}$ i tempi si bilanciano: il riporto del blocco $j-1$ arriva a $M\,t_{carry}+(j-1)\,t_{mux}$ e il blocco $j$, con un bit in più, finisce di calcolare le sue due alternative esattamente allora. Nel caso generale $t_{mux}\ne t_{carry}$ i blocchi crescono di $t_{mux}/t_{carry}$ bit alla volta.

Confronto

Con $t_{setup}=t_{carry}=t_{mux}=t_{sum}=T$:

(Per il square-root select: $N=32$ con $M=3$: blocchi da $3,4,5,6,7,8$ ($=33$ bit), $K=6$ e $t=1+3+6+1=11T$.) Al crescere di $N$ il vantaggio delle strutture a blocchi variabili aumenta; il costo è l'area (le architetture select duplicano i full adder) e la complessità del routing.

Altre soluzioni

Esistono anche sommatori carry-lookahead e ad albero (prefix adders, per esempio Kogge-Stone), che calcolano i riporti in tempo $O(\log N)$ combinando i segnali di generate e propagate di gruppi di bit; nelle FPGA (FPGA - LUT, slice e risorse della famiglia 7Una FPGA è una matrice di blocchi logici configurabili (CLB) immersi in una griglia di interconnessioni programmabili, con risorse dedicate: block RAM, blocchi DSP, gestione del clock (MMCM, PLL), blocchi di I/O e transceiver. La memoria di configurazione è SRAM. L'elemento base è la LUT: una memoria SRAM con 2^k celle che realizza una qualsiasi funzione di k ingressi (i segnali di selezione del multiplexer sono gli ingressi della funzione). Nella famiglia 7 di Xilinx un CLB ha 2 slice; uno slice ha 4 LUT a 6 ingressi (ciascuna divisibile in due LUT a 5), multiplexer larghi F7/F8 (funzioni a 7-8 ingressi), una catena di riporto veloce, 4 flip-flop/latch più 4 flip-flop. Nei SLICEM la LUT può essere usata come RAM distribuita o registro a scorrimento (SRL32), nei SLICEL solo come logica.FPGA - LUT, slice e risorse della famiglia 7 →) la catena di riporto dedicata (carry chain) fa tutto questo con un cammino fisico veloce.

Errori comuni

• Dimenticare di contare i multiplexer come $N/M-1$ (bypass) o $N/M$ (select): sono tanti quanti i blocchi attraversati.
• Applicare $M_{opt}=\sqrt{N\,t_{mux}/(2t_{carry})}$ al carry-select (che ha il fattore $2$ in meno: $M_{opt}=\sqrt{N\,t_{mux}/t_{carry}}$).
• Dimenticare che nel carry-bypass il caso peggiore è determinato dal riporto (non dalla somma).
• Credere che i blocchi del square-root select siano uguali: crescono di un bit per blocco.