CacheStudyExercise - MIPT-ILab/MDSP GitHub Wiki

Introduction

In this exercise you should create a fully parametrized program model of a simple instruction cache, then using a memory trace of a rial application research how the cache miss rate depends on its size and associativity.

Note: this program model does not shows performance in terms of processor clocks (or real time). It only says as many misses/hits were on a given sequence of cache request.

Requirements

Location in svn

Create a folder in https://mdsp.googlecode.com/svn/branches/2011/sandbox/<name_of_your_branch_folder>. The folder name should consists of the first letter of you name + your surname + "cache". For example, for Alexander Titov the folder name is "atitov_cache".

Mandatory files

In this folder you have to create two files: main.cpp and cache.h. You are not prohibited to add more files, but these two are mandatory.

Note: your code has to be organized in such way that only thing that a user should do is to include cache.h.

Cache model parametrization

File cache.h should describe a C++ class called Cache which implements a functional simulator of a real instruction cache. It has to contain the following public methods:

  1. CacheArray is a class constructor that allows to customize almost all cache parameters: * size 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/16. * ways is a number of associative ways in a set, i.e. how many blocks are referred by the same index. * block_size is a number of Bytes in a data block. * addr_size_in_bit is a number of bits in address.
  2. processRead simulates a cache read. The given parameter, addr, is a request address. It is checked for hit/miss and in case of miss it evicts some old address.
  3. getMissRate just returns miss rate which is calculated as a ratio of total a number of missed requests to a number of total requests.
class Cache
{
   
public:
    Cache( unsigned int size, unsigned int ways,
           unsigned int block_size, 
           unsigned int addr_size_in_bit);

    void processRead( unsigned int addr);
    double getMissRate() const;
};

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

.

Task description

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 should obtain a chart like the following one:

https://mdsp.googlecode.com/svn/wiki/images/miss_rate_chart_example.png

Configurations

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

https://mdsp.googlecode.com/svn/wiki/images/configuration_table_for_cache_exercise.png

You should gather miss rate for each cell of the table.

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

For replacement the Round-Robin algorithm is used. For example, if there is only 4 ways than 0 is replaced first, then 1, 2, 3 and then again 0 and so on.

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

Input data

Your program should take as a given parameter the name of a text file where addresses of cache requests are located. The example of such file you can found at this link. 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.

Your program should received the name of a file with requests as the first input argument.

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, you will gather the miss rates for 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 should receives 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:

cache.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.
⚠️ **GitHub.com Fallback** ⚠️