Lezione 7 Sommatori e Moltiplicatori Sommario Sommatori ad

Architettura degli Elaboratori e delle Reti
Lezione 7
Sommatori e Moltiplicatori
Proff. A. Borghese, F. Pedersini
Dipartimento di Scienze dell’Informazione
Università degli Studi di Milano
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 1/36
Sommario

Sommatori ad anticipazione di riporto

Addizionatori modulari

Moltiplicatori – approccio hardware

Moltiplicatori – approccio firmware
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 2/36
1
Anticipazione di riporto

Anticipazione di riporto (carry look-ahead)



Approccio per diminuire la latenza della somma
Propagazione di riporto: tL = 3N
Principio di funzionamento:

Si genera un riporto in uscita quando ho almeno due “1” sui tre
ingressi (rin, a, b)
rIN
a
b
s
FA
rOUT
A.A. 2006/07
1 1 0 0 0  riporto
1101+
100=
––––––––
10001
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 3/36
Propagazione e generazione

Ho riporto quando ho almeno 2 dei 3 ingressi (rin, a, b) = “1”

Due casi possibili:

GENERAZIONE: gi
Viene generato un riporto allo stadio i,
per qualsiasi rin, se:
gi = aibi ;

gi = 1  ri,out = 1
PROPAGAZIONE: pi
Viene generato un riporto allo stadio i,
se rin = 1 e (a OR b) = 1
pi = (ai + bi) ;
A.A. 2006/07
rIN
a
b
FA
s
rOUT
pi ri,in = 1  ri,out = 1
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 4/36
2
Esempio

Calcolo: r4,out

supponiamo r0,in = 0
10100101+
10000=
1
10101101+
11010=
r4,out = 0
A.A. 2006/07
10110101+
10100=
r4,out = 1
r4,out = 1
Propagazione:
Generazione:
p4r3,out =(a4+b4)r3,out = 1
g4 = a4b4 = 1
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 5/36
Sviluppo della funzione logica riporto
Dato che:
ri,out = aibi + (ai + bi) ri,in =
= gi + pi ri,in

ri = ri,out = ri+1,in = ri+1
Ricavo r3,out come funzione degli ingressi: ai , bi , rin,0:
r0,out = g0 + p0· r0,in
r0,in
r1,out = g1 + p1r0,out = g1 + p1g0 + p1p0 r0,in
r2,out = g2 + p2r1,out = g2 + p2(g1 + p1g0 + p1 p0 r0,in)
= g2 + p2g1 + p2p1g0 + p2p1p0 r0,in
r3,out = g3 + p3r2,out =
= g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0 r0,in) =
= g3 + p3g2 + p3p2g1 + p3p2p1 g0 + p3p2p1p0·r0,in
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
s
a
b
FA4
r3,out
L 7 – 6/36
3
Anticipazione di riporto (4 bit)
r3,out
= g3 + p3r2 = g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0,in) =
= g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0·r0,in
r0,in
p3
a3
b3
a2
b2
a1
b1
a0
b
a00
b0
a1
b1
a2
b2
a3
b3
p2
p1
p0
g0
·
p3p2
·
·
p3p2p1p0r0
r3,out
p1p0
p1g0
·
p3p2p1g0
+g1p3p2
g1
g2
g3++g2p3
g3
Cammino critico = 6
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 7/36
Sommario

Sommatori ad anticipazione di riporto

Addizionatori modulari

Moltiplicatori – approccio hardware

Moltiplicatori – approccio firmware
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 8/36
4
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 = 32 bit  M = N/4
 C = 6·N/4 = 48
A propagazione di riporto:
N = 32 bit
 C = 3·N = 96
A.A. 2006/07
s
a
FA4
b
r3,out
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 9/36
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
P0 = p3p2p1p0
G0 = g3 + p3g2 + p3p2g1 + p3p2p1g0
FA4
b
P0 G0
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 10/36
5
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 11/36
Sommario

Sommatori ad anticipazione di riporto

Addizionatori modulari

Moltiplicatori – approccio hardware

Moltiplicatori – approccio firmware
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 12/36
6
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. 2006/07
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
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 13/36
La matrice dei prodotti parziali
In binario i prodotti parziali sono degli AND
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 14/36
7
Il circuito che effettua i prodotti
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 15/36
Somma – prime 2 righe dei prodotti parziali
11011 x
111 =
___________
11111
11011 +
11011–
___________
1
1010001 +
11011–
___________
10111101
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 16/36
8
Somma della terza riga
11011 x
111 =
___________
11111
11011 +
11011–
___________
1
1010001 +
11011–
___________
10111101
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 17/36
Somma prodotti parziali – circuito completo
Overflow: A e B su: N bit  P su: 2N bit
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 18/36
9
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. 2006/07
20
20
17
12
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
6
2
1
L 7 – 19/36
Sommario

Sommatori ad anticipazione di riporto

Addizionatori modulari

Moltiplicatori – approccio hardware

Moltiplicatori – approccio firmware
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 20/36
10
Approcci tecnologici alla ALU.

Approcci tecnologici alla costruzione di ALU:

Hardware

Ad ogni operazione corrisponde un circuito combinatorio specifico

ROM



Approccio esaustivo (tabellare).
Per ogni funzione, per ogni ingresso viene memorizzata l’uscita. Utilizzabile per
funzioni molto particolari (ad esempio di una variabile). Non molto utilizzato.
Firmware o microprogrammato


Si dispone di circuiti specifici solamente per alcune operazioni
elementari (tipicamente addizione e sottrazione).
Le operazioni più complesse vengono sintetizzate a partire
dall’algoritmo che le implementa
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 21/36
L’approccio firmware

La ALU contiene una unità di controllo e dei
registri

L’unità di controllo attiva opportunamente le unità
aritmetiche ed il trasferimento da e verso i registri.



Approccio “controllore-datapath”
Viene inserito un microcalcolatore dentro la ALU
FIRMWARE vs. HARDWARE:

Hardware: più veloce ma più costosa per numero di porte e
complessità dei circuiti

Firmware: risolve l’operazione complessa mediante una
sequenza di operazioni semplici.


A.A. 2006/07
La soluzione HW conviene per le operazioni frequenti
Meno veloce, ma più flessibile e, potenzialmente, adatta ad inserire
nuove procedure.
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 22/36
11
Presentazione seriale/parallela

Presentazione parallela

an
Tipico dell’approccio HW
b0
b1


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
sn
bn
a0 a1 …an
Presentazione seriale a gruppi

s0
s1
..
.
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
I bit vengono presentati a gruppi di k bit (es.
k=8: bytes)
ALU
s0 s 1…s n
b0 b1 …bn
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 23/36
Operazione di SHIFT (scalamento)
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
shift a sx d i 1
shift a d x d i 1
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 24/36
12
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. 2006/07
11011x
101=
_______________
11011+
00000–
11011––
_______________
10000111
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 25/36
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. 2006/07
11011x
111=
_______________
11111
11011+
110110
_______________
1
1010001+
1101100
_______________
10111101
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 26/36
13
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 27/36
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 28/36
14
Implementazione circuitale – modifica
A (moltiplicando) + shift a sx – 64 bit
1
ALU 64
add
P (prodotto) – 64 bit
A.A. 2006/07
B (moltiplicatore)
+ shift a dx – 32 bit
shift dx
shift sx
scrivi
Controllo
Ad ogni iterazione:
B ← shift_dx(B)
UC riceve sempre
LSB
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 29/36
Esempio
A,B: 4 bit – P: 8 bit
2x3=6
0010 x 0011 = 0110
0000 0100
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 30/36
15
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. 2006/07
shift
P2
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 31/36
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. 2006/07
scrivi
shift dx
Controllo
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 32/36
16
Implementazione ottimizzata
11011x
111=
_______________
11111
11011+
11011_______________
1
1010001+
11011- _______________
10111101
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 33/36
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 34/36
17
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. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 35/36
Esempio di esecuzione alg. ottimizzato
A, B: 4 bit – P: 8 bit
2x3=6
0010 x 0011 = 0000 0110
A.A. 2006/07
Copyright : A. Borghese, F. Pedersini – DSI, UniMI
L 7 – 36/36
18