L_06 - Home - Università degli Studi di Milano

I sommatori
Prof. Alberto Borghese
Dipartimento di Scienze dell’Informazione
[email protected]
Università degli Studi di Milano
Riferimenti: Appendice B5 prima parte.
A.A. 2014-2015
1/30
http:\\borghese.di.unimi.it\
Sommario
Addizionatori
Addizionatori ad anticipazione di riporto
A.A. 2014-2015
2/30
http:\\borghese.di.unimi.it\
1
Somma e prodotto logico
Somma => OR
ABY
0 0 0
0 1 1
1 0 1
1 1 1
A
Y
B
ABY
A
0 0 0
Moltiplicazione
0 1 0
=> AND
Y
B
1 0 0
1 1 1
3/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
AND e OR su più bit
1
0
0
1
1
1
0
1
0
1
=
1
A.A. 2014-2015
0
0
1
0
0
0
1
OR
AND
1
0
=
10
10
1
4/30
1
http:\\borghese.di.unimi.it\
2
Operazione di somma
Riporto
111
1011 +
110 =
------10001
Addendo 1
Addendo 2
3 Attori: addendo 1, addendo 2, riporto.
Viene eseguita sequenzialmente da dx a sx.
5/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
(Half) Adder ad 1 bit
a b
Tabella della verità della somma:
ab
00
01
10
11
somma
0
1
1
0
s=a⊕b
r = ab
riporto
0
0
0
1
HA
r
s
s
a
b
r
La somma è diventata un’operazione logica!
Cammini critici:
Somma = 1;
Riporto = 1;
A.A. 2014-2015
6/30
Complessità
Somma = 1 porta;
Riporto = 1 porta;
http:\\borghese.di.unimi.it\
3
Full Adder ad 1 bit
Tabella della verità della somma completa:
s = m1 + m2 + m4 + m7
r = m3 + m5 + m6 + m7
ab
00
01
10
11
00
01
10
11
rin somma riporto
0
0
0
0
1
0
_ _
__ __
0
1
0
s = a b rin + a b rin + a b rin + a b rin =
0
0
1
_
__
1
1
0
= (a ⊕ b) rin + (ab + ab) rin =
1
0
1
rin a b
_
______
1
0
1
= (a ⊕ b) rin + (a ⊕ b) rin
1 _1 _
1 _
rout= a b rin + a b rin + a b rin + a b rin = ab + (a ⊕ b) rin
FA
rout= a rin + (a ⊕ rin) b
rout
s
Quale è meglio?
7/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Implementazione circuitale
_
_____
s = (a ⊕ b) rin + (a ⊕ b) rin
rout= ab + (a ⊕ b) rin
rin
rin
(a ⊕ b)
ab
a
rout
(a ⊕ b)
!rin
b
!(a ⊕ b)
s
rin
7 porte logiche.
Cammini critici: s -> 3; rout -> 3
A.A. 2014-2015
8/30
http:\\borghese.di.unimi.it\
4
Semplificazione circuitale
s = (a ⊕ b )rin + (a ⊕ b )rin = (a ⊕ b ) ⊕ rin
rout = ab + (a ⊕ b )rin
6 porte logiche.
Cammini critici: s –> 2; rout -> 3
a
s
b
rin
rin
a
rout
b
9/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Semplificazione ulteriore
s = (a ⊕ b )rin + (a ⊕ b )rin = (a ⊕ b ) ⊕ rin
rout = ab + (a ⊕ b )rin
5 porte logiche.
Cammini critici: s –> 2; rout -> 3
a
b
rout
rin
a
b
A.A. 2014-2015
s
ri-2out
rin
10/30
http:\\borghese.di.unimi.it\
5
Implementazione mediante PLA
ab
00
01
10
11
00
01
10
11
rin somma
0
0
0
1
0
1
0
0
1
1
1
0
1
0
1
1
rout
0
0
0
1
0
1
1
1
rin a
b
·
·
·
·
··
· ·
·· · · · ·
·· ·
·· ·· · ·
· · ·
· · ·
AND
SOP: costruisco i
mintermini e li sommo.
A.A. 2014-2015
OR
11/30
rout s
http:\\borghese.di.unimi.it\
Complessità circuitale
• Definire la complessità circuitale e il cammino critico di HA:
– s = m1 + m2
– r = m3
• Definire la complessità circuitale e il cammino critico di FA:
– s = m1 + m2 + m4 + m7
– r = m3 + m5 + m6 + m7
Traccia: m1 è un circuito con 3 ingressi ed un’uscita e si può spezzare in
due parte AND in cascata.
A.A. 2014-2015
12/30
http:\\borghese.di.unimi.it\
6
Esercizi con ROM e PLA
Implementare il circuito del Full Adder mediante ROM
Scrivere il circuito che esegue la somma di: 3 + 4 in base 2.
Riportare tutte le uscite delle porte logiche.
Scrivere il circuito che esegue la seguente sottrazione: 5-2 in base
2. Riportare tutte le uscite delle porte logiche.
A.A. 2014-2015
13/30
http:\\borghese.di.unimi.it\
Sommario
Addizionatori
Addizionatori ad anticipazione di riporto
A.A. 2014-2015
14/30
http:\\borghese.di.unimi.it\
7
. ..
.
ai-1
bi-1
Circuito della somma
ri-2out
Stadio i-1
rini-1
ai-1
si-1
bi-1
ai
riin = ri-1out
ai
bi
routi-1=rini
Stadio i
.. .
.
si-i
Il riporto r
è una variabile
Interna.
Viene
propagato.
E’ l’elemento
critico
del sommatore.
si
bi
routi
r out
si
i
http:\\borghese.di.unimi.it\
15/30
A.A. 2014-2015
Cammini critici
ai-1
bi-1
. ..
.
ri-2out
Cammino critico
Per ogni stadio:
Somma: 2
Riporto: 3
Per due stadi:
Somma: 2
Riporto: 3 + 3 = 6
riin = ri-1out
ai
bi
Riporto = 3 * N
111
1011 +
110 =
------10001
.. .
.
si-i
Funzionamento
sequenziale
si
A.A. 2014-2015
16/30
riout
http:\\borghese.di.unimi.it\
8
I problemi del full-adder
Il full adder con propagazione del riporto è lento:
• Il riporto si propaga sequenzialmente
caratteristica dell’algoritmo di calcolo
• la commutazione dei circuiti non è istantanea (tempo di
commutazione)
caratteristica fisica dei dispositvi
• Soluzioni
modificare l’algortimo
modificare i dispositivi
17/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Prima possibilità: forma tabellare
Riscrivo le equazioni del riporto in modo non sequenziale. Come?
rout = f( a0, b0, a1, b1, a2, b2, a3, b3,....)
Scrivo la tabella della verità dove in uscita ho gli N riporti ed
In ingresso 2 * N valori (gli N bit dei 2 addendi).
La tabella della verità ha 22N righe (per N=32, …)
A.A. 2014-2015
18/30
http:\\borghese.di.unimi.it\
9
Carry look-ahead (anticipazione di riporto)
Approccio strutturato per diminuire la latenza della somma.
rout= ab + (a ⊕ b) rin
rin a b
Analisi del singolo stadio.
Quando si genera un riporto in uscita?
FA
rout
Quando ho almeno due 1, in ingresso;
cioè tra rin, a e b.
A.A. 2014-2015
s
11000 riporto
1101 +
100 =
-------10001
19/30
http:\\borghese.di.unimi.it\
Propagazione e generazione
Ho riporto quando ho almeno due 1, in ingresso; cioè tra rin, a e b.
rin a b
FA
Osservazioni:
1)
Viene generato un riporto dallo stadio i, qualsiasi sia il
riporto in ingresso se a = b = 1 => gi = aibi.
2)
Viene generato un riporto allo stadio i, se il riporto in
ingresso è = 1 ed una delle due variabili in ingresso è = 1
=>se pi = (ai ⊕ bi) => viene generato riporto se pi riin = 1 (pi
propaga il segnale di riporto riin).
rout
s
Quando sia la condizione 1) che la condizione 2) è verificata?
Cosa succede se entrambe le condizioni sono verificate?
A.A. 2014-2015
20/30
http:\\borghese.di.unimi.it\
10
Esempio
Sono interessato ad r4out. Supponiamo r0in = 0.
rin 0 0 0 0 0 0 0
a 10101101+
b
10000=
----------------10111111
0111000
10101101+
11010=
----------------11100111
r5in =r4out = 0
r5in = r4out = 1
Per propagazione
p4 = (a4 ⊕ b4)r4in.
0111000
10111101+
11000=
----------------11010101
r5in = r4out = 1
Per generazione
g4 = a4b4
21/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Sviluppo della funzione logica riporto
riout= ab + (a ⊕ b) riin
riout= gi + pi riin
rout0 = g0 + p0rin0
rout1 = g1 + p1rin1 = g1 + p1g0 + p1p0rin0
rin0 rout1
rout1
110
111
1001 +
1001 +
11 =
10 =
------------1100
1100
A.A. 2014-2015
g0 = 0
p0 = p1 = 1
g0 = 1
p1 = 1
22/30
rout1
1 0
1010 +
11 =
------1100
g1 = 1
http:\\borghese.di.unimi.it\
11
Sviluppo della funzione logica riporto
riout= ab + (a ⊕ b) riin
riout= gi + pi riin
r0 = g0 + p0r0
r1 = g1 + p1r0 = g1 + p1g0 + p1p0r0
r2 = g2 + p2r1 = g2 + p2(g1 + p1g0 + p1p0r0) = g2 + p2g1 + p2p1g0 +
p2p1p0r0.
r3 = g3 + p3r2 = g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0) =
g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0r0.
23/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Determinazione del cammino critico.
r3 = g3 + p3r2 = g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0) =
g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0r0.
r0
a3
b3
a2
b2
a1
b1
a0
b0
a0
b0
a1
b1
a2
b2
a3
b3
p3
p2
·
·
p1
p0
g0
p3p2p1p0r0
p3p2
·
r3
p1p0
p1g0
·
p3p2p1g0
+g1p3p2
g1
g2
g3+g2p3
g3
Cammino critico = 6, senza anticipazione sarebbe 3 * 4 = 12
A.A. 2014-2015
24/30
http:\\borghese.di.unimi.it\
12
Quanto si guadagna con l’anticipazione del
riporto?
Cammino critico per le variabili interne:
r2out => 5
r1out => 4
r0out => 3
Cammino critico per le variabili esterne:
r3out => 6
s3 => 6 NB la prima porta XOR è in comune con r2out
s2 => 5 NB la prima porta XOR è in comune con r1out
s2 => 4 NB la prima porta XOR è in comune con r0out
s0 => 2
Cammino critico => log2(N)
25/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Determinazione la complessità.
r3 = g3 + p3r2 = g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0) =
g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0r0.
r0
a0
b0
a1
b1
a2
b2
a3
b3
a0
b0
a1
b1
a2
b2
a3
b3
p0
p1
p2
p3
g0
·
·
p1p0r0
p0p1
·
·
p3p2p1p0r0
r3
p2p3
p1g0
··
p3p2p1g0
+g1p3p2
g1
g2
g3+g2p3
g3
Complessità di r3 = 20 porte logiche
A.A. 2014-2015
26/30
http:\\borghese.di.unimi.it\
13
Complessità
s0 = (a ⊕ b) ⊕r0 = g0 ⊕r0
s1 = g1 ⊕ r1 = g1⊕ (p0 r0+ g0)
s2 = g2 ⊕ r2 = g2⊕ (p1 p0 r0+ p1 g0 + g1)
s3 = g3 ⊕ r3 = g3⊕ (p2 p1 p0 r0+ p2 p1 g0+ p2 g1 + g2)
Vengono richieste molte più porte a 2 ingressi. Quante?
La complessità aumenta.
Aumenta il cammino critico?
r3 = g3 + p3r2 = g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0r0) =
g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0r0.
27/30
A.A. 2014-2015
http:\\borghese.di.unimi.it\
Addizionatori modulari
rin
La complessità del circuito è
tollerata per piccoli n.
Circuiti sommatori indipendenti si
hanno per 4 bit.
Moduli elementari.
a0
b0
a1
b1
a2
b2
a3
b3
s0
s1
s2
s3
rout
Come si ottiene la somma?
Collegando in cascata i moduli (sommatori elementari).
Cammino critico = 6 * N/4. Per 32 bit, 48.
Per confronto, senza parallelizzazione, per 32 bit, N * 3 = 96.
A.A. 2014-2015
28/30
http:\\borghese.di.unimi.it\
14
Addizionatori modulari::esempio
Occorre sommare 2 variabili, A e B, su N = 32 bit
Ho a disposizione due sommatori su 16 bit.
Come si ottiene la somma?
16
16
16
rin
1
A16… A31
B0… B15
A0… A15
Sommatore su 16 bit
rout = rin
A.A. 2014-2015
16
rout
Sommatore su 16 bit
1
1
1
16
B16… B31
16
S0… S15
29/30
S16… S31
http:\\borghese.di.unimi.it\
Sommario
Addizionatori
Addizionatori ad anticipazione di riporto
A.A. 2014-2015
30/30
http:\\borghese.di.unimi.it\
15

Download Report