Description
Exercise 1. [16 marks]
For each of the following MIPS assembly instructions, give the
instruction format, the decimal value of each bit field for that instruction format, and the
32-bit instruction word encoding that instruction written as a single hexadecimal number.
• add $v1, $a2, $t8
• lb $s2, 37($t7)
• bne $v0, $t4, 732
• sra $s4, $s6, 11
Exercise 2. [10 marks]
(a) Consider the following MIPS assembly code fragment. What is the correct value of L2
to be used in the beq instruction? Assume the lw instruction labelled by L1 is located at
address 0x89aa1b. Show your workings.
L1 :
lw $t0 , 0 ( $a0 )
lw $t1 , 4 ( $a0 )
lw $t2 , 0 ( $a1 )
lw $t3 , 4 ( $a1 )
s l t $t4 , $t0 , $ t2
s l t $t5 , $t1 , $ t3
and $t4 , $t4 , $ t5
beq $t4 , $0 , L2
sub $t3 , $t3 , $ t2
j L3
L2 :
sub $t3 , $t2 , $ t3
L3 :
sw $t3 , 0 ( $a0 )
j r $ ra
(b) Assume that, for a particular clock cycle in a single-cycle MIPS datapath, the program
counter is 0x1258AB91 and the fetched instruction word is 0x089F01A7. What is the value of
the program counter on the next clock cycle? Write you answer in hexadecimal. Show your
workings.
2
Exercise 3. [20 marks]
Consider the following MIPS assembly code fragment. The sort
function implements bubble sort using a helper function swap.
Assume there are no syntax errors. But, there are 10 bugs in this code with respect to the
semantics of MIPS and runtime bugs. That is, there are exactly 10 lines of code that either
need to be modified or added to get this code working correctly.
• If an instruction needs to be modified, state the instruction as is and then state what
it should be modified to be.
• If an instruction needs to be added, state before which instruction it should be added
and the instruction to add.
3
1 # swap k and k +1 of an array where a0 is array addreess and a1 is k
2 swap :
3 add $t0 , $v1 , $zero # t0 = k
4 add $t0 , $v0 , $t0 # t0 = v [ k ]
5 lw $t1 , 0( $t0 ) # load v [ k ]
6 lw $s1 , 4( $t0 ) # load v [ k +1]
7 sw $s1 , 0( $t0 ) # v [ k ] = v [ k +1]
8 sw $t1 , 4( $t0 ) # v [ k +1] = v [ k ]
9 jr $ra
10
11 # Bubble sort an array of ints with address a0 and length a1
12 sort :
13 addi $sp , $sp , 16 # make room for ints on stack
14 sw $s3 , 12( $sp )
15 sw $s2 , 8( $sp )
16 sw $s1 , 4( $sp )
17 sw $s0 , 0( $sp )
18 add $s2 , $a0 , $zero # s2 = a0 ( address of v array )
19 add $s3 , $a1 , $zero # s3 = a1 ( length of v array )
20 add $s0 , $zero , $zero # s0 = i = 0
21 for1tst :
22 slt $t0 , $s0 , $s3 # t0 = ( s0 < s3 )
23 beq $t0 , $zero , exit1
24 addi $s1 , $s0 , -1 # s1 = j = i-1
25 for2tst :
26 slti $t0 , $s1 , 0 # t0 = ( s1 < 0)
27 bne $t0 , $zero , exit2 # go to exit2 if ( s1 < 0)
28 sll $t1 , $s1 , 2 # t1 = j * 4
29 add $t2 , $s2 , $t1 # t2 = v + ( j *4)
30 lw $t3 , 0( $t2 ) # t3 = v [ j ]
31 lw $t4 , 4( $t2 ) # t4 = v [ j +1]
32 slt $t0 , $t4 , $t3 # t3 = v [ j +1] < v [ j ]
33 beq $t0 , $zero , exit2 # go to exit2 if v [ j +1] >= v [ j ]
34 add $v0 , $s2 , $zero # set args for swap proc
35 add $v1 , $s1 , $zero
36 j swap # call swap
37 addi $s1 , $s1 , -1 # decrement j
38 j for2tst # iterate inner loop
39 exit2 :
40 addi $s0 , $s0 , 1 # increment i
41 j for1tst # iterate outer loop
42 exit1 :
43 lw $s0 , 0( $sp )
44 lw $s1 , 4( $sp )
45 lw $s2 , 8( $sp )
46 lw $s3 , 12( $sp )
47 addi $sp , $sp , -16
48 jr $ra
4
Exercise 4. [14 marks]
Consider the above circuit, and assume the following timings for its constituent pieces.
• Transfer along wires is instantaneous.
• NOT operations are instantaneous (the small circle before the top-right MUX).
• Propagation delay of AND gate: 20ns
• Propagation delay of XOR gate: 45ns
• Propagation delay of MUX: 120ns
(a) Assume the values of A1, A2, A3, B1, B2, B3 all change to new values at time 𝑡 = 0.
For each of C1, C2, C3, C4, C5, C6, determine the time at which its new value becomes
available. That is, determine each output’s critical path.
(b) What is the propagation delay of this circuit as a whole?
5
Exercise 5. [20 Marks]
Consider the single-cycle MIPS datapath with control signals
as presented in Figure 1. We want to add a new instruction to the MIPS instruction set
architecture: foo. Its specification is as follows:
MIPS assembly RTL
foo $rt $rs IMM Mem[Reg[$rs]] ← Reg[$rt]
Reg[$rt] ← Mem[Reg[$rs] + Reg[$rt]]
Reg[$rs] ← Reg[$rs] + IMM
PC ← PC + 4
*Note that this is the normal “PC + 4” as for any non-branch, non-jump instruction.
Your task is to modify the MIPS datapath so that it can fulfill this new instruction foo. To
do that, you should:
(i) add new wires, ports, circuitry, MUX, control signals, etc. to the datapath so that it
can execute the new instruction foo (see, e.g., Slides 16-23 in L11-CPUControl);
(ii) ensure that any newly added circuitry and control signals do not hinder the execution
of any existing operations in the MIPS ISA (i.e. your modified datapath should still
be able to successfully execute all the preexisting instructions in the MIPS ISA).
Assume that IMM is a signed integer. Assume that memory is fast enough to read and write
within one clock cycle, and that the read from memory occurs before the write to memory.
To structure your solution to this exercise, perform the following:
(a) Modify (using Photoshop, Gimp, OneNote, etc.) the MIPS datapath (supplied as
MIPSDatapath.png) with new circuits and control signals so that it can perform the foo
instruction. That is, simply draw your new circuits and wires on top of the original image.
Add your modifications in a colour other than black so they are clearly distinguishable from
the original data path. Ensure you include bit-widths and labels.
(b) Give a brief English description of the modifications you have made. Explain how data
flows through the modified datapath when the foo instruction is being executed. Explain how
data flows through the modified datapath when any instruction besides foo is being executed.
(c) Give the values of the control signals required to execute your instruction. That is, when
executing the foo instruction, give the values of the 8 preexisting control signals as well as
the values of any new control signals you have added.
(d) If you have added any new control signals, give the values of these control signals when
any instruction besides foo is being executed.
6
Figure 1: MIPS datapath with control signals
7
Exercise 6.
Consider the following 8-stage datapath and the timings for each stage.
Stage IM1 IM2 DEC REG SHFT ALU DM1 DM2
Time 115ps 225ps 175ps 200ps 150ps 425ps 200ps 225ps
(a) [2 marks] Using single-cycle clocking for this datapath what is the minimum clock cycle
possible for this datapath?
(b) [2 marks] If this datapath were to be pipelined, what is the minimum clock cycle which
would be possible?
(c) [6 marks] Assume this datapath was pipelined. What is the ideal speedup? Assuming
no data dependencies or pipeline hazards, what is the actual speedup obtained when executing 300 instructions? Round your answers to 3 decimal places. As always, show your
workings.
(d) [10 marks] Let us assume this datapath is not pipelined but still follows a multi-cycle
clocking method. Let us further assume that the datapath has an additional optimization in
which instructions skip stages that are unused for that instruction. Consider the following
set of instructions to be executed on this datapath along with the stages which are used by
that instruction.
add: IM1, DEC, REG, ALU, DM2
sll: IM1, REG, SHFT, DM2
sw: IM2, DEC, REG, ALU, DM1
lw: IM1, IM2, DEC, REG, ALU, DM1, DM2
beq: IM1, IM2, REG
𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝐶𝑜𝑢𝑛𝑡
add 1500
sll 250
sw 500
lw 400
beq 350
Table 1: Program Instructions
Consider also a program composed of instructions as detailed in Table 1. If this program
was to be executed on this datapath, determine: (𝑖) the ideal CPI of this program, and (𝑖𝑖)
the total execution time of this program. Assume that there are no dependencies or hazards
between instructions. Assume there are no memory stalls.
8
