Divisioni e numeri in virgola mobile
ALU
(1)
a
(3
parte)
moltiplicazione
°Abbiamo 3 versioni:
• Alu a 64 bit, due “registri” a 64 bit ed uno
a 32
• Alu a 32 bit, un registro a 64 e due a 32
• Alu a 32 bit, un registro a 64 ed uno a 32
°Osservazione: ho un solo algoritmo…
gli altri sono sono basati su
osservazioni su come risparmiare
spazio
°Per le moltiplicazioni con il segno…
algoritmo di Booth
(2)
La divisione
°Un po’ più complicata…offre la
possibilità di un’operazione non
valida, la divisione per 0.
°L’idea è la solita, sottrazioni
successive…
(3)
Esempio
°Divisione…..
facciamone una
dividendo
1001010 : 1000
-1000
1001
10
101
1010
-1000
10
divisore
quoziente
Resto
(4)
Idea
L’algoritmo cerca di verificare quanto è grande
il numero che può essere sottratto, costruendo
il quoziente un bit alla volta, ad ogni tentativo.
Quando abbiamo a che fare con 0 e 1 è facile
prevedere quante volte il divisore stia nella
porzione di dividendo considerata: sarà
sempre 0 volte o 1 volta.
(5)
Prima versione della logica della divisione
Ad ogni passo l’algoritmo scala il divisore a
destra di una posizione per allinearlo con il
dividendo, e quindi si deve iniziare con il
divisore messo nella metà sinistra del
registro di 64 bit ed eseguire uno
scalamento dello stesso di 1 bit.
Il registro del resto è inizializzato con il
valore del dividendo.
(6)
Ancora…
Diversamente dagli esseri umani il
calcolatore non è abbastanza furbo da
capire in anticipo se il divisore è più piccolo
del dividendo. Deve prima sottrarre il
divisore: se il risultato è positivo, il divisore
è più piccolo o uguale al dividendo e si
genera un 1 nel quoziente. Altrimenti si
ripristina il valore iniziale (aggiungendo al
resto il divisore) e si genera uno 0 nel
quoziente. Il divisore è scalato a destra.
(7)
Divisione (1/3)
Metto 0 nel registro quoziente (32 bit)
Metto il divisore nella parte sinistra del registro
divisore (64 bit)
Metto il dividendo nella parte destra del registro
resto (64 bit)
1. Sottraggo il divisore dal resto
2. Controllo il resto
a) se è < 0 ripristino il valore originale del resto e scalo
di una cifra a sinistra il quoziente (inserendo uno 0)
b) se è > o uguale a 0 allora scalo di una cifra a sinistra
il quoziente inserendo un 1
3. scala il divisore di 1 bit a destra
4. quante volte? n + 1
(8)
Divisione (2/3)
inizio
1a
resto < 0
resto  0
2
2a
2b
3
no
(9)
si
n +1 volte?
fine
Divisione (3/3)
divisore
64 bit
scalamento a destra
ALU a 64 bit
quoziente
scalamento a sinistra
64 bit
resto
scrittura
(10)
controllo
32 bit
Divisione rivista (1/3)
Come prima… mi accorgo che il divisore
da 32 bit mi basta
Scaliamo a sinistra il resto al posto dello
scalare a destra il divisore
(11)
Divisione rivista (2/3)
Metto 0 nel registro quoziente (32 bit)
Metto il dividendo nel registro resto (64 bit)
1. Sottraggo il divisore dal resto (i 32 bit alti)
2. Controllo il resto
a) se è < 0 ripristino il valore originale del resto
e scalo di una cifra a sinistra il quoziente
(inserendo uno 0)
b) se è > o uguale a 0 allora scalo di una cifra a
sinistra il quoziente inserendo un 1
3. scala il resto di 1 bit a sinistra
4. quante volte? n + 1
(12)
Divisione rivista (3/3)
divisore
ALU a 32 bit
32 bit
quoziente
scalamento a sinistra
resto
scrittura
scalamento a sinistra
(13)
64 bit
controllo
32 bit
Divisione finale (1/3)
avevamo eliminato il moltiplicatore?
eliminiamo il quoziente
dove lo mettiamo?
nel resto ( si inserisci I vari bit al posto
degli 0)
(14)
Non solo, ma dato che il primo passo
dell’algoritmo non può produrre un 1
nel quoziente (il quoziente sarebbe
troppo grande), cambiando l’ordine (
prima scalamento e poi sottrazione, si
può
eliminare
un’iterazione
dell’algoritmo.
Divisione finale (2/3)
inizio
scalamento di 1 bit
a sinistra del resto
resto < 0
resto?
(15)
resto  0
scalare a sinistra
resto inserendo 1
ripristinare valore
originale
scalare a sinistra
resto inserendo 0
fine
scala a destra metà
sinistra del resto
sottrarre il divisore dalla
metà sinistra del resto e
mettere il risultato nella
metà sinistra del resto
si
no
n volte?
Divisione finale (3/3)
divisore
32 bit
ALU a 32 bit
64 bit
scalamento a sinistra
scrittura
resto
scalamento a destra
(16)
controllo
Come faccio a fare divisioni con il segno?
°Si fanno le divisioni tra i numeri
rappresentati normalmente e poi si
mettono i segni corretti nei risultati
°Attenzione al segno del resto…
(17)
Virgola mobile….
(18)
Sommare due numeri in virgola mobile
°Allineare la virgola (esponenti uguali)
°Sommare le mantisse
°Normalizzare di nuovo, se è
necessario…
°Vediamo come
(19)
Algoritmo della somma
inizio
confronta gli esponenti
se sono diversi aumenta
il minore fino a che non
diventano uguali
eccezione
si
somma le
mantisse
normalizza la somma
(o scalando a destra e incrementando e, o scalando a
sinistra e decrementando e)
problemi?
no
no
(20)
fine
normalizzato?
si
arrotondamento
mantissa
Vediamo l’hardware…. complesso….
Sign
Exponent
Significand
Sign
Exponent
Significand
Compare
exponents
Small ALU
Exponent
difference
0
1
0
Control
1
0
Shift smaller
number right
Shift right
Big ALU
0
1
0
Increment or
decrement
Sign
Exponent
Add
1
Shift left or right
Rounding hardware
(21)
1
Significand
Normalize
Round
moltiplicazione
°Sommo gli esponenti
°Moltiplico le mantisse
°Normalizzo
°Determino il segno (positivo se
concordi, negativo altrimenti)
(22)
L’algoritmo della moltiplicazione
inizio
eccezione
somma gli esponenti
(sottraendo la costante
di polarizzazione)
si
moltiplica le
mantisse
normalizza il prodotto
(scalando a destra e incrementando e)
no
fine
no
(23)
problemi?
determina il
segno
normalizzato?
si
arrotondamento
mantissa
Arrotondamento (in decimale)
°Fisso il numero di cifre dopo la virgola
°Devo rappresentare un numero con più
cifre dopo la virgola normalizzato
• considero l’ultima cifra rappresentabile
• considero la prima cifra che non posso
rappresentare (cifra di guardia)
• considero la seconda cifra che non posso
rappresentare (cifra di arrotondamento)
rappresentabile
x
x
x+1
(24)
guardia
0-4
5
5-9
arrotondamento
0-9
0
0-9
E in binario?
°Dipende, considero o due o tre bit…
°I tre bit dipendono da situazioni
particolari
°Predispongo dell’hw per fare questo
(25)