Quiz4 of Computer Architecture (2024 Fall)

Solutions

Problem `A`

Implement a RISC-V function called sum_of_squares that, given an integer n, calculates the following sum:

n^{2} + (n - 1)^{2} + (n - 2)^{2} + \dots + 1^{2}

n

is not a positive integer (n ≤ 0), the function should return the value of

m

This task requires a recursive algorithm that uses the a1 register to keep track of the accumulated sum. You will implement the following function:

Function: sum_of_squares
Input:

a0: A 32-bit integer representing n. You can assume that n ≤ 10000.
a1: A 32-bit integer representing m.

Output:

The function should return in a0 the result of:

$m + n^{2} + (n - 1)^{2} + (n - 2)^{2} + \dots + 1^{2}$
If n ≤ 0, return the value of m.

You have access to a helper function square that computes the square of an integer.

Function: square
Input:

a0: An integer n.

Output:

a0 will hold the value of
$n^{2}$ .

To implement the recursive logic, consider updating the value of m at each step. Specifically, let:

m^{'} = m + n^{2}

Then, the original sum:

m + n^{2} + (n - 1)^{2} + \dots + 1^{2}

can be rewritten as:

m^{'} + (n - 1)^{2} + \dots + 1^{2}

This transformation allows you to reduce the problem size by decrementing

n

and updating

m

with the new accumulated sum (

m^{'}

). Use this approach to implement the recursive function and follow the RISC-V calling convention.

sum_of_squares:
    # Check if n (a0) is less than or equal to zero
    bgt a0, x0, recurse_case # __ A01 __

zero_case:
    # If n ≤ 0, return m (a1)
    add a0, a1, x0
    jalr x0, ra, 0 # __ A02 __

recurse_case:
    # Save caller-saved registers on the stack
    add t0, a0, x0           # t0 = a0 (copy n)
    addi sp, sp, -12         # Allocate stack space __ A03 __
    sw a1, 0(sp)             # Save a1 (m)
    sw t0, 4(sp)             # Save t0 (n)
    sw ra, 8(sp)             # Save return address __ A04 __

    # Call the square function
    jal ra, square # __ A05 __

    # Restore registers and stack
    lw a1, 0(sp)             # Restore a1 (m)
    lw t0, 4(sp)             # Restore t0 (n)
    lw ra, 8(sp)             # Restore return address __ A06 __
    addi sp, sp, 12          # Deallocate stack space __ A07 __

    # Update m = m + n^2
    add a1, a1, a0

    # Decrement n: a0 = n - 1
    addi a0, t0, -1

    # Recursive call to sum_of_squares
    addi sp, sp, -4          # Allocate stack space for ra __ A08 __
    sw ra, 0(sp)             # Save return address
    jal ra, sum_of_squares # __ A09 __
    lw ra, 0(sp)             # Restore return address
    addi sp, sp, 4           # Deallocate stack space __ A10 __

    # Return from the function
    jalr x0, ra, 0 # __ A11 __

You are required to complete the RISC-V assembly code above, ensuring that no pseudoinstructions are used.

A01 = blt x0, a0, recurse_case
A02 = jalr x0, ra, 0
A03 = addi sp, sp, -12
A04 = sw ra, 8(sp)
A05 = jal ra, square
A06 = lw ra, 8(sp)
A07 = addi sp, sp, 12
A08 = addi sp, sp, -4
A09 = jal ra, sum_of_squares
A10 = addi sp, sp, 4
A11 = jalr x0, ra, 0

From the perspective of the callee, is it necessary to save any registers in the prologue and epilogue of the function? If so, which registers need to be saved, and where should the prologue and epilogue be placed? If not, provide a brief explanation as to why. __ A12 __

A12 = (一定要有 No 或 Not，意思相近就給分)

No, we do not need to consider callee-saved registers because we are not using any in this function. However, since the function makes two function calls, it may be necessary to save the ra register in the prologue and restore it in the epilogue, right before the jalr x0, ra, 0 instruction, just before the zero_case label.

Next, we will implement the square function, which calculates the square of an integer (a0 = n) and returns the result in a0. This function adheres to the RISC-V calling convention and avoids using RV32M instructions, ensuring compatibility with the RV32I base ISA.

# Function: square
# Computes the square of an integer (a0 = n), returns result in a0
square:
    addi sp, sp, -8         # Allocate stack space
    sw ra, 0(sp)            # Save return address __ A13 __

    add t0, x0, x0          # t0 = 0 (accumulator for the result)
    add t1, a0, x0          # t1 = a0 (copy of n, multiplicand)
    add t2, a0, x0          # t2 = a0 (copy of n, multiplier)

square_loop:
    and t3, t2, x1          # Check the lowest bit of t2 (t2 & 1) __ A14 __
    beq t3, x0, skip_add    # If the bit is 0, skip addition
    add t0, t0, t1          # Accumulate: t0 += t1

skip_add:
    sll t1, t1, 1           # Left shift t1 (multiply by 2) __ A15 __
    srl t2, t2, 1           # Right shift t2 (divide by 2) __ A16 __
    bne t2, x0, square_loop # Repeat loop if t2 is not zero __ A17 __

square_end:
    add a0, t0, x0          # Move result to a0

    lw ra, 0(sp)            # Restore return address __ A18 __
    addi sp, sp, 8          # Deallocate stack space
    jalr x0, ra, 0          # Return from function __ A19 __

A13 = sw ra, 0(sp)
A14 = and t3, t2, x1
A15 = slli t1, t1, 1
A16 = srli t2, t2, 1
A17 = bne t2, x0, square_loop
A18 = lw ra, 0(sp)
A19 = jalr x0, ra, 0

Problem `B`

Similar to logic gates, registers also experience a delay before their output reflects the sampled input. This delay is called the clock-to-Q (clk-to-q) delay, where "Q" typically denotes the output. The clk-to-q delay is the time between the rising edge of the clock signal and when the register's output updates to match the input.

In the circuit below:

Registers RegA and RegB have setup, hold, and clk-to-q times of 4 ns each.
Each logic gate has a delay of 5 ns.
Register RegC has a setup time of 6 ns.

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Determine:

What is the maximum allowable hold time for RegC? __ B01 __ ns
What is the minimum acceptable clock cycle time for this circuit? __ B02 __ ns
What clock frequency does this correspond to? __ B03 __ HZ

B01 = 14
B02 = 25
B03 = 40M

The maximum allowable hold time for RegC is determined by the time it takes for the input of RegC to change. This is calculated as the clk-to-q delay of RegA or RegB plus the shortest combinational logic delay:

$4 ns + (5 ns + 5 ns) = 14 ns$

The minimum clock cycle time must account for the clk-to-q delay, the longest combinational logic delay, and the setup time of RegC:

$4 ns + (5 ns + 5 ns + 5 ns) + 6 ns = 25 ns$

A clock cycle time of 25 ns corresponds to a clock frequency of:

$\frac{1}{25 \times 10^{- 9} s} = 40 MHz$

Problem `C`

Consider a left-complete binary search tree represented as an array. For example:

nodes = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

The corresponding binary tree structure is:

                8  (index 0)
        4  (index 1)      12 (index 2)
    2 (index 3)   6 (index 4)   10 (index 5)   14 (index 6)
  1 (index 7) 3 (index 8) 5 (index 9) 7 (index 10) 9 (index 11) 11 (index 12) 13 (index 13) 15 (index 14)

To find the position of elements in sorted order, we perform an in-order traversal (left-root-right) on this tree. The sorted order is:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Let's go through two specific examples:

3rd Element in Sorted Order:
- The 3rd element in the sorted order is 3.
- In the array representation (nodes), 3 is at index 8 (0-based).
- In 1-based indexing, this corresponds to position 9.
7th Element in Sorted Order:
- The 7th element in the sorted order is 7.
- In the array representation (nodes), 7 is at index 10 (0-based).
- In 1-based indexing, this corresponds to position 11.

This example demonstrates how elements in a left-complete, array-based binary search tree can be efficiently accessed and positioned based on their sorted order.

Sorted Order	Element	0-Based Index	1-Based Position
3rd	3	8	9
7th	7	10	11

Now let's generalize the problem. Suppose we want to find the position of the

k

-th element in sorted order for a subtree rooted at position

p

with a given height

h

Define the function:

k_child(p, h, k)

$p$ : Position of the root of the subtree (1-based indexing).
$h$ : Height of the subtree (a tree with a single node has height 0).
$k$ : The rank of the desired element in sorted order.

For example:

For the subtree rooted at position
$p = 3$ (element 12) with height
$h = 2$ , the 3rd element in sorted order is at position 13 (element 11).
For
$p = 3$ ,
$h = 1$ , and
$k = 3$ , the 3rd element is at position 7 (element 7).

The typical method involves traversing the tree using a loop, utilizing the fact that the left and right child positions can be calculated as

2 \times p

and

2 \times p + 1

, respectively. This approach has a time complexity of

O (b^{2})

, where

b

is the number of bits in the integer representation (commonly 32 bits).

We can achieve a more efficient solution with a time complexity of

O (b)

using a direct bitwise calculation:

#define k_child(p, h, k) (((p << h) | (k >> 1)) / (k & (~(k - 1))))

$p ≪ h$ : Shifts the position
$p$ left by
$h$ bits, effectively scaling the root position to the height of the subtree.
$k ≫ 1$ : Shifts
$k$ right by 1 bit, halving it and adjusting for 0-based indexing.

The proposed approach avoids iterative traversal, greatly speeding up the computation, and you should complete the above. Explain whether the division (/) operation could become a performance bottleneck in this

O (b)

solution. __ C02 __

C01 = ~(k - 1) (或等效的形式)

$k & ((k - 1))$ : Isolates the least significant bit set in
$k$ , which represents the smallest power of 2 divisor of
$k$ .

C02 = (意思相近就給分，務必提到 power of 2)

Since the division operation is performed by a power of 2, the compiler optimizes it into a bit shift. This results in an efficient
$O (b)$ solution for finding the
$k$ -th element in a left-complete, array-based binary tree.

Problem `D`

We have several addressing modes for accessing memory (excluding the immediate mode):

Base Displacement Addressing: Adds an immediate value to a register's value to form a memory address (used by instructions like lw, lb, sw, and sb).
PC-Relative Addressing: Uses the current value of the program counter (PC) and adds the immediate value (multiplied by 2) from the instruction to form a target address (used by branch and jump instructions).
Register Addressing: Uses the value in a register as the target address (e.g., jalr, jr, and ret, where jr and ret are pseudoinstructions translated into jalr).

What is the maximum range of 32-bit instructions that can be reached from the current PC using a jump instruction?
The range covers addresses within

[- 2^{18}, 2^{18} - 1]

instructions from the current PC.

D01 =

- 2^{18}

D02 =

2^{18} - 1

The immediate field for the jal instruction is 20 bits, while for the jalr instruction, it is only 12 bits. This means jal can cover a wider range of addresses. Similar to the previous addressing mode, the 20-bit immediate value is multiplied by 2 and added to the program counter (PC) to determine the target address. Since the immediate value is signed, it spans a range of
$[- 2^{20}, 2^{20} - 2]$ bytes, or
$[- 2^{19}, 2^{19} - 1]$ 2-byte instructions. However, because we are dealing with 4-byte instructions, the effective range is
$[- 2^{18}, 2^{18} - 1]$ instructions relative to the current PC.

Assume we are implementing a minimal RISC-V RV32I disassembler, which operates as follows:

Disassembling raw binary: jalr.bin
   0:  00000097          auipc     x1, 0x0    
   4:  00808093          addi      x1, x1, 8
   8:  06428293          addi      x5, x5, 100
   c:  00008067          jalr      x0, x1, 0

You need to complete the program by filling in the specified placeholders, such as D03 and D04.

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;

typedef int32_t s32;

/* stream of 32 bit fixed length instructions */
struct progbits {
    u32 size;
    u32 *data;
};

static struct progbits loadbits_raw(char *filename)
{
    FILE *f = fopen(filename, "rb");
    unsigned int size;
    fseek(f, 0, SEEK_END);
    size = ftell(f);
    fseek(f, 0, SEEK_SET);
    u32 *text = malloc(size);
    fread(text, size, 1, f);
    fclose(f);
    return (struct progbits) {size / sizeof(u32), text};
}

enum format { R, I, S, B, U, J };

struct {
    u8 opcode; /* 7-bit */
    enum format fmt;
} opcodefmt[] = {
    {0x37, U}, {0x17, U}, {0x6f, J}, {0x67, I}, {0x63, B}, {0x03, I},
    {0x23, S}, {0x13, I}, {0x33, R}, {0x0f, I}, {0x73, I},
};

union encoding {
    u32 insn;
    struct { /* generic */
        u32 opcode : 7;
        u32 rd : 5;
        u32 funct3 : 3;
        u32 rs1 : 5;
        u32 rs2 : 5;
        u32 funct7 : 7;
    };
    struct {
        u32 opcode : 7;
        u32 rd : 5;
        u32 funct3 : 3;
        u32 rs1 : 5;
        u32 rs2 : 5;
        u32 funct7 : 7;
    } r;
    struct {
        u32 opcode : 7;
        u32 rd : 5;
        u32 funct3 : 3;
        u32 rs1 : 5;
        s32 i11_0 : 12; /* sign extension */
    } i;
    struct {
        u32 opcode : 7;
        u32 i4_0 : 5;
        u32 funct3 : 3;
        u32 rs1 : 5;
        u32 rs2 : 5;
        s32 i11_5 : 7; /* sign extension */
    } s;
    struct {
        u32 opcode : 7;
        u32 i11 : 1;
        u32 i4_1 : 4;
        u32 funct3 : 3;
        u32 rs1 : 5;
        u32 rs2 : 5;
        u32 i10_5 : 6;
        s32 i12 : 1; /* sign extension */
    } b;
    struct {
        u32 opcode : 7;
        u32 rd : 5;
        u32 i31_12 : 20;
    } u;
    struct {
        u32 opcode : 7;
        u32 rd : 5;
        u32 i19_12 : 8;
        u32 i11 : 1;
        u32 i10_1 : 10;
        s32 i20 : 1; /* sign extension */
    } j;
};

static int format(u8 opcode)
{
    for (int i = 0, n = sizeof opcodefmt / sizeof opcodefmt[0]; i < n; ++i)
        if (opcode == opcodefmt[i].opcode) return opcodefmt[i].fmt;
    return -1;
}

static char *iname(u32 insn)
{
    union encoding e = {insn};
    switch (format(e.opcode)) {
    case R:
        switch (e.funct3) {
        case 0: return e.funct7 ? "sub" : "add";
        case 1: return "sll";
        case 2: return "slt";
        case 3: return "sltu";
        case 4: return "xor";
        case 5: return e.funct7 ? "sra" : "srl";
        case 6: return "or";
        case 7: return "and";
        }
        break;
    case I:
        switch (e.opcode) {
        case 0x67: return "jalr"; /* D03 */
        case 0x03:
            switch (e.funct3) {
            case 0: return "lb";
            case 1: return "lh";
            case 2: return "lw";
            case 4: return "lbu"; /* D04 */
            case 5: return "lhu"; /* D05 */
            }
            break;
        case 0x13:
            switch (e.funct3) {
            case 0: return "addi";
            case 1: return "slli"; /* D06 */
            case 2: return "slti"; /* D07 */
            case 3: return "sltiu"; /* D08 */
            case 4: return "xori";
            case 5: return e.funct7 ? "srai" : "srli";
            case 6: return "ori";
            case 7: return "andi"; /* D09 */
            }
            break;
        case 0x0f:
            switch (e.funct3) {
            case 0: return "fence";
            case 1: return "fence.i";
            }
            break;
        case 0x73:
            switch (e.funct3) {
            case 0: return e.rs2 ? "ebreak" : "ecall"; /* D10 */
            case 1: return "csrrw";
            case 2: return "csrrs"; /* D11 */
            case 3: return "csrrc";
            case 5: return "csrrwi";
            case 6: return "csrrsi";
            case 7: return "csrrci";
            }
            break;
        }
        break;
    case S:
        switch (e.funct3) {
        case 0: return "sb";
        case 1: return "sh";
        case 2: return "sw";
        }
        break;
    case B:
        switch (e.funct3) {
        case 0: return "beq";
        case 1: return "bne";
        case 4: return "blt";
        case 5: return "bge";
        case 6: return "bltu"; /* D12 */
        case 7: return "bgeu"; /* D13 */
        }
        break;
    case U:
        switch (e.opcode) {
        case 0x37: return "lui"; /* D14 */
        case 0x17: return "auipc"; /* D15 */
        }
        break;
    case J: return "jal"; /* D16 */
    }

    return NULL;
}

static char *op0(u32 insn)
{
    union encoding e = {insn};
    char *name = calloc(16 + 1, sizeof *name);
    switch (format(e.opcode)) {
    case R:
    case I: sprintf(name, "x%d", e.rd); break;
    case S: sprintf(name, "x%d", e.rs2); break;
    case B: sprintf(name, "x%d", e.rs1); break;
    case U:
    case J: sprintf(name, "x%d", e.rd); break;
    }
    return name;
}

static char *op1(u32 insn)
{
    union encoding e = {insn};
    char *name = calloc(16 + 1, sizeof *name);
    switch (format(e.opcode)) {
    case R:
    case I:
    case S: sprintf(name, "x%d", e.rs1); break;
    case B: sprintf(name, "x%d", e.rs2); break;
    case U: sprintf(name, "0x%x", e.u.i31_12); break; /* D17 */
    case J:
        sprintf(name, "%d",
                (e.j.i20 << 20) | (e.j.i19_12 << 12) | (e.j.i11 << 11) |
                    (e.j.i10_1 << 1)); /* D18 */
        break;
    }
    return name;
}

static char *op2(u32 insn)
{
    union encoding e = {insn};
    char *name = calloc(16 + 1, sizeof *name);
    switch (format(e.opcode)) {
    case R: sprintf(name, "x%d", e.rs2); break;
    case I: sprintf(name, "%d", e.i.i11_0); break;
    case S: sprintf(name, "%d", (e.s.i11_5 << 5) | e.s.i4_0); break; /* D19 */
    case B:
        sprintf(name, "%d",
                (e.b.i12 << 12) | (e.b.i11 << 11) | (e.b.i10_5 << 5) |
                    (e.b.i4_1 << 1)); /* D20 */
        break;
    case U: break;
    case J: break;
    }
    return name;
}

int main(int argc, char **argv)
{
    if (argc < 2) return 1;
    struct progbits pb;
    printf("disassembling raw binary %s\n", argv[1]);
    pb = loadbits_raw(argv[1]);

    for (u32 i = 0, n = pb.size, insn = pb.data[i]; i < n;
         ++i, insn = pb.data[i])
        printf("%4x:  %08x          %-8s %3s %3s %3s\n", 4 * i, insn,
               iname(insn), op0(insn), op1(insn), op2(insn));
    return 0;
}

D03 = "jalr"
D04 = "lbu"
D05 = "lhu"
D06 = "slli"
D07 = "slti"
D08 = "sltiu"
D09 = "andi"
D10 = "ecall"
D11 = "csrrs"
D12 = "bltu"
D13 = "bgeu"
D14 = "lui"
D15 = "auipc"
D16 = "jal"
D17 = e.u.i31_12
D18 = e.j.i10_1 << 1
D19 = e.s.i11_5 << 5
D20 = e.b.i4_1 << 1

Problem `E`

The critical path is the longest delay path between state elements in a circuit. The circuit’s clock speed cannot exceed this limit, as a faster clock would not allow sufficient time for the correct value to propagate to the state elements. By placing additional registers along the critical path, we can reduce the clock period by decreasing the amount of logic between registers.

The delay times for each circuit element are as follows:

For a single-cycle CPU, how long does it take to execute each instruction? Disregard the clock cycle duration based on the critical path, and assume that the setup times for both the register file (RegFile) and the program counter (PC) are identical.

sw : __ E01 __ ns
lw : __ E02 __ ns
jal : __ E03 __ ns

E01 = 665

sw = clk-to-Q + Mem-Read + max(RegFileRead + Mux(ASel), Imm-Gen +
Mux(BSel)) + ALU + DMEM Setup
= 5ns + 300 ns + 60ns + 100ns + 200ns
= 665ns

E02 = 800

lw = clk-to-Q + Mem-Read + max(RegFileRead + Mux(ASel), Imm-Gen +
Mux(BSel)) + ALU + Mem-Read + Mux(WBSel) + RegFileSetup
= 5ns + 300ns + 60ns + 100ns + 300ns + 15ns + 20ns
= 800ns

E03 = 500

jal= clk-to-Q + Mem-Read + Imm-Gen + Mux(BSel) + ALU + Mux(PCSel) + PCSetup
= 5ns + 300ns + 45ns + 15ns + 100ns + 15ns + 20ns
= 500ns

The top diagram shows the standard single-cycle datapath, while the second diagram illustrates a modified version. Referring to the modified single-cycle datapath, consider the information that must be carried forward from one stage to the next. Which pipeline registers are necessary at the end of each stage?

MEM to WB:

__ E04 __: input into WBSel mux.
__ E05 __: input into WBSel mux.
__ E06 __: input into WBSel mux.
__ E07 __: input into next stage’s control logic.

E04 = PC + 4 注意: E04-E06 的順序可換
E05 = ALUOut
E06 = MEM
E07 = Inst

EX to MEM:

__ E08 __: input into the +4 block in the MEM stage.
__ E09 __: is an input into DMEM.
__ E10 __: is an input into DMEM,
__ E11 __: input into next stage’s control logic.

E08 = PC
E09 = ALUOut 注意: E09 和 E10 的順序可換
E10 = RegReadData2
E11 = Inst

Problem `F`

For all questions, assume there is no branch prediction or double-pumping (i.e., no write-then-read in a single cycle for the RegFile). Most data hazards can be resolved through forwarding, where the result from the EX or MEM stage is sent directly to the EX stage for use by a subsequent instruction.

Note: How is forwarding (EX to EX or MEM to EX) implemented in hardware? We add two wires: one from the start of the MEM stage carrying the ALU output, and another from the start of the WB stage. Both wires connect to the A/B multiplexers in the EX stage.

Identify data hazards in the code below and determine how forwarding could be used to resolve them.

There are two data hazards: one between instructions __ F01 __ and __ F02 __ , and another between instructions __ F03 __ and 3. The first hazard can be resolved by forwarding the ALU output from the __ F04 __ stage in cycle C3 to the start of the __ F05 __ stage in cycle C4. The second hazard can be resolved by forwarding the ALU output from the __ F06 __ stage in cycle C4 to the start of the __ F07 __ stage in cycle C5.

F01 = 1
F02 = 2
F03 = 1
F04 = MEM
F05 = EX
F06 = WB
F07 = EX

Identify the data hazards in the code below. One of them cannot be resolved using forwarding—why not? How can we address this issue?

There are two data hazards present in the code:

The first hazard is between instructions __ F08 __ and __ F09 __ , involving the register t0.
The second hazard is between instructions __ F10 __ and __ F11 __ , involving the register t1.

The hazard between instructions __ F12 __ and __ F13 __ can be resolved using forwarding. However, the hazard between instructions __ F14 __ and __ F15 __ cannot be resolved with forwarding. This is because instruction __ F16 __ requires the result of instruction __ F17 __ at the beginning of cycle C6, but the result is not available until the end of cycle C6.

To resolve this, we can introduce a stall by inserting a nop (no-operation) instruction between instructions __ F18 __ and __ F19 __.

F08 = 2
F09 = 3
F10 = 3
F11 = 4
F12 = 2
F13 = 3
F14 = 3
F15 = 4
F16 = 4
F17 = 3
F18 = 3
F19 = 4

Imagine you are the compiler and can reorder instructions to minimize data hazards while still producing the same output. How would you modify the code? Reorder the instructions as __ F20 __ , since instruction 1 has no dependencies and can be moved without affecting the result.

F20 = 2-3-1-4

For the RISC-V code provided below and a pipelined CPU without forwarding, how many data hazards would occur? __ F21 __

F21 = 4

There are four hazards: a data hazard from t1 between instructions 1 and 2, a data hazard from s0 between instructions 2 and 3, another data hazard from s0 between instructions 2 and 4, and a control hazard between instructions 4 and 5.

How many stalls would be required to resolve the data hazard(s) if the RegFile supports double-pumping (i.e., write-then-read capability)? __ F22 __

F22 = 2

Assuming the RegFile allows simultaneous read and write operations in the same cycle, two stalls are needed between instructions 1 and 2 (WB → ID), and another two stalls are needed between instructions 2 and 3 (WB → ID).

Problem `G`

In Chisel, hardware components are referred to as modules. Each module extends the Module class and includes a field named io for defining its interface. The interface is specified using a Bundle, which is wrapped with a call to IO(). The Bundle contains fields representing the input and output ports of the module. The direction of these ports is specified using Input() or Output(), based on the perspective of the component itself.

We will demonstrate this with a simple design where a counter is constructed using two components: an adder and a register. Next, we create a counter using these two components that counts from 0 to 9 and then resets. The schematic of the counter is depicted below.

An adder is used to increment the current counter value by 1. A multiplexer selects between the incremented value and 0. The result of this selection, referred to as next, is used as the input to the register component. The output of the register represents the current count value and also serves as the output of the Count10 module (dout).

The following shows the Chisel code for the Count10 module. The two components are instantiated using new, wrapped with Module(), and assigned the names add and reg. The register's output (reg.io.q) is given the name count.

class Adder extends Module {
  val io = IO(new Bundle {
    val a = Input(UInt (8.W))
    val b = Input(UInt (8.W))
    val y = Output(UInt (8.W))
  })
  io.y := io.a + io.b
}

class Register extends Module {
  val io = IO(new Bundle {
    val d = Input(UInt (8.W))
    val q = Output(UInt (8.W))
  })
  val reg = RegInit (0.U)
  reg := io.d
  io.q := reg
}

class Count10 extends Module {
  val io = IO(new Bundle {
    val dout = Output(UInt (8.W))
  })
  val add = Module(new Adder ())
  val reg = Module(new Register ())

  // the register output
  val count = reg.io.q // G01

  // connect the adder
  add.io.a := 1.U
  add.io.b := count
  val result = add.io.y

  // connect the Mux and the register input
  val next = Mux(count === 9.U, 0.U, result) // G02
  reg.io.d := next // G03
  io.dout := count
}

We connect 1.U and count to the inputs of the adder component. The adder's output is named result. The multiplexer selects between 0.U and result based on the current counter value (count). The output of the multiplexer, named next, is connected to the input of the register component. Finally, we connect the counter value (count) to the output of the Count10 module (io.dout).

Complete the above to make the design work.

G01 = reg.io.q
G02 = Mux(count === 9.U, 0.U, result)
G03 = reg.io.d := next

A key component in circuits that perform computation, such as a microprocessor, is the Arithmetic Logic Unit (ALU). The figure below depicts the symbol of an ALU.

The ALU has two data inputs, labeled a and b, one function input labeled fn, and an output labeled y. The ALU processes inputs a and b and produces the result at the output y. The fn input determines which operation is applied to a and b. Typical operations include arithmetic functions like addition and subtraction, as well as logical functions like AND, OR, and XOR, hence the name ALU.

The ALU is typically a combinational circuit with no state elements. It may also include additional outputs to indicate specific properties of the result, such as whether the result is zero or its sign.

The following code defines an ALU with 16-bit inputs and outputs, supporting addition, subtraction, OR, and AND operations, selected by a 2-bit fn signal.

import chisel3.util._

class Alu extends Module {
  val io = IO(new Bundle {
    val a = Input(UInt (16.W))
    val b = Input(UInt (16.W))
    val fn = Input(UInt (2.W))
    val y = Output(UInt (16.W)) // G04
  })
    
  // some default value is needed
  io.y := 0.U

  // The ALU selection
  switch(io.fn) {
    is (0.U) { io.y := io.a + io.b }
    is (1.U) { io.y := io.a - io.b }
    is (2.U) { io.y := io.a | io.b }
    is (3.U) { io.y := io.a & io.b } // G05
  }
}

G04 = val y = Output(UInt (16.W))
G05 = io.y := io.a & io.b

Problem `H`

Examine the following RISC-V assembly code for the floating-point addition function (fadd), designed for single-precision floating-point addition using custom bitwise operations. Your task is to complete the code so that it functions as intended. This version includes simplified rounding logic, which may need enhancements for full IEEE 754 compliance.

fadd:
    # Unpack exponent of X
    srl     a2, a0, 23          # A2 = A0 >> 23
    andi    a2, a2, 0xFF        # A2 = A2 & 0xFF (Exponent of X)

    # Unpack exponent of Y
    srl     a3, a1, 23          # A3 = A1 >> 23
    andi    a3, a3, 0xFF        # A3 = A3 & 0xFF (Exponent of Y)

    # Flush-to-zero: if X exponent is zero, return Y
    beqz    a2, __addsf_return_y_flushed

    # If Y exponent is zero, return X
    beqz    a3, __addsf_return_x

    # Unpack significands and prepare for alignment
    slli    a4, a0, 9           # A4 = A0 << 9
    slli    a5, a1, 9           # A5 = A1 << 9

    # Check for NaN or Infinity
    li      t0, 255
    beq     a2, t0, __addsf_x_nan_inf
    beq     a3, t0, __addsf_y_nan_inf

    # Finish unpacking significands
    srli    a4, a4, 6           # A4 = A4 >> 6
    srli    a5, a5, 6           # A5 = A5 >> 6

    # Restore the implicit '1' bit
    li      t1, 1 << (23 + 3)   # t1 = 1 << 26
    or      a4, a4, t1          # A4 |= t1
    or      a5, a5, t1          # A5 |= t1

    # Negate significand of X if sign bit is set
    srl     t2, a0, 31          # t2 = A0 >> 31, H01
    andi    t2, t2, 1
    beq     t2, x0, skip_neg_x
    neg     a4, a4              # A4 = -A4
skip_neg_x:
    # Store 25 in t1
    li      t1, 25

    # Negate significand of Y if sign bit is set
    srl     t2, a1, 31          # t2 = A1 >> 31, H02
    andi    t2, t2, 1
    beq     t2, x0, skip_neg_y
    neg     a5, a5              # A5 = -A5
skip_neg_y:
    # Compare exponents
    bltu    a2, a3, __addsf_ye_gt_xe  # If A2 < A3, swap operands

    # Proceed with addition where exponent of X >= exponent of Y
__addsf_xe_gte_ye:
    # Compute exponent difference
    sub     t3, a2, a3          # t3 = exp_lhs - exp_rhs

    # Check if exponent difference is too large
    bgeu    t3, t1, __addsf_return_x  # If difference >= 25, return X

    # Shift significand of Y (rhs) right by exponent difference
    sra     a5, a5, t3          # A5 = A5 >> t3

    # Set sticky bit if bits were shifted out
    sll     t4, a5, t3          # t4 = A5 << t3
    sltu    t4, t4, a5          # t4 = (t4 < A5) ? 1 : 0
    or      a5, a5, t4          # A5 |= t4

    # Add significands
    add     a4, a4, a5          # A4 = A4 + A5

    # Check for zero result
    beqz    a4, __addsf_return_0

    # Convert from two's complement to sign-magnitude
    srai    t2, a4, 31          # t2 = Sign of result
    xor     a4, a4, t2          # If negative, invert bits
    sub     a4, a4, t2          # If negative, add 1

    # Normalize the result
    li      t5, 0               # t5 will count leading zeros
norm_loop_xe_gte_ye:
    sll     t4, a4, 1           # t4 = A4 << 1
    bltz    t4, norm_done_xe_gte_ye  # If MSB is 1, done
    addi    t5, t5, 1           # Increment leading zero count
    sll     a4, a4, 1           # Shift A4 left
    j       norm_loop_xe_gte_ye
norm_done_xe_gte_ye:
    sub     a2, a2, t5          # Adjust exponent

    # Check for underflow or overflow
    bgeu    a2, t0, overflow_xe_gte_ye  # If exponent >= 255, overflow, H03
    bltz    a2, underflow_xe_gte_ye     # If exponent < 0, underflow

    # Pack the result
    slli    a2, a2, 23          # Shift exponent to position
    srli    a4, a4, 9           # Align significand, H04
    or      a0, a2, a4          # Combine exponent and significand

    # Restore sign
    sll     t2, t2, 31          # Shift sign bit back, H05
    or      a0, a0, t2          # Set sign bit

    # Return
    jalr    x0, ra, 0

# Handle underflow
underflow_xe_gte_ye:
    add     a0, x0, x0          # Return zero
    jalr    x0, ra, 0

# Handle overflow
overflow_xe_gte_ye:
    li      a0, 0x7F800000      # Set to Infinity, H06
    sll     t2, t2, 31          # Shift sign bit back, H07
    or      a0, a0, t2          # Set sign bit
    jalr    x0, ra, 0

# Case where exponent of Y > exponent of X
__addsf_ye_gt_xe:
    # Swap operands and repeat the process
    mv      t6, a0              # Temporarily store A0
    mv      a0, a1              # A0 = A1
    mv      a1, t6              # A1 = original A0
    mv      t6, a2              # Swap exponents
    mv      a2, a3
    mv      a3, t6
    mv      t6, a4              # Swap significands
    mv      a4, a5
    mv      a5, t6
    j       __addsf_xe_gte_ye   # Jump to the same handling

# Handle NaN or Infinity for X
__addsf_x_nan_inf:
    add     a0, a0, x0          # Return X
    jalr    x0, ra, 0

# Handle NaN or Infinity for Y
__addsf_y_nan_inf:
    add     a0, a1, x0          # Return Y
    jalr    x0, ra, 0

# Return Y if X is zero
__addsf_return_y_flushed:
    add     a0, a1, x0          # A0 = Y
    jalr    x0, ra, 0

# Return X if Y is zero
__addsf_return_x:
    jalr    x0, ra, 0

# Return zero result
__addsf_return_0:
    add     a0, x0, x0          # A0 = 0
    jalr    x0, ra, 0

H01 = srli t2, a0, 31
H02 = srli t2, a1, 31
H03 = bgeu a2, t0, overflow_xe_gte_ye
H04 = srli a4, a4, 9
H05 = slli t2, t2, 31
H06 = 0x7F800000
H07 = slli t2, t2, 31

Consider the following implementation of converting a signed 32-bit integer to a single-precision floating-point number (IEEE 754 format) using the RISC-V RV32I assembly. The focus is on understanding the low-level operations required to perform this conversion without relying on pseudo-instructions or extended instruction sets.

# Convert signed int to float
# float i2f(s32 num);
# INPUT:  A0 = integer number
# OUTPUT: A0 = float number (IEEE 754 single-precision)
i2f:
    # Prepare result sign in A1
    srli    a1, a0, 31          # A1 = (A0 >> 31), extract sign bit
    slli    a1, a1, 31          # A1 = A1 << 31, position sign bit at bit 31

    # Get absolute value of the number
    beq     a1, x0, positive    # If sign bit is zero, number is positive
    sub     a0, x0, a0          # A0 = -A0 (negate to get absolute value)

positive:
    # Check if number is zero
    beq     a0, x0, zero_result # If A0 == 0, result is zero

    # Store sign and absolute value
    add     a2, x0, a1          # A2 = A1 (store sign)
    add     a1, x0, a0          # A1 = A0 (store absolute value)

    # Count leading zeros in A0 (result stored in T0)
    # Initialize T0 (leading zero count) to 0
    add     t0, x0, x0          # T0 = 0

clz_loop:
    sll     t1, a1, 1           # Shift A1 left by 1 bit
    addi    t0, t0, 1           # T0 = T0 + 1 (increment count)
    mv      a1, t1              # Update A1 with shifted value
    bgez    a1, clz_loop        # Loop while A1 >= 0 (MSB is 0)

    # Adjust for possible overflow in shift
    li      t1, 32              # Load 32 into t1
    blt     t0, t1, clz_done    # If t0 < 32, proceed to clz_done
    li      a0, 32              # If t0 >= 32, leading zeros = 32
    j       normalize

clz_done:
    # A0 now contains the number of leading zeros (stored in T0)
    add     a0, x0, t0          # Move T0 to A0

normalize:
    # Normalize the number (shift left by leading zeros)
    sub     t1, x0, a0          # t1 = -A0
    sll     a1, a1, t1          # A1 = A1 << (32 - leading zeros), H08

    # Prepare result exponent
    # Exponent = 158 - leading_zeros
    li      t1, 158
    sub     a0, t1, a0          # A0 = 158 - leading zeros

    # Rounding: Add 0x80 to A1 (rounding bit at position 7)
    addi    a1, a1, 128         # A1 = A1 + 0x80

    # Check for overflow after rounding
    bgez    a1, rounding_ok     # If A1 >= 0, no overflow
    addi    a0, a0, 1           # Exponent increment due to rounding overflow
    j       adjust_mantissa

rounding_ok:
    # Check if lowest 8 bits are zero (for rounding to even)
    andi    a3, a1, 0xFF        # A3 = A1 & 0xFF (lowest 8 bits)
    beq     a3, x0, round_even  # If lowest 8 bits are zero, round to even

adjust_mantissa:
    # Remove leading hidden bit '1'
    slli    a1, a1, 1           # A1 = A1 << 1 (remove hidden '1')
    j       compose_result

round_even:
    # Ensure even mantissa (clear least significant bit)
    srli    a1, a1, 9           # A1 = A1 >> 9
    slli    a1, a1, 10          # A1 = A1 << 10 (remove hidden '1'), H09
    j       compose_result

compose_result:
    # Align mantissa and exponent
    srli    a1, a1, 9           # A1 = A1 >> 9 (align mantissa to bits 0..22)
    slli    a0, a0, 23          # A0 = A0 << 23 (align exponent to bits 23..30), H10
    or      a0, a0, a1          # A0 = exponent | mantissa
    or      a0, a0, a2          # A0 = A0 | sign bit (bit 31)
    jalr    x0, ra, 0           # Return from function

zero_result:
    # Return zero (signed zero with correct sign)
    or      a0, x0, a2          # A0 = sign bit (A2)
    jalr    x0, ra, 0           # Return from function

H08 = sll a1, a1, t1
H09 = slli a1, a1, 10
H10 = slli a0, a0, 23

Quiz4 of Computer Architecture (2024 Fall)

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

Problem G

Problem H