CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
Exam Instructions
1. You must follow all the MIPS procedure call conventions.
2. You are allowed to use SPIM pseudo instructions.
3. You must show all steps of your work for full credit.
4. You are allowed to use a non-communicating calculator. You cannot use your phone, tablet, or laptop as a calculator. You cannot borrow a calculator from your colleagues.
5. You are allowed to have the reference sheet containing the summary of the MIPS instructions from the front of the textbook or an unchanged copy of that reference sheet (e.g., a printout of the version that I made available on the class Google Drive).
6. You are allowed one regular-size sheet of paper (front and back) on which you can write anything that you wish, as long as it is hand-written (i.e., not typed) by you (i.e., not by somebody else or a photocopy). You are not allowed to use any mechanical or electronic method of reproduction to create this sheet.
Solution
Question
Points
Score
Question 1
30
Question 2
65
Total:
95
1/6
CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
Question 1: (30 points)
Figure 1 shows an unoptimized implementation for a simple while loop, and Figure 2 shows a slightly optimized version of the same loop. Given both implementations and the information in Table 1, answer the following questions:
Figure 1: The unoptimized MIPS implementation of a simple while loop.
0x3FFF FFE8
0x3FFF FFEC
0x3FFF FFF0
0x3FFF FFF4
0x3FFF FFF8
0x3FFF FFFC
0x4000 0000
Loop:
Exit:
sll $t1, $s3, 2
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
add $s3, $s3, $s4
j Loop
#$t1 ← i*4
# $t1 ← Addr(save[i])
# $t0 ← save[i]
# if save[i] ≠ k goto Exit #i←i+j
# goto Loop
0x6000 0000
0x6000 0004
0x6000 0008
0x6000 000C
0x6000 0010
0x6000 0014
0x6000 0018
0x6000 001C
0x6000 0020
0x6000 0024
Loop_opt:
Exit_opt:
sll $t1, $s3, 2
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit_opt
add $s3, $s3, $s4
sll $t1, $s3, 2
add $t1, $t1, $s6
lw $t0, 0($t1)
beq $t0, $s5, Loop_opt
#$t1 ← i*4
# $t1 ← Addr(save[i])
# $t0 ← save[i]
# if save[i] ≠ k goto Exit #i←i+j
#$t1 ← i*4
# $t1 ← Addr(save[i])
# $t0 ← save[i]
# if save[i] ≠ k goto Exit
Figure 2: The optimized MIPS implementation of a simple while loop.
Instruction
Cycles Per Instruction
1 1
Table 1: Instruction information.
sll
add j2 bne 3 beq 3 lw 5
2/6
CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
a. (10 points) Given the same number of loop iterations n, how many cycles are re- quired to execute the code in each of Figure 1 and Figure 2?
Solution: Figure 1 = 13n + 10, Figure 2 = 11n + 10
Each answer is worth 3 marks for the final equation and 2 marks for the steps.
n Figure 1 Figure 2
0 1×(1+1+5+3)+0×(1+2)=10 10+0×(1+1+1+5+3)=10
1 2×(1+1+5+3)+1×(1+2)=23 10+1×(1+1+1+5+3)=21
2 3×(1+1+5+3)+2×(1+2)=36 10+2×(1+1+1+5+3)=32
3 4×(1+1+5+3)+3×(1+2)=49 10+3×(1+1+1+5+3)=43
n ((n+1)×10)+(n×3) (11×n)+10 n 13n+10 11n+10
b. (10 points) Assuming the same very large number of iterations n for each loop version, what is the average number of cycles per instruction (rounded to the nearest 1 decimal place) when executing the code in Figure 1 and Figure 2?
Solution: Figure 1 = 2.2, Figure 2 = 2.2
Each answer is worth 3 marks for the steps and 2 marks for final answer. Similar to the previous question but counting the number of instructions instead of the clock cycles. We’ll get:
# instructions Figure 1 # instructions Figure 2
Since CPI Therefore CPI Figure 1
And CPI Figure 2
= 6n + 4 = 5n + 4
= # clock cycles # instructions
= 13n + 10 6n+4
≈ 13n 6n
= 13
6
= 2.16 ≈ 2.2
= 11n + 10 5n+4
≈ 11n 5n
= 11
5 = 2.2
3/6
CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
c. (10 points) Assuming the same very large number of iterations n for each loop version, and that both run on the same processor, which version is faster and why? Express your answer in the form “A is k times faster than B”.
Solution: Figure 2 is 1.18× faster than Figure 1.
Because the processor is the same, the clock frequency is the same. Therefore:
(3 marks)
Performance Figure 2 Performance Figure 1
(2 marks)
(1 mark)
(1 mark)
(1 mark) (2 marks)
= Execution Time Figure 1 Execution Time Figure 2
= # instructions Figure 1 × # CPI Figure 1 # instructions Figure 2 × # CPI Figure 2
= (6n+4)×(13n+10)×(5n+4) (5n+4)×(11n+10)×(6n+4)
= 13n+10 11n+10
≈ 13n 11n
= 13
11 = 1.18
4/6
CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
Question 2: (65 points)
Two strings have a common substring if they share at least one character. For exam- ple, the strings “hello” and “world” have a common substring, because both share the characters ‘o’ and ‘l’. On the other hand, the strings “cmput” and “bio” do not have a common substring, because they do not share any characters.
An efficient algorithm to determine whether two strings (s1 and s2) share a common substring has a complexity of O(n). This algorithm first creates an integer array v of size 26 (assuming strings consist of only lower-case alphabets), and initialize each array element with 0. For every character in s1, the algorithm increments the array element at the index that corresponds to that character (i.e., v[s1[i]-‘a’]) by 1 to indicate the occurrence of that character in s1. Then, for every character in s2, the algorithm checks the corresponding array element (i.e., v[s2[i]-‘a’]). If the array element has a value that is greater than 0, then a common character has been found and the algorithm returns 1 (i.e., true). Otherwise, the algorithm returns 0 (i.e., false). Assuming that strings are null-terminated character arrays, and given the C method signature below, your task is to implement that efficient algorithm in MIPS Assembly according to the description above.
int haveCommonSubstr(char* s1, char* s2) {
}
Solution: This is one way to solve this question. Marking Scheme:
• 5 marks for assuming arguments in right registers
• 5 marks for the assumption made about array v
• 5 marks for initializing the array v (all elements should be set to 0).
• 20 marks for first loop (loop termination, index calculation, loading correct array element, increment, store)
• 20 marks for second loop (loop termination, index calculation, load/lookup, check/branch, increment loop index)
• 5 marks for returning the correct value in $v0
• 5 marks for properly exiting the procedure
5/6
CMPUT 229 (Winter 2021) – Midterm II Instructor: Karim Ali
# $a0 = s1, $a1 = s2, $t2 = v
haveCommonSubstr:
addi $t3, $zero, 104
addi $t4, $zero, -4
init:
addi $t4, $t4, 4
sw $zero, 0($t4)
slt $t5, $t4, $t3
bne $t5, $zero, init
findChars:
lb $t1, 0($a0)
# loop count (26 elements)
# initialize array index to -4
# go to the next integer counter #v[i]=0
#if$t4<$t3
# loop
# load s1[i] (1 byte)
beq $t1, $zero, searchString # reached end of string
addi $t2, $t1, -0x61
sll $t2, $t2, 2
add $t2, $t2, $t0
lw $t1, 0($t2)
addi $t1, $t1, 1
sw $t1, 0($t2)
addi $a0, $a0, 1
j findChars
searchString:
lb $t1, 0($a1)
beq $t1, $zero, noSubstr
addi $t2, $t1, -0x61
sll $t2, $t2, 2
add $t2, $t2, $t0
lw $t1, 0($t2)
bne $t1, $zero, isSubstr
addi $a1, $a1, 1
j searchString
noSubstr:
addi $v0, $zero, 0
jr $ra
isSubstr:
addi $v0, $zero, 1
jr $ra
# compute s1[i]-‘a’
# because v is an integer array
# compute index to array v
# load the current counter
# increment the counter
# store it back in the array
# go to the next character in s1
# loop
# load s2[i] (1 byte)
# reached end of string, no match
# compute s2[i] - ‘a’
# because v is an integer array
# compute index to array v
# load the current counter
# if counter != 0 => match found
# go to next character in s2
# return 0 (false)
# return 1 (true)
6/6