---
# System prepended metadata

title: CSE141L Lab 3 Caching Optimizations Worksheet1

---

# CSE141L Lab 3 Caching Optimizations Worksheet1

Name: __________________________
Student ID: ____________________

# Instructions

* Complete this worksheet while reading/working through the lab write up.  The worksheet doesn't make sense without the lab.

* The point values are listed for each question.   Altering the size of the cells will cost you 1 point. The write up portion of the lab is 30% of your total point for the lab as shown in the lab's README.md 

## Cache and dataset characteristics

#### P1 (4pt) Find out the dimensions (number of data elements) of the following tensors/vectors used in `fc_layer_t::activate` for the cifar100 dataset and fill the following table

| Tensor/Vector       | Number of Data Elements               |
|---------------------|---------------------------------------|
| `in`                | _____________________________________ |
| `out`               | _____________________________________ |
| `weights`           | _____________________________________ |
| `activation_input`  | _____________________________________ |

#### P2 (4pt) Calculate the size (in Bytes) of the following tensors/vectors used in `fc_layer_t::activate` for the cifar100 dataset and fill the following table

| Tensor/Vector       | Size in Bytes                         |
|---------------------|---------------------------------------|
| `in`                | _____________________________________ |
| `out`               | _____________________________________ |
| `weights`           | _____________________________________ |
| `activation_input`  | _____________________________________ |


#### P3 (4pt) How much of each of these data structures used in `fc_layer_t::activate()` will fit in the L1 and L2 cache (Note The cache size for our machine is L1-dCache: 32kb, L2: 256kb, L3: 8Mb)?

| tensor              | % that'll fit in L1| % that'll fit in L2 |
|---------------------|--------------------|---------------------|
| `in`                | __________________ | ___________________ |
| `out`               | __________________ | ___________________ |
| `weights`           | __________________ | ___________________ |
| `activation_input`  | __________________ | ___________________ |

## Understanding Tensor_t

Given `tensor_t<double> foo(tdsize(4,3,5,7))`, answer the following (double are 8 bytes)(Hint: Look at lecture slides) : 

#### P1 (1pt) How many elements are there in `foo`?



#### P2 (1pt) What's the linear index of element (1,1,1,1)?




#### P3 (1pt) How far apart are elements that differ by 1 in each dimension?

|dim. | distance in bytes     | distance in linear index | 
|-----|------|------|
| x   |      | | 
| y   |      | |
| z   |      || 
| b   |      ||

## Tier 1: Reordering and Tiling loops in `fc_layer_t::activate`

#### P1 (3pt) Fill out the following table. Report the Misses per Instruction by using the performance counters (there should be a column for "MPI" in the reported data when running with L1/2/3.cfg ) 

| Cache-Level | Miss rate - Base | Miss rate - loop reordering | Miss rate - Tiling |
|---------------| --------------| --------| -- |
| L1 | 
| L2 |
| L3 |


#### P2 (4pt) Change the order of loops from `b i n` to `b n i` in `fc_layer_t::activate` and report the speedup.

Speedup after loop reordering : _______________

#### P3 (4pt) Block the loop `n` in `fc_layer_t::activate` with the tile sizes 1, 2, 4, 8, 16 and fill out the table below.

| Dataset  | Step size | Blocked implementation time            | Speedup vs step size == 1|
|----------|-----------|----------------------------------------|---------|
| cifar100 | 1         | ______________________________________ | _______ |
| cifar100 | 2         | ______________________________________ | _______ |
| cifar100 | 4         | ______________________________________ | _______ |
| cifar100 | 8         | ______________________________________ | _______ |
| cifar100 | 16        | ______________________________________ | _______ |



#### P4 (4pt) In a single line graph, plot the speed up against the different block sizes for blocking the loop `n` in `fc_layer_t::activate`. Block size is the independent vairable.

```




    Your graph here





```
#### P5 (4pt) Consider the blocksize which gave maximum speedup in the previous question P4 and fill out the following table

1. Base implementation time                         : _____________________________________ 
2. Implementation time of your optimized solution   : _____________________________________ 
3. Base implementation L1 miss rate                    : _____________________________________ 
4. Your fastest solution L1 misse rate                 : _____________________________________ 


#### P6 (3pt) Insert the memory access patterns (take screenshots from moneta) for loop orders b-i-n, b-n-i and nn-b-n-i. Do this for weights tensor and pass the runtime options that set scale to 4 and reps to 1 in config.env. The dataset should be cifar100 (which should be the default). Leave the cache lines and block size fields as they are but set the max accesses to 2 million. In the file opt_cnn.cpp, there is an example of where and what to put to run the moneta please take a look at it. 


```







    memory access pattern with loop order b-i-n









```


```









    memory access pattern with loop order b-n-i









```


```








    memory access pattern with loop order nn-b-n-i









```






