Assignment 5

** Note: this assignment is finished.**

Introduction

In this assignment you will implement a configurable model of a cache with initial interfaces and will carry out a small performance study.

All requirements remain the same as in previous tasks

---

Task

You should create a new branch task_5 and create the following files:

• perf_sim/mem/cache_tag_array.h
• perf_sim/mem/cache_tag_array.cpp
• perf_sim/mem/miss_rate_sim.cpp <- this file will contain the program doing performance measurements
• perf_sim/mem/Makefile

You are not prohibited to add more files, but these four are mandatory. Also, note that your code has to be organized in such way that only thing that a user should do in order to use your cache model is to include cache_tag_array.h.

Note that for this task you don't need any results of the previous assignments.

---

Implementation

CacheTagArray class

Class CacheTagArray implements the concepts of a real tag array in a CPU cache. As you know, the cache tag array (unlike cache data array) does not stores any real data (bytes of instructions, variables, arrays, etc). It is only responsible for generation hit signal, i.e. it can say whether a particular block is contained by the cache or not, but cannot provide the block data itself.

Your implementation should provide at least these interfaces:

class CacheTagArray
{
   
public:
    /**
     * Constructor params:
     *
     * 1) size_in_bytes is a number of data bytes that can be stored in the cache,
     *    i.e. if the block size is 16 Bytes then the number of data blocks in the cache is size_in_bytes/16.
     *
     * 2) ways is a number of associative ways in a set, i.e. how many blocks are referred by the same index.
     *
     * 3) block_size_in_bytes is a number of Bytes in a data block
     *
     * 4) addr_size_in_bit is a number of bits in the physical address.
     */
    CacheTagArray( unsigned int size_in_bytes,
                   unsigned int ways,
                   unsigned short block_size_in_bytes, 
                   unsigned short addr_size_in_bits);
    /**
     * Return true if the byte with the given address is stored in the cache,
     * otherwise, return false.
     *
     * Note that his method updates the LRU information.
     */
    bool read( uint64 addr);
    
    /**
     * Mark that the block containing the byte with the given address
     * is stored in the cache.
     *
     * Note: in order to put the given address inside the tags it is needed
     * to select a way where it will be written in.
     * This selection is being done according to LRU (Least Recently Used)
     * policy.
     */
    void write( uint64 addr);
};

You are free to add as many additional methods and classes as you want, but you cannot change these interfaces.

---

Performance study

Your target is to receive miss rates on different cache configurations using a real memory request trace as a input workload. Changing the cache size and associativity (number of ways) you will obtain a chart like the following one:

Note that the form of your curves can be different from ones on the picture, as you have another workload.

Remember that our goal is to investigate the most effective cache configuration for the given program (it can be done if the miss rates, size and power of each configuration are known). It can be surprised, but to do that we do not need to execute the program. We even do not need to know what instructions the program contains and what they do. The only thing we have to know is a sequence of addresses of memory accesses generated by the program.

To measure the miss rate you have to go through this sequence, check each address (using CacheTagArray::read method) and calculate the number of hits and misses. It is important that when CacheTagArray::read finds out a miss the address has to be written into the tags array (using CacheTagArray::write method). It needs to be done, because in the real cache a missed block is downloaded from the main memory (or the next cache) and then is written into the cache. Of course, after a hit there should not be any write into the cache (and, consequently, into the cache array). After a hit you just move to the next address in the sequence.

Configurations

It this study you investigate only the different combinations of cache size (size_in_bytes) and associativity (ways). All of them are specified in the following table:

You should gather the miss rate for each cell of this table for each workload (i.e. address sequence).

The other parameters of the cache are always the same in this study: block_size_in_bytes = 4, addr_size_in_bits = 32. But your model still have to support their changing if it is needed.

Note: when a simulation starts the cache is considered to be empty (for each new configuration and workload).

Input data

Your program (located in miss_rate_sim.cpp) should take as the first parameter the name of a text file where addresses of cache requests are located. The example of such file you can found at <trunk>/mem_trace.txt. The beginning of the file is presented below:

0x11018 0x11060 0x11030 0x11050 0x5220d0 0x11040 0x11090 0x5221a0 0x522220

Note: that addresses are presented in hexadecimal format, i.e 0x465b118 instead of 73773336 and separated by a space.

Output data

Output data should be presented in the CSV format where numbers in a row are miss rates for a certain cache size and they are separated by commas. Each row corresponds to the certain associativity.

In fact, it will be the table from the Configurations chapter above.

An example of the output is presented below:

0.349048, 0.27356, 0.216863, 0.164309, 0.127481, 0.0896536, 0.0614431, 0.0385261, 0.0342199, 0.0278209, 0.0277584, 
0.341117, 0.254755, 0.194426, 0.154902, 0.119156, 0.085989, 0.0524071, 0.0354602, 0.0275645, 0.0275323, 0.0271651, 
0.337479, 0.255616, 0.190327, 0.149961, 0.118951, 0.0860855, 0.0507263, 0.0303543, 0.0275824, 0.0271651, 0.0271651, 
0.338298, 0.256382, 0.192536, 0.149813, 0.118232, 0.0861409, 0.0500471, 0.0283276, 0.0271651, 0.0271651, 0.0271651, 
0.338556, 0.25701, 0.193569, 0.150662, 0.118576, 0.0856468, 0.0495244, 0.027711, 0.0271651, 0.0271651, 0.0271651, 
0.340405, 0.258033, 0.194169, 0.151537, 0.119232, 0.0850615, 0.0501856, 0.0271651, 0.0271651, 0.0271651, 0.0271651,

The first row contains miss rates for 1 way set-associative cache. It starts from the size of 1 KB and ends with 1 MB. The second row contains data for 2 ways set-associate cache and so on.

Note: that data for each associativity starts from a new line creating a new row.

Command line arguments

Your program (located in miss_rate_sim.cpp) should receive two argument from the command line. The first one is the name of an input file with memory access addresses. The second is the name of an output file where miss rates are printed in the CSV format.

For example, if an input file is located in the same folder as the executive file the command line can be the following:

miss_rate_sim.exe mem_trace.txt miss_rate.csv

Note: if there are not enough arguments or the names are incorrect your program has to cancel and to display a proper message about a reason of the failure.