Traslatori, comparatori e moltiplicatori

In questa pagina 4

I blocchi aritmetici di una ALU (Blocchi logici di un microprocessore - ALU, bus e logica tri-state) comprendono, oltre ai sommatori (Sommatori - full adder e ripple-carry, Sommatori veloci - carry-bypass, carry-select e square-root), i traslatori, i comparatori e i moltiplicatori.

Traslatori (shifter)

Un traslatore sposta i bit di una parola di $k$ posizioni. Tipi, per una parola $a_{N-1}\dots a_0$ :

shift logico a sinistra (LSL): i bit si spostano verso l'MSB, si entra con $0$ da destra: equivale a moltiplicare per $2^k$ (senza overflow);
shift logico a destra (LSR): si entra con $0$ da sinistra: divisione per $2^k$ per i numeri senza segno;
shift aritmetico a destra (ASR): si replica il bit di segno da sinistra: divisione per $2^k$ per i numeri in complemento a due;
rotazione (ROL, ROR): i bit usciti da un lato rientrano dall'altro.

Esempi (8 bit). $0001\,0110\ (22)$ , LSL di $2$ : $0101\,1000\ (88)=22\cdot4$ . $1110\,0100\ (-28)$ , ASR di $1$ : $1111\,0010\ (-14)$ ; LSR di $1$ darebbe $0111\,0010\ (114)$ , sbagliato per un numero con segno. Rotazione a destra di $0001\,0110$ di $2$ : $1000\,0101$ .

Barrel shifter. Un traslatore a una sola posizione (un multiplexer $2\to1$ per bit: "shifta" o "non shifta") non basta per spostamenti variabili. Il barrel shifter usa $\log_2N$ livelli di multiplexer $2\to1$ : il livello $j$ trasla di $2^j$ posizioni se il bit $j$ del numero di posizioni $s$ vale $1$ . Per $N=8$ : tre livelli (traslazioni di $1$ , $2$ , $4$ ) coprono ogni $s$ da $0$ a $7$ ; per $s=5=101_2$ sono attivi i livelli $1$ e $4$ . Costo: $N\log_2N$ multiplexer; ritardo: $\log_2N$ ritardi di multiplexer, indipendente da $s$ . In VHDL gli operatori di traslazione sono sll, srl, sla, sra, rol, ror (VHDL - struttura, tipi di dato e processi).

Comparatori

Uguaglianza. $A=B$ se e solo se ogni coppia di bit è uguale: il bit $i$ è uguale se $e_i=A_i\overline{\oplus}B_i=\overline{A_i\oplus B_i}$ (XNOR); $EQ=e_{N-1}\,e_{N-2}\cdots e_0$ (AND di $N$ XNOR, ad albero per limitare il fan-in: Porte logiche CMOS - ritardo di Elmore, fan-in e consumo).

Grandezza (senza segno). Si confrontano i bit a partire dal più significativo: $A>B$ se al primo bit in cui differiscono $A_i=1$ e $B_i=0$ . Con $g_i=A_i\overline{B_i}$ (qui $A_i>B_i$ ) e $e_i$ come sopra: $GT=g_{N-1}+e_{N-1}\big(g_{N-2}+e_{N-2}(g_{N-3}+\dots)\big),\qquad LT\text{ analogo},\quad EQ=\prod e_i.$ Esempio: $A=1011$ , $B=1001$ : $e_3=1$ (1,1), $e_2=1$ (0,0), il bit $1$ : $A_1=1>B_1=0$ ( $g_1=1$ ): quindi $GT=0+1\cdot(0+1\cdot1)=1$ , $A>B$ ( $11>9$ ).

Con la sottrazione. Si calcola $A-B=A+\overline B+1$ e si legge: $Z$ per l'uguaglianza; per i numeri senza segno $A\ge B$ se il riporto d'uscita vale $1$ (nessun prestito); per i numeri con segno $A<B$ se $N\oplus V$ vale $1$ (segno del risultato corretto dall'overflow). È il metodo dei processori (flag $Z$ , $C$ , $N$ , $V$ ).

Moltiplicatori

Il prodotto di due numeri senza segno di $N$ bit ha $2N$ bit. Per ogni bit $B_j$ del moltiplicatore si forma un prodotto parziale $PP_j=A\cdot B_j$ (un AND per bit) traslato di $j$ posizioni e si sommano tutti.

Esempio ( $4\times4$ bit): $A=1011\ (11)$ , $B=1101\ (13)$ :

        1011   A  (11)
      x 1101   B  (13)
      ------
        1011   bit B0 = 1: A
       0000    bit B1 = 0: zero, traslato di 1
      1011     bit B2 = 1: A traslato di 2
     1011      bit B3 = 1: A traslato di 3
     --------
     10001111  = 11 + 44 + 88 = 143

Moltiplicatore a matrice (array): $N^2$ porte AND generano i prodotti parziali e una matrice di $N(N-1)$ full adder ne somma le righe (il riporto di ciascuna riga si propaga alla successiva): $N=4$ : $16$ AND e $12$ full adder. Il cammino critico attraversa circa $2N$ celle: ritardo $\approx(2N-2)\,t_{carry}+t_{sum}$ , lineare in $N$ ma con area quadratica ( $O(N^2)$ celle).

Alternative.

Wallace tree (somma con riporto salvato, carry-save): i prodotti parziali si riducono con livelli di full adder usati come compressori 3:2 (tre bit in ingresso, due in uscita) fino a due righe; l'ultimo passo è un sommatore veloce. Ritardo $O(\log N)$ .
Booth: raggruppa il moltiplicatore in coppie di bit ( $radix\text{-}4$ ): dimezza il numero di prodotti parziali e gestisce direttamente il complemento a due.
Sequenziale (shift-and-add): un solo sommatore e un registro che accumula; ad ogni ciclo si somma $A$ (se il bit $B_j=1$ ) e si trasla: $N$ cicli, area minima.
Nelle FPGA (FPGA - LUT, slice e risorse della famiglia 7) i moltiplicatori sono blocchi DSP dedicati ( $25\times18$ bit con pre-sommatore e accumulatore), molto più veloci di quelli in logica generale.

Errori comuni

Usare lo shift a destra logico per un numero con segno (perde il segno): serve quello aritmetico.
Dimenticare che il prodotto di due numeri a $N$ bit richiede $2N$ bit.
Confrontare i bit da quello meno significativo: il confronto di grandezza parte dall'MSB.
Dire che il moltiplicatore array è $O(\log N)$ : lo è il Wallace tree (con sommatore finale veloce).

Versione ripasso

Shift: LSL $\times2^k$ ( $0001\,0110\to0101\,1000$ ); LSR senza segno; ASR replica il segno ( $1110\,0100\,(-28)\to1111\,0010\,(-14)$ ); rotazioni. Barrel shifter: $\log_2N$ livelli di mux $2\to1$ ( $N\log_2N$ mux, $s=5$ : livelli $1$ e $4$ per $N=8$ ); ritardo $\log N$ .
Comparatore: uguaglianza $=\prod$ XNOR; grandezza dal MSB: $GT=g_{N-1}+e_{N-1}(g_{N-2}+e_{N-2}(\ldots))$ ( $1011>1001$ ); con la sottrazione: $Z$ , riporto (senza segno), $N\oplus V$ (con segno).
Moltiplicatore: $2N$ bit di prodotto; prodotti parziali con AND traslati e sommati ( $1011\times1101=143=1000\,1111$ ); array: $N^2$ AND, $N(N-1)$ full adder, ritardo $\approx2N$ celle; Wallace (carry-save, $O(\log N)$ ), Booth radix-4, sequenziale ( $N$ cicli); DSP in FPGA.
Errori: LSR su numeri con segno; $2N$ bit dimenticati; confronto dall'LSB; array $=O(\log N)$ .

Traslatori, comparatori e moltiplicatori

Traslatori (shifter)

Comparatori

Moltiplicatori

Errori comuni

Teoria collegata