# Using Ripes simultor to test the impact of the memory accessing pattern
<`contributed by eddie9712`>
[Question Reference](https://cs61c.org/su20/labs/lab07/)
### environment:

operating system:ubuntu 20.04
simulator:Ripes-v2.1.0-linux-x86_64.AppImage
virtual machine:virtualbox 6.1

CPU info:

vendor_id       : GenuineIntel
cpu family      : 6
model           : 126
model name      : Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz
stepping        : 5
cpu MHz         : 1497.602
cache size      : 8192 KB
physical id     : 0
siblings        : 1
core id         : 0
cpu cores       : 1
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 22
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_known_freq pni pclmulqdq monitor ssse3 cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_single fsgsbase avx2 invpcid rdseed clflushopt md_clear flush_l1d arch_capabilities
bugs            : spectre_v1 spectre_v2 spec_store_bypass swapgs itlb_multihit
bogomips        : 2995.20
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

Clone the source code from here:
`https://github.com/61c-teach/su20-lab-starter`

## Exercise 1 - A Couple of Memory Access Scenarios
At the first exercise we need to adjust the program parameters and run the piece of code on Ripes simulator to see how the cache works and discuss the questions in lab07.**(There are some difference between the Venus and Ripes, so I will adjust some cache parameters in lab07)**

`cache.s` is the piece of code that we should run with different cache configurations (assembly code) [here](https://github.com/eddie9712/Computer_Architecture/tree/main/riscv/Lab4)

PSEUDOCODE of `cache.s`:

  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
      }          
    }            

### Scenario 1:

Program Parameters:
    Array Size (a0): 128 (bytes)
    Step Size (a1): 8
    Rep Count (a2): 4
    Option (a3): 0
Cache Parameters:
    Cache Levels: 1
    Block Size: 8
    Number of Blocks: 4
    Placement Policy: Direct Mapped
    Associativity: 1 
    Block Replacement Policy: LRU

According to the cache parameter, we can get the configuration of cache :

Index: 2 bits (4 slots)
offset: 3 bits (8 bytes each block(entry))
Tag: 32-2-3=27 bits

* task 1:try to figure out the hit rate before I run the code:
In `cache.s` , with the program parameters above, we assume that the memory addresses of the array is started at ` 0x10000000` so the accessed address will be will be `0x1000000`, `0x10000020`,`0x10000040`, `0x10000060` , and then I break them down to the **TIO** format(direct mapped) , they all have the same index(0) ,so I think the miss pattern is =>
`0x1000000` : miss
`0x10000032` : miss
`0x10000064` : miss
`0x10000096`: miss
and even though the program repeats for 4 times ,the hit rate is still the same that is 0;

* task 2: What combination of parameters is producing the hit rate you observe?
I think the combination of the **step size** and **block size** cause the hit rate 0, because the block size just 8 bytes so the step size is too big to access the data which is btought to cache previous time, and the step size=8 also cause the **ping pong effect**(with mapping to index 0)

* task 3: What is our hit rate if we increase Rep Count arbitrarily? Why?
There isn't any influences if we increase Rep Count arbitrarily , because the accessing patterns are the same at each iteration(Rep Count)

* task 4:How could we modify one program parameter to increase our hit rate?
I think the answer is **decreaseing the step size**, because when the step_size=eight the next accessing of the address will not include in the block that we bring to cache(and the next accessing will evict the previous block) , so we need to **decrease the step_size to 1(hit rate:0.5)**

### Scenario 2:

Program Parameters: (set these by initializing the a registers in the code)

    Array Size (a0): 256 (bytes)
    Step Size (a1): 2
    Rep Count (a2): 1
    Option (a3): 1

Cache Parameters: (set these in the Cache tab)

    Cache Levels: 1
    Block Size: 16
    Number of Blocks: 16
    Placement Policy: N-Way Set Associative
    Associativity: 4
    Block Replacement Policy: LRU

And here is the cache configuration:
Index: 2 bits(4 sets)
Offset: 4 bits(16 bytes/block)
Tag: 32-2-4=26 bits

1. How many memory accesses are there per iteration of the inner loop? (not the one involving repcount). It’s not 1.
Ans: 2 times(lw and sw)

2. What is the repeating hit/miss pattern? WHY? (Hint: it repeats every 4 accesses).
Ans:
access pattern:
array[0] : miss
array[0] : hit
array[2] : hit
array[2] : hit
After that, every accessing to the array[4n] will get a miss

3. This should follow very straightforwardly from the above question: Explain the hit rate in terms of the hit/miss pattern.
Ans: 3/4=>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!
You should have noticed that our hit rate was pretty high for this scenario, and your answer to the previous question should give you a good understanding of why. IF YOU ARE NOT SURE WHY, consider the size of the array and compare it to the size of the cache. Now, consider the following:

Ans:
If I set the program parameter to 1000(***when the value of repcount increasing the value of hit rate also increasing***) then I get the hit rate 0.998. It is very close to 1, I think the reason why we get this result is that the cache can contain the all data accessed by us.However, it still need to consider the compulsory miss when the block first time brought to cache

* Extension question:
>Suppose we have a program that iterates through a very large array (AKA way bigger than the size of the cache) repcount times. During each Rep, we map a different function to the elements of our array (e.g. if Rep Count = 1024, we map 1024 different functions onto each of the array elements, one per Rep). (For reference, in this scenario, we just had one function (incrementation) and one Rep).

>QUESTION: Given the program described above, how can we restructure its array accesses to achieve a hit rate like that achieved in this scenario? Assume that each array element is to be modified independently of the others AKA it doesn’t matter if Rep k is applied to element arr[i] before Rep k is applied to element arr[i+1], etc.

Ans:To achieve the hit rate like that achieved in this scenario, I think I can access the array with size of **"block"**.
At first, we need to access the whole array(assume it is an integer array) each `repcount`, so we will access all of elements in the array(`array[0],array[1],array[2].....`) since we would like to take adventage of the spatial locality we will access the array sequentially then we get:

array[0]:miss
array[1]:hit
array[2]:hit
array[3]:hit

Because we can't avoid the compulsory miss, so we will get the hit rate `0.75`, thereby we can take advantage of the temporal locality with the next `repcount` with the reversing order accessing, so the hit rate will increase when the repcount increase.

**Explanation:**
Assume the array contains 10 blocks that map to the first set(4-way set)

When the cache full:
first set:
slot 1: block 1 ==>LRU
slot 2: block 2
slot 3: block 3
slot 4: block 4
at the next time when the cache full:
slot 1: block 5 ==>LRU
slot 2: block 6
slot 3: block 7
slot 4: block 8
there still 2 blocks to access, so:
slot 1: block 9
slot 2: block 10
slot 3: block 7 ==>LRU
slot 4: block 8
Then it goes on the next repcount(reversing order)
slot 1: block 9
slot 2: block 10
slot 3: block 7 ==>LRU
slot 4: block 8
so the block 10 ,9 , 7, 8 will all hit in the cache

Then we can observe the miss/hit patterns:
rep 1:
1:m
2:m
3:m
4:m
5:m
6:m
7:m
8:m
9:m
10:m
rep 2:
10:h
9:h
8:h
7:h
6:m
5:m
4:m
3:m
2:m
1:m

And then We can directive the concept to our experiment=>
Each block accessing will get 1 misses and 3 hits.Howerver ,the next repcount will get 4 hits(each block) for the fisrt four blocks.

Experiment:(Get the source code [here]())
I modify the given code `cache.s`, this program accesses the whole array(set each element to zero).When the repcount is an odd number ,it accesses the program with increasing index, contrastly , it accesses the array with decreasing index.
* Result:

### Scenario 3:
No multilevel cache in Ripes.

## Exercise 2 - Loop Ordering and Matrix Multiplication
* task 1 : Think about what the strides are for the nested loops in the other five implementations.
* multMat2:
* moves through A with stride: 0
* moves through B with stride: n
* moves through C with stride: n
* multMat3:
* moves through A with stride: n
* moves through B with stride: 1
* moves through C with stride: 0
* multMat4:
* moves through A with stride: 1
* moves through B with stride: 0
* moves through C with stride: 1
* multMat5:
* moves through A with stride: 0
* moves through B with stride: n
* moves through C with stride: n
* multMat6:
* moves through A with stride: 1
* moves through B with stride: 0
* moves through C with stride: 1
* task 2:
Afetr executing `make ex2` we get the results of the matrix multiplcation in different ways:
(Gflop/s=>Giga-floating-point-operations per second)
ijk: n = 1000, 1.486 Gflop/s
ikj: n = 1000, 1.275 Gflop/s
jik: n = 1000, 1.573 Gflop/s
jki: n = 1000, 10.009 Gflop/s
kij: n = 1000, 1.361 Gflop/s
kji: n = 1000, 9.560 Gflop/s

* task 3,4,5:Which ordering(s) perform best for these 1000-by-1000 matrices? Why?

As you can see, since the higher Gflop/s represents the higher performance so the order `jki` gets the best performance on matrix mulitiplcation. In my opinion, we can look at the answers for the first question, the order `jki` has the strides in the innermost loop:

* multMat4:
    * moves through A with stride: 1
    * moves through B with stride: 0
    * moves through C with stride: 1

So I go to check the block size of my cache:
`vi /proc/cpuinfo`:
and hen I get:
`cache_alignment : 64`(each block has 64 bytes)

Ok, so it is reasonable that the stride of accessing the array will impact the performance , if the stride of accessing is bigger than the block size , it will cause a cache miss, take the the order `ikj` for example(which has the worst performance):
In the innermost loop, the accessing patterns wiill be:

i=0,k=0 j=0
C[0] A[0] B[0]
C[1000] A[0] B[1000]
C[2000] A[0] B[2000]
C[3000] A[0] B[3000]
......
C[1000000] A[0] B[1000000]

Contrastly, the accessing pattern of order `ijk`:
j=0,k=0 i=0
C[0] A[0] B[0]
C[1] A[0] B[1]
C[2] A[0] B[2]
C[3] A[0] B[3]
......
C[1000] A[0] B[1000]

We can observe that In the `jki` case, it will cause the cache miss again and again(poor locality).However ,the `ijk` will take adventage of the locality and then it will cause the lower miss rate.

However, we can find the order `kji` has the same strides to `ijk` in the innermost loop:

* multMat6:
    * moves through A with stride: 1
    * moves through B with stride: 0
    * moves through C with stride: 1

(It has the 2th performance on matrix multiplication)

But why it has the worse performance than `ijk`?
When we check the strides of every loop we can find that they are all composed of three types of strides:

e.g.(stride for C,A,B)
order `kji`:
The first loop: 0,n,1
The second loop: n,0,n
The third loop(innermost): 1,1,0
order `ijk`:
The first loop: n,0,n
The second loop: 0,n,1
The third loop(innermost): 1,1,0
At the third loop they both have the strides `1,1,0` to access the array , but at the second loop order `kji` has the strides `n,0,n` which will cause more cache miss than `0,n,1`. Because the frequency of the different loops => if we have strides n in second loop which means after execuing the third loop completely the next second loop will access the array with strides n.

**Explanation:**
**(order `ijk`):**
The third loop access the array C with stride 0
C[0],C[0],C[0]....C[0]
After executing completely,the second loop will access with strides 1(at second loop k++),so it start accesses C[1] in the third loop(**no cache miss**)

**(order `kji`):**
The third loop access the array C with stride 0
C[0],C[0],C[0]....C[0]
After executing completely,the second loop will access with strides n(at second loop k++),so it start accesses C[1000] in the third loop(**cache miss**)

From the result above, since the **stride n** will cause cache miss.Furthermore, if the stride n is taken for the more inner loop the more times it will be taken.I think that is the reason why the `ijk` has the best performance(innermost loop strides : 1,1,0),and the `kji` has the worst performace(innermost loop strides :n,0,n)

## Exercise 3 - Cache Blocking and Matrix Transposition
At first, I implement the `transpose_blocking()` function :

void transpose_blocking(int n, int blocksize, int *dst, int *src) {
 
      for (int x = 0; x < n; x+=blocksize) {
        for (int y = 0; y < n ; y+=blocksize) {
          for(int i=x ; i < x+blocksize ; i++){      //transpose each block
           for(int j=y ; j < y+blocksize ; j++){
              if( i<n && j<n){    //to avoid accessing out of the array
                dst[j + i * n] = src[i + j * n];
               }
            }
        }
    }
}
}

### Part 1 - Changing Array Sizes
Fix the blocksize to be 20, and run your code with n equal to 100, 1000, 2000, 5000, and 10000.
* The experiment results:

n=100
Testing naive transpose: 0.004 milliseconds
Testing transpose with blocking: 0.008 milliseconds
n=1000
Testing naive transpose: 1.043 milliseconds
Testing transpose with blocking: 1.162 milliseconds
n=2000
Testing naive transpose: 16.898 milliseconds
Testing transpose with blocking: 9.398 milliseconds
n=5000
Testing naive transpose: 339.297 milliseconds
Testing transpose with blocking: 67.806 milliseconds
n=10000
Testing naive transpose: 1473.8 milliseconds
Testing transpose with blocking: 232.271 milliseconds

* When the array size became n=2000, transpose with blocking become faster
* I guess that the reason why the cache blocking cache is outperforming the non-blocking cache in certain size is because of **cache size**. Let's take my cpu for example, my cpu has a 8192KB cache, so if the the array size that we accessing is smaller than our cache, the two ways will have the similar performance(compulsory miss).
* Result with pyplot:

### Part 2 - Changing Blocksize
Fix n to be 10000, and run your code with blocksize equal to 50, 100, 500, 1000, 5000.
* The experiment result:

Testing naive transpose: 1119.9 milliseconds
Testing transpose with blocking: 194.637 milliseconds
Testing naive transpose: 1100.25 milliseconds
Testing transpose with blocking: 165.453 milliseconds
Testing naive transpose: 1108.46 milliseconds
Testing transpose with blocking: 147.401 milliseconds
Testing naive transpose: 1085.85 milliseconds
Testing transpose with blocking: 178.388 milliseconds
Testing naive transpose: 1100.17 milliseconds
Testing transpose with blocking: 851.952 milliseconds

* Acorrding to the experiment result, when the blocksize achieved 5000 , the performance of the blocking-cache is similar to the non-blocking cache ,

* Results with pyplot:

# Modified Code:
Here I moidified the makefile and the `transpose.c` to test the results with different argument, and I also write a python script for plotting the results:
run `make ex3_part1` for different arraysize,run `make ex3_part2` for different blocksize

[source code](https://github.com/eddie9712/Computer_Architecture/tree/main/riscv/Lab4)