SFU Intro Systems Class Caches
Skip to main content
Copyright By PowCoder代写 加微信 powcoder
Toggle navigation
Intro to Computer Systems
Assignments
Quiz/Exams
developed the first compiler for a computer programming language.
Github clone link
Background
Part 1 Cache Model
Check yourself
Trace files
Reference Cache Binary
Source Files
Debugging Hints
End-to-End Grading
Acknowledgments
Github clone link
Github clone
Learning Objectives:
Gain basic familiarity with cache geometries and how different associativities and line sizes present themselves.
Evaluate a claim made in the lecture slides that two seemingly equivalent ways of writing a program can have vastly different performance.
Gain experience in designing cache-friendly code.
In the first part we build a simulator for modeling a single level cache. We run traces extracted from valgrind through this cache model and estimate the number of misses, hits, and evictions.
In the second part of this assignment we try to reverse engineer and discover cache geometries. Instead of running programs on these processors and inferring the cache layout from timing results, you will approximate his work by using a simulator.
WARNING: Note that the logical variable used to represent block offset vary from the lecture slides. In representation below, case matters
Lecture Assignment Description
s s Number of set bits
S S $2^s$ Number of sets
E E Number of ways
k b Number of block bits or byte offset.
K B $2^b$ Size of block in bytes
Background
This image shows the last 2 bytes of the address of each cache block as they align to the 32×32 matricies. Red squares notate the start of a section that would fit in cache. Green lines divide individual integers, and black lines divide cache blocks.
Part 1 Cache Model
This assignment will help you understand the impact that cache memories can have on the performance of your C programs. You will write a small C (not C++!) program of about 200-300 lines that simulates the behavior of a cache memory.
Check yourself
Do you know what a tag is ?
Do you know what is the difference between int*_ and int_?
Given number of set bits, and block bits, do you know how to extract tag bits ?
Tag Comparison Selects the set Block offset
Tag(t) Set index (s) byte offset
Trace files
cd $REPO/model
ls traces/
dave.trace fifo_m2.trace fifo_s3.trace yi2.trace
fifo_l.trace fifo_s1.trace long.trace trans.trace
fifo_m1.trace fifo_s2.trace small.trace yi.trace
The traces directory contains a collection of reference trace files that we will use as input to evaluate the correctness of your cache simulator. The trace files are generated by a Linux program called valgrind. For example, typing
valgrind –log-fd=1 –tool=lackey -v –trace-mem=yes ls -l
on the command line, valgrind runs the executable program ls -l, captures a trace of each of its memory accesses in the order they occur, and prints them to stdout.
Memory traces have the following form:
M 0421c7f0,4
L 04f6b868,8
S 7ff0005c8,8
Each line denotes one or two memory accesses. The format of each line is operation,address,size.
The operation field denotes the type of memory access: L a data load, S a data store, and M a data modify (i.e., a data load followed by a data store).
WARNING: The trace files we consider will not have I operations in them.
The address field specifies a 64-bit hexadecimal memory address.
The size field specifies the number of bytes accessed by the operation.
Reference Cache Binary
We have provided you with the binary executable of a reference cache simulator, called cache-ref, that simulates the behavior of a cache with arbitrary size and associativity on a valgrind trace file. Your assignment is to create a cache model cache that mimics the behavior of cache-ref.
-h: Optional help flag that prints usage info
-v: Optional verbose flag that displays trace info
-s : S = \(2^s\). s is the number of bits used for the set index)
-E : Number of lines per set (associativity or number of ways)
-b : is the number of bits used for the byte offset within the line. Number of bytes per block = $2^b$
-t : Trace file to be processed. cache-ref reads file line-by-line and feeds to cache simulator
-v : verbose mode. Displays what happens to each line.
Displays “ hit “, “ miss eviction “, “ miss “ for each access based on what happened when operating on the cache.
-L – LRU policy. Your own model cache only needs to implement LRU and does not need to implement this option.
WARNING: Note that when running with cache-ref you have to include -L option. But when running with your own model you should remove option
# sets = 2^2 = 4 E=1 Number of lines per set (Number of ways) b = 5. Block size = 2^5 = 32 bytes. -L : LRU policy
./cache-ref -s 2 -E 1 -b 5 -L -t traces/yi.trace
hits:4 misses:5 evictions:3
# If you have implement cache.c correctly run as such
./cache -v -s 2 -E 1 -b 5 -t traces/yi.trace
hits:4 misses:5 evictions:3
# Verbose run
./cache -v -s 2 -E 1 -b 5 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3
Source Files
You will write a cache simulator in cache.c that takes a valgrind memory trace as input (we provide the traces), simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions. The output has to match the reference simulator, both verbose and concise.
Functions you will have to fill in:
Function to be implemented Description
cache_tag Return the tag of an address
cache_set return the set index of the address
probe_cache check if the block of the address is in the cache. If yes, return true. Else return false
allocate_cache Insert block in cache
avail_cache check if empty way available. if yes, return true, else return false
victim_cache Find the victim line to be removed from the set . Return the index/way of the block. The victim will be the least-recently-used block
evict_cache Remove/Invalidate the cache block in corresponding set and way.
operateCache Top-level method that is given an address, and then invokes other methods to implement the cache model.
Data structures that have been provided
// Per cache-line datastructure
typedef struct Line {
unsigned long long block; // Dummy Datablock. Need not implement.
short valid; // True: Cacheblock valid False: Cacheblock invalid
unsigned long long tag; // The tag of block
int lru_clock; // Used to maintain the LRU of the line
typedef struct Set {
Line *lines; // List/Array of lines in set
int lru_clock; // Per-set lru clock
typedef struct Cache {
// Parameters
int setBits; // s
int linesPerSet; // E
int blockBits; // k
// Core data structure
Set *sets;
// Cache statistics
int eviction_count;
int hit_count;
int miss_count;
// Used for verbose prints
short displayTrace;
When selecting a victim to evict from the cache set you need to implement the LRU policy. To implement the LRU policy we give you a lru_clock field per-line and per-set. The lru_clock is incremented on each access to the set. Thus, the lru_clock value when a cache line in accessed is the indicative of recency. Try and figure out when is lru_clock per set incremented, when is the line’s lru_clock set?, what value is it set to?, how to find LRU block when choosing victim?
Debugging Hints
Here are some hints and suggestions for working on this assignment:
Do your initial debugging on the smaller traces.
. Number shows number of memory accesses in trace.
5 dave.trace
269998 fifo_l.trace
400 fifo_m1.trace
10 fifo_s1.trace
14 fifo_s2.trace
16 fifo_s3.trace
267988 long.trace
2 small.trace
7 yi.trace
16 yi2.trace
The reference simulator takes an optional -v argument that enables verbose output, displaying the hits, misses, and evictions that occur as a result of each memory access. It will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator on the reference trace files.
The data modify operation (M) is treated as a load followed by a store to the same address. Thus, an M operation can result in two cache hits, or a miss and a hit plus a possible eviction (even when only 1 byte is modified).
End-to-End Grading
$ bash ./scripts/localci.sh
# if you see SUCCESS and *.log.sucess then you passed. You can also check your *_Grade.json to see your tentative grade.
# If you see FAILED, then inspect *.log.failed. Check the failed section to see what tests failed.
Remember from the testing framework section that these sanity tests are not comprehensive, and you should rely on your own tests to decide whether your code is correct. Your score will be determined mostly by hidden tests that will be ran after the submission deadline has passed.
Double check your tag and set calculations
Check if the victim blocks match your expectations against the reference simulator
Acknowledgments
This assignment has been created by the CMPT 750 instructor based on the CS:APP textbook.
Last updated June 29, 2022.
Derived from
and modified by
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com