ALU - sommatore, overflow, carry look-ahead e shift

** i riporti si calcolano da **generazione** $g_i=A_iB_i$ e **propagazione** $p_i=A_i+B_i$ in pochi livelli di logica. L'**overflow** è $V=C_{in,n-1}\oplus C_{out,n-1}$. Gli **shift** logici inseriscono 0, gli aritmetici estendono il segno; il **barrel shiftercircuito che sposta una parola di un numero qualsiasi di posizioni in un solo ciclo** sposta di $m$ posti in un ciclo. -->

In ogni sistema a microprocessore si individuano ALU, unità di controllo, memoria e I/O (Organizzazione del processore - Von Neumann, Harvard, bus, ALU e registriOgni processore ha ALU, memoria e dispositivi di I/O. Nell'organizzazione Von Neumann dati e istruzioni stanno nella stessa memoria e viaggiano su un solo sistema di bus (semplice ed economica, usata nei µC più semplici); nell'organizzazione Harvard memorie e bus sono separati (più accessi per ciclo: tipica di DSP e µC veloci). I bus sono pilotati da porte tri-state; l'ALU lavora su registri (accumulatore o molti registri); il controllo è cablato o microprogrammato; la gerarchia di memoria va dai registri alla RAM interna e a quella esterna.Organizzazione del processore - Von Neumann, Harvard, bus, ALU e registri →). L'ALU (unità aritmetico-logica) è l'insieme di circuiti digitali che permette al processore di eseguire le operazioni di base: somma e differenza, funzioni logiche (AND, OR, ...), scorrimenti e rotazioni per il cambio di scala dei dati; in alcuni processori anche prodotto e divisione.

Cella elementare e ALU a $n$ bit

I circuiti fondamentali sono: reti combinatorie per le funzioni logiche, il sommatore/sottrattore, i registri a scorrimento, i multiplexer (selettori) e il moltiplicatore.

• Il multiplexercircuito che sceglie una tra più linee di ingresso in base a un segnale di selezione con $S=0$ lascia passare $A$, con $S=1$ lascia passare $B$. Con un selettore si ottiene una cella che calcola $r=a\,\text{AND}\,b$ oppure $r=a\,\text{OR}\,b$.
• Il full addersommatore completo: somma due bit e un riporto entrante e produce un bit di somma e un riporto uscente (sommatore completo) di una cella $i$ ha ingressi $A_i$, $B_i$ e il riporto entrante $C_{in,i}$, e uscite il risultato $R_i$ e il riporto uscente $C_{out,i}$: $$R_i=A_i\oplus B_i\oplus C_{in,i},\qquad C_{out,i}=A_iB_i+A_iC_{in,i}+B_iC_{in,i}.$$ Con segnali di controllolinee con cui l'unità di controllo abilita o seleziona le operazioni dell'ALU ($s_1,s_2$ per scegliere l'uscita, $Inv$ per negare $B_i$) la cella esegue AND, OR, somma o sottrazione.

Collegando in parallelo $n$ celle (il $C_{out,i}$ di una è il $C_{in,i+1}$ della successiva) si opera su tutta la parola quasi simultaneamente. Il ritardo del circuito è dovuto solo alla propagazione del riporto, e limita la frequenza di clock (che è fissata dall'operazione più lenta eseguita in un ciclo).

La sottrazione si ottiene dalla stessa struttura: $A-B=A+C_2(B)=A+\mathrm{NEG}(B)+1$ (Numeri binari e complemento a dueI processori lavorano con un numero fisso di bit $n$. I naturali vanno da $0$ a $2^n-1$; per i negativi si usa il complemento a due: $C_2(N)=2^n-N=\overline N+1$ (si invertono tutti i bit e si somma 1). Con $n$ bit rappresenta $-2^{n-1}\le N\le2^{n-1}-1$, ha un solo zero e unifica somma e sottrazione. Quando il risultato esce dall'intervallo c'è overflow; gli overflow intermedi si compensano se il risultato finale è rappresentabile. La lunghezza di parola non è l'accuratezza.Numeri binari e complemento a due →). Basta attivare l'inversione di $B$ e caricare il riporto iniziale a 1 (invece che 0). La rappresentazione in complemento a 2 permette così di unificare i circuiti di somma e sottrazione.

Carry look-ahead

Nel sommatore a propagazioneuna cella propaga il riporto entrante all'uscita quando almeno uno dei suoi bit vale 1 del riporto (ripple carrysommatore in cui il riporto si propaga da una cella alla successiva, con ritardo proporzionale al numero di bit), se ogni cella introduce un ritardo $2\tau$ sul riporto, per $n$ bit servono $2n\tau$. Per un sommatore a 8 bit con $\tau=1$ ns: $8\cdot2+1=17$ ns (l'ultimo $\tau$ serve per formare il bit di somma).

Con il carry look-ahead (CLA) i riporti si calcolano direttamente dagli ingressi. Per ogni cella si definiscono $$g_i=A_iB_i\ (\text{generazione}),\qquad p_i=A_i+B_i\ (\text{propagazione}),\qquad C_{in,i+1}=g_i+p_i\,C_{in,i}.$$ Il riporto uscente è prodotto se la cella lo genera da sola ($A_i=B_i=1$) o se lo propaga ($A_i$ oppure $B_i=1$) quando ce n'è uno in ingresso. Iterando: $$\begin{aligned}C_{in,1}&=g_0+p_0C_{in}\\C_{in,2}&=g_1+p_1g_0+p_1p_0C_{in}\\C_{in,3}&=g_2+p_2g_1+p_2p_1g_0+p_2p_1p_0C_{in}\\C_{in,4}&=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0+p_3p_2p_1p_0C_{in}.\end{aligned}$$ Poiché $g_i$ e $p_i$ si ottengono da $A_i,B_i$ con una porta, ogni riporto richiede solo 3 livelli di logica (uno per $g,p$, due per i termini AND/OR) indipendentemente dalla posizione. Per più di 4 bit si ragiona a blocchi: ogni blocco da 4 celle è un "supersommatoreblocco di 4 celle trattato come un'unica cella, con generazione e propagazione proprie" con generazioneuna cella genera un riporto da sola quando entrambi i suoi bit valgono 1 $G$ e propagazione $P$ di blocco ($G_0=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0$, $P_0=p_3p_2p_1p_0$) e lo stesso schema si ripete tra i blocchi. Per 16 bit i riporti richiedono $3+2=5$ livelli ($5\tau$) contro $16\cdot2=32\tau$ del ripple: il CLA è 5-6 volte più veloce. Per 8 bit con due blocchi da 4 si hanno $5\tau$ per i riporti più $\tau$ per la somma: $6$ ns contro i $17$ ns del ripple (con $\tau=1$ ns).

Rivelazione dell'overflow

Sommando due numeri con lo stesso segno può verificarsi overflow; con segni diversi mai (il risultato è compreso tra i due operandi). Detti $a_{n-1},b_{n-1}$ i bit di segno degli addendi e $s_{n-1}$ quello della somma, l'overflow si ha quando $s_{n-1}$ è diverso da entrambi: $$V=s_{n-1}\,\overline{a_{n-1}}\,\overline{b_{n-1}}+\overline{s_{n-1}}\,a_{n-1}\,b_{n-1}.$$ Questa espressione è scomoda perché richiede di memorizzare i segni degli addendi (uno dei quali viene sovrascritto dalla somma). Una condizione equivalente e più economica usa i riporti dell'ultima cella: $$\boxed{V=\overline{C_{in,n-1}}\,C_{out,n-1}+C_{in,n-1}\,\overline{C_{out,n-1}}=C_{in,n-1}\oplus C_{out,n-1}}$$ Dimostrazione. Si analizza l'ultima cella ($n-1$), con $s_{n-1}=a_{n-1}\oplus b_{n-1}\oplus C_{in,n-1}$.

• Due positivi ($a=b=0$): $s_{n-1}=C_{in,n-1}$ e $C_{out,n-1}=0$. Il risultato è corretto (positivo) se e solo se $C_{in,n-1}=0$; c'è overflow se $C_{in,n-1}=1$: coincide con il termine $C_{in}\overline{C_{out}}$ (con $C_{out}=0$).
• Due negativi ($a=b=1$): $s_{n-1}=C_{in,n-1}$ e $C_{out,n-1}=1$. Il risultato è corretto (negativo) se $s_{n-1}=1$, cioè $C_{in}=1$; c'è overflow se $C_{in,n-1}=0$: coincide con il termine $\overline{C_{in}}\,C_{out}$.
• Segni diversi ($a\neq b$): $s_{n-1}=\overline{C_{in,n-1}}$ e $C_{out,n-1}=C_{in,n-1}$, quindi $C_{in}=C_{out}$ e $V=0$: nessun overflow. $\square$

Registri a scorrimento (shifter)

Lo shifter serve per allineare i dati prima o dopo operazioni aritmetiche, per moltiplicare o dividere per potenze di 2, per gestire la modalità intera o frazionaria del moltiplicatore, per funzioni logiche. A destra:

• shift logico: entrano 0 da sinistra;
• shift aritmetico: il bit di segno viene esteso (copiato). Lo shift a sinistra è sempre uguale (entra 0 da destra). Esempio su 8 bit: $10010011\gg2$: logico $00100100$, aritmetico $11100100$ (a destra di 2 posti equivale a dividere per 4 mantenendo il segno: $-109\to-28$). I $\mu$C più semplici offrono solo shift di un bit per volta; i processori più veloci hanno il barrel shifter, che sposta di $m$ bit nelle due direzioni in un ciclo; alcuni hanno anche lo shift circolare.

Realizzazione: una catena di flip-flopelemento di memoria a un bit, che cambia stato sul fronte del clock (D o J-K, con comando sul fronte e struttura master-slavestruttura a due latch in serie che impedisce all'ingresso di attraversare il registro nello stesso fronte di clock per evitare il fenomeno di ripple lungo il registro) con multiplexer che permettono il caricamento in parallelo (CTRL=1), il caricamento in serie e lo shift a destra di $m$ posti con $m$ impulsi di clock. Un generatore di impulsi programmabile ($m$ impulsi) si ottiene con un contatore binario (sincrono o asincrono "ripple") e un comparatorecircuito che confronta due parole e segnala se sono uguali binario (array di porte XNOR) che ferma il conteggio quando il contatorecircuito sequenziale che incrementa un numero binario a ogni impulso di clock raggiunge il valore del registro.

Errori comuni

• Sommare due numeri di segno uguale senza controllare l'overflow, e credere che l'overflow possa esserci con segni diversi.
• Dire che l'overflow coincide con il riporto uscente dall'ultima cella: è invece lo XOR dei riporti in ingresso e in uscita (un riporto uscente da solo è normale per numeri negativi).
• Applicare lo shift logico a destra a un numero negativo (cambia segno).
• Dimenticare di caricare il riporto iniziale a 1 nella sottrazione.