Lezione 7 ALU: Moltiplicazione e divisione Sommario Sommatori ad

Architettura degli Elaboratori e delle Reti
Lezione 7
ALU: Moltiplicazione e divisione
F. Pedersini
Dipartimento di Scienze dell’Informazione
Università degli Studi di Milano
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 1/34
Sommario
!
Sommatori ad anticipazione di riporto
!
Addizionatori modulari
!
Moltiplicatori – approccio hardware
!
Moltiplicatori – approccio firmware
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 2/34
Addizionatori modulari
!
Moduli elementari, collegabili in cascata.
"
!
Complessità del circuito tollerata per piccoli n
(es. n=4)
r0,in
Cammino critico C:
"
"
M moduli da 4 bit: C = 6·M
N = 16 bit # M = N/4
# C = 6·N/4 = 24
A propagazione di riporto:
N = 16 bit
# C = 3·N = 48
A.A. 2008/09
s
a
FA4
b
r3,out
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 3/34
Struttura sommatore a blocchi
!
Vogliamo 32 bit ! 8 sommatori elementari
"
Come collegarli tra loro?
r3 = g3 + p3r2 =
= g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0) =
= (g3+ p3g2+ p3p2g1+ p3p2p1g0) + p3p2p1p0·r0 =
= G0 + P0·r0
r0,in
s
a
dove:
P 0 = p 3 p2 p 1 p 0
G0 = g3 + p3g2 + p3p2g1 + p3p2p1g0
FA4
b
P0 G0
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 4/34
Struttura di un sommatore su 16 bit
C1 = G0 + P0·r0
C2 = G1 + P1·C1 =
= G1 + P1·G0 + P1·P0·r0
C3 = G2 + P2·C2 =
= G2 + P2·G1 + P2·P1·G0 +
+ P2·P1·P0·r0
rout = C4 = G3 + P3·C3 =
= G3 + P3·G2 + P3·P2·G1 +
+ P3·P2·P1·G0 + P3·P2·P1·P0·r0
Cammino critico = 6+6 = 12
• CLA + prop: 6M = 24
• Prop: 3N = 48
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 5/34
Sommario
!
Sommatori ad anticipazione di riporto
!
Addizionatori modulari
!
Moltiplicatori – approccio hardware
!
Moltiplicatori – approccio firmware
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 6/34
Moltiplicazione binaria
Moltiplicando
1 1 0 1 1 x (2710)
1 1 1 = (710)
___________________
111111
1 1 0 1 1 Moltiplicatore
11011–
11011––
___________________
1 0 1 1 1 1 0 1 (18910)
!
Come fare il calcolo
con circuiti logici ?
"
Possiamo scomporre
l’operazione in due stadi:
"
Primo stadio: prodotti
parziali
!
"
Secondo stadio: somme
!
Prodotto
A.A. 2008/09
si mette in AND ciascun bit
del moltiplicatore con i bit
corrispondenti del
moltiplicando
si effettuano le somme (full
adder) dei bit sulle righe
contenenti i prodotti parziali
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 7/34
La matrice dei prodotti parziali
In binario i prodotti parziali sono degli AND
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 8/34
Il circuito che effettua i prodotti
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 9/34
Somma – prime 2 righe dei prodotti parziali
1011 x
0111 =
___________
111
1011 +
1011–
___________
1
100001 +
1011––
___________
1101101
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 10/34
Somma della terza riga
11011 x
111 =
___________
11111
11011 +
11011–
___________
1
1010001 +
11011–
___________
10111101
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 11/34
Somma prodotti parziali – circuito completo
Overflow: A e B su: N bit # P su: 2N bit
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 12/34
Valutazione del cammino critico
!
N=4
"
Ritardo AND = 1
"
Ritardo HA = 1
Ritardo FA = 3
"
!
1
Cammino critico
= 20
2
5
8
14
17
11
17
20
A.A. 2008/09
20
20
17
12
© A. Borghese, F. Pedersini – DSI, UniMI
6
2
1
L 7 – 13/34
Sommario
!
Sommatori ad anticipazione di riporto
!
Addizionatori modulari
!
Moltiplicatori – approccio hardware
!
Moltiplicatori – approccio firmware
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 14/34
Approcci tecnologici alla ALU
Approcci tecnologici alla costruzione di ALU:
! Hardware
"
!
Ad ogni operazione corrisponde un circuito combinatorio specifico
Firmware o microprogrammato
"
"
"
Circuiti specifici solamente per alcune operazioni elementari
Le operazioni complesse vengono sintetizzate mediante combinazione di
operazioni elementari, eseguendo uno specifico algoritmo (implementato
mediante microprogrammazione)
Approccio “controllore-datapath”
!
!
La ALU contiene una unità di controllo e dei registri
FIRMWARE vs. HARDWARE:
"
Hardware: più veloce ma più costosa per complessità dei circuiti
!
"
La soluzione HW conviene per le operazioni frequenti
Firmware: meno veloce ma più flessibile. Potenzialmente adatta a modificare o
inserire nuove procedure.
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 15/34
Presentazione seriale/parallela
!
Presentazione parallela
"
an
Tipico dell’approccio HW
!
Viene utilizzata un’unica copia del circuito aritmetico
Il tempo di calcolo cresce linearmente con il numero
di bit
non si possono utilizzare tecniche di carry look-ahead
Presentazione seriale a gruppi
s0
s1
sn
..
.
!
"
b0
b1
Gli operandi vengono presentati 1 bit alla
volta, del quale viene eseguita l’operazione e
fornito il risultato
!
ALU
..
.
Presentazione seriale
"
!
..
.
!
!
a0
a1
Tutti i bit vengono presentati
simultaneamente;
La ALU genera tutti i bit del risultato
bn
a0 a1 …an
I bit vengono presentati a gruppi di k bit (es.
k=8: bytes)
ALU
s0 s1…sn
b0 b1 …bn
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 16/34
Operazione di SHIFT (scorrimento)
Dato A={an an-1 … a1 a0} ! sk(A)=A! , a!j = aj–k
"
k: shift amount
!
!
Tempo comparabile con quello della somma
Effettuato al di fuori delle operazioni selezionate dal MUX della ALU, da un
circuito denominato Barrel Shifter
an
an-1
an-2
a1
a0
an-1
an-2
an-3
a0
0
0
an
an-1
a2
!"#$%&'&!(&)#&*
a1
!"#$%&'&)(&)#&*
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 17/34
La moltiplicazione firmware
Algoritmo della moltiplicazione – firmware
Si analizzano sequenzialmente i
bit del moltiplicatore
se il bit è = 1
! moltiplicando in posizione
opportuna
se il bit è = 0
! 0 in posizione opportuna
A.A. 2008/09
11011x
101=
_______________
11011+
00000–
11011––
_______________
10000111
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 18/34
Moltiplicazione firmware
!
Utilizzo un
registro prodotto da
2n bit, inizializzato a 0
!
Ciclo iterativo: per ogni bit
del moltiplicatore
Se bit = 1 ! sommo il
moltiplicando al prodotto
shift a SX di 1 bit del
moltiplicando
"
"
A.A. 2008/09
11011x
111=
_______________
11111
11011+
110110
_______________
1
1010001+
1101100
_______________
10111101
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 19/34
L’algoritmo
Inizio (P = 0, k = 0)
A
B
P
11011x
111=
_______________
11111
11011+
110110
_______________
1
1010001+
1101100
_______________
10111101
no
bk=1 ?
sì
P"A+P
shift A a sx ,
k=k+1
k=n ?
no
sì
Fine
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 20/34
Implementazione circuitale
A (moltiplicando) + shift sx – 64 bit
B (moltiplicatore) – 32 bit
ALU 64
add
shift
P (prodotto) – 64 bit
scrivi
32
Controllo
UC riceve 32
bit ma ne legge
1 alla volta
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 21/34
Implementazione circuitale – modifica
A (moltiplicando) + shift a sx – 64 bit
ALU 64
P (prodotto) – 64 bit
A.A. 2008/09
B (moltiplicatore)
+ shift a dx – 32 bit
1
add
shift dx
shift sx
scrivi
Controllo
© A. Borghese, F. Pedersini – DSI, UniMI
Ad ogni iterazione:
B " shift_dx(B)
UC riceve sempre
LSB
L 7 – 22/34
Esempio
A,B: 4 bit – P: 8 bit
2x3=6
0010 x 0011 = 0110
0000 0100
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 23/34
Implementazione alternativa: idea
P0
!
Soltanto metà dei bit del
registro moltiplicando vengono
utilizzati ad ogni iterazione
"
shift
Ad ogni iterazione si aggiunge 1 bit al
registro prodotto
P1
!
IDEA
Si caricano i risultati parziali in P
nella metà SINISTRA
" Si sposta la somma dei prodotti
parziali (in P) verso destra ad ogni
iterazione
"
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
shift
P2
L 7 – 24/34
Seconda implementazione
A – moltiplicando, 32 bit
B – moltiplicatore
+ shift dx – 32 bit
add
ALU 32
shift dx
P – prodotto + shift dx – 64 bit
A.A. 2008/09
scrivi
shift dx
Controllo
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 25/34
Implementazione ottimizzata
Numero di bit del prodotto corrente
+
Numero di bit da esaminare di B
=
64 bit: costante ad ogni iterazione
$
elimino il registro moltiplicatore: B
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
11011x
111=
_______________
11111
11011+
11011_______________
1
1010001+
11011- _______________
10111101
L 7 – 26/34
Circuito ottimizzato
!
Situazione alla prima iterazione
A – moltiplicando, 32 bit
ALU 32
P – prodotto –
64 bit
add
scrivi
Moltiplicatore
B – 32 bit
shift dx
Controllo
+ shift dx
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 27/34
L’algoritmo ottimizzato
Inizio (P = 0, k = 0)
P
A
11011x
B
111=
_______________
11111
11011+
110110
_______________
1
1010001+
1101100
_______________
10111101
sì
bk=0?
no
P"A+P
shift [P|B] a dx
k=k+1
k=n ?
no
sì
Fine
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 28/34
Esempio di esecuzione alg. ottimizzato
A, B: 4 bit – P: 8 bit
2x3=6
0010 x 0011 = 0000 0110
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 29/34
Divisione intera - n bit (unsigned)
!
Algoritmo: n+1 iterazioni
1.
2.
3.
4.
5.
K=n
Sottraggo il divisore moltiplicato per 2K dal dividendo
Se differenza > 0 ! dividendo = dividendo – divisore x 2K
K=K–1
Se K > 0, torna a 2 altrimenti FINE
7 : 2 = 3, resto 1
00000111 –
00100000 =
bit4 quoz.: 0
"
"
00000111 –
00100 =
bit1 quoz.: 1
A.A. 2008/09
"
0111 : 0010 = 0011, resto 0001
00000111 –
0010000 =
bit3 quoz.: 0
"
"
00000011 –
0010 =
bit0 quoz.: 1
© A. Borghese, F. Pedersini – DSI, UniMI
00000111 –
001000 =
bit2 quoz.: 0
"
quoz: 00011
resto: 1
L 7 – 30/34
Divisione intera (unsigned) : n=32 bit
!
Dividendo, divisore, quoziente, resto: 32 bit
"
Remainder: inizializzato con divisore x 232
A.A. 2008/09
" servono 64 bit
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 31/34
Divisione intera (unsigned) : n=32 bit
!
Esempio di funzionamento:
divisore x 24
dividendo
resto
quoziente
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 32/34
Divisione intera (unsigned) : n=32 bit
!
Progetto ottimizzato:
"
"
"
Allineo il dividendo senza shiftare il divisore " ALU a soli 32 bit
Se differenza < 0 ! ripristina di Remainder (+= divisor),
SLL remainder, R0 = 0
altrimenti:
! SLL remainder, R0 = 1
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 33/34
Divisione intera (unsigned) : n=32 bit
!
Esempio, struttura ottimizzata:
divisore
resto
A.A. 2008/09
© A. Borghese, F. Pedersini – DSI, UniMI
dividendo
quoziente
L 7 – 34/34