# Homework4: Cache

## Exercise 1 - A Couple of Memory Access Scenarios

The program [cache.s](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/cache.s) is below.
And we can also see the C program format in the program.

:::spoiler **cache.s**

# 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:

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

* Array Size (a0): 128 (bytes)
* Step Size (a1): 8
* Rep Count (a2): 4
* Option (a3): 0

#### Cache Parameters: (set these in the Cache tab)
* Cache Levels: 1
* Block Size: 8
* 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

The cache table followed the cache parameters is like the picture below.


#### Task:
##### 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.”)

The result show at the picture below.
The **hit rate** is zero.


The reason of the hit rate is zero is step size**(a1)** equal to 8

Look the program, we know the value will be stored in **0(s0)**, and the address of the **s0** is **0x10000000**.
Through the loop, the next value wiil be stored in **32(s0)**, and the address is **0x10000020**.

Followed the cache parameters, the **offset bit** is 2 bits, the **block bit** is 1 bit, the **index bit** is 2 bits, and the **tag bit** is 27 bits

The address **0x10000000** is pointed to the cache table with index 0, block 0, and Tag is 0x00800000, and The address **0x10000020** is also pointed to the cache with index 0, block 0, and Tag is 0x00800001.

Because every address of the value stored is pointed to the same cache table location, at the following loop, the cache is always cache miss and the hit rate is zero

##### 2.What is our hit rate if we increase Rep Count arbitrarily? Why?

**No**
The reason is mention at the task 1.

##### 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.

We can modify the **step size** to 1, and the hit rate is like the picture below.


### 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
* Enable?: Should be green
* Placement Policy: N-Way Set Associative
* Associativity: 4
* Block Replacement Policy: LRU

The cache table followed the cache parameters is like the picture below.


#### Task:

##### 1.How many memory accesses are there per iteration of the inner loop? (not the one involving repcount). It’s not 1.

Because the **option(a3)** is 1, the program will do the operation

array[index] = array[index] + 1

Two memory accesses are there per iteration of the inner loop.
One is read, and the other is write.

##### 2.What is the repeating hit/miss pattern? WHY? (Hint: it repeats every 4 accesses).

Look the program, it will read the value at the **0(s0)**, and store the value plus 1 back to the **0(s0)**, and the address is **0x10000000**.

And the next loop is read the value at the **8(s0)**, the address is **0x10000008**, is upload in cache at the previous loop.

##### 3.This should follow very straightforwardly from the above question: Explain the hit rate in terms of the hit/miss pattern.

Above question, every two loop will cache miss one time, and hit three time, so the hit rate is 0.75.

The **hit rate** is 0.75 and show at the picture below.


##### 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!

The program only cache miss at the **first rep count**.

At the final loop of the first rep count is read the value at the **240(s0)**, and the address is **0x100000f8**, which is pointed to the cache with index 15, block 2, and Tag is 0x00100000.

And the first loop of the second rep count is read the value at the **240(s0)**, and the address is **0x100000f8**, which is pointed to the cache with index 1, block 0, and Tag is 0x00100000.

The first loop of the second rep count, the program doesn't cache miss.

So when the rep count goes to infinity, the hit rate will be close to 1.

You can see at the picture below with rep count 1, 10, 100.

**rep count 1 :**

**rep count 10 :**

**rep count 100 :**

##### 5.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:

##### 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.

##### HINT: You do not want to iterate through the entire array at once because it’s much bigger than your cache. Doing so would reduce the amount of temporal locality your program exhibits, which makes cache hit rate suffer. We want to exhibit more locality so that our caches can take advantage of our predictable behavior. SO, instead, we should try to access **__** of the array at a time and apply all of the **_** to that **__** so we can be completely done with it before moving on, thereby keeping that **_** hot in the cache and not having to circle back to it later on! (The 1st, 3rd, and 4th blanks should be the same. It’s not some vocabulary term you should use to fill them in. It’s more of an idea that you should have.)

### Scenario 3:

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

* Array Size (a0): 128 (bytes)
* Step Size (a1): 1
* Rep Count (a2): 1
* Option (a3): 0

#### Cache Parameters: (set these in the Cache tab)
* Cache Levels: 2

NOTE: Make sure the following parameters are for the L1 cache! (Select L1 in the dropdown right next to the replacement policy)

* Block Size: 8
* Number of Blocks: 8
* Enable?: Should be green
* Placement Policy: Direct Mapped
* Associativity: 1
* Block Replacement Policy: LRU

The L1 cache table followed the cache parameters is like the picture below.


NOTE: Make sure the following parameters are for the L2 cache! (Select L2 in the dropdown right next to the replacement policy)

* Block Size: 8
* Number of Blocks: 16
* Enable?: Should be green
* Placement Policy: Direct Mapped
* Associativity: 1
* Block Replacement Policy: LRU

The L2 cache table followed the cache parameters is like the picture below.


#### Task:

##### 1.What is the hit rate of our L1 cache? Our L2 cache? Overall?

The hit rate of our L1 cache is 0.5.


The hit rate of our L1 cache is 0.5.


##### 2.How many accesses do we have to the L1 cache total? How many of them are misses?

32 times, and 16 times are miss.

##### 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)?

32 times, and 16 times are miss.

##### 4.What program parameter would allow us to increase our L2 hit rate, but keep our L1 hit rate the same? Why?

Rep Count.

At the second Rep Count, L2 will always hit , and L1 hit rate is equal to 0.5, because the program will access 32 times with different address, and L1 only has 16 blocks to save the address but the L2 has 32 blocks.

##### 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?

Nothing happens to hit rate by increasing the number of blocks, because the program Rep Count is equal to 1.

The hit rate will increase by increasing the number of block sizes, because when cache miss, cache will access more data from the memory at one time.

## Exercise 2 - Loop Ordering and Matrix Multiplication

The program [matrixMultiply.c](https://github.com/61c-teach/su20-lab-starter/blob/master/lab07/matrixMultiply.c) is below.

:::spoiler **matrixMultiply.c**

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>


/* To save you time, we are including all 6 variants of the loop ordering
   as separate functions and then calling them using function pointers.
   The reason for having separate functions that are nearly identical is
   to avoid counting any extraneous processing towards the computation
   time.  This includes I/O accesses (printf) and conditionals (if/switch).
   I/O accesses are slow and conditional/branching statements could
   unfairly bias results (lower cases in switches must run through more
   case statements on each iteration).
*/
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];
}

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

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

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

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

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

/* uses timing features from sys/time.h that you haven't seen before */
int main( int argc, char **argv ) {
    int nmax = 1000,i;

    void (*orderings[])(int,float *,float *,float *) =
        {&multMat1,&multMat2,&multMat3,&multMat4,&multMat5,&multMat6};
    char *names[] = {"ijk","ikj","jik","jki","kij","kji"};

    float *A = (float *)malloc( nmax*nmax * sizeof(float));
    float *B = (float *)malloc( nmax*nmax * sizeof(float));
    float *C = (float *)malloc( nmax*nmax * sizeof(float));

    struct timeval start, end;

    /* fill matrices with random numbers */
    for( i = 0; i < nmax*nmax; i++ ) A[i] = drand48()*2-1;
    for( i = 0; i < nmax*nmax; i++ ) B[i] = drand48()*2-1;
    for( i = 0; i < nmax*nmax; i++ ) C[i] = drand48()*2-1;

    for( i = 0; i < 6; i++) {
        /* multiply matrices and measure the time */
        gettimeofday( &start, NULL );
        (*orderings[i])( nmax, A, B, C );
        gettimeofday( &end, NULL );

        /* convert time to Gflop/s */
        double seconds = (end.tv_sec - start.tv_sec) +
            1.0e-6 * (end.tv_usec - start.tv_usec);
        double Gflops = 2e-9*nmax*nmax*nmax/seconds;
        printf( "%s:\tn = %d, %.3f Gflop/s\n", names[i], nmax, Gflops );
    }

    free( A );
    free( B );
    free( C );

    printf("\n\n");

    return 0;
}

:::

We can run the program.

make ex2

And it will run with the makefile.

gcc -o matrixMultiply -ggdb -Wall -pedantic -std=gnu99 -O3 matrixMultiply.c
./matrixMultiply

And the result will be showed at the command line

### Task:

##### 1.Record your results in answers.txt

ijk:    n = 1000, 0.508 Gflop/s
ikj:    n = 1000, 0.105 Gflop/s
jik:    n = 1000, 0.406 Gflop/s
jki:    n = 1000, 0.948 Gflop/s
kij:    n = 1000, 0.095 Gflop/s
kji:    n = 1000, 0.679 Gflop/s

##### 2.Which ordering(s) perform best for these 1000-by-1000 matrices? Why?

jki is the best

Look the program, i is used to be the row number of the matrix. And we know the matrix is row major.

##### 3.Which ordering(s) perform the worst? Why?

ikj is the worst

Look the program, j is used to be the column number of the matrix. But we know the matrix is row major.

##### 4.How does the way we stride through the matrices with respect to the innermost loop affect performance?

The innermost loop must be the spatial for the mnatrix.

## Exercise 3 - Cache Blocking and Matrix Transposition

### Part 1 - Changing Array Sizes

#### Task:

##### 1.Show your results
##### 2. At what point does cache blocked version of transpose become faster than the non-cache blocked version?
##### 3.Why does cache blocking require the matrix to be a certain size before it outperforms the non-cache blocked code?

### Part 2 - Changing Blocksize

#### Task:

##### 1.Show your results
##### 2.How does performance change as blocksize increases? Why is this the case?