Cache Simulator You are to write a cache memory simulator. Your cache simulator must be able to:
1. Handle any cache data size.
2. Handle any block blocks sizes which is a power of 2.
3. Be able to simulate direct mapped, or "N way set" associative caches (N is a power of two)
4. Be able to simulate either write back or write-back caches.
5. Be able to handle either an allocate or non-allocate policy on write miss.
6. Implement Least-recently used block replacement.
7. Accept a parameter for memory access time (in clocks) and compute average access time, hit/ miss ratios for both read and write operations.
8. Be able to specify a victim buffer of K blocks (victim buffer is fully associative)

You cannot work in groups. A sample of what your cache program should output is shown below:

% cache -s 1 -b 4 -W -c -a 1 -m 3 sample.din
size (kbytes) = 1
# of lines = 256
bytes/line = 4
associativity = 1
write policy = write back
write allocate = Yes
mem penalty = 3
--------------
accesses = 1000 [reads = 704 ( 70.40%) writes = 296 ( 29.60%)]
hits = 765 ( 76.50%) [reads = 559 ( 55.90%) writes = 206 ( 20.60%)]
misses = 235 ( 23.50%) [reads = 145 ( 14.50%) writes = 90 ( 9.00%)]
access time = 1.5270 

Program options are: 
cache {options}: 
-s size cache size in K bytes (power of two) 
-b size cache size in bytes (power of 2), assume each access is word 
-a num cache associativity, 1 is direct mapped 
-c write-back, normally write through 
-W write allocate, normally not write allocate 
-m num memory access time in clock cycles 
-v number of victim buffer blocks 
Cache access time is assumed to be 1 clock cycle 

There some cache trace files ('*. din file extension') that you can use for test purposes. The format of the trace data files is show 
below: 
2 20d Dinero input format "din" is an ASCII file with 
2 211 one LABEL and one ADDRESS per line. The rest of 
0 1fc780 the line is ignored so that it can be used for 
1 7fffccb0 comments. 
2 213 
2 217 LABEL = 0 read data 
0 1fc77c 1 write data 
1 7fffccac 2 instruction fetch 
2 219 3 escape record (treated as unknown access type) 
2 21d 4 escape record (causes cache flush) 
0 1fc778 
1 7fffcca8 

an ADDRESS is  ffffffff where the hexadecimal addresses 
are NOT preceded by "0x."
Some Data sets

small sample
1000 addresses
a real program addresses

The important thing to note about this data input file is that each line specifies a memory access via address information and whether the access was read or write. It DOES NOT contain the data for that memory access. The data bytes actually associated with the access are not needed when determining hit/ miss information for the cache; we just need to know which LOCATION (address) is being accessed.

When simulating your cache, you will need to keep an integer array (cache_ array) whose size is equal to the number of blocks in the cache. This array will be used to store the tag value currently associated with that block. The size of cache_ array is the number of blocks in the cache which is computed as:

# of blocks = (cache_ size * 1024)/( block_ size). where cache_ size is the size of the cache in Kbytes. You can think of this linear array being grouped into lines, where each line contains 'associativity' number of blocks. The number of lines is computed as:

#lines = # of blocks / associativity Note that if associativity = 1, then #lines = # of blocks and we have a direct mapped cache. Each entry in cache_ array will contain the tag value for that block. Given an address, we need to compute the index (or line number) and the tag value which corresponds to that address and check this tag against the tag values stored in cache_ array at that line number. The index and tag value can be computed from the address via:
index = (address / (block_ size)) modulo #lines
tag = address / (block_ size * # lines)

Initially, each cache array value should initialized to a '- 1' value indicating that this cache block is empty. To check for a hit given an address you should:

1. compute the tag corresponding to that address 2. compute the index (line number) corresponding to that address 3. Starting at array value = index * associativity, check the next 'associativity' entries to see if the tag stored in the array is equal to the tag computed from the address. If a match is found this indicates a hit, else it is a miss.

If a cache miss is found and associativity > 1, then you must choose a particular block to replace. If one of the blocks is 'empty' (tag = -1), then this block should be chosen. If all blocks in a line have valid tags, then you must choose a block using Least- Recently- Used replacement. The easiest way to do this is to keep a separate integer array ('lru_ count') whose size is equal to the number of blocks in the cache. Initially, these values should be '0'. When checking all of the blocks in a line for a hit, if the block tag value does NOT match the address tag value then the associated 'lru_ count' entry should be incremented by one (this is a miss). If the block tag value DOES match the address tag value, then the associated 'lru_ count' entry should be set back to zero (a hit, a zero value indicates this block is the most- recently- used block in this cache line). When picking a block in a particular line to replace, choose the block with the highest 'lru_ count' value - this will be the 'oldest' or least- recently- used block in that cache line.

You must also keep a separate array which tracks dirty bit values for each block in the cache - this will be used when you are simulating a writeback policy.

The easiest way to compute average access time is to keep two counters - one for total number of accesses and one for total number of clocks. Increment the accesses counter for each address processed. Increment the clock counter by 1 for each word (4 bytes) read/ written to the cache; increment the clock counter by the memory penalty for each word read/ written to main memory. Divide the total number of accesses into the clock counter for average word access time.

Here are a few more sample runs: 

./cache -s 1 -b 4 -W -c -a 1 -m 3 sample.din

cache.exe -s 1 -b 4 -W -c -a 1 -m 3 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 1
# of lines = 256
bytes per line  = 4
associativity = 1
write policy = Write back
write allocate = Yes
mem penalty = 3 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 765(76.5%)[ reads = 559(55.9%) writes = 206(20.6%)]
miss = 235(23.5%)[ reads = 145(14.5%) writes = 90(9%)]
access time = 1.492 cache accesses 1000 mem acccesses 164
bash-2.05b$ ./cache -s 1 -b 8 -W -c -a 1 -m 3 sample.din

cache.exe -s 1 -b 8 -W -c -a 1 -m 3 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 1
# of lines = 128
bytes per line  = 8
associativity = 1
write policy = Write back
write allocate = Yes
mem penalty = 3 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 863(86.3%)[ reads = 619(61.9%) writes = 244(24.4%)]
miss = 137(13.7%)[ reads = 85(8.5%) writes = 52(5.2%)]
access time = 1.912 cache accesses 1000 mem acccesses 304
bash-2.05b$ ./cache -s 1 -b 8 -W -c -a 2 -m 3 sample.din

cache.exe -s 1 -b 8 -W -c -a 2 -m 3 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 1
# of lines = 64
bytes per line  = 8
associativity = 2
write policy = Write back
write allocate = Yes
mem penalty = 3 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 872(87.2%)[ reads = 627(62.7%) writes = 245(24.5%)]
miss = 128(12.8%)[ reads = 77(7.7%) writes = 51(5.1%)]
access time = 1.81 cache accesses 1000 mem acccesses 270
bash-2.05b$ ./cache -s 16 -b 32 -W  -a 1 -m 3 sample.din

cache.exe -s 16 -b 32 -W -a 1 -m 3 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 16
# of lines = 512
bytes per line  = 32
associativity = 1
write policy = Write Through
write allocate = Yes
mem penalty = 3 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 953(95.3%)[ reads = 674(67.4%) writes = 279(27.9%)]
miss = 47(4.7%)[ reads = 30(3%) writes = 17(1.7%)]
access time = 2.128 cache accesses 1000 mem acccesses 376
bash-2.05b$ ./cache -s 16 -b 32 -W  -a 16 -m 3 sample.din

cache.exe -s 16 -b 32 -W -a 16 -m 3 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 16
# of lines = 32
bytes per line  = 32
associativity = 16
write policy = Write Through
write allocate = Yes
mem penalty = 3 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 953(95.3%)[ reads = 674(67.4%) writes = 279(27.9%)]
miss = 47(4.7%)[ reads = 30(3%) writes = 17(1.7%)]
access time = 2.128 cache accesses 1000 mem acccesses 376
bash-2.05b$ ./cache -s 16 -b 32 -W  -a 64 -m 10 sample.din

cache.exe -s 16 -b 32 -W -a 64 -m 10 sample.din
file : sample.din


---cs641 cache simulator --- 
cache size(kbytes)  = 16
# of lines = 8
bytes per line  = 32
associativity = 64
write policy = Write Through
write allocate = Yes
mem penalty = 10 


accesses = 1000 [reads = 704(70.4%) writes = 296(29.6%)]
hits = 953(95.3%)[ reads = 674(67.4%) writes = 279(27.9%)]
miss = 47(4.7%)[ reads = 30(3%) writes = 17(1.7%)]
access time = 4.76 cache accesses 1000 mem acccesses 376
bash-2.05b$
How to submit your result

You will need to create a directory in your cs641 unix account that will hold both your source files and your executable image. To submit your assignment, you will need to email the path to that directory to me: norm@cs.umb.edu.