# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`clare8151214`](https://github.com/clare8151214) >
# Problem B
> ref: [Quiz1 of Computer Architecture (2025 Fall) Problem-B](https://hackmd.io/@sysprog/arch2025-quiz1-sol#Problem-B)
## Implementation
The number of cycles consumed by my implementation is about 50264
> [my code Commit ff1556a](https://github.com/clare8151214/ca2025-quizzes/commit/ff1556a7fda1fe99955b8d99ae6ce8c25d3e1222#diff-7206aed52dcfe0c0fccc1d691f4e306e7eb87b5b8adb0978a09b605c1670a1f7)
Meanwhile, the code optimized with gcc -O3 consumes only 29082 cycles:
> [gcc -o3 code](https://github.com/clare8151214/ca2025-quizzes/blob/main/q1-uf8_O3.s)
This clearly shows how powerful modern compiler optimizations can be. My implementation is slower mainly due to two reasons, which I will analyze and propose optimization strategies for below.
## Reason 1: The Massive Overhead of Function Calls
This is the biggest cause of performance difference, likely accounting for more than 80% of the gap.
In the main_loop_start loop, each iteration (total 256 times) performs:
```
jal ra, uf8_decode
jal ra, uf8_encode
```
And inside uf8_encode, another function call occurs:
```
jal ra, clz
```
This means 3 function calls per iteration.
What is the cost of a function call?
Each jal may look like a single instruction, but it hides a lot of overhead:
Prologue: addi sp, sp, -X, sw ra, ..., sw s0, ..., etc., to save context before entering the function.
Epilogue: lw ra, ..., lw s0, ..., addi sp, sp, X, jr ra, to restore state before returning.
Pipeline flush: jal and jr ra are jump instructions. In a pipelined processor (like Ripes), each jump flushes the pipeline, causing multiple cycles of wasted time.
Estimated cost:
Total calls: 256 iterations × 3 calls per iteration = 768 function calls.
Assuming ~8 extra instructions per call (prologue/epilogue): ~768 × 8 = 6144 extra instructions.
Adding the pipeline flush penalties… most CPU cycles are wasted “preparing for function calls” and “returning,” not actual computation.
What does GCC -O3 do?
The compiler uses function inlining. It notices that uf8_decode and clz are small and directly embeds their code into the caller instead of calling them. This completely eliminates the overhead described above.
---
### Optimization Strategy 1: Manual Function Inlining
This is the most impactful optimization. I can embed the uf8_decode and clz code directly where they are called.
1. Inline uf8_decode in main
#### Original Main loop
```ass
main_loop_start:
# for loop condition check
bge s1,s5,loop_exit # if (i >= 256), exit loop
# Round-trip Test Logic
# 1. Decode fl
mv a0, s1 # a0 = fl = i
jal ra, uf8_decode
mv s0, a0 # s0 = value (result of decode)
# 2. Encode value
mv a0, s0 # a0 = value (parameter for encode)
jal ra, uf8_encode
mv s3, a0 # s3 = fl2 (result of encode)
# 3. Check if (fl != fl2)
beq s3, s1, check_monotonicity # if (fl2 == fl), skip failure
li s6, 0 # if failed, passed = false
```
#### New Main loop
```ass
main_loop_start:
bge s1,s5,loop_exit # if (i >= 256), exit loop
mv a0, s1 # Input: a0 = fl = i
andi t0, a0, 0x0f # t0 = mantissa
srli t1, a0, 4 # t1 = exponent
li t2, 0x7FFF
li t3, 15
sub t3, t3, t1 # t3 = 15 - exponent
srl t4, t2, t3
slli t4, t4, 4 # t4 = offset
sll t0, t0, t1
add s0, t0, t4 # s0 = value (decode result)
# 2. Encode value
mv a0, s0 # a0 = value (parameter for encode)
jal ra, uf8_encode
mv s3, a0 # s3 = fl2 (result of encode)
# 3. Check if (fl != fl2)
beq s3, s1, check_monotonicity
li s6, 0 # passed = false
```
2. Inline `clz` inside uf8_encode
#### Original uf8_encode:
`clz` is called as a separate function.
```ass
uf8_encode:
mv t0, a0 # t0 = value
li t6, 16
bltu t0, t6, encode_small # if value < 16 → return value
addi sp, sp, -8 # push frame
sw ra, 4(sp) # save ra
sw t0, 0(sp) # save original value
# call clz
mv a0, t0
jal ra, clz # a0 = lz
# pop frame
lw t0, 0(sp) # restore original value
lw ra, 4(sp) # restore ra
addi sp, sp, 8
mv t1, a0 # lz
li t2, 31
sub t2, t2, t1 # msb = 31 - lz
li t3, 0 # exponent
li t4, 0 # overflow
li t6, 5
blt t2, t6, exp_est_done # if msb < 5 → skip estimate
li t6, 4
sub t3, t2, t6 # exponent = msb - 4
li t6, 15
blt t6, t3, cap_to_15
j exp_est_loop_init
cap_to_15:
mv t3, t6 # exponent = 15
exp_est_loop_init:
# overflow = (2^exp - 1) * 16
beqz t3, exp_est_done
li t4, 0
li t5, 0
exp_make_ovl: # while (t5 < t3) { overflow = (overflow<<1)+16; t5++; }
blt t5, t3, 1f
j exp_make_ovl_done
1: slli t4, t4, 1
addi t4, t4, 16
addi t5, t5, 1
j exp_make_ovl
exp_make_ovl_done:
li t5, 0 # reset, reused in adj_up_loop
# backtrack: while (exp>0 && value < overflow)
exp_back_check:
beqz t3, exp_est_done
bltu t0, t4, exp_back_step
j exp_est_done
exp_back_step:
addi t4, t4, -16
srli t4, t4, 1
addi t3, t3, -1
j exp_back_check
exp_est_done:
# fine-tune exponent / overflow upward
adj_up_loop:
li t6, 15
beq t3, t6, adj_done
slli t5, t4, 1 # next = (overflow << 1) + 16
addi t5, t5, 16
bltu t0, t5, adj_done
mv t4, t5
addi t3, t3, 1
j adj_up_loop
adj_done:
# form result
sub t6, t0, t4 # value - overflow
srl t6, t6, t3 # >> exponent
slli t3, t3, 4 # exponent << 4
or a0, t3, t6 # combine
andi a0, a0, 0xFF # keep 8 bits
ret
encode_small:
andi a0, t0, 0xFF # direct return
ret
clz:
li t0, 32 # n = 32
li t1, 16 # c = 16
clz_loop:
srl t2, a0, t1 # y = x >> c
beq t2, x0, clz_skip
sub t0, t0, t1 # n -= c
mv a0, t2 # x = y
clz_skip:
srli t1, t1, 1 # c >>= 1
bne x0, t1, clz_loop
sub a0, t0, a0 # return n - x
ret
```
#### new uf8_encode
`clz` logic is implemented inline, eliminating function call overhead.
```c
uf8_encode:
mv t0, a0 # t0 = value
li t6, 16
bltu t0, t6, encode_small # if (value < 16) return value
mv a5, t0 # a5 is our 'x' for the clz logic
li t1, 32 # t1 is 'n'
li t2, 16 # t2 is 'c'
clz_inline_loop:
srl t3, a5, t2 # t3 = y = x >> c
beq t3, x0, clz_inline_skip
sub t1, t1, t2 # n -= c
mv a5, t3 # x = y
clz_inline_skip:
srli t2, t2, 1
bne x0, t2, clz_inline_loop
sub t1, t1, a5 # t1 = lz = n - x
li t2, 31
sub t2, t2, t1 # msb = 31 - lz
li t3, 0 # exponent = 0
li t4, 0 # overflow = 0
li t6, 5
blt t2, t6, exp_est_done # if (msb < 5)
li t6, 4
sub t3, t2, t6 # exponent = msb - 4
li t6, 15
bgeu t3, t6, cap_to_15 # if exponent >= 15
j exp_est_loop_init
cap_to_15:
li t3, 15 # exponent = 15
exp_est_loop_init:
beqz t3, exp_est_done
li t4, 0
li t5, 0
exp_make_ovl:
bgeu t5, t3, exp_make_ovl_done
slli t4, t4, 1
addi t4, t4, 16
addi t5, t5, 1
j exp_make_ovl
exp_make_ovl_done:
li t5, 0
exp_back_check:
beqz t3, exp_est_done
bltu t0, t4, exp_back_step
j exp_est_done
exp_back_step:
addi t4, t4, -16
srli t4, t4, 1
addi t3, t3, -1
j exp_back_check
exp_est_done:
adj_up_loop:
li t6, 15
beq t3, t6, adj_done
slli t5, t4, 1
addi t5, t5, 16
bltu t0, t5, adj_done
mv t4, t5
addi t3, t3, 1
j adj_up_loop
adj_done:
sub t6, t0, t4
srl t6, t6, t3
slli t3, t3, 4
or a0, t3, t6
andi a0, a0, 0xFF
ret
encode_small:
andi a0, t0, 0xFF
ret
```
---
Our cycle count decreased from `50624` to `41076`
---
## Reason 2: Algorithm Structure – Generic Loops vs. Optimized Lookup
My uf8_encode function uses three independent loops to iteratively approximate the correct exponent and overflow. This is logically generic but inefficient — each loop requires comparisons and branches, which disrupt the CPU pipeline.
What does GCC -O3 do?
The compiler abandons loops in favor of a decision tree and lookup table:
It uses a series of bleu instructions to quickly determine the range of the input value (e.g., value <= 15, value <= 47, value <= 111).
Once the range is known, it jumps directly to a code block with precomputed exponent and overflow values.
This “space-for-time” approach produces larger code but drastically shortens execution paths and eliminates loops.
---
### Optimization Strategy 2: Simplify Algorithm and Reduce Loops
It’s very difficult to replicate the compiler’s entire decision tree manually, but we can borrow its idea by creating fast paths for the most common cases to reduce the number of loops and branch instructions.
This analysis shows why compiler-optimized code runs much faster — not because the logic is fundamentally different, but because function call overhead and loop inefficiency are systematically removed.
#### Implementation Steps
Determine the fast-path boundaries:
We need to identify the threshold values where the exponent changes:
* exponent = 0: value ≤ 15
* exponent = 1: value ≤ 47 (uf8_decode(0x1F))
* exponent = 2: value ≤ 111 (uf8_decode(0x2F))
* exponent = 3: value ≤ 239 (uf8_decode(0x3F))
#### Create branches:
At the beginning of uf8_encode, add bleu instructions to check these boundary conditions.
#### Write fast handling blocks:
For each exponent, implement a very short handling block. Since both exponent and overflow are known constants in these cases, calculating the mantissa requires only one subtraction and one shift instruction.
#### Build the general fallback path:
Convert your existing code (with the inlined clz) into a general path or fallback path that will handle all larger values not caught by the fast-path branches.
```ass
uf8_encode:
mv t0, a0 # t0 = original value (preserved)
li t6, 15
bleu t0, t6, encode_exp_0_fast_path
li t6, 47
bleu t0, t6, encode_exp_1_fast_path
li t6, 111
bleu t0, t6, encode_exp_2_fast_path
li t6, 239
bleu t0, t6, encode_exp_3_fast_path
j encode_generic_path
encode_exp_0_fast_path: # Handles values <= 15
# For exp=0, the encoded form is the value itself.
andi a0, t0, 0xFF
ret
encode_exp_1_fast_path: # Handles values 16-47
# For exp=1, overflow is 16. mantissa = (value - 16) >> 1
addi t1, t0, -16 # value - 16
srli t1, t1, 1 # >> 1
ori a0, t1, 0x10 # | (1 << 4)
ret
encode_exp_2_fast_path: # Handles values 48-111
# For exp=2, overflow is 48. mantissa = (value - 48) >> 2
addi t1, t0, -48 # value - 48
srli t1, t1, 2 # >> 2
ori a0, t1, 0x20 # | (2 << 4)
ret
encode_exp_3_fast_path: # Handles values 112-239
# For exp=3, overflow is 112. mantissa = (value - 112) >> 3
addi t1, t0, -112 # value - 112
srli t1, t1, 3 # >> 3
ori a0, t1, 0x30 # | (3 << 4)
ret
encode_generic_path:
#Inlined clz
mv a5, t0
li t1, 32
li t2, 16
clz_inline_loop:
srl t3, a5, t2
beq t3, x0, clz_inline_skip
sub t1, t1, t2
mv a5, t3
clz_inline_skip:
srli t2, t2, 1
bne x0, t2, clz_inline_loop
sub t1, t1, a5 # t1 = lz
li t2, 31
sub t2, t2, t1
li t3, 0
li t4, 0
li t6, 5
blt t2, t6, exp_est_done
li t6, 4
sub t3, t2, t6
li t6, 15
bgeu t3, t6, cap_to_15
j exp_est_loop_init
cap_to_15:
li t3, 15
exp_est_loop_init:
beqz t3, exp_est_done
li t4, 0
li t5, 0
exp_make_ovl:
bgeu t5, t3, exp_make_ovl_done
slli t4, t4, 1
addi t4, t4, 16
addi t5, t5, 1
j exp_make_ovl
exp_make_ovl_done:
li t5, 0
exp_back_check:
beqz t3, exp_est_done
bltu t0, t4, exp_back_step
j exp_est_done
exp_back_step:
addi t4, t4, -16
srli t4, t4, 1
addi t3, t3, -1
j exp_back_check
exp_est_done:
adj_up_loop:
li t6, 15
beq t3, t6, adj_done
slli t5, t4, 1
addi t5, t5, 16
bltu t0, t5, adj_done
mv t4, t5
addi t3, t3, 1
j adj_up_loop
adj_done:
sub t6, t0, t4
srl t6, t6, t3
slli t3, t3, 4
or a0, t3, t6
andi a0, a0, 0xFF
ret
```
---
Our cycle count decreased from `41076` to `38866`
Although it cannot reach the level of GCC -O3 optimization, it is already very close.
---
# Problem C
> ref: [Quiz1 of Computer Architecture (2025 Fall) Problem-C](https://hackmd.io/@sysprog/arch2025-quiz1-sol#Problem-C)
## Implementation
My hand-written code takes roughly 3350 cycles to run:
>[my original code Commit d91a170](https://github.com/clare8151214/ca2025-quizzes/commit/d91a17068a04c98151b88e04a7c621943cd6fc23)
The code compiled with `gcc -O3` finishes in about 1177 cycles:
> [gcc -o3 code](https://github.com/clare8151214/ca2025-quizzes/blob/main/q1-bfloat16_O3.s)
>However, I’ve noticed that this optimization is unsafe—it is valid only within the narrow context of the current test run. If the inputs were to include negative numbers, the simplified version would produce incorrect results.
### How the compiler “thinks”
Based on the exact information it can see, the compiler follows one guiding principle—the **“as-if” rule**. It may apply **any** transformation to the code as long as the program’s **observable behavior** remains *as if* the original source had been executed.
Here, the only observable behavior is printing the correct **PASS / FAIL** messages.
With that in mind, the compiler’s internal reasoning can be outlined like this:
#### For `bf16_sqrt`
> “The human wrote a generic binary-search algorithm to compute a square root, but I notice it is called only with the constants **4.0** and **9.0**.
> Since I already know at compile time that `sqrt(4.0)` is **2.0** and `sqrt(9.0)` is **3.0**, why should I keep the whole algorithm?
> The entire loop is dead code for this run, so I’ll replace the function with a simple chain of `if` statements:
>
> ```c
> if (input == 4.0) return 2.0;
> else if (input == 9.0) return 3.0;
> ```
>
> That’s exactly what the `-O3` build produces.”
#### For `bf16_add`
> “The author implemented a fully-featured adder that handles NaNs, infinities, zeros, negative numbers and subnormals.
> In `test_arithmetic`, however, the function is called only with **1.0** and **2.0**—ordinary positive, normalized numbers.
> All branches that deal with special cases are therefore never taken; they are dead code in this context and can be eliminated.
> What’s more, the function is now tiny. Calling it would cost more (saving/restoring registers, jumping) than executing its body, so I’ll inline the simplified core path directly into `test_arithmetic`, eliminating the call overhead altogether.”
Therefore I want to optimize my own implementation—bringing its speed as close as possible to the `-O3` build—**without** sacrificing its full, general-purpose correctness.
### Optimization roadmap – from *macro* to *micro*
---
#### Phase 1 – Eliminate memory-access overhead in function calls (**top priority**)
At the moment the biggest performance bottleneck is the load/store traffic generated inside each function. Repeated stack accesses (`lw`, `sw`) are expensive.
I need to refactor the routines that violate a “high-performance ABI” style.
*Functions to tackle first*: **`bf16_eq`, `bf16_lt`**
##### Strategy
Rewrite both routines into the classic **prologue → body → epilogue** layout:
1. **Prologue** Save every incoming argument **once** to `s*` (saved) registers.
2. **Body** Operate *only* in registers—no further stack traffic.
3. **Epilogue** Restore the saved registers in one shot and return.
##### Implementation example – refactoring `bf16_eq`
*Before (slow version):*
```
bf16_eq:
addi sp, sp, -12
sw ra, 8(sp)
sw a0, 4(sp)
sw a1, 0(sp)
jal ra, bf16_isnan
# ...
lw a0, 0(sp)
jal ra, bf16_isnan
# ...
```
*After (High Performance):*
```assembly
bf16_eq:
# --- Prologue ---
addi sp, sp, -16
sw ra, 12(sp)
sw s0, 8(sp)
sw s1, 4(sp)
mv s0, a0 # Save original value of a0 into s0
mv s1, a1 # Save original value of a1 into s1
# --- Body - Use registers only ---
jal ra, bf16_isnan # a0 holds the value from s0
bnez a0, eq_false_opt
mv a0, s1 # Restore value of a1 from s1 into a0
jal ra, bf16_isnan
bnez a0, eq_false_opt
mv a0, s0 # Restore a0
jal ra, bf16_iszero
mv t0, a0
mv a0, s1 # Restore a1
jal ra, bf16_iszero
mv t1, a0
and t2, t0, t1
bnez t2, eq_true_opt
sub t2, s0, s1 # Compare directly using s0 and s1
seqz a0, t2
j eq_exit_opt
eq_true_opt:
li a0, 1
j eq_exit_opt
eq_false_opt:
li a0, 0
eq_exit_opt:
# --- Epilogue ---
lw ra, 12(sp)
lw s0, 8(sp)
lw s1, 4(sp)
addi sp, sp, 16
ret
```
*I need to perform the exact same refactoring for `bf16_lt`.*
---
#### Phase 2: Reduce Control Flow Overhead (Medium Priority)
Every jump in a loop (`j`, `bnez`) incurs a performance penalty. By reducing the number of loop iterations, I can significantly lower this overhead.
**Target Functions**: `integer_multiply`, `integer_divide_unsigned`
**Optimization Strategy**: **Loop Unrolling**. I will duplicate the loop body a few times and adjust the loop counter and step size accordingly.
**【Implementation】 Partially Unrolling `integer_multiply` (4 times):**
This is a more aggressive version that can achieve better performance.
```assembly
integer_multiply:
mv t0, a0 # Multiplicand
mv t1, a1 # Multiplier
li a0, 0 # Result
li t3, 8 # 32 bits / 4 iterations per loop = 8 loops
int_multiply_loop_unrolled:
# Iteration 1
andi t2, t1, 1
beqz t2, bit0_zero
add a0, a0, t0
bit0_zero:
slli t0, t0, 1
# Iteration 2
andi t2, t1, 2
beqz t2, bit1_zero
add a0, a0, t0
bit1_zero:
slli t0, t0, 1
# Iteration 3
andi t2, t1, 4
beqz t2, bit2_zero
add a0, a0, t0
bit2_zero:
slli t0, t0, 1
# Iteration 4
andi t2, t1, 8
beqz t2, bit3_zero
add a0, a0, t0
bit3_zero:
slli t0, t0, 1
srli t1, t1, 4 # Shift multiplier by 4 bits at once
addi t3, t3, -1
bnez t3, int_multiply_loop_unrolled
int_multiply_end:
ret
```
---
#### Phase 3: Instruction-Level Micro-Optimizations (Low Priority)
In the race for cycle counts, every saved instruction matters. I will review my code to find opportunities to accomplish the same work with fewer or faster instructions.
**Target Functions**: All functions, especially the core paths of `add`, `mul`, `div`.
**Optimization Strategies**:
1. **Eliminate Redundant Instructions**: Look for `mv` instructions that can be omitted or computations that can be merged.
2. **Choose Faster Instructions**: For example, `andi` is often faster than `and` (since one operand is an immediate).
3. **Optimize Branches**: Reorganize `if-else` structures so that the most common case is handled with the fewest jumps. This is known as **branch prediction optimization**.
**【Implementation】 Micro-optimizing the normalization part of `bf16_mul`:**
**Before:**
```assembly
li t5, 0x8000
and t5, t6, t5
beqz t5, mul_no_carry
# Carry path
j mul_round_ok
mul_no_carry:
# No carry path
```
**After (Branch Optimization):**
Assuming the "no carry" case is more common, I can let it fall through and only have the "carry" case jump.
```assembly
li t5, 0x8000
and t5, t6, t5
bnez t5, mul_handle_carry # Only jump if there is a carry
# --- No carry path (The common case) ---
srli t6, t6, 7
j mul_round_ok
mul_handle_carry:
# --- Carry path ---
srli t6, t6, 8
addi s1, s1, 1
# Fall through to mul_round_ok
mul_round_ok:
...
```
---
# Analysis
I test my code using [Ripes](https://github.com/mortbopet/Ripes) simulator.
>[!Note] AI tools usage
>I used ChatGPT to help me prepare for Quiz 1 by reviewing code concepts, improving grammar, conducting background research, summarizing implementation details, and explaining how standard RISC-V instructions are applied.
>
>I used [Compiler Explorer](https://godbolt.org/) to generate the `gcc -O3` optimized code and then refactored it using GPT.
# Reference
- [Inline assembler - Wikipedia](https://en.wikipedia.org/wiki/Inline_assembler)
- [RISC-V Instruction Set Manual](https://riscv.org//wp-content/uploads/2017/05/riscv-spec-v2.2.pdf)
- [決策樹 (Decision tree)](https://ithelp.ithome.com.tw/articles/10271143?sc=hot)
- [The as-if rule](https://en.cppreference.com/w/cpp/language/as_if.html)
Sign in with Wallet
Connect another wallet