ALU (2a parte)
Shift e Moltiplicazioni
(1)
Alu
°Sappiamo fare alcune cose:
•Somme
•Sottrazioni
•and bit a bit
•or bit a bit
•negazione
•Controllare se a < b
°Basta?
(2)
Moltiplicare per 2
°Come facciamo a moltiplicare
per 2?
°a x 2 = a + a
°Potrei usare di nuovo la ALU
°Ma… esiste un hw particolare,
il barrel shifter che sposta a
destra o sinistra…
(3)
Barrel shifter
Il barrel shifter è un circuito che può
eseguire lo scalamento di un’entità
da 1 a 32 bit esattamente nel tempo
necessario per sommare due numeri
su 32 bit, così che lo scalamento è
normalmente eseguito al di fuori
della ALU. di
(4)
Esercizio: progettare il barrel shifter
°Lo progettiamo piccolino… a 4 bit
°Dati in ingresso: numero di 4 bit (a) e il
numero di bit che vogliamo shiftare
(5)
Cosa significa “shiftare” (1/3)
°Shiftare a sinistra = Moltiplicare per la
base:
00000000000000000000000000001001
0 00000000000000000000000000010010
°Si perde
si introduce
°Il primo numero è 9, il secondo 18
°Posso specificare di quante cifre…
(6)
Cosa significa “shiftare” (2/3)
°Shiftare a destra= Dividere per la base
00000000000000000000000000001001
00000000000000000000000000000100 1
°Si introduce
si perde
°Attenzione: se il numero è negativo devo
introdurre un 1
(7)
°In effetti, 9 diviso 2 da 4 (resto 1)
Cosa significa “shiftare” (3/3)
°Se specifico la direzione e il numero di cifre
ho tutto quello che serve.
°Quante possono essere? Al più il numero
di bit del numero in input
Moltiplico per 232 il numero
00011100010100010001000110001001
00000000000000000000000000000000
(8)
Vediamo una direzione: moltiplicazione
°Ingressi:
• numero da shiftare
• quantità
°Uscita:
• Il numero corretto…
°Avete tutti gli elementi (multiplexer…)
(9)
soluzione
°Attenzione, non è l’unica!
a0
0
a1
a2
a3
(10)
s0
s1
0
1
0
1
s0 s1
q0
0
0
1
0
1
q1
shift amount
0
0
0
1
0
1
0
1
2
1
1
3
0
0
1
0
1
0
1
q2
0
1
q3
E per la divisione?
°Riorganizzate i fili.
°Mettiamo assieme il tutto
a0
0
a1
0
(11)
0
1
2
3
0
1
2
3
direzione quantità
q0
q1
direzione quantità
destra
0
10
destra
1
11
sinistra
0
00
sinistra
1
00
Perché?
°Moltiplicazione….
facciamone una
moltiplicando
0010 x
1001 =
0010 +
0000 +
0000 +
0010
=
moltiplicatore
0010010
(12)
sommo 0010 a 0000
sommo 0000x2 a 0010
sommo 0000x4 a 0010
sommo 0010x8 a 0010
prodotto
Moltiplicazione (1/3)
Il risultato su 2n bit tutti posti a zero
1. controllo la cifra più a destra del
moltiplicatore
a) se è 0 non fare nulla
b) se è 1 allora somma il moltiplicando al
risultato
2. scala il moltiplicando di 1 bit a sinistra
3. scala il moltiplicatore di 1 bit a destra
4. quante volte? n
(13)
Moltiplicazione (2/3)
inizio
moltiplicatore0 = 1
1
moltiplicatore0 = 0
1b
2
3
fine
n volte?
si
(14)
no
Moltiplicazione (3/3)
64 bit
moltiplicando
scalamento a sinistra
ALU a 64 bit
moltiplicatore
scalamento a destra
64 bit
prodotto
scrittura
(15)
controllo
32 bit
Critiche
°Nel primo algoritmo metà dei bit del
moltiplicando rimane a 0 e quindi solo
metà contiene bit utili.
°Una ALU a 64 bit diventa lenta e inutile
dal momento che metà dei bit del
sommatore sommano 0 alla somma
parziale.
(16)
Cosa posso fare
L’algoritmo visto esegue lo scalamento
verso sinistra del moltiplicando inserendo
degli 0 nelle nuove posizioni, così che il
moltiplicando non può influenzare i bit meno
significativi del prodotto dopo che questi
sono stati forzati al loro valore. Non potrei
scalare il prodotto a destra invece che il
moltiplicando a sinistra?
(17)
Ed ancora…
In tal modo il moltiplicando potrebbe restare
fisso rispetto al prodotto e dal momento che
si stanno sommando 32 bit, il sommatore
deve essere ampio 32 bit.
Il prodotto da 64 bit viene modificato dalla
somma solo nella metà sinistra (di 32 bit).
(18)
Moltiplicazione rivista (1/3)
Il risultato su 2n bit tutti posti a zero
1. controllo la cifra più a destra del
moltiplicatore
a) se è 0 non fare nulla
b) se è 1 allora somma il moltiplicando alla
parte sinistra del risultato
2. scala il risultato di 1 bit a destra
3. scala il moltiplicatore di 1 bit a destra
4. quante volte? n
(19)
Moltiplicazione rivista (2/3)
inizio
moltiplicatore0 = 1
1
moltiplicatore0 = 0
1b
2
3
fine
n volte?
si
(20)
no
Moltiplicazione rivista (3/3)
moltiplicando
ALU a 32 bit
32 bit
moltiplicatore
scalamento a destra
prodotto
scrittura
scalamento a destra
(21)
64 bit
controllo
32 bit
ho davvero bisogno del moltiplicatore?
°No, posso fare tutto con il risultato
°Parto mettendo nella meta’ destra del
risultato il moltiplicatore (il prodotto
spreca uno spazio che corrisponde
esattamente alla dimensione del
moltiplicatore)
Man mano che lo
spazio sprecato dal prodotto
scompare, scompaiono anche I bit del
moltiplicatore.
(22)
Moltiplicazione finale (1/3)
Il risultato su 2n bit in cui mettiamo il
moltiplicatore
1. controllo la cifra più a destra del
risultato
a) se è 0 non fare nulla
b) se è 1 allora somma il moltiplicando alla
parte sinistra del risultato
2. scala il risultato di 1 bit a destra
3. quante volte? n
(23)
Moltiplicazione finale (2/3)
inizio
risultato0 = 1
1
risultato0 = 0
1a
2
fine
n volte?
si
(24)
no
Moltiplicazione finale (3/3)
moltiplicando
32 bit
ALU a 32 bit
prodotto
scrittura
scalamento a destra
(25)
64 bit
controllo
Numeri con il segno…
°Faccio le moltiplicazioni normalmente
e mi ricordo i segni
°Applico le solite regole per
determinare il segno
°Oppure: algoritmo di Booth
(26)
Algoritmo di Booth (1/3)
Il risultato su 2n bit in cui mettiamo il
moltiplicatore
1. controllo le due cifre più a destra del
risultato
a) se sono 10 allora sottrai dal risultato il
moltiplicando (nella parte sinistra)
b) se è 11 o 00 allora non fare nulla
c) se sono 01 allora somma il moltiplicando
alla parte sinistra del risultato
2. scala il risultato di 1 bit a destra
3. quante volte? n
(27)
Algoritmo di Booth (2/3)
inizio
no
era 0
si
risultato0 = 1
1
risultato0 = 0
risultato0 = 1
1
1a
risultato0 = 0
1c
2
(28)
fine
si
n volte?
no
Algoritmo di Booth (3/3)
moltiplicando
32 bit
Uso l’ultima versione
ALU a 32 bit
prodotto
scrittura
scalamento a destra
(29)
64 bit
controllo
Perché funziona?
ai
ai+1
Operazione
0
0
Non fare nulla
0
1
Sommare b
1
0
Sottrarre b
1
1
Non fare nulla
ai+1 – ai =
(30)
{
0
+1
-1
Non fare nulla
Sommare b
Sottrarre b
Tenete presente che scalare il moltiplicando è come fare x2k