ECE 4480/5480 Computer Architecture and Design
Spring 2012
Name: ______Solution______(print)
1. (10%) Using the single precision floating point representation to represent the following numbers
-0.21875
-0.21875 = - 7/32 = -7 x 2-5 = -111 x 2-5 = -1.11 x 2-3
S = 1 exponent = -3 + 127 = 124 = 01111100 in binary
significand = 11000000000000000000000 (23 bits)
1 01111100 11000000000000000000000
225
225 = 11100001 = 1.1100001 x 27
S= 0 exponent = 7 + 127 = 134 = 10000110
significand = 11000010000000000000000
0 10000110 11000010000000000000000
2. (10%)
Multiplexers can be used to fix design errors. Now you need to implement a function f = abc' + a'd' provided that all you have are 2-input multiplexers.
3. (10%) Using the restoring division algorithm, show step by step operations of dividing 00000111 by 0011. Also show the register contents at each iteration.
iteration step divisor remainder
0011 0000 0111 initial
0 1 0011 0000 1110 shift left 1 bit
1 2 0011 1101 1110 rem = rem – div
3b 0011 0001 1100 rem <0, restore & slr, r0=0
2 2 0011 1110 1100 rem = rem – div
3b 0011 0011 1000 rem<0, restor & slr, r0 = 0
3 2 0011 0000 1000 rem = rem – div
3a 0011 0001 0001 rem > 0, slr, r0=1
4 2 0011 1110 0001 rem-rem – div
3b 0011 0010 0010 rem <0, restore & slr, r0=0
correction step: 0001 0010 shift left half of the remainder
right 1 bit
4. (10%) Using the Booth algorithm, show step by step operation of multiplying 110101 by 011100. Also need to show the register contents at each iteration.
multiplier = 011100 multiplicand = 110101
Iteration step product
0 initial value 000000 011100 0
1 1a 00=>nop 000000 011100 0
2. shift right 000000 001110 0
2 1a 00=>nop 000000 001110 0
2. shift right 000000 000111 0
3 1c. 10=>prod=prod-mcnd 001011 000111 0
2 shift right 000101 100011 1
4. 1d. 11=> nop 000101 100011 1
2. shift right 000010 110001 1
5. 1d 11=>nop 000010 110001 1
2. shift right 000001 011000 1
6. 1b. 01=>prod=prod+mcnd 110110 011000 1
2. shift right 111011 001100 0
5. (20%) The following two figures show the state diagram and the control logic implementation
Now we like to add another instruction jal
(1) Modify the following state diagram to include the instruction jal and list the control signals used by
jal instruction
The existing datapath is insufficient.
We need to expand the two multiplexors controlled by RegDst and MemtoReg.
The execution steps would be:
state0: Instruction fetch (unchanged)
state1: Instruction decode and register fetch (unchanged)
state10: jal: Reg[31] = PC; PC = PC[31:28] || (IR[25:0] <2);
add state10 into the above state diagram.
Here we are writing PC into Reg[31] after it has been incremented by 4.
The existing datapath
requires that PC be an input to the MemtoReg multiplexor and
31 needs to be an input to the RegDst multiplexor.
MemtoReg multiplexor is modified to have 3 inputs and 2 selection signals
ReqDst multiplexor is modified to have 3 inputs and 2 selection signals
Control signals asserted at state 10:
PCwrite
PCSource = 10
MemtoReg = 10 to select PC+4 as input.
RegDst = 10 to select 31 as the Destination Register.
(2) Derive the logic equation for NS2 after including the new instruction jal.
The following next state will have NS2 = 1
next state 4 = state 3 =S3’ S2’ S1 S0
next state 5 = (state 2) · (Op = ‘SW’) = S3’ S2’ S1 S0’ Op5 Op4’ Op3 Op2’ Op1 Op0
next state 6 = (state 1) · (Op = R_type) = S3’ S2’ S1’ S0 Op5’ Op4’ Op3’ Op2’ Op1’ Op0’
next state 7 = state 6 = S3’ S2 S1 S0’
NS2 = S3’ S2’ S1 S0 + S3’ S2’ S1 S0’ Op5 Op4’ Op3 Op2’ Op1 Op0 +
S3’ S2’ S1’ S0 Op5’ Op4’ Op3’ Op2’ Op1’ Op0’ + S3’ S2 S1 S0’
6. (20%) Consider executing the following code on the pipelined datapath with forwarding unit and hazard detection unit.
lw $4, 100($2)
sub $6, $4, $3
add $2, $4, $6
How many cycles will it take to execute this code?
CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8
lw $4, 100($2) F D E M W
sub $6, $4, $3 F D S E M W
add $2, $4, $6 F S D E M W
total 8 clock cycles
Illustrates the dependencies that need to be resolved and propose a way to resolve this data dependency
forward the memory contents addressed by 100 + $2
to the Execution stage for instruction sub
A stall is needed between D and E of the instruction sub.
The instruction after the sub is also stalled.
7. (20%) Can the hazard in the MIPS code shown below be handled by forwarding on the five stage MIPS pipeline discussed in class?
lw $2, 400($3)
sw $2, 800($4)
If so, add the additional forwarding logic to datapath on the next page (the Forward Unit shown
is to handle the data hazard discussed in class). If not, add the hazard logic to the MIPS
pipelined datapath and state how many stalls cycles are incurred.
Yes, need to add forwarding path.
For loads immediately followed by stores (memory-to-memory copies) can avoid
a stall by adding forwarding hardware from the MEM/WB pipeline register
to the data memory input.
Need to add a Forward Unit and a mux to the memory access stage