Write in you choice of object-oriented language (Java, C++, C#, Smalltalk, Common LISP), an N-way set-associative cache simulation. Your program should accept the following command-line arguments (in any order): -s cache-size, -w ways, -f (for FIFO) or -l (for LRU), in addition to the name of the trace file containing memory traces in Dinero format. The cache-size is the total number of memory words that your program's cache can store at any one time. The ways is the associativity of the cache, for example -w 4 is a 4-way set-associative cache. In a normal cache, entries include both the address and data, but in your case, your cache entries will include only the address tag. Also, your cache will always have a block size of one memory word and use write-back (so a dirty bit is needed). Your program will simulate memory accesses as specified in the trace file and your program will keep track of hits, misses, and compute the hit ratio. Your program will print the total number of hits, misses and the hit ratio at the end of the program. Misses include all reads from memory and all writes to memory, which happen when a dirty cache entry is evicted from the cache.
Be sure to use proper object-oriented programming practice. Points will be deducted for any duplicate code. If you have LRU and FIFO cache clases and these have code (either methods or data members) in common, then this common code should be inherited from a shared parent class.
To implement an N-way cache, I recommend N arrays of int (to store the memory address tags), each of size cache-size/N. For example, a 4-way 2K cache would have 4 arrays, each of size 512 entries (2K/4). To implement FIFO, you need an array of queue indices (one for each entry) that specifies which array should be overwritten with a memory address tag (don't forget to increment this modulo N after each insertion). To implement LRU, you need to keep track of the order that each entry was last used (entered into the cache or matched in the cache). The easiest way is to keep a ranking (an int in your program, but only a few bits in hardware) with each entry. For example, the rankings in a 4-way cache would have possible values from 0 (most recent) to 3 (least recent) with each entry in a slice having a unique ranking. Each time an entry is used, its ranking is reset to 0 and all rankings of other entries in the same slice that are below the entry's old ranking are incremented (e.g., the old rank 0 entry now becomes rank 1). Alternatively, you can keep the subcache numbers in a priority queue and each time an array entry is entered/matched, it is moved to the end of the queue. Be sure to initialize your valid bits to invalid at the start of your program.
Test your program with all combinations of FIFO and LRU, 1-way (equivalent to direct-mapped), 2-way and 4-way and cache sizes of 2k, 8k, and 32k (15 different cases because there is no difference between FIFO and LRU for a direct-mapped caches, so your statistics for FIFO 1-way should be exactly thexp same as your statistics for LRU 1-way for the three different cache sizes). Use data from either cc1.din, spice.din and tex.din (.din is the extension for Dinero format trace files) depending on whether you are the first (use cc1.din), second (use spice.din), or third (use tex.din) or fourth (use cc1.din) member listed in your Quiz Show Group. Present your results by graphing the hit-ratios and by summarizing the hit-ratios in tables. In your analysis, answer the questions: Under what conditions (if any) does FIFO or LRU work better than the other? How does cache size and associativity affect how well the cache works (i.e., the hit-ratios)?
Here are some Dinero format memory trace files from J. Hennessy and D. Patterson (of RISC fame) Computer Architecture textbook. cc1.din is a trace of running the C compiler; spice.din is a trace of running the Spice circuit design/simulator software; tex.din is a trace of running the Tex text formatting software.
In GNU gzip format:
In zip format:
Here are truncated (200-line) versions of the above that I recommend for use in initial testing of your program:
Submit all your source code files. Name your compilation and running instructions readme.txt and name your analysis file(s) analysisN.doc, analysisN.rtf, analysisN.txt, analysisN.gif, analysisN.jpg or analysisN.pdf where N is a unique number for each file starting from 1 (it's best to have just one file, especially if you have a .doc, .rtf or .pdf type file). Put all the files into one directory (without subdirectories) and compress it using the one of the widespread archivers (zip, tar, rar, gzip etc.). Then you have to send the archive to our TA for examination.