Starting from:
$29
Project 2 Cache subsystem organizations
Project 2
The goal of this project is to measure the effectiveness of cache subsystem organizations using traces of memory instructions obtained from the realistic programs. Each trace contains about 1 million memory instructions with two values provided for each instruction: a flag indicating whether this is a load or a store (L stands for a load, S stands for a store), and the byte memory address targeted by this instruction. Three traces are provided.
Your goal is to write a program in C or C++ that would use these traces to measure the cache hit rate of various data cache organizations and prefetching techniques (note: we are not estimating the instruction cache performance in this project, only the data cache). Specifically, the following cache designs have to be implemented.
*****32 bit address = tag, index, and offset bits*****
Cache line size == 32 bytes so 5 bits for offset
1) [10%] Direct-Mapped Cache. Assume that each cache line has a size of 32 bytes and model the caches sized at 1KB, 4KB, 16KB and 32KB
number of lines = 1KB (2^10) / 32 bytes (2^5) = 32 (2^5)
number of lines = 4KB (2^12) / 32 bytes (2^5) = 128 (2^7)
2) [20%] Set-Associative Cache. Again, assume that the cache line size is 32 bytes and model a 16KB cache with associativity of 2, 4, 8 and 16. Assume that the least recently used (LRU) replacement policy is implemented.
Cache associativity is how many caches you will have
for 2 set associativity: each cache is 8KB = 256 lines
26 bits, 5 bits, and 1 bit to know which cache to go into (offset)
for 4 set associativity: each cache is 4KB = 128 lines
25 bits, 5 bits, and 2 bit
3) [20%] Fully-Associative cache. Assume that each cache line is 32 bytes and the total cache size is 16KB. Implement Least Recently Used (LRU) and hot-cold LRU approximation policies. For the hot-cold LRU approximation policy the initial state of all hot-cold bits should be 0 corresponding to the case where the left child is “hot” and the right child is “cold”. Furthermore, the policy should be utilized (and updated) for all accesses, including placing the initial blocks into the cache as well as replacements once the cache is full.
Single line 16KB/32 = 512 caches with one line each
split in two, 1-256 and 257-512
one becomes hot and one cold
4) [10%] Set-Associative Cache with no Allocation on a Write Miss. In this design, if a store instruction misses into the cache, then the missing line is not written into the cache, but instead is written directly to memory. Evaluate this design for the same configurations as in question (2) above.
5) [20%] Set-Associative Cache with Next-line Prefetching. In this design, the next cache line will be brought into the cache with every cache access. For example, if current access is to line X, then line (x+1) is also brought into the cache, replacing the cache’s previous content. Evaluate this design for the same configurations as in question (2) above. Note that prefetched blocks should update the LRU order of the corresponding set meaning that the prefetched block should become the most recently used block in its set.
6) [20%] Prefetch-on-a-Miss. This is similar to part (5) above, but prefetching is only triggered on a cache miss. (Prefetched blocks should update the LRU order as in part 5).
Extra credit problem [20%]: Propose and implement a new cache replacement or prefetching mechanism that outperforms either the LRU replacement or the next-line prefetcher. Evaluate your proposal on the designs listed in question (2) above. Feel free to use any supplementary literature that you can find on this subject. If you choose to do the extra credit you should provide an explanation of what you have done, how to test it, and why it works in the README file in your submission.
Materials on Blackboard:
There is a tar/gzipped archive of materials on Mycourses that contains the following:
A directory called project2/, containing the following files:
- sample_output.txt – Sample output file with comments
- traces/ – Directory containing three trace files
- correct_outputs/ – The correct output for each of the provided traces
To access these materials, download a copy from Mycourses, cd into the directory where you placed the tar/gzipped archive and unzip it.
This will create a new directory (named project2/ ) containing the files mentioned above.
The goal of this project is to measure the effectiveness of cache subsystem organizations using traces of memory instructions obtained from the realistic programs. Each trace contains about 1 million memory instructions with two values provided for each instruction: a flag indicating whether this is a load or a store (L stands for a load, S stands for a store), and the byte memory address targeted by this instruction. Three traces are provided.
Your goal is to write a program in C or C++ that would use these traces to measure the cache hit rate of various data cache organizations and prefetching techniques (note: we are not estimating the instruction cache performance in this project, only the data cache). Specifically, the following cache designs have to be implemented.
*****32 bit address = tag, index, and offset bits*****
Cache line size == 32 bytes so 5 bits for offset
1) [10%] Direct-Mapped Cache. Assume that each cache line has a size of 32 bytes and model the caches sized at 1KB, 4KB, 16KB and 32KB
number of lines = 1KB (2^10) / 32 bytes (2^5) = 32 (2^5)
number of lines = 4KB (2^12) / 32 bytes (2^5) = 128 (2^7)
2) [20%] Set-Associative Cache. Again, assume that the cache line size is 32 bytes and model a 16KB cache with associativity of 2, 4, 8 and 16. Assume that the least recently used (LRU) replacement policy is implemented.
Cache associativity is how many caches you will have
for 2 set associativity: each cache is 8KB = 256 lines
26 bits, 5 bits, and 1 bit to know which cache to go into (offset)
for 4 set associativity: each cache is 4KB = 128 lines
25 bits, 5 bits, and 2 bit
3) [20%] Fully-Associative cache. Assume that each cache line is 32 bytes and the total cache size is 16KB. Implement Least Recently Used (LRU) and hot-cold LRU approximation policies. For the hot-cold LRU approximation policy the initial state of all hot-cold bits should be 0 corresponding to the case where the left child is “hot” and the right child is “cold”. Furthermore, the policy should be utilized (and updated) for all accesses, including placing the initial blocks into the cache as well as replacements once the cache is full.
Single line 16KB/32 = 512 caches with one line each
split in two, 1-256 and 257-512
one becomes hot and one cold
4) [10%] Set-Associative Cache with no Allocation on a Write Miss. In this design, if a store instruction misses into the cache, then the missing line is not written into the cache, but instead is written directly to memory. Evaluate this design for the same configurations as in question (2) above.
5) [20%] Set-Associative Cache with Next-line Prefetching. In this design, the next cache line will be brought into the cache with every cache access. For example, if current access is to line X, then line (x+1) is also brought into the cache, replacing the cache’s previous content. Evaluate this design for the same configurations as in question (2) above. Note that prefetched blocks should update the LRU order of the corresponding set meaning that the prefetched block should become the most recently used block in its set.
6) [20%] Prefetch-on-a-Miss. This is similar to part (5) above, but prefetching is only triggered on a cache miss. (Prefetched blocks should update the LRU order as in part 5).
Extra credit problem [20%]: Propose and implement a new cache replacement or prefetching mechanism that outperforms either the LRU replacement or the next-line prefetcher. Evaluate your proposal on the designs listed in question (2) above. Feel free to use any supplementary literature that you can find on this subject. If you choose to do the extra credit you should provide an explanation of what you have done, how to test it, and why it works in the README file in your submission.
Materials on Blackboard:
There is a tar/gzipped archive of materials on Mycourses that contains the following:
A directory called project2/, containing the following files:
- sample_output.txt – Sample output file with comments
- traces/ – Directory containing three trace files
- correct_outputs/ – The correct output for each of the provided traces
To access these materials, download a copy from Mycourses, cd into the directory where you placed the tar/gzipped archive and unzip it.
This will create a new directory (named project2/ ) containing the files mentioned above.
2 files (7.5MB)
