---
tags: computer-arch
---
# Quiz3 of Computer Architecture (2023 Fall)
> Solutions
## Problem `A`
Consider an algorithm for [transposing a square matrix](https://en.wikipedia.org/wiki/Transpose) in-place by swapping rows and columns. Below, you will find the C code for this operation, and it is important to note that the matrix elements are 32-bit integers.
```c
#include <stddef.h>
void transpose(size_t n, int *m)
{
for (size_t i = 0; i < n; i++) {
for (size_t j = i + 1; j < n; j++) {
int t = m[(i * n) + j];
m[(i * n) + j] = m[(j * n) + i];
m[(j * n) + i] = t;
}
}
}
```
Next, we utilize [vector](https://en.wikipedia.org/wiki/Vector_processor)-style instructions to implement the transposition. Below, you will find an abbreviated listing of potentially relevant vector load/store instructions.
Vector Load/Store Instructions
| instruction | definition |
| :---------- | :--------- |
| `vsetvli rd, rs, eN, mX, tP, mP` | This instruction updates `rd` with the vector length computed; `rs` is an input register operand that contains the application vector length (AVL) which represents the vector length the program wants to use.<br> N in eN is the sew (8, 16, 32, 64, …); X in mX is the lmul (spelled as fY for 1/Y cases); P is the policy for tail (t) and mask (m): u for undisturbed, a for agnostic |
| `vle32.v vd, (rs1), vm` | `vd[i] = mem[(rs1) + i*4]` |
| `vse32.v vs3, (rs1), vm` | `mem[(rs1) + i*4] = vs3[i]` |
| `vlse32.v vd, (rs1), rs2, vm` | `vd[i] = mem[(rs1) + i*rs2]` |
| `vsse32.v vs3, (rs1), rs2, vm` | `mem[(rs1) + i*rs2] = vs3[i]` |
| `vluxei32.v vd, (rs1), vs2, vm` | `vd[i] = mem[(rs1) + vs2[i]]` (unordered) |
| `vsuxei32.v vs3, (rs1), vs2, vm` | `mem[(rs1) + vs2[i]] = vs3[i]` (unordered) |
| `vloxei32.v vd, (rs1), vs2, vm` | `vd[i] = mem[(rs1) + vs2[i]]` (ordered) |
| `vsoxei32.v vs3, (rs1), vs2, vm` | `mem[(rs1) + vs2[i]] = vs3[i]` (ordered) |
Complete the vector code provided below to vectorize the matrix transpose operation.
```c
# a0: n
# a1: m
transpose:
li t0, 1
bleu a0, t0, end # skip if n <= 1
slli t0, a0, __A01__ # initialize t0 with stride in bytes
addi a0, a0, -1 # decrement n
loop_i:
mv t2, a0 # number of elements to swap = n - (i+1)
addi t3, a1, __A02__ # temporary pointer to row at m[i][i+1]
add t4, a1, t0 # temporary pointer to column m[i+1][i]
addi a1, t4, __A03__ # bump m pointer by (n + 1) elements
loop_j:
vsetvli t5, t2, e32, m1, ta, ma
vle32.v v0, (t3) # vector load row m[i][...]
vlse32.v v1, (t4), t0 # vector load column m[...][i]
vsse32.v v0, (t4), t0 # vector store column m[...][i]
vse32.v v1, (t3) # vector store row m[i][...]
sub t2, t2, t5 # decrement vl
mul t6, t5, t0 # vl*stride in bytes
slli t5, t5, 2 # vl in bytes
add t3, t3, t5 # bump row pointer
__A04__ # bump column pointer
bnez t2, loop_j
addi a0, a0, -1 # decrement n
__A05__
end:
ret
```
> * A01 = ?
==2==
> * A02 = ?
==4==
> * A03 = ?
==4==
> * A04 = ?
==`add t4, t4, t6`==
> * A05 = ?
==`bnez a0, loop_i`==
---
## Problem `B`
Consider `REV` as a [macro-operation fusion instruction](https://en.wikichip.org/wiki/macro-operation_fusion) that reverses a linked list in memory. The rs1 operand for this instruction is the memory address of a pointer to the first node in the linked list, which is essentially a pointer to a pointer.
```
REV rs1
```
Each node in the linked list has the following structure. In this architecture, assume that pointers are 32 bits wide. The 'next' pointer can either hold the memory address of the next node in the list or be set to 0 (`NULL`) to indicate the end of the linked list.
```c
struct node {
struct node *next;
void *value;
}
```
To provide a point of reference, we have included both the C and assembly code equivalents for this instruction below.
```c
void REVLL(struct node **head)
{
struct node *prev = NULL;
struct node *curr = *head;
while (curr) {
struct node *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}
```
```c
# head is passed in a0
# t0 holds prev
# t1 holds next
lw a0, 0(a0)
beqz a0, done
addi t0, t0, 0
loop:
lw t1, 0(a0)
sw t0, 0(a0)
addi t0, a0, 0
addi a0, t1, 0
bnez t1, loop
done:
```
Let's analyze the execution of the assembly code for linked list reversal on an unpipelined RISC-V core. In this core, each instruction has a CPI (Cycles Per Instruction) of 1, except for load and store instructions, which require 2 cycles each. How many instructions are needed to reverse a linked list with a length of 4 using this program? (Fill in the numbers)
* Prologue: __ B01 __ load, __ B02 __ store , __ B03 __ other instructions
* Loop: __ B04 __ load, __ B05 __ store, __ B06 __ other instructions
> * B01 = ?
==1==
> * B02 = ?
==0==
> * B03 = ?
==2==
> * B04 = ?
==1==
> * B05 = ?
==1==
> * B06 = ?
==3==
---
## Problem C
A [garage door](https://en.wikipedia.org/wiki/Garage_door) will initiate its opening sequence when it detects the password '011' in a transmission. To put it formally, this [Finite State Machine](https://en.wikipedia.org/wiki/Finite-state_machine) (FSM) accepts a bitstring composed of 0's and 1's as input and produces a continuous stream of 0's until it encounters the substring '011,' at which point it begins generating a continuous stream of 1's. Below are examples of how this FSM operates:
* Input: 010101001100001010101
* Output: 000000000111111111111
* Input: 000000000001000000010
* Output: 000000000000000000000
Mark the correct FSM state transition for each numbered arrow.
* Arrow 5
> __ C01 __
* Arrow 6
> __ C02 __
* Arrow 7
> __ C03 __
* Arrow 8
> __ C04 __
> * C01 = ?
==0/0==
> * C02 = ?
==1/1==
> * C03 = ?
==1/1==
> * C04 = ?
==0/1==
---
## Problem D
Take a look at the circuit diagram below along with the delays of its components:
* t~multiplier~ = 50ps
* t~subtract~ = 35ps
* t~XOR~ = 25ps
* t~AND~ = 20ps
* t~OR~ = 20ps
* t~NOT~ = 5ps
* t~clk-q~ = 5ps
* t~setup~ = 2ps
1. What is the smallest combinational delay of all paths in this circuit, in picoseconds? __ D01 __
> * D01 = ?
> ==25ps==
> The shortest CL path is between the right register and the top left register, consisting of a NOT gate and an OR gate, for a total delay of 25ps.
2. What is the maximum hold time the registers can have so that there are no hold time violations in the circuit above?
> * D02 = ?
> ==30ps==
> The shortest CL path is 25ps (see Q6.1), and the maximum hold time is the shortest CL path + clk-to-q, which gives us 30ps.
3. What is the minimum allowable clock period for this circuit to function properly?
> * D03 = ?
> ==117ps==
> The longest path between any two registers is between the top left register and the register, consisting of a multiplier, a NOT gate, a subtractor, and an AND gate, for a total of 110ps.
> Additionally, we need to account for clk-to-q and setup, which gives us 117ps.
---
## Problem E
Decode the following RISC-V instruction. You can use [online RISC-V Instruction Encoder/Decoder](https://luplab.gitlab.io/rvcodecjs/).
```
0x24A009EF
```
which is mapped to
```
jal __E01__, __E02
```
E01 should start with `x`.
> * E01 = ?
==x19==
> * E02 = ?
==586==
---
## Problem F
Examine the circuit diagram presented below. SEL is a single-bit control signal that undergoes instantaneous updates at the rising edge of each clock cycle, maintaining stability throughout each clock cycle. You can make the assumption that Input will not result in any hold time violations.
* t~multiplier~ = 1000 ps
* t~clk-q~ = 30 ps
* t~mux~ = 25 ps
* t~setup~ = 20 ps
* t~NOT~ = 8 ps
* t~shifter~ = 2 ps
The combinational logic block on the left performs a left shift operation on the top input by the number of bits specified by the bottom input. In the diagram, the shifter connected to the register on the left shifts its output to the left by 1 bit.
Suppose we want to maximize the circuit's frequency without altering its behavior, and we are not allowed to modify the delays of any component.
The most significantly slow component in this context is the multiplier, and addressing this issue is necessary. Specifically, if our sole multiplication requirement is doubling numbers, we do not require a versatile multiplier capable of multiplying any two inputs together.
What is the minimum clock period after implementing the above change? __ F01 __
> * F01 = ?
> ==77 ps==
> With the multiplier replaced by a shifter, the new longest path starts from either left-side register, goes through the shifter and the mux, and ends at the rightmost register.
> From the rising edge, we wait 30 ps for the output to appear out of the left registers (clk-to-q).
> Then we wait another 2 ps for the signal to travel through the shifter, and another 25 ps for the multiplexer. Finally, we have to get to the rightmost register 20 ps before the next rising edge to account for setup time. In total, this is 30 + 2 + 25 + 20 = 77 ps.
---
## Problem G
The function `add_even` is specified as follows:
Input:
* a0: Pointer to the beginning of an array containing 32-bit integers.
* a1: The number of integers in the array.
Output:
* a0: The sum of all even numbers within the array.
Example: Let's consider an input where a0 points to $[4, 5, 6, 7]$, and a1 holds the value `4`. In this case, the output in a0 will be `10` (4 + 6).
Complete the missing sections in the RISC-V code provided below. Each line should consist of exactly one instruction or pseudo-instruction.
```c
add_even:
addi t0, x0, 0 # set t0 to be the running sum
loop:
beq a1, x0, end
lw t1 0(a0) # set t1 to be the number in the array
srli t2, t1, 1
__G01__
bne t1, t2, pass
add t0, t0, t2
pass:
__G02__
addi a0, a0, 4
j loop
end:
mv a0, t0
```
> * G01 = ?
==`slli t2, t2, 1`==
> * G02 = ?
==`addi a1, a1, -1`==
---
## Problem H
A [Hamming Error Correcting Code](https://en.wikipedia.org/wiki/Hamming_code) is capable of rectifying single-bit errors. In scenarios where data is susceptible to errors, such as in satellite communication or L1 caches, it's advantageous to employ Hamming codes to store data blocks. These codes can internally correct errors during memory retrieval.
In this context, we will examine a (7,4) Hamming Code with even parity. This code utilizes 7 bits in total to store 4 data bits. Please refer to the following bit pattern for the (7,4) Hamming Code:
We follow the convention where the first bit is considered the most significant in the data, and the seventh bit is the least significant. Then, we create a circuit that, when provided with a (7,4) Hamming Code, produces a corrected nibble of data. What components should be placed in the labeled boxes? Assume that multiple-input gates are created by connecting two-input gates.
It is known that both Box I and Box II belong to this category. Please provide answers accordingly.
* AND gate
* OR gate
* XOR gate
* Adder gate
* Multiplier gate
* Multiplexer (with 0 input on top)
* Demultiplexer (with 0 input on top)
* Priority Encoder (with 0 input on top)
1. What should be placed inside Box I? __ H01 __
> * H01 = ?
> ==XOR gate==
> Cascaded XOR gates can be used to determine the parity of the input bits; XOR returns 1 if the number of input “1” bits is odd, and 0 if the number of input `1` bits is even. This matches our definition of parity.
2. What should be placed inside Box II? __ H02 __
> * H02 = ?
> ==Multiplexer (with 0 input on top)==
> We need to output the corrected data based on the parity bits; this can only be done using a multiplexer.
3. Given that the component in Box I has a 3 ns delay, the component in Box II has a 5 ns delay, and the computation of labels A-H takes 1 ns, if the inputs are received at time 0, what are the earliest and latest times at which the output can change in response?
* Earliest: __ H03 __ ns
* Latest: __ H04 __ ns
> * H03 = ?
> ==6== ns.
> The values of A-H are computed at 1 ns. Then after the 5 ns delay of Box 2, the output changes.
> * H04 = ?
> ==8== ns.
> The inputs change at 0 ns. Then after the 3 ns delay of Box I, the bottom input to Box II changes. Then after the 5 ns delay of Box II, the output changes.
---
## Problem I
The function `verify_password` is defined as follows:
* Input: There are no register inputs; however, the function receives a string input from stdin.
* Output: a0 returns 1 if the input from stdin matches "secretpass," and 0 otherwise.
You have access to the following externally defined labels:
* `password`: This is a pointer to a statically stored string "secretpass."
* `getchars`: This function is defined as follows:
* Input: a0 is a pointer to a buffer.
> Effect: It reads characters from stdin and populates the buffer pointed to by a0 with the read data, null-terminating the string. Your code can assume that the input consists of a maximum of 19 characters, not including the null-terminator.
* Output: None
In your current role as a hacker, your objective is to target the implementation of `verify_password`.
```c
verify_password:
addi sp, sp, -24 # Make space for a 20-byte buffer
sw ra, 20(sp)
mv a0, sp
jal ra, getchars
la t0, password
mv t1, sp
Loop:
lb t2, 0(t0)
lb t3, 0(t1)
bne t2, t3, Fail
beq t2, x0, Pass
addi t0, t0 1
addi t1, t1 1
j Loop
Pass:
li a0, 1
j End
Fail:
li a0, 0
End:
lw ra, 20(sp)
addi sp, sp, 24
jr ra
```
During your testing, you have uncovered an intriguing revelation: the function `getchars` does not function as originally intended. Instead of truncating at the 20th character, `getchar` continues writing data until it encounters the first null terminator within its input. Just as before, `verify_password` resides at memory address `0x1000`, and `getchars` is situated at address 0x0F00. Additionally, assume that the stack pointer is initially positioned at 0xBFFF F800 when `verify_password` begins execution. Our page size is 4 KiB, and we are currently operating on a little-endian system.
1. Given the ability to relocate the program counter to any desired location, we intend to execute a jump to our custom RISC-V code. To accomplish this, our plan is to initiate a jump to the beginning of the buffer stored on the stack. What is the maximum number of RISC-V standard instructions we can inject into this buffer? __ I01 __
> * I01 = ?
> ==5==
> The buffer is 20 bytes long. Each RISC-V instruction is 4 bytes long. In total, we can fit 20 / 4 = 5 instructions in the buffer.
2. Setting aside your previous response, let's assume we can insert a maximum of 5 instructions into the buffer. However, this limitation doesn't provide us with sufficient instructions to achieve our goals effectively. Consequently, we opt to introduce code that grants us the ability to execute more extensive programs, rather than being confined to only 5 instructions. Please fill in the following 5-line code, ensuring that you can employ pseudo-instructions, as long as they ultimately resolve to exactly one instruction.
```
# Allocate a buffer of 256 bytes, which does not overlap with any data
# we already are using (such as the instructions injected in part 1)
1: addi sp, sp, __I02__
# Set the argument of getchars to the start of the allocated buffer
2: mv __I03__, sp
# Set t1 so the next instruction jumps to getchars
3: lui t1, __I04__
4: jalr ra t1 -256 # Call getchars
# Jump to the start of the buffer
5. jr __I05__
```
> * I02 = ?
> ==-280==.
> We allocate 256 bytes of buffer, plus 24 bytes to avoid overlap with the injected instructions and the saved ra register from part 1, for a total of 280 bytes. (This does mean that we rely on data after our stack pointer to stay constant, which is technically undefined behavior. In reality, the data will stay consistent for long enough that
we move the stack pointer back down; since our sp starts in the middle of a page, the data will not be deallocated.
> * I03 = ?
> ==a0==
> The `getchars` function expects the address of a buffer as an argument in the a0 register.
> * I04 = ?
> ==1==
> This puts the value 0x1000 in t1, which then causes the next line to jump to 0x1000 - 256 = 0x0F00, the address of Get20Chars. Note that we needed to use lui here, since addi can only increase by up to 0x7FF. Line 4 could also not have been a jal operation, since our jump distance would have exceeded the size of a 20-bit immediate.
> * I05 = ?
> ==sp==
> We want to jump to the address in the sp register, and we do not care about saving a return address anywhere.
3. Among the following jump instructions, which ones are suitable for use in our injected code? There's no need to be concerned about these lines not correctly calling `getchars`; our goal is to have a valid RISC-V jump instruction. Additionally, please take note that +3840 is equivalent to 0x00000F00. Select all possible choices. __ I06 __
a. `ret`
b. `jalr x0, t1, -256`
c. `jalr s0, t1, -256`
d. `jalr ra, t2, -256`
e. `jalr ra, t0, 16`
f. `jalr s0, x0, 3840`
g. None of the above
> * I06 = ?
> ==d, e==
> `ret` = `jr ra` = `jalr x0 ra 0` and `jalr x0, t1 -256` contain a null byte when translated to machine code: 0x00008067 and 0xF0030067.
> jalr s0 x0 3840 is an invalid instruction because the immediate 3840 is greater than 2047.
> I-type immediates must be between -2048 and +2047.
> `jalr s0 t1 -256` and `jalr ra t0 16` are valid, and do not have a null byte; note that jalr s0, t1, -256 = 0xF0030467 does not have a null byte, because it gets split up into bytes as 0x67 0x04 0x03 0xF0.
---
## Problem J
Examine the provided RISC-V code snippet:
```c
Loop:
andi t2, t1, 1
srli t3, t1, 1
bltu t1, a0, Loop
jalr s0, s1, MAX_POS_IMM
...
```
1. What is the value of the byte offset that would be stored in the immediate field of the `bltu` instruction?
> * J01 = ?
> ==-8==
> Two instructions away = `-8` bytes
> Each instruction is $4$ byte, so to go back to Loop, it needs to minus $4*2$ bytes.
2. We propose a revision to the standard 32-bit RISC-V instruction formats. In this revised format, each instruction will have a unique opcode, still represented using 7 bits. As a result of this change, we will eliminate the funct3 field from the R, I, S, and SB instructions, allowing us to allocate bits to other instruction fields, while retaining the opcode field. Assuming that s0 = 0x10000000, s1 = 0x40000000, and PC = 0xA0000000, let's examine the instruction: `jalr s0, s1, MAX_POS_IMM`, where `MAX_POS_IMM` represents the maximum possible positive immediate value for `jalr`. After this instruction executes, what will be the values in the following registers? (Provide your answers in hexadecimal.)
* `s0` = J02
* `s1` = J03
* `PC` = J04
> * J02 = ?
==0xA000 0004==
> * J03 = ?
==0x4000 0000==
> * J04 = ?
==0x4000 0FFF==
> We know that rd and rs1 fields are now 6 bits. `jalr` is an I-type instruction, so we take out the `funct3` bits but we give each of rd and rs1 fields 1 bit, meaning we have 1 bit leftover to give to the immediate field. Thus, we now have a 13-bit immediate. Thus, the maximum possible immediate a `jalr` instruction can hold is $+2^{12} - 1$ halfwords away, which is represented as 0b0 1111 1111 1111, which is `0x0FFF`.
>
> `s0` is the linking register -- itss value is PC + 4
> `s1` does not get written into so it stays the same.
> `PC = R[s1] + 0x0FFF`
---
## Problem `K`
Let's examine the program that recursively calculates the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number). On the left, you will find the C code, and on the right, you can see its corresponding translation into RISC-V assembly. It's important to note that the execution has been paused just before executing the 'ret' instruction. The 'SP' label on the stack frame (part 3) indicates the location where the stack pointer is pointing when the execution was halted.
- [ ] C code
```c
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
```
- [ ] RISC-V Assembly (incomplete)
```c
fib:
addi sp, sp, -12
sw ra, 0(sp)
sw a0, 4(sp)
sw s0, 8(sp)
li s0, 0
li a7, 1
if:
ble __K01__
L2:
addi a0, a0, -1
call fib
add s0, s0, a0
lw a0, 4(sp)
addi a0, a0, -2
call fib
mv t0, a0
add a0, s0, t0
done:
lw ra, 0(sp)
lw s0, 8(sp)
L1:
addi sp, sp, 12
ret
```
1. Complete the missing portion of the `ble` instruction to make the assembly implementation match the C code.
> * K01 = ?
==a0, a7, done==
> a0 is n in C code.
> a7 is `1` in C code.
> done is ready to return in C code.
2. How many distinct words will be allocated and pushed into the stack each time the function `fib` is called?
> * K02 = ?
==3==
> $12/4=3$
3. Please fill in the values for the blank locations in the stack trace below. Please express the values in HEX.
| Notation | address |
| :------: | ------- |
| Smaller address | 0x280 |
| | 0x1 |
| | K03 |
| SP $\to$ | K04 |
| | K05 |
| | 0x0 |
| | 0x280 |
| | 0x3 |
| | 0x0 |
| | 0x2108 |
| | 0x4 |
| | 0x6 |
| Larger address | 0x1 |
> * K03 = ?
==0x0==
> * K04 = ?
==0x280==
> * K05 = ?
==0x2==
> 
> Initial `n` is 0x3, and the after the inst. `L2: addi a0, a0, -1` the k05 becomes 0x3-1=0x2.
> K04 = ra = 0x280
> s0 is to store the temporary value to add `fib(n - 1) + fib(n - 2)` together equal to inst `add a0, s0, t0`.
4. What is the hex address of the `done` label? (Answer in HEX)
> * K06 = ?
==0x298==
> There have 6 instructions between the first `call fib` and done label. Therefore the address is 0x280+6*4=0x298
5. What was the address of the original function call to `fib`? (Answer in HEX)
> * K07 = ?
==0x2104==
> Since call would store the next instruction's address so the first ra minus 4 is the answer, which is 0x2108.
Sign in with Wallet
Connect another wallet