computer architecture

CSE 420 Spring 2014 Project 3 Due: 11:59 pm, March 28, 2014

Cache Behavior

To change the cache configurations and run gem5 on saguaro: Use the following command line to get help on the options to make changes to the cache architecture configuration:

Before running gem5, execute module-load.sh to load all required libraries. For example,

> ./module-load.sh

Once the script executes, you can run gem5. For example, to run the qsort benchmark with the cache specification inProblem 1 & 3: > ./build/ALPHA/gem5.opt ./configs/example/se.py --cpu-

type=timing --caches --l2cache --num-l2caches=1 --l1d_size=8kB -

-l1i_size=8kB --l1d_assoc=1 --l1i_assoc=1 --l2_assoc=4 --

cachelilne_size=16 -c <path to qsort benchmark> -o <path to

input.dat>

To understand what each of the above parameters represent, please use the script: > build/ALPHA/gem5.opt configs/example/se.py -h

(For the successful execution of the command-line in saguaro, the required modules have to be loaded. And this has to be done for every login into the saguaro system. For this, the "module-load.sh" script will load the required modules.)

Problem 1 [25 Points]: Caches are vital to computer architecture. Since direct mapped caches may suffer from a lot of interference, and are very susceptible to the data placement in memory, most caches are set associative. Step 1 – Run the given matrix multiplication program ("Program/MatrixMultiply") for the following cache configurations with the Gem5 simulator with the TimingSimpleCPU model. (The source code of the program is also given for you to analyze the data access behavior.)

Config. No. L1 Cache Name

Cache Size

Set Associativity (k)

Cache Block Size

1 (Direct-map)

L1-Inst & Data 8KB 1 16B

L2-Cache 16KB 4 16B

2 (Associativity)

L1-Inst & Data 8KB 2 16B

L2-Cache 16KB 8 16B

3 (Cache size)

L1-Inst & Data 16KB 2 16B

L2-Cache 32KB 8 16B

4 (Block size)

L1-Inst & Data 16KB 2 64B

L2-Cache 32KB 8 64B

5 (Associativity)

L1-Inst & Data 16KB 4 64B

L2-Cache 32KB 16 64B

Step 2 – For each of the cache configurations, compute the following values, for each benchmark, and also the average values for each configuration:

- L1 Instruction cache (Cache-misses/Instruction) - L1 data cache (Cache-misses/Instruction) - L2 cache (Cache-misses/Instruction)

Question 1:

Explain the difference in the number of misses/instruction for the four configurations, through analysis of the data access patterns of the program across the cache configurations.

Problem 2 [50 Points]: In the design of set associative caches, an important design parameter to analyze - is the block replacement policy. Block replacement policy essentially determines which block (of the blocks in the set) must be evicted from the cache, when it is time to bring in new data. “One of the most popular cache replacement policies is Least Recently Used (LRU) block. In this scheme, we evict the block that has been unused for the longest period of time. While it seems to be one of the most intuitively promising block replacement schemes, implementation complexity is its main disadvantage. LRU has to maintain an access history for each block, which will slow down the cache. As a result, most caches implement only an approximation of LRU.” Step 1 – Study the LRU block replacement policy implemented in gem5, and comment on its accuracy. Note: You will find the cache replacement policy implementation in the following file in the gem5 source: “/src/mem/cache/tags/lru.cc”

Step 2 – Read the RRIP replacement schemes proposed and explained in a recently

published paper in ISCA 2010 - [http://dl.acm.org/citation.cfm?id=1815971]. (The

paper is attached with this project zip file). Implement the 2-bit SRRIP block

replacement policy in Gem5. The RRIP replacement schemes are proposed and

explained in a recently published paper in International Symposium on Computer

Architecture (ISCA) 2010 –

Note: You will have to make changes in the file - “lru.cc”, and other files (like the

block.cc or block.hh) as required by your implementation.

Question 2:

Briefly describe the logic behind the SRRIP replacement policy implementation in gem5.

Under what conditions or data patterns would you expect the SRRIP methodology to

perform better than LRU, and vice-versa. Explain your answer briefly.

Problem 3 [25 Points]: Run Gem5 with the newly implemented cache replacement

policy on the four benchmarks (attached with this project zip file), provided to you in the

last assignment. Study the performance of the two replacement policies, by studying the

following cache simulation statistics. You may also include other cache output statistics

to study and analyze the two block replacement policies:

- L1 Instruction cache (Cache-misses/Instruction) - L1 data cache (Cache-misses/Instruction) - L2 cache (Cache-misses/Instruction)

Question 3:

Run all the benchmarks with SRRIP replacement policy, with the cache specifications

from Problem 1. Compare the performance against LRU (from problem 1) for L1I, L1D

and L2 caches using bar graphs for each of the cache parameters analyzed.

Project Deliverables:

1. Source code of your SRRIP implementation. You need to submit only the new

versions of the source files that you have modified. Please do not submit the

entire source for gem5.

2. For Problem 1: Briefly answer the question posed. You may use graphs or plots

to support your explanations.

3. For Problem 2: Briefly, in a small paragraph, summarize your understanding of

the SRRIP replacement policy, and its difference with respect to the LRU cache-

replacement policy.

4. For Problem 3: Present graphs that demonstrate and compare the simulation

results for each of the cache parameters analyzed. From the graphs, explain the

observed differences (or the lack thereof), and justify with your understanding of

the SRRIP and LRU replacement policies.

5. Team.txt : which contains names and ASU IDs of team participants, and their

percentage of effort in the project.