Midterm I CMPT 295
Arrvindh Shriraman September 20, 2020
• HONOR CODE
• Questions Sheet.
• Q2 Mystery [8 Points]
– A. When the above code executes, which line is modified? How many times? [2]
– B. What is the value of register a6 at the end ? [2]
– C. What is the value of register a4 at the end ? [2]
– D. In one sentence what is this program calculating ? [2]
• Q3. Tree Search in RISC-V; each question [12 points] • Q4. RISCV – The MOD operation [6 points]
– The data segment starts at address 0x10000000. What are the memory locations modified by this program and what are their values ?
• Q5 Floating Point [10 points.]
– A. What is the smallest nonzero positive value that can be represented?
Write your answer as a numerical expression in the answer packet?
[2]
– B. Consider some positive normalized floating point number where p
is represented as:
– C. Now instead let p be a positive denormalized number described
asp = 2y x 0.significand. What is the distance between p and the
next largest number after p that can be represented? [2]
– Sort the following minifloat numbers.
HONOR CODE
• I have not used any online resources during the exam.
• I have not obtained any help either from anyone in the class or outside
when completing this exam.
• No sharing of notes/slides/textbook between students.
• NO SMARTPHONES.
Questions Sheet.
Read all of the following information before starting the exam:
1
• For each question fill out the appropriate choice or write text on Canvas page. Also type clearly on in the exam on the appropriate text.
• IF THE MULTIPLE CHOICE ANSWER IS WRONG WE WILL MARK THE ANSWER WRONG. IF THE MULTIPLE-CHOICE ANSWER IS CORRECT, WE WILL READ THE WRITTEN PORTION.
• Show all work, clearly and in order, if you want to get full credit.
• I reserve the right to take off points if I cannot see how you logically got to the answer (even if your final answeris correct).
• Circle or otherwise indicate your final answers.
• Please keep your written answers brief; be clear and to the point.
• I will take points off for rambling and for incorrect or irrelevant statements. This test has six problems.
Q2 Mystery [8 Points]
.globl main
.text
main:
li a0,1
li a1,0
la s0, L1
lw s1, 8(s0)
addi s2, zero, 6
addi s3, zero, 0
li s4,8449
slli s4, s4,7
L1:
beq s3, s2, done add s1, s1, s4 add a2, a0, a1 sw s1, 8 (s0) addi s3, s3, 1
j L1
done:
li a0,10
ecall
A. When the above code executes, which line is modified? How many times? [2]
2
Line 18 6 times.
B. What is the value of register a6 at the end ? [2]
8. first iteration line 18 is add a2,a0,a1. Next iteration it is add a3,a1,a2, next iteration add a4,a2,a3. . . and so on.
C. What is the value of register a4 at the end ? [2]
3
D. In one sentence what is this program calculating ? [2]
Fibonacci series
3
Q3. Tree Search in RISC-V; each question [12 points]
We’re interested in running a search on a tree, and labeling the nodes in the order we finish examining them. Below we have the struct definition of a node in the tree, and the implementation of the function in C.
Note that initially, all nodes in the graph have their label set to -1. The address width of our machine is 32 bits.
struct node {
int item;
int label;
int n_edges;
struct node** edges[];
}
int label(struct node* nd, int counter) {
if (nd->label != -1) { return counter;
}
for (int i = 0; i < nd->n_edges; ++i) { counter = label(nd->edges[i], counter);
}
nd->label = counter++;
return counter; }
Fill in the blanks in the code below
dfs_label:
# prologue
addi sp sp, -12
# Q1. We need to make space for 3 registers on stack. # 3*4bytes/register = 12
sw ra, 0(sp)
sw s0, 4(sp)
4
sw s1, 8(sp) sw s2, 12(sp)
# a1 is counter. We do not need temporaries for counter # since it is always overwritten
# by a call. a0 is node*
# Base case
addi t1, zero, -1 # Q2: Base case load immediate -1
lw t0, 4 (a0) # Q3 Load n->label for comparison to base case.
bne t0, t1, epilogue
# Loop header
add s0, a0, zero # Save node in a saved register. # a0 is going to be eventually overwritten.
addi s1, zero, 0 # Set loop index to 0
loop:
lw t0 _8(s0)_ # Load in n_edges in t0
beq t0, s1, fin # Iterator. If s1 end of loop iteration. We stop
lw a0, 12(s0) # load edges into a0
sll t0, s1, 2 # Shift by 2 to get byte offset
add a0, a0, t0 # Get ptr for next node
lw a0, 0(a0) # Load ptr into a0
jal label
addi a1, a0, 0 # Put return value into second argument for next call. addi s1, s1, 1 # Increment counter after returning from recursion
j loop
fin:
sw a1 _4(s0)_
addi a1, a1, 1
# counter++;
# you have to increment after storing the value. addi a0, a1, 0
epilogue:
lw ra (sp)
lw s0 4(sp)
lw s1 8(sp) add sp, sp, 12 jr ra
5
Q4. RISCV – The MOD operation [6 points]
We will be introducing a new instruction called “mod” in RISC-V which calculates the remainder. The semantics of the mod instruction (mod dst,src1,src2) are dst = src1%src2. e.g., lets say s1=5 s2=2 mod s3,s1,s2 stores the value 1 in s3.
We will be using the mod operation in the program below called cipher. You want to impress your friend, so you predict the result of executing the program as it is written, just by looking at it. If the program is guaranteed to execute without crashing, describe what it prints, otherwise explain the bug that may cause a crash.
.globl main
.data
a: .string “happy”
init: .string “XXXXX” # 12 Xs
.text
# C : Cipher(char* str).
cipher:
addi s3,zero,25
loop_header:
lbu s2, 0(a0) # Read character ch beqz s2, end
addi s7,a0,0
addi a0,a0,1
loop:
addi s1, s2, -97 #
bltu s3,s1,loop_header
addi s2,s2,13
mod s2,s2,26 # New instruction
addi s2,s2,97
sb s2, 0(a1) addi a1,a1,1 jal loop_header end:
ret
main:
la a0, a la a1,init jal cipher li a0,10 ecall
6
The data segment starts at address 0x10000000. What are the mem- ory locations modified by this program and what are their values ?
ngvve : 0x10000006 0x100000A
7
Q5 Floating Point [10 points.]
The TAs get tired of having to convert floating-point values into 32 bits. As a result they propose the following smaller floating-point representation which is useful in a number of machine learning applications. It consists of a total of 8 bits as show below.
Exponent bias is 3.
Sign Exponent Mantissa 1 bit 3 bits. Bias 3. 4 bits.
Exponent Significand Meaning 000
7 non-zero 7 0
0 non-zero
NaN
+- inf Denorm
• The largest exp remains reserved as in traditional floating point
• The smallest exp follows the same denormalized formula as traditional
floating point
• Numbers are rounded to the closest representable value. Any numbers
that have 2 equidistant representations are rounded down towards zero.
A. What is the smallest nonzero positive value that can be repre- sented? Write your answer as a numerical expression in the answer packet? [2]
Exponent – 0 .0001 – Denormalized = 2−2 * 0.0001 = 2−6
B. Consider some positive normalized floating point number where p
is represented as:
p= $2^y$ x 1.significand.
What is the distance (i.e. the difference) between p and the next- largest number after p that can be represented? [2]
2(y−4)
C. Now instead let p be a positive denormalized number described asp = 2y x 0.significand. What is the distance between p and the next largest number after p that can be represented? [2]
2−6
8
Sort the following minifloat numbers.
0x04, 0xb2, 0x62, 0x45, 0x32
0x32 (1.125), 0xb2 (-1.125), 0x45 (2.625), 0x62 (8.75), 0x04 (0.0625) 0xb2 < 0x04 < 0x32 < 0x45 < 0x62
9