Progetto di una ALU
Progettare una ALU veloce
Quali sono le specifiche?
n
Deve supportare le operazioni Aritmetico/Logiche
di una macchina moderna
n
Deve essere garantito un efficiente compromesso
tra costi e velocità basato sulla frequenza di
occorrenza delle operazioni e sul budget
Tecniche di progetto
o
Divide et Impera
o
Riuso di componenti
Specifiche ALU MIPS (semplificata)
o
Add, AddU, Sub, SubU, AddI, AddIU
n
=> add/sub in complemento a 2 con
rilevamento dell’overflow
o
And, Or, AndI, OrI, Xor, Xori, Nor
n
=> AND e OR logiche, XOR, NOR
o
SLTI, SLTIU (set less than)
n
=> comparazione usata come condizione per i
Formato istruzioni aritmetiche
o
L’aritmetica con
segno genera
overflow, non riporti
R-type:
I-Type:
31
25
20
15
5
0
op
Rs
Rt
Rd
funct
op
Rs
Rt
Immed 16
Type op funct ADDI 10 xx ADDIU 11 xx SLTI 12 xx SLTIU 13 xx ANDI 14 xx ORI 15 xx XORI 16 xx LUI 17 xx Type op funct ADD 00 40 ADDU 00 41 SUB 00 42 SUBU 00 43 AND 00 44 OR 00 45 XOR 00 46 NOR 00 47 Type op funct 00 50 00 51 SLT 00 52 SLTU 00 53divide et impera
o
Suddividere il problema in problemi
più semplici, risolverli e mettere
assieme le soluzioni
o
Esempio: assumiamo che gli
immediati siano stati trattati prima
di arrivare alla ALU
00 add 01 addU 02 sub 03 subU 04 and 05 or 06 xor 07 nor 12 slt 13 sltU
ci siamo ridotti a 10
operazioni (4 bits)
Specifiche raffinate
(1) Specifiche Funzionali
inputs: 2 operandi da 32-bit
A
e
B
,
4-bit per
il controllo
outputs: risultato a 32-bit
S
,
1-bit riporto
,
1
bit overflow
operazioni: add, addu, sub, subu, and, or, xor,
nor, slt, sltU
ALU
A
B
m
ovf
S
32
32
32
4
c
(2)
Diagramma
a Blocchi
Decomponiamo in bit-slice
ALU0
a0 b0 cin cout s0ALU31
a31 b31 cin cout s31M
4
m mA
32
B
32
S
32
Qual è il nostro elemento base?
o
Logica
Combinatoria
7-a-2
M
4
ALU0
a0
b0
m
cin
co
s0
Function
Inputs
Outputs
M0 M1 M2 M3 A B Cin S Cout
add 0 0 0 0 0 0 0 0 0
0
Semi Addizionatore (Half Adder)
Ai 0 0 1 1 Bi 0 1 0 1 Sum 0 1 1 0 Carry 0 0 0 1 Ai Bi 0 1 0 1 0 1 1 0 Sum = Ai Bi + Ai Bi = Ai + Bi Ai Bi 0 1 0 1 0 0 1 0 Carry = Ai BiSchema realizzativo
Carry Sum A i B iFull Adder
+
A3 B3
S3
+
A2 B2
S2
+
A1 B1
S1
+
A0 B0
S0
C1
C2
C3
Cascaded Multi-bit
Adder
Come abbiamo visto, di solito siamo interessati ad addizionare
più di 2 bit
Ecco perché ci serve un full adder
Addizione Binaria
Full Adder
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
CI
0
1
0
1
0
1
0
1
S
0
1
1
0
1
0
0
1
CO
0
0
0
1
0
1
1
1
A B
CI
0
1
00 01 11 10
0
1
1
0
1
0
0
1
A B
CI
0
1
00 01 11 10
0
0
0
1
0
1
1
1
S
CO
S = CI xor A xor B
CO = B CI + A CI + A B = CI (A + B) + A B
Full Adder/Half Adder
Implementazione
Alternativa : 5 Gates
Half
Adder
A
B
Half
Adder
A + B
CI
A + B + CI
S S CO COA B
CI (A + B)
S
CO
A B + CI (A xor B) = A B + B CI + A CI
Approccio Standard : 6 Gates
+
A A A B B B CI CI S COTorniamo alla ALU
o
Trucco N. 2: prendiamo
pezzi noti e proviamo a
metterli assieme
o
Trucco N. 3: risolvere
parti del problema e
provare a estendere la
soluzione
A B CarryIn 1-bit Full Adder addand
or
M u x ResultS-select
E se usassimo un MUX ?
Come estendiamo a
tutte le operazioni
richieste?
Estensione a ulteriori operazioni
o
A - B = A + (– B)
n
formare il complemento a 2 invertendo e sommando 1
A B 1-bit Full Adder CarryOut M u x CarryIn Result add
and
or
S-select
invert
Operazioni addizionali: Schema modificato
o
LSB e MSB richiedono qualche piccolo
extra
A
B
M
S
32
32
32
4
Ovflw
ALU0
a0
b0
cin
co
s0
ALU31
a31 b31
cin
co
s31
Logica di
controllo
per
produrre
select,
comp,
?
Overflow
o
Esempi: 7 + 3 = 10 ma ...
o
- 4 - 5 = - 9 ma ...
Complemento a 2 Binario Decimale 0 0000 1 0001 2 0010 3 0011 0000 1111 1110 1101 Decimale 0 -1 -2 -3 4 0100 5 0101 6 0110 7 0111 1100 1011 1010 1001 -4 -5 -6 -7 1000 -8 0 1 1 1 0 0 1 1 + 1 0 1 0 1 1 1 0 0 1 0 1 1 + 0 1 1 1 1 1 0 7 3 1 – 6 – 4 – 5 7Rilevazione dell’Overflow
o
Overflow: il
risultatoè troppo grande (o troppo piccolo) per essere
rappresentato opportunamente
n
Esempio: - 8 < = numero binario a 4-bit <= 7
o
Se stiamo sommando operandi con segni differenti, l’overflow non
può accadere!
o
L’Overflow accade quando sommiamo:
n
2 positivi e la somma è negativa
n
2 numeri negativi e la somma è positiva
o
Esercizio
: Dimostrate che è possibile rilevare l’overflow quando
n
C’è riporto entrante nel MSB ° C’è riporto uscente dal MSB
0 1 1 1 0 0 1 1 + 1 1 0 7 3 1 1 1 0 0 1 0 1 1 + 1 –4 – 5 0
Logica Combinatoria per l
’
Overflow
o
Carry in MSB ° Carry out of MSB
n
Per una ALU a N-bit : Overflow = CarryIn[N - 1] XOR CarryOut[N - 1]
CarryOut3 A0 B0 1-bit ALU Result0 CarryIn0 CarryOut0 A1 B1 1-bit ALU Result1 CarryIn1 CarryOut1 A2 B2 1-bit ALU Result2 CarryIn2 A3 B3 1-bit ALU Result3 CarryIn3 Overflow X Y X XOR Y 0 0 0 0 1 1 1 0 1 1 1 0
Ancora sullo Schema Modificato
o
I bit LSB e MSB necessitano di qualche
Extra
A
B
M
S
32
32
32
4
Ovflw
ALU0
a0
b0
cin
co
s0
ALU0
a31 b31
cin
co
s31
Logica di
controllo per
produrre
select,
comp,
c-in
Aritm. con segno
and cin xor co
La nostra ALU
o
Dobbiamo fornire l’istruzione slt:
set-on-less-than
n
Attenzione: slt è una istruzione aritmetica
n
produce un 1 se rs < rt e uno 0 in caso contrario
n
usiamo la sottrazione: (a-b) < 0 implica a < b
o
Dobbiamo fornire l’istruzione un test di
eguaglianza (beq $t5, $t6, $t7)
Set a31 ALU0 Result0 CarryIn a0 Result1 a1 0 Result2 a2 0 Operation b31 b0 b1 b2 Result31 Binvert CarryIn Less CarryIn CarryOut ALU1 Less CarryIn CarryOut ALU2 Less CarryIn CarryOut ALU31 CarryIn
