$30
1. (25 pts) Rename the following code segment (don’t forget to also show the
overwritten register) assuming the initial map table as shown. The free list starts with
p5 and has as many free registers in it as you need to complete the renaming (e.g.,
p5, p8, p9, p10, …). On your renamed code indicate (by drawing an arrow from the
W to the R) how many true data hazards still exist. After renaming, how many
instructions have no true data dependencies (and thus could be executed in parallel
with enough functional units)?
loop: lw $2, 40($6)
lw $3, 60($6)
add $4, $3, $2
sll $2, $2, 2
sw $4, 80($7)
sw $2, 40($6)
addi $6, $6, 4
addi $7, $7, 4
addi $1, $1, -1
bnez $1, loop
2. (25 pts) Given the following instruction sequences of three threads, how many
clock cycles will FGMT on a 4-way static superscalar datapath and SMT on a
4-way dynamic superscalar datapath use to complete execution?
Thread 1 Thread 2 Thread 3
[1.11] [1.12] [1.13] [2.11] [2.12] [3.11]
[1.21] [1.22] [1.23] [1.24] [2.21] [2.22] [2.23] [3.21] [3.22]
[1.31] [1.32] stall [3.31] [3.32] [3.33]
[1.41] [1.42] [2.31] [2.32] [2.33] [2.34] stall
[1.51] [1.52] [1.53] [2.41] [3.41] [3.42]
stall [2.51][2.52] stall
stall [2.61] [2.62] [3.61] [3.62] [3.63] [3.64]
[1.61] [1.62] stall [3.71] [3.72] [3.73]
stall [2.71] [3.81]
$1 p1
$2 p2
$3 p3
$4 p4
$6 p6
$7 p7
[1.71] [1.72]
3. (25 pts) How many cycles will it take to execute the code from the two threads
shown below, X and Y, on a single-issue, fine-grain multi-threaded 5-stage
pipelined MIPS datapath? How many issue slots are wasted due to hazards?
Thread X Thread Y
A1 – a load that takes 4
cycles to execute
B1 – takes 2 cycles to
execute
A2 – has a load-use
hazard with A1
B2 – conflicts for a
functional unit with B1
A3 – no dependencies B3 – depends on the
result of B2
A4 – depends on the
result of A3
B4 – depends on the
result of B3
4. (25 pts) Instruction bundle dependency checking has to be done in a static
superscalar datapath. How many load-use cross-checks have to be done for a 4-
way datapath? How many for a 8-way datapath? How many RAW intra-bundle
dependency checks have to be done for a 4-way datapath? How many for a 8-way
datapath? How many read and write ports does the RF have to have for a 4-way
datapath? How many for a 8-way datapath?