---
tags : Computer Architecture
---
# Assignment 4 : Cache Observation
[TOC]
<style>
.red {
color: red;
}
</style>
## Exercise 1 - A Couple of Memory Access Scenarios
### Pseudo Code
:::spoiler <span class="red">*Click here to expand*</span>

int array[];  //Assume sizeof(int) == 4
for (k = 0; k < repcount; k++) { // repeat repcount times
  /* Step through the selected array segment with the given step size. */
  for (index = 0; index < arraysize; index += stepsize) {
    if(option==0)
      array[index] = 0;                // Option 0: One cache access - write
    else
      array[index] = array[index] + 1; // Option 1: Two cache accesses - read AND write
  }
}

:::
### Assembly code
[Cache.s](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/cache.s) [ from UCB summer2020 Lab7 ]
:::info
**line #30 : ~~li a0, 10~~ => li a7, 10** ( Compatible with ***Ripes*** )
:::
:::spoiler <span class="red">*Click here to expand*</span>

# Rewriten by Stephan Kaminsky in RISC-V on 7/30/2018
# This program accesses an array in ways that provide data about the cache parameters.
# Coupled with the Data Cache Simulator and Memory Reference Visualization to help students
#    understand how the cache parameters affect cache performance.
#
# PSEUDOCODE:
#    int array[];  //Assume sizeof(int) == 4
#    for (k = 0; k < repcount; k++) {		// repeat repcount times
#      /* Step through the selected array segment with the given step size. */
#      for (index = 0; index < arraysize; index += stepsize) {
#        if(option==0)
#          array[index] = 0;			// Option 0: One cache access - write
#        else
#          array[index] = array[index] + 1;	// Option 1: Two cache accesses - read AND write
#      }
#    }
.data
array:	.word	2048	# max array size specified in BYTES (DO NOT CHANGE)
.text
##################################################################################################
# You MAY change the code below this section
main:	li	a0, 128			# array size in BYTES (power of 2 < array size)
	li	a1, 8			# step size  (power of 2 > 0)
	li	a2, 4			# rep count  (int > 0)
	li	a3, 0			# 0 - option 0, 1 - option 1
# You MAY change the code above this section
##################################################################################################
	jal	accessWords		# lw/sw
	#jal	accessBytes		# lb/sb
	li	a7,10			# exit
	ecall
# SUMMARY OF REGISTER USE:
#  a0 = array size in bytes
#  a1 = step size
#  a2 = number of times to repeat
#  a3 = 0 (W) / 1 (RW)
#  s0 = moving array ptr
#  s1 = array limit (ptr)
accessWords:
	la	s0, array		# ptr to array
	add	s1, s0, a0		# hardcode array limit (ptr)
	slli	t1, a1, 2		# multiply stepsize by 4 because WORDS
wordLoop:
	beq	a3, zero,  wordZero
	lw	t0, 0(s0)		# array[index/4]++
	addi	t0, t0, 1
	sw	t0, 0(s0)
	j	wordCheck
wordZero:
	sw	zero,  0(s0)		# array[index/4] = 0
wordCheck:
	add	s0, s0, t1		# increment ptr
	blt	s0, s1, wordLoop	# inner loop done?
	addi	a2, a2, -1
	bgtz	a2, accessWords	# outer loop done?
	jr	ra
accessBytes:
	la	s0, array		# ptr to array
	add	s1, s0, a0		# hardcode array limit (ptr)
byteLoop:
	beq	a3, zero,  byteZero
	lbu	t0, 0(s0)		# array[index]++
	addi	t0, t0, 1
	sb	t0, 0(s0)
	j	byteCheck
byteZero:
	sb	zero,  0(s0)		# array[index] = 0
byteCheck:
	add	s0, s0, a1		# increment ptr
	blt	s0, s1, byteLoop	# inner loop done?
	addi	a2, a2, -1
	bgtz	a2, accessBytes	# outer loop done?
	jr	ra

:::
### Scenario 1
:::warning
* Program Parameters: (set these by initializing the a registers in the code)
* Array Size (a0): 128 (bytes)
* Step Size (a1): 8 "***words***" **(I determine from assembly code)**
* Rep Count (a2): 4
* Option (a3): 0

* Cache Parameters: (set these in the Cache tab)
* Cache Levels: 1
* Block Size: 8 "***Bytes***" **(I guess)**
* Number of Blocks: 4
* Enable?: Should be green
* Placement Policy: Direct Mapped
* Associativity: 1 (Venus won’t let you change this, why?)
* Block Replacement Policy: LRU
:::
> * Following the code below, we can find the <span class="red">**unit of StepSize**</span> is **a word** !
>>```
>>#40 : la s0, array # s0 : ptr to array
>>#41 : add s1, s0, a0 # s1 : array limit (ptr)
>>#42 : slli t1, a1, 2 # t1 : multiply StepSize by 4 (a word)
>> :
>> :
>> :
>>#52 : add s0, s0, t1 # increment : StepSize is a word !
>>```
> * Since the <span class="red">**unit of Block Size**</span> from Venus's Cache is "**Bytes**", so I guess the Block Size of Cache Parameters is 8 "**Bytes**"
>>
>>[color=#14ad40]
* **Cache Setup** (according to the parameters above)

> * "**A block**" of Ripes means a word, but "**a block**" from what we learned which means a total size of a cache line. So here I follow what I learned, "**8 bytes per cache line**"
>:::info
> * Lines : ${Number \ of \ Blocks(4) \over Associativity(1)} = 4 = 2^2$
> * Ways : $Associativity(1) = 2^0$
> * Blocks : ${Block \ Size(8 \ Bytes) \over a \ word(4 \ Bytes)} = 2 = 2^1$
>:::

* **Results**
:::info
* Hit rate = 0
* Hits = 0
* Misses = 16 (**All Misses**)
:::

* **Observation & Thinking**
* **Total access times**
The outer loop will iterate 4 times
The inner loop will iterate 4 ($ArraySize(128bytes)\over StepSize(8*4bytes)$) times
Total memory access is <span class="red">**4*4 = 16**</span> times

* **Hits & Misses**
Since the StepSize is 8 "**words**" is equal to CacheSize in bytes, so each access is at the same cache line. So, we can get the <span class="red">**16 misses**</span> totally.

* **Tasks**
1. What combination of parameters is producing the hit rate you observe? (Hint: Your answer should be of the form: “Because [parameter A] in bytes is exactly equal to [parameter B] in bytes.”)
:::success
Because StepSize in bytes is exactly equal to CahceSize in bytes
:::
2. What is our hit rate if we increase Rep Count arbitrarily? Why?
:::success
Hit rate will always 0 if we increase RepCount arbitrarily.
* Each iteration of outer loop is restart the address.
* Each iteration of inner loop is access 4 memory locations 0->8->16->24.
* So, the memory access will be 0->8->16->24->0->8->16->24->... ...->0->8->16->24->... ...
* Therefore, it will always miss since the the next address always have a difference of a multiple of 8 which is eqaul to the multiple of CacheSize.

:::
3. How could we modify one program parameter to increase our hit rate? (Hint: Your answer should be of the form: “Change [parameter] to [value].” Note: we don’t care if we access the same array elements. Just give us a program parameter modification that would increase the hit rate.
:::success
Change BlockSize to 32 bytes(8 words).
* Cache Setup
* Results
> Hit rate = 0.75
> Hits = 12
> Misses = 4
* Observation & Thinking
* Since 1 StepSize is 8 words, we can do a Cahce which is 8 words per Cache lines
* Since iteration of inner loop is 4 times, we do 4 Cache lines.
* The first 4 iteration can't avoid missing, but the rest can reuse the data load before, since they are all the same address.
* The Best Way : **Full-Associative Cache**
>Since we definitively use the same 4 address, we can do a full-associative cache that has only one set but 4 slots(ways), we can get the "<span class="red">***best Hit rate***"</span> like above but use a "<span class="red">***smaller CacheSize***"</span> than above.
:::

### Scenario 2
:::warning
* Program Parameters: (set these by initializing the a registers in the code)
* Array Size (a0): 256 (bytes)
* Step Size (a1): 2 "***words***"
* Rep Count (a2): 1
* Option (a3): 1
* Cache Parameters: (set these in the Cache tab)
* Cache Levels: 1
* Block Size: 16 "***Bytes***"
* Number of Blocks: 16
* Enable?: Should be green
* Placement Policy: N-Way Set Associative
* Associativity: 4
* Block Replacement Policy: LRU
:::
* **Cache Setup**
:::info
* Lines : ${Number \ of \ Blocks(16) \over Associativity(4)} = 4 = 2^2$
* Ways : $Associativity(4) = 2^2$
* Blocks : ${Block \ Size(16 \ Bytes) \over a \ word(4 \ Bytes)} = 4 = 2^2$
:::

* **Results**
:::info
* Hit rate : 0.75
* Hits : 48
* Misses : 16
:::

* **Observation & Thinking**
* **Total access times**
The outer loop will iterate 1 times
The inner loop will iterate 32 ($ArraySize(256bytes)\over StepSize(2*4bytes)$) times
Do Read & Write in 1 iteration = 2 accesss per iteration
Total memory access is <span class="red">**1\*32\*2 = 64**</span> times

* **Hits & Misses**
* Since the StepSize is 2 "**words**", each Cache line (4 words) has 2 datas to use (i.e. **two iterations per Cache line**).
* Each data will be access 2 times (Read & Write), so there are 4 accesses per Cache line.
* Besides the first time access the first data of the Cache line will miss, the rest will hit. So, there are <span class="red">**3 hits**</span> and <span class="red">**1 miss**</span> per Cache line.
* There are 32 iterations, so we will use ${32 \over 2}$ = <span class="red">**16**</span> Cache lines.
* Since we use a **4 sets and 4 slots Cache**, we have 4*4 = <span class="red">**16**</span> Cache lines to use.
* And because of ***LRU policy*** and the ***fixed StepSize***, no Cache line will Write-Back.
* Misses : ${32 \over 2}$ = <span class="red">**16**</span>
* Hits : Misses * 3 = <span class="red">**48**</span>

* **Tasks**
1. How many memory accesses are there per iteration of the inner loop? (not the one involving repcount). It’s not 1.
:::success
Read & Write => 2 accesses
:::
2. What is the repeating hit/miss pattern? WHY? (Hint: it repeats every 4 accesses).
:::success
1 Miss with 3 Hits.
* Since the StepSize is 2 "**words**", each Cache line (4 words) has 2 datas to use (i.e. **two iterations per Cache line**).
* Each data will be access 2 times (Read & Write), so there are 4 accesses per Cache line.
* Besides the first time access the first data of the Cache line will miss, the rest will hit. So, there are <span class="red">**3 hits**</span> and <span class="red">**1 miss**</span> per Cache line.
:::
3. This should follow very straightforwardly from the above question: Explain the hit rate in terms of the hit/miss pattern.
:::success
Hit rate = ${Hits(3) \over Hits(3) \ + \ Misses(1)} = 0.75$
:::
4. Keeping everything else the same, what happens to our hit rate as Rep Count goes to infinity? Why? Try it out by changing the appropriate program parameter and letting the code run!
:::success
Since Rep Count goes to infinity, the Hit rate will gradually close to **1**
Because all the data inner loop used will always in Cache after the first iteration of outer loop.
* Misses : fixed at **16**
* Hits : 48(first inner iteration) + 64(after first iteration)*(Rep Count - 1)
Hit rate = ${Hits \over Hits \ + \ Misses} = {all \ access(64 \ * \ Rep Count) \ - \ 16 \over all \ access(64 \ * \ Rep Count)} \approx 1 \ (as \ Rep \ Count \rightarrow \infty)$
:::

### Scenario 3
:::danger
Since Ripes only has L1\$, this Scenario I use [Venus](https://venus.cs61c.org) instead of Ripes.
:::
:::info
[Cache.s](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/cache.s) [ from UCB summer2020 Lab7 ]
line #30 : li a0, 10 ( Compatible with ***Venus*** )
:::
:::warning
* Program Parameters: (set these by initializing the a registers in the code)
* Array Size (a0): 128 (bytes)
* Step Size (a1): 1 "***words***"
* Rep Count (a2): 1
* Option (a3): 0
* Cache Parameters: (set these in the Cache tab)
* Cache Levels: 2
* L1\$
* Block Size: 8 "***Bytes***"
* Number of Blocks: 8
* Enable?: Should be green
* Placement Policy: Direct Mapped
* Associativity: 1
* Block Replacement Policy: LRU
* L2\$
* Block Size: 8 "***Bytes***"
* Number of Blocks: 16
* Enable?: Should be green
* Placement Policy: Direct Mapped
* Associativity: 1
* Block Replacement Policy: LRU
:::

* **Cache Setup**
* **L1\$**
* **L2\$**

* **Results**
* **L1\$**
* **L2\$**

* **Observation & Thinking**
* Block Size(2 words) of L1\$ is equal to L2\$
* Step Size is 1 words
* Since L1\$ Miss, L2\$ might miss too
:::info
1. Because the Block Size of L1\$ = L2\$
2. The access address increase steadily
:::
* When L1\$ Miss, L2\$ Miss too, then L2\$ load the data from main memory, then deliver it to L1\$. When next iteration L1\$ will hit since the data delivered from L2\$ last iteration is 2 words.
* Because of LRU Policy, L1\$ and L2\$ will use different Cache Line in order. Since the access address increases steadily.
* Finally, L1\$ displays all Hits is that hit the second word of each cache line. L2\$ displays all Misses is that because the access address increase steadily and not repeat, and the second word hit happen in L1\$, so L2\$ always Miss.
:::info
* **L1\$**
* Access times : ${ArraySize(128 \ Bytes) \over StepSize(1*4 \ bytes)} = 32$
* Hit rate = 0.5 (first word misses, second word hits)
* Hits = ${Access \ times(32) \over 2} = 16$
* Misses = ${Access \ times(32) \over 2} = 16$
* **L2\$**
* Access times : ${L1 \ Access \ times \over 2} = 16$
* Hit rate = 0 (**All Miss**)
* Hits = 0
* Misses = 16
* **Global**
* Global Hit rate = L1\$ Hit rate + L1\$ Miss rate * L2\$ Hit rate = 0.5 + 0 = 0.5
* Global Miss rate = 1 - Global Hit rate = 0.5
:::

* **Task**
1. What is the hit rate of our L1 cache? Our L2 cache? Overall?
:::success
Hit rate
* L1\$ = 0.5 (first word misses, second word hits)
* L2\$ = 0 (**All Miss**)
* Global = L1\$ Hit rate + L1\$ Miss rate * L2\$ Hit rate = 0.5
:::
2. How many accesses do we have to the L1 cache total? How many of them are misses?
:::success
* L1\$ Access times : ${ArraySize(128 \ Bytes) \over StepSize(1*4 \ bytes)} = 32$
* L1\$ Misses = ${Access \ times(32) \over 2} = 16$
:::
3. How many accesses do we have to the L2 cache total? How does this relate to the L1 cache (think about what the L1 cache has to do in order to make us access the L2 cache)?
:::success
* L2\$ Access times : ${L1 \ Access \ times \over 2} = 16$
:::
4. What program parameter would allow us to increase our L2 hit rate, but keep our L1 hit rate the same? Why?
:::success
Increase the Block Size of L2\$.
* Since every access from L1\$ is a increment of 2 of the last access address.
* So, let L2\$ load more datas from main memory once can improve the hit rate of L2\$ effectively.

:::
5. What happens to our hit rates for L1 and L2 as we slowly increase the number of blocks in L1? What about L1 block size?
:::success
1. Increse the number of blocks in L1\$
* Hit rates for L1\$ and L2\$ will still be the same as before.
* Since L1\$ is still first word misses and second word hits.
2. Increse the block size in L1\$
* Since we increase the block size of L1\$, we need also increase the block size of L2\$. The block size of L2\$ need always >= L1\$.
* Suppose the above is true, it will improve the hit rates for L1\$ but conditionally improve L2\$.
* L1\$ will miss first and hits the rest ( hit rate$\uparrow$ ).
* If the block size of L2\$ = L1\$, L2\$ wouldn't improve.
* If the block size of L2\$ > L1\$, L2\$ would improve.
:::

## Exercise 2 - Loop Ordering and Matrix Multiplication
### Objective

void multMat1( int n, float *A, float *B, float *C ) {
    int i,j,k;
    /* This is ijk loop order. */
    for( i = 0; i < n; i++ )
        for( j = 0; j < n; j++ )
            for( k = 0; k < n; k++ )
                C[i+j*n] += A[i+k*n]*B[k+j*n];
}

Compare the order of ```i, j, k``` of Matrix Multiplication, then conclude which order has the best performance.
* The picture below which is **Column Major**

### Setup
Download [source code folder](https://github.com/61c-teach/su20-lab-starter/tree/master/lab07)

$ make
$ ./matrixMultiply

* Result
:::info
We can find the **jki** & **kji** has the better performance than others.
:::

### My Little Experiment
* **Objective**
Use ***Ripes*** to visualize how the spaciality dependence of different order ```i, j ,k``` affect the Cache Hit rate.

* **To Do**
Do a simple 4\*4 Matrix multiplication of different order of ```i, j, k```, and check Hit rate of each.

* **Cache Setup**
:::info

    C[i+j*n] += A[i+k*n]*B[k+j*n];

Memory Accesses per iteration of the innest loop
* A Matrix : Read 4 datas
* B Matrix : Read 4 datas
* C Matrix : Read 4 datas & Write 4 datas (Write address is same as Read address).

For the purpose of visualizing the influence of spaciality, we setup Cache like below.
* Full-Associatuve Cache (1 set $\rightarrow$ 1 Cache line = $2^0$)
* ~~3 Slots(Ways)~~ (A, B, C per slot) $\rightarrow$ 4 Slots(Ways) (Since it need to be $2^N$) = $2^2$
* 4 words per slot (Since taking 4 datas to operate per iteration) = $2^2$
:::

* **Generate Test Assembly Programs**
* There are six test functions in [matrixMultiply.c](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/matrixMultiply.c) [from UBC summer2020 Lab7]
* Use [Compiler Explorer](https://godbolt.org) to help us cross compile from source code(**C Language**) to assembly code(**RISC-V**)
* Follow the steps in the below picture
1. Copy one function in [matrixMultiply.c](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/matrixMultiply.c) and paste at the left side.
2. Choose "**RISC-V rv32gc clang 11.0.0**"
3. Key in "**-O3 -march=rv32im -mabi=ilp32**"
4. You will get the transformed RISC-V assembly code after finish the above steps
5. Do the above steps by six times for six different functions in [matrixMultiply.c](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/matrixMultiply.c)
:::info
:::
* Copy the assembly code and paste in the editor of **Ripes**
* Add the main fuction and static data before the the function
:::info

        jal    ra, multMat1(int, int*, int*, int*)  #Call the function you paste

* (line #12) You should rewrite the function name to what you paste.
* It will be multMat**X** ( **X** = 1 ~ 6 )
:::
:::spoiler <span class="red">*Click here to expand*</span>

        .data
        n: .word 4    # Number of row(and column) of the square matrix 
        arrA: .word 2, 3, 7, 4, 1, 3, 6, 9, 5, 7, 2, 4, 0, 4, 5, 8     
        arrB: .word 6, 3, 4, 10, 2, 5, 7, 3, 5, 7, 9, 2, 6, 0, 2, 1
        arrC: .word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        .text
        main:
                lw        a0, n
                la        a1, arrA                                  #Load address of array 
                la        a2, arrB
                la        a3, arrC
                jal       ra, multMat1(int, int*, int*, int*)       #Call the function you paste
                li        a7, 10                                    #Halt the simulator
                ecall

:::
* Finally, it will like below. `Take multMat6 for examples.`
:::spoiler <span class="red">*Click here to expand*</span>

        .data
        n: .word 4                      # Number of row(and column) of the square matrix 
        arrA: .word 2, 3, 7, 4, 1, 3, 6, 9, 5, 7, 2, 4, 0, 4, 5, 8     
        arrB: .word 6, 3, 4, 10, 2, 5, 7, 3, 5, 7, 9, 2, 6, 0, 2, 1
        arrC: .word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        .text
        main:
                lw 		a0, n
                la 		a1, arrA       							#Load address of array 
                la 		a2, arrB
                la 		a3, arrC
                jal 	ra, multMat6(int, int*, int*, int*)  	#Call multMat6()
                li 		a7, 10         							#Halt the simulator
                ecall
        multMat6(int, int*, int*, int*):                     # @multMat6(int, int*, int*, int*)
                addi    sp, sp, -16
                sw      s0, 12(sp)
                addi    a4, zero, 1
                blt     a0, a4, .LBB0_7
                mv      a7, zero
                slli    a6, a0, 2
        .LBB0_2:                                # =>This Loop Header: Depth=1
                mv      t1, zero
                mv      t0, a3
        .LBB0_3:                                #   Parent Loop BB0_2 Depth=1
                mul     a4, t1, a0
                add     a4, a4, a7
                slli    a4, a4, 2
                add     t2, a2, a4
                mv      t3, a1
                mv      a4, t0
                mv      s0, a0
        .LBB0_4:                                #   Parent Loop BB0_2 Depth=1
                lw      t4, 0(t3)
                lw      t5, 0(t2)
                lw      t6, 0(a4)
                mul     a5, t5, t4
                add     a5, t6, a5
                sw      a5, 0(a4)
                addi    s0, s0, -1
                addi    a4, a4, 4
                addi    t3, t3, 4
                bnez    s0, .LBB0_4
                addi    t1, t1, 1
                add     t0, t0, a6
                bne     t1, a0, .LBB0_3
                addi    a7, a7, 1
                add     a1, a1, a6
                bne     a7, a0, .LBB0_2
        .LBB0_7:
                lw      s0, 12(sp)
                addi    sp, sp, 16
                ret

:::

* **Results**
1. multMat1 (i, j, k) $\rightarrow$ <span class="red">**Hit rate : 0.5359**</span>
2. multMat2 (i, k ,j) $\rightarrow$ <span class="red">**Hit rate : 0.444**</span>
3. multMat3 (j, i, k) $\rightarrow$ <span class="red">**Hit rate : 0.5308**</span>
4. multMat4 (j, k, i) $\rightarrow$ <span class="red">**Hit rate : 0.8161**</span>
5. multMat5 (k, i, j) $\rightarrow$ <span class="red">**Hit rate : 0.4904**</span>
6. multMat6 (k, j, i) $\rightarrow$ <span class="red">**Hit rate : 0.7413**</span>

* **Summary**
| Order | Gflop / s | Hit rate | Rank (according to Gflop / s) |
|:------:|--------:|:------:|:---:|
| multMat1 (i, j, k) |1.761|0.5359|4|
| multMat2 (i, k, j) |1.559|0.4440|6|
| multMat3 (j, i, k) |1.908|0.5308|3|
| multMat4 (j, k, i) |14.513|0.8161|1|
| multMat5 (k, i, j) |1.598|0.4904|5|
| multMat6 (k, j, i) |12.639|0.7413|2|
We can find that :
* the innest loop of the best two is <span class="red">**i**</span>
* the innest loop of the third & forth is <span class="red">**k**</span>
* the innest loop of the last two is <span class="red">**j**</span>
:::info
* $\rightarrow$ The inner the loop is at, the more important it is
* $\rightarrow$ **i > k > j**
:::
-----------------
* the third can win the forth is because its middle loop is <span class="red">**i**</span>
* the fifth can win the sixth is also because its middle loop is <span class="red">**i**</span>
:::info
* $\rightarrow$ **i > j**
* $\rightarrow$ **i > k**
:::
-----------------
:::info
* The performance is affected by Spaciality dependence.
* We can confirm it by comparing to each Hit rate.
:::

* **Task**
1. Which ordering(s) perform best for these 1000-by-1000 matrices? Why?
:::success
* From "Gflop / s" in Summary Table ```j, k, i``` perform best.
* Because its spaciality dependence is greater than others $\rightarrow$ Hit rate is high $\rightarrow$ speed is fast.
:::
2. Which ordering(s) perform the worst? Why?
:::success
* `i, k, j` performs worst.
* The inner the loop is at, the more important it is
* **i > k > j**
* Since its inner loop is j, middle loop is k and outer loop is i, it doomed to be the worst becaus of the Spaciality.
:::
3. How does the way we stride through the matrices with respect to the innermost loop affect performance?
:::success
* Since the inner loop decides the next memory address where to access for, if its stride can be as small as possible, it will raise the **hit rate** since we do **maximum use of Cache** as we can.
* **i > k > j**
* ***Column Major***
:::
## Exercise 3 - Cache Blocking and Matrix Transposition
Continued...