# Quiz5 of Computer Architecture (2020 Fall)

:::info
:information_source: General Information
* You are allowed to read [lecture materials](http://wiki.csie.ncku.edu.tw/arch/schedule).
* That is, an open book exam.
* You shall not disclose your answer during the quiz.
* Each answer has **5 points**.
* :timer_clock: 09:10 ~ 10:30AM on Dec 1, 2020
:::

## Question `A`

1. Consider a cache in certain RISC-V processor with an AMAT (average memory access time) of `1.5` cycles. Accessing our cache takes `1` cycle, and on a miss, it takes an additional `10` cycles to retrieve the data from main memory and update the cache. What does our hit ratio need to be in order to achieve the target AMAT?
$\to$ Hit ratio = __ A01 __
> * A01 = ?

2. The timing for a particular cache is as follows: checking the cache takes 1 cycle. If there is a hit the data is returned to the CPU at the end of the first cycle. If there is a miss, it takes `10` additional cycles to retrieve the word from main memory, store it in the cache, and return it to the CPU. If we want an average memory access time of `1.4` cycles, what is the minimum possible value for the cache’s hit ratio?
$\to$ Minimum possible value of hit ratio: __ A02 __
> * A02 = ?

---

## Question `B`

Consider that `P1` is a five-stage pipelined RISC-V processor (IF, DEC, EXE, MEM, WB), where:
* All branches are predicted not-taken.
* Branch decisions are made in the EXE stage.
* The pipeline has **full bypassing**.

Assume that the loop shown to the right has been running for a while and will be re-executed after this iteration.

1. Given the program below. How many cycles does it take to execute one iteration of the loop on this processor?

    loop: add  x3, x2, x1
          slli x2, x2, 1
          xor  x4, x3, x4
          bnez x2, loop
          and  x11, x2, x1
          or   x12, x22, x7
          sra  x13, x23, x8
          ...

$\to$ Cycles per iteration on this processor `P1`: __ B01 __
> B01 = ?

2. Now consider that `P2` is a variant of the previous five-stage pipelined RISC-V processor (IF, DEC, EXE, MEM, WB), where:
* All branches are predicted not-taken.
* Branch decisions are made in the EXE stage.
* The pipeline has **no bypass paths**.

Assume that our example loop (same as the previous program) has been running for a while and will be re-executed after this iteration. How many cycles does it take to execute one iteration of the loop on this processor?
$\to$ Cycles per iteration on processor `P2`: __ B02 __
> * B02 = ?

---

## Question `C`

You are designing a four stage RISC-V processor (IF, DEC, EX, WB) that:
* Resolves branches in the EX stage.
* Uses a scoreboard to track and stall on data hazards.
* Initiates accesses to data memory in the EX stage, but data memory responses are not available until the WB stage.

This processor has a tight area constraint, and you only have enough area for one bypass path for read-after-write hazards. You are trying to decide whether to put the bypass path from EX to DEC or from WB to DEC. As part of this evaluation, you construct two processors:
* Processor `P1`: Bypassing from WB to DEC.
* Processor `P2`: Bypassing from EX to DEC.

These processors ensure that if the instruction in the DEC stage does not have all of its operands ready to read from the register file or read from a bypass path, the instruction in the decode stage is stalled.

You are using the following loop of a program to evaluate the performance of the processor:

loop: lw   t0, 0(a0)
      addi t1, t0, 1
      xor  t3, t1, a0
      slli t2, t1, 1
      blt  t0, a0, loop

Assume this loop has been running for a long time, and that the processor assumes that the branch will be taken.

How many cycles does this loop take to execute in each of the processors?
* Processor `P1` cycles per iteration: __ C01 __
* Processor `P2` cycles per iteration: __ C02 __
> * C01 = ?
> * C02 = ?

---

## Question `D`

Consider the execution of the following code sequence on a 5-stage pipelined RISC-V processor, which is fully bypassed. The code below iterates over the array shown below to find the index of the element whose value is 0x104. Thus, on the second iteration of the loop, it branches to label done. The instruction unimp signals the end of the program. This processor:
* Always speculates that the next instruction should come from address PC+4.
* Computes branch decisions and jump targets in the EXE stage.
* Annuls incorrectly fetched instructions resulting from branches and jump instructions.
* Receives the results of load instructions (from the data memory) in the WB stage.

The program:

. = 0x0
/* x10 holds the value we are looking for
 * x11 holds the address of A[0]
 * x13 holds the address of the current data access
 * Assume x10 = 0x104; x11 = 0x500; and x13 = 0x500 before executing the loop
 */
loop:
lw x14, 0(x13)
beq x14, x10, done
addi x13, x13, 4
j loop
done:
sub x13, x13, x11
srli x13, x13, 2
unimp
. = 0x500
/* Array data */
.word 0x0000100 /* A[0] */
.word 0x0000104 /* A[1] */
.word 0x0000108 /* A[2] */
.word 0x000010C /* A[3] */

1. Are any instructions stalled in the decode (DEC) stage during execution of this loop? If so, list the opcode(s) here. If not, write `N/A`.
$\to$ Instructions stalled in DEC stage: __ D01 __
> * D01 = ?

2. How many NOPs, if any, are inserted into the pipeline to handle the stalls required for execution of one iteration of the loop?
$\to$ Number of NOPs added to handle stalls: __ D02 __
> * D02 = ?

3. How many cycles does one iteration of the loop (first iteration, i.e. lw -> beq -> addi -> j -> sub -> srli) take?
$\to$ Number of cycles for one iteration of the loop: __ D03 __
> * D03 = ?

4. How many NOPs, if any, are inserted into the pipeline to handle the final iteration of the loop through the end of the program?
$\to$ Number of NOPs added to handle stalls: __ D04 __
> * D04 = ?

5. Which additional instructions, if any, would need to be stalled if the processor did not have a bypass path from the EXE stage but still had one from the MEM and WB stages?
$\to$ Instructions stalled due to removal of EXE bypass path: __ D05 __
> * D05 = ?

6. How many additional NOPs, if any, are required to handle the removal of the EXE bypass path?
$\to$ Number of NOPs required to handle removal of EXE bypass path: __ D06 __
> * D06 = ?

---

## Question `E`

Consider a direct-mapped cache with 64 total data words with 1 word/cache line.

The program shown below repeatedly executes an inner loop that sums the 16 elements of an array that is stored starting in location `0x310`.

 . = 0 /* tell assembler to start at address 0 */
outer_loop:
    addi x4, x0, 16 // initialize loop index J
    mv x1, x0 // x1 holds sum, initially 0
loop: // add up elements in array
    subi x4, x4, 1 // decrement index
    slli x2, x4, 2 // convert to byte offset
    lw x3, 0x310(x2) // load value from A[J]
    add x1, x1, x3 // add to sum
    bne x4, x0, loop // loop until all words are summed
    j outer_loop // perform test again!

The program is executed for many iterations, then a measurement of the cache statistics is made during one iteration through all the code, i.e., starting with the execution of the instruction labeled `outer_loop:` until just before the next time that instruction is executed.

1. In total, how many instruction fetches occur during one complete iteration of the outer loop? How many data reads?
$\to$ Number of instruction fetches: __ E01 __
$\to$ Number of data reads: __ E02 __
> * E01 = ?
> * E02 = ?

2. The memory address has 32 bits total which will be divided up into bits for the tag, index, block offset and byte offset.
- Since there are 64 total words with 1 word/cache line, there must be 64 cache lines.
- The index bits must fully index into these 64 lines. This requires 6 bits.
- Each cache line holds one block which is specified to be one word (32 bits or 4 bytes).
- Since there is only one word in each block, we need no bits (i.e. 0 bits) for this offset. Since each byte has its own address, we need four possible offsets into each block. Thus, the two bits are sufficient for the byte offset.
- Tag: 24 bits, Index: 6 bits, Block offset: 0 bits, Byte offset: 2 bits.

For each memory access, we look at bits `[7:2]` of the address to determine which index in the cache that particular memory address maps to.
- Remember that both instructions and the array are stored in memory. Thus, each instruction fetch is a memory access and is also cached along with all "normal" memory accesses in the form of `lw` instructions.
- Also note that this program has been executing for multiple cycles already.

Thus, many slots in the cache are already populated. We need to figure out which ones will result in cache misses. As we walk through the program for the first time, we will not count initializing the cache contents as cache misses. How many instruction fetch misses occur during one complete iteration of the outer loop? How many data read misses? Hint: remember that the array starts at address 0x310.
$\to$ Number of instruction fetch misses: __ E03 __
$\to$ Number of data read misses: __ E04 __
> * E03 = ?
> * E04 = ?

3. What is the hit ratio measured after one complete iteration of the outer loop?
$\to$ Hit ratio: __ E05 __
> * E05 = ?

---

## Question `F`

Assume, the program shown below is being run on a RISC-V processor with a cache with the following parameters:
* 2-way set-associative
* block size of 2, i.e., 2 data words are stored in each cache line
* total number of data words in the cache is 32
* LRU replacement strategy

. = 0x240 // start of program
test:
    addi x4, x0, 16 // initialize loop index J to size of array
    mv x1, x0 // x1: sum
loop: // add up elements in array
    subi x4, x4, 1 // decrement index
    slli x2, x4, 2 // convert to byte offset
    lw x3, 0x420(x2)// load value from A[J]
    add x1, x1, x3 // add to sum
    bnez x4, loop // loop N times
    j test // perform test again!
// allocate space to hold array
. = 0x420
A: .word A[0]
 .word A[1]

1. The cache will divide the 32-bit address supplied by the processor into four fields: 2 bits of byte offset, B bits of block offset, L bits of cache line index, and T bits of tag field. Based on the cache parameters given above, what are the appropriate values for B, L, and T?
$\to$ value for B: __ F01 __
$\to$ value for L: __ F02 __
$\to$ value for T: __ F03 __
> * F01 = ?
> * F02 = ?
> * F03 = ?

2. If the `SLLI` instruction is resident in a cache line, what will be its cache line index? the value of the tag field for the cache?
$\to$ Cache line index for SLLI when resident in cache: __ F04 __
$\to$ Tag field for SLLI when resident in cache: __ F05 __
> * F04 = ?
> * F05 = ?

3. Given that the code begins at address `0x240` and the array begins at address `0x420`, and that there are 16 elements in the array as shown in the code above, list all the values j ($0 \le j \le 16$) where the location holding the value `A[j]` will map to the same cache line index as the `SLLI` instruction in the program.
$\to$ List all `j` where `A[j]` have the same cache line index as `SLLI`: __ F06 ___
> * F06 = ?

---

## Question `G`

Consider a 2-way set-associative cache where each way has 4 cache lines with a **block size of 2 words**. Each cache line includes a valid bit (V) and a dirty bit (D), which is used to implement a write-back strategy. The replacement policy is least-recently-used (LRU). The cache is used for both instruction fetch and data (LD,ST) accesses. Please use this cache when answering questions (A) through (D).

1. Using this cache, a particular benchmark program experiences an average memory access time (AMAT) of 1.3 cycles. The access time on a cache hit is 1 cycle; the miss penalty (i.e., additional access time) is 10 cycles. What is the hit ratio when running the benchmark program?
$\to$ Hit ratio for benchmark program: __ G01 __
> * G01 = ?

2. This cache is used to run the following benchmark program. The code starts at memory address `0`; the array referenced by the code has its first element at memory address `0x200`. First determine the number of memory accesses (both instruction and data) made during each iteration through the loop. Then estimate the steady-state average hit ratio for the program, i.e., the average hit ratio after many iterations through the loop.

    . = 0
        mv x3, x0 // byte index into array
        mv x1, x0 // initialize checksum accumulator
    loop:
        lw x2, 0x200(x3) // load next element of array
        slli x1, x1, 1 // shift checksum
        addi x1, x1, 1 // increment checksum
        add x1, x1, x2 // include data value in checksum
        addi x3, x3, 4 // byte index of next array element
        slti x2, x3, 1000 // process 250 entries
        bnez x2, loop
        unimp // halt
    . = 0x200
    array:
        ... /* array content */ 

$\to$ Number of memory accesses made during each iteration of the loop: __ G02 __
$\to$ Estimated steady-state average hit ratio: __ G03 __
> * G02 = ?
> * G03 = ?

---

## Question `H`

Consider the diagram below for a 2-way set associative cache to be used with our RISC-V processor. Each cache line holds a single 32-bit word of data along with its associated tag and valid bit (`0` when the cache line is invalid, `1` when the cache line is valid).

1. The RISC-V produces 32-bit byte addresses, A[31:0]. To ensure the best cache performance, which address bits should be used for the cache index? For the tag field?
$\to$ address bits used for cache index: A[ __ H01 __]
$\to$ address bits used for tag field: A[ __ H02 __]
> * H01 = ?
> * H02 = ?

2. Suppose the processor does a read of location `0x5678`. Identify which cache location(s) would be checked to see if that location is in the cache. For each location specify the cache section (`P` or `Q`) and row number (0 through 7). E.g., `3P` for row `3`, section `P`. If there is a cache hit on this access what would be the contents of the tag data for the cache line that holds the data for this location?
$\to$ cache location(s) checked on access to `0x5678`: __ H03 __
$\to$ cache tag data on hit for location `0x5678` (hex): __ H04 __
> * H03 = ?
> * H04 = ?

3. Estimate the approximate cache hit ratio for the following program. Assume the cache is empty before execution begins (all the valid bits are 0) and that an LRU replacement strategy is used. Remember the cache is used for both instruction and data (LD) accesses.

            . = 0
            addi x4, x0, 0x100
            mv x1, x0
            lui x2, 1 // x2 = 0x1000
    loop:   lw x3, 0(x4)
            addi x4, x4, 4
            add x1, x1, x3
            addi x2, x2, -1
            bnez x2, loop
            sw x1, 0x100(x0)
            unimp // halt
            . = 0x100
    source:
            . = . + 0x4000 // Set source to 0x100, reserve 0x1000 words

$\to$ approximate hit ratio: __ H05 __
> * H05 = ?

---