A Simple Multi-Function Logic Unit

• build a logic unit to support the and and or

instructions for MIPS (32-bit registers)
– 1-bit unit and use 32 of them
operation
selector

a
output
b

• Possible implementation using a multiplexor :

Implementation with a Multiplexor

• Selects one of the inputs to be the output

based on a control input

Operation
.
.
.
a
0
Result
1
b

• build ALU using a MUX (multiplexor):

 Implementations
• Not easy to decide the best way to implement something
– do not want too many inputs to a single gate
– do not want to have to go through too many gates (= levels)

• Let's look at a 1-bit ALU for addition:

CarryIn

cout = a.b + a.cin + b.cin

a

Sum sum = a.b.cin + a.b.cin +

b
a.b.cin + a.b.cin
= a  b  cin
CarryOut exclusive or (xor)

• How could we build a 1-bit ALU for add, and, and or?
• How could we build a 32-bit ALU?
 1-bit Adder Logic

xor

Half-adder with one xor gate

Full-adder from 2 half-adders and

an or gate

Half-adder with the xor gate replaced

by primitive gates using the equation
AB = A.B +A.B
 Building a 32-bit ALU

Multiplexor control line

Operation
CarryIn

a
0

1
Result

2
b

CarryOut
1-bit ALU for AND, OR and add
 Building a 32-bit ALU
CarryIn Operation

a0 CarryIn
Multiplexor control line Result0
Operation ALU0
b0
CarryIn CarryOut

a
0 a1 CarryIn
Result1
ALU1
b1
1 CarryOut
Result

2 a2 CarryIn
b Result2
ALU2
b2
CarryOut

CarryOut
1-bit ALU for AND, OR and add

a31 CarryIn
Result31
ALU31
b31

Ripple-Carry Logic for 32-bit ALU

What about Subtraction (a – b) ?
• Two's complement approach: just negate b and add.
invert each bit of b and set Carry In to least significant
bit (ALU0) to 1
Binvert Operation
CarryIn

a
0

1
Result

b 0 2

CarryOut
 Tailoring the ALU to MIPS:
Test for Less-than and Equality
• Need to support the set-on-less-than instruction
– e.g., slt $t0, $t3, $t4
– slt is an R-type instruction that produces 1 if rs <
rt and 0 otherwise
– use subtraction: rs < rt  rs – rt < 0. Recall msb
of negative number is 1
 Tailoring the ALU to MIPS:
Test for Less-than and Equality
– two cases after subtraction rs – rt:
• if no overflow then rs < rt  most significant bit of rs – rt = 1
• if overflow then rs < rt  most significant bit of rs – rt = 0

– e.g., 5ten – 6ten = 0101 – 0110 = 0101 + 1010 = 1111 (ok!)

-7ten – 6ten = 1001 – 0110 = 1001 + 1010 = 0011 (overflow!)
– therefore
set bit = msb of rs – rt  overflow bit
where set bit, which is output from ALU31, gives the result of slt

– set bit is sent from ALU31 to ALU0 as the Less bit at ALU0; all other
Less bits are hardwired 0; so Less is the 32-bit result of slt
 B inv e rt O p era tion
C arryIn

a
0

R esult
b 0 2

1
Less input of
L ess 3 the 31 most
significant ALUs
is always 0
a. C arryO u t
1- bit ALU for the 31 least significant bits
Extra set bit, to be routed to the Less input of the least significant 1-bit
ALU, is computed from the most significant Result bit and the Overflow bit

Bin ve rt Op eration
C arryIn

a
0

R esu lt
b 0 2

Le ss 3

Set

Ov erflo w
O ve rflow
de tection
b.

1-bit ALU for the most significant bit

 B inv e rt O p era tion
C arryIn

a
0 Binvert CarryIn Operation

R esult a0 CarryIn
b 0 2 b0 ALU0 Result0
Less
1
CarryOut
Less input of
L ess 3 the 31 most
significant ALUs
is always 0
a1 CarryIn
a. C arryO u t
b1 ALU1 Result1
1- bit ALU for the 31 least significant bits 0 Less
Extra set bit, to be routed to the Less input of the least significant 1-bit CarryOut
ALU, is computed from the most significant Result bit and the Overflow bit

Bin ve rt Op eration
a2 CarryIn
C arryIn
b2 ALU2 Result2
0 Less
a CarryOut
0

R esu lt CarryIn
b 0 2

1
a31 CarryIn Result31
Le ss 3 b31 ALU31 Set
0 Less Overflow
Set

Ov erflo w
O ve rflow
de tection
b.
32-bit ALU from 31 copies of ALU at top left and 1 copy
1-bit ALU for the most significant bit of ALU at bottom left in the most significant position
 Shift-add Multiplier
Start

Product0 = 1 1. Test Product0 = 0

Product0

Multiplicand

32 bits 1a. Add multiplicand to the left half of

the product and place the result in
the left half of the Product register

32-bit ALU

Shift right Control 2. Shift the Product register right 1 bit

Product
Write test
64 bits

No: < 32 repetitions

32nd repetition?
Product register is initialized with multiplier on right

No separate multiplier register; multiplier Yes: 32 repetitions

placed on right side of 64-bit product register

Done Algorithm
 Implementing MIPS
• Implementation of the MIPS instruction set
• Simplified to contain only
– arithmetic-logic instructions: add, sub, and, or, slt
– memory-reference instructions: lw, sw
– control-flow instructions: beq, j

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

op rs rt rd shamt funct R-Format

6 bits 5 bits 5 bits 16 bits

op rs rt offset I-Format
6 bits 26 bits

op address J-Format
 Implementing MIPS: the
Fetch/Execute Cycle
• High-level abstract view of fetch/execute implementation
– use the program counter (PC) to read instruction address
– fetch the instruction from memory and increment PC
– use fields of the instruction to select registers to read
– execute depending on the instruction
– repeat…

Data

Register #
PC Address Instruction Registers ALU Address
Instruction Register #
memory Data
Register # memory

Data
 Ex: State Elements on the Datapath:
Register File
• Port implementation:
Clock
Clock

Write

Read register C
number 1 0
Register 0
Register 0 1 D
Register 1 M n-to-1 C
Register number
u Read data 1 decoder Register 1
Register n – 1 x D
n– 1
Register n n
Read register
number 2
C
Register n – 1
M D
u Read data 2 C
x Register n
Register data D

Read ports are implemented Write port is implemented using

with a pair of multiplexors a decoder – 5-to-32 decoder for
for 32 registers 32 registers. Clock is relevant to
write as register state may change
only at clock edge