I220A-Project 5 Solved

You are being provided with a main program to exercise your implementation of the above simulation API. When this program is run, it expects a required argument of the form s-E-b-m where:

s The number of address bits used to specify a cache set; the cache will contain a total of 2s sets.

E The number of cache lines stored in each cache set; b The number of address bits used to specify an o set within a cache line (block). The size of a cache block will be 2b bytes.

m The total number of address bits used to specify a primary memory address. The total size of the main memory will be 2m bytes.

Optionally, the main program accepts one or more of the following options before the above required argument:

-r     REPLACEMENT The replacement strategy to be used by the cache simulator. Possible values are lru (for least recently used), mru (for most recently used) or rand (for random replacement). The default is lru.

-s    SEED SEED must be non-negative integer specifying a seed for the random number generator. The default value is 0.

-v If this option is speci ed, then the program produces additional verbose output.

You should ensure that when the program is invoked, the $HOME/cs220/lib directory will be searched for necessary libraries.

When run, the main program is set up to read whitespace-separated hexadecimal addresses from standard input and repeatedly call your cache_sim_result(¬ ) function with those addresses. If the -v verbose option is speci ed, then it prints out the result of each call. Otherwise, it will merely print out a summary of the cache statistics when end-of- le is encountered on standard input.

1.4          Random Number Generation
Most programming environments provide a pseudo-random number generation facility. The facility is pseudo in that it does not generate real random numbers but only pseudo random numbers in that the generated sequence meets some statistical tests for randomness. In fact, to facilitate testing, the random sequence is repeatable and is controlled by a seed for the random number generation.

In the C programming environment, the random number facilities are available using two library functions rand() and srand() which are speci ed in the <stdlib.h header le; successive calls to the former function return random non-negative integers; the seed of the random number generator can be speci ed by calling srand(). You will need to use the rand() function to simulate the random cache replacement strategy speci ed by the -r rand option.

1.5         The lib Directory
You may continue to use the following library contained within the course lib directory:

libcs220:: A trivial library which provides help with memory allocation and error reporting:

•    Provides checked versions mallocChk(), reallocChk(), and callocChk¬ () of the memory allocation routines which wrap the standard memory allocation routines with the program exiting on failure. The speci cation le is in memalloc.h.

•    Provides routines for reporting errors using printf()-style format strings with one modi cation: if the format string ends with :, then strerror¬ (errno) is appended to the error-message. The speci cation le is in errors.h.

You may assume that the environment in which your program will be compiled and run will have this library available.

1.6        Provided Files
The prj5-sol directory contains the following          les:

main.c This provides the main() program described above. You should not modify this le.

Cache Simulator Files The cache-sim.h le contains the speci cation for the API you are required to implement. You should not modify this le.

The cache-sim.c le will be the le where you do your work. As provided, it contains a skeleton implementation su cient to compile the program without errors. You should remove the placeholder return values and esh out the function de nitions given there (adding in any auxiliary declarations or de nitions which may be needed).

Make le A Makefile for the project. Note that this Makefile is set up to include a reference to the $HOME/cs220/lib directory in the executable so that it is possible to run the executable without needing to set up LD_LIBRARY_PATH. You should not need to modify this le.

README            A README template.

You must submit all the les in the above prj5-sol directory whether you modify them or not.

The aux- les directory contains the following           les:

Test les lru_2-2-2-8.test and mru_4-2-8-16.test These les provides addresses which can be used for testing your program. The les contain the expected output as comments following # characters. The options to your program should be those corresponding to the name of the test le. You will need to strip out the # comments before feeding the le to your program; this can be done simply using a Unix utility like sed. For example, assuming that you are in the directory containing your executable:

$ sed -e ’s/#.*//’ $HOME/cs220/projects/prj5/aux-files/lru_2-

2-2-8.test \

| ./cache-sim -r lru -v 2-2-2-8

If your simulator is working correctly, your output should match that shown within the test le.

A ruby script address-trace.rb This script can be used to generate address traces which can be piped into your program. It generates the following kind of traces:

matrix Addresses used to access a square matrix. The size of each matrix element is hardwired to be 8, but you can specify the size of the matrix as well as the access pattern (by row or by column).

program A typical program address trace. You can specify the probability of intra-procedure branches or inter-procedure calls/returns.

random A random address trace.

You can run the script with a --help option in general:

$ ./address-trace.rb --help to get general usage information or on a speci ed subcommand:

$ ./address-trace.rb matrix --help

For example, to run your program with an address trace corresponding to row-access for a 1024x1024 matrix:

$ $HOME/cs220/projects/prj5/aux-files/address-trace.rb matrix \

--access=row \

| ./cache-sim -r lru -v 4-4-8-32 t.log

To repeat, for column-access:

$ $HOME/cs220/projects/prj5/aux-files/address-trace.rb matrix \

--access=col \

| ./cache-sim -r lru -v 4-4-8-32 t.log You should not submit les from the aux-files directory.

1.7      Hints
Review the material covered in class and from the text pertaining to memory caches. Also, review online or other material to understand how to use the rand() function.

The following steps are merely suggestions:

1.   Look at how you can implement the CacheSimImpl structure for your cache simulator. Note that your cache simulator is not required to track the cached data, merely to simulate the hit/miss behavior of a real cache. Hence it seems su cient to merely:

•    For each cached line, merely track the address of the block it contains.

•    When the cache is empty, the contents of all cached lines will be invalid. As the cache lls up, these contents will become valid. Hence tracking the valid/invalid status of a cached line will be necessary.

•    For implementing the di erent replacement strategies, you will need to gure out how you will track the age of a cached line and/or organize them in a manner which facilitates the replacement strategy.

•    Since the cache parameters are only provided to the new_cache_¬ sim() function and you will need those parameters to simulate the cache in cache_sim_result(), the CacheSimImpl structure will also need to track the cache parameters provided to new_cache_sim().

2.   Since the cache parameters are available only at runtime (via the CacheParams argument), you will need to use dynamic memory allocation for the cache simulation.

Abstractly, a cache consists of a collection of cache sets with each cache set consisting of a collection of cache lines; i.e. a cache is a collection of collections. Alternatives for representing collections in C include arrays, linked lists, etc.

If you go with using arrays for representing collections, you might wish to use multi-dimensional arrays. OTOH, if you set up ragged arrays (as described in the transparencies), you can still use multi-dimensional array notation with dynamic memory (at the cost of extra memory for pointers).

Speci cally, you can always use dynamic allocation to get a pointer to a vector of elements and then use array indexing notation with the return’d pointer. For example, to emulate int a[m][n] using dynamically allocated ragged arrays, one can do:

int **a = malloc(m * sizeof(int *));

for (int i = 0; i < n; i++) {

a[i] = malloc(n * sizeof(int));

}

//can now use array notation like a[i][j].

3.   Start out your implementation without bothering about the replacement strategy; i.e. simply use any ad-hoc replacement strategy which is convenient for your code.

4.   Once you have veri ed that your code works for accessing the correct set and cache line, implement the di erent replacement strategies. For each cache line you could track when it was last accessed (where time can be tracked using a simulation clock which is advanced for each step of the simulation). Alternately, you could track relative access age using ordering within the tracked information.

Iterate until you meet all requirements.