Homework 2 For the MIPS assembly instructions

Homework 2
Q1 (25pts)
For the MIPS assembly instructions below, what is the corresponding C statement? Assume that
the variables f, g, h, i, and j are assigned to registers $s0, $s1, $s2, $s3, and $s4, respectively.
Assume further that the base addresses of the arrays A and B are in registers $s6 and $s7,
respectively (A and B both contain 32bit integers).
sll $t0, $s0, 2
add $t0, $s6, $t0
sll $t1, $s1, 2
add $t1, $s7, $t1
lw $s0, 0($t0)
addi $t2, $t0, 4
lw $t0, 0($t2)
add $t0, $t0, $s0
sw $t0, 0($t1)
Q2 (25pts)
When processor designers consider a possible improvement to the processor datapath, the
decision usually depends on the cost/performance tradeoffs. In the following problems, assume
that we are starting with a datapath from Figure below, where I-Mem, ALU, Regs, D-Mem, and
Control blocks have latencies of 400 ps, 120 ps, 200 ps, 350 ps, and 100 ps, respectively. Consider
the addition of a multiplier to the ALU. This addition will add 100 ps to the latency of the ALU. The
result will be 5% fewer instructions executed since we will no longer need to emulate the MUL
instruction in software.
i. What is the clock cycle time with and without this improvement? (10pts)
ii. What is the speedup achieved by adding this improvement? (15pts)
Q3 (25pts)
Your professor is contemplating changing the MIPS ISA to support 128 registers and twice as many
instructions as the ISA discussed in class. Such changes would clearly impact the instruction format.
Assuming that all instructions still have to fit into 32 bits, give an instruction format that will
accommodate these changes, indicating the fields and their size in bits, for R-type instructions, for
I-type instructions, and for jump and jump-register instructions. For your modified I-type
instructions what range of immediate can be represented? For your jump instruction what is the
impact on the jump distance? For your jump-register instruction, what is the impact on the jump
distance? What (in terms of our performance equation) would be your professor’s motivation in
making these changes?
Q4 (25pts)
Give the Control Flow Graph (CFG) for the following code fragment:
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(a[i]==b[j])
opt[i][j]=opt[i-1][j-1];
else{
if(opt[i-1][j]<opt[i][j-1])
opt[i][j]=opt[i-1][j]+1;
else
opt[i][j]=opt[i][j-1]+1;
}
}
}
return opt;