CS61C

Estimated conceptual difficulty: 6/5
Estimated temporal difficulty: 8/5

Individual Project

This project will be done INDIVIDUALLY. The will be NO PARTNERS. If you partner, your grade will be divided by the number of members in your team.

Nonetheless, you are still encouraged to ask your peers for help, and answer their questions as well. As the gradescale has now been fixed, there is no longer any need to feel anxiety regarding the curve. Anxiety regarding your grade, however, may continue for another month.

Stay motivated! Two weeks from now, you'll be able to say that you're done with all your CS61C projects. Assuming, of course, that you're still alive.

What you should remember about caches in five years

The idea of caching is not unique to SRAM caches and swap files. Any time you access a lot of information, the concepts of temporal and spatial locality will boost performance.

Cache	Backing Store	Example: How It Uses Temporal Locality	Example: How It Uses Spatial Locality
Web Broswer Cache	The Internet	stores recently used pages	some advanced caches prefetch the current page's links
Database DRAM cache	database on disk	stores recently used data, plus additional features	data which are used together are placed sequentially on disk and prefetched
CD DRAM cache	data CD's	stores recently used data	prefetches nearby data
FAQ	all questions and answers in a newsgroup	if a question is asked a lot, it will probably be asked again	no real spatial locality here...
refrigerator	Costco	if you don't have lima beans in your refrigerator today, you probably won't want them tomorrow, either	when you buy from Costco, buy a lot so you don't have to go back too often

Note that all of the above caching systems have large miss penalties. As a result, most of them are fully associative and high capacity. Also, most of these caching systems typically worry about reads, not writes.

If the system requires a fast hit time, then it will prefer less associativity and smaller capacity.

In general, most systems use some form of LRU replacement, since the past often yields accurate predictions for the future.

Free Throw (1pt)

1) memory accesses in general, e.g. A[i] = B[i];
2) modern DDR SDRAM or RDRAM accesses using physical addresses
3) disk accesses
4) Internet accesses
5) CD-ROM accesses
6) tape accesses
7) food accesses

In a file called q.txt, put your answers as follows. Put your answer to #1 in the first byte in the file q.txt. The second byte will be your answer to #2, and so on. The eighth byte should be a newline. Your q.txt file should be 8 bytes long. Your answer should be the character '1' if you think it is truly random access, and '0' otherwise.

For example, if you think #3 and #5 are truly random access, then running ll and cat on your file should reveal:

quasar%ll q.txt
-rw-------   1 cs61c-xx cs61c          8 Nov  2 11:39 q.txt
quasar%cat q.txt
0010100
quasar%

Grading
0.3 points for correct formatting
0.1 point for each correct answer

Getting oriented

Otherwise, all you need to read is in print.h, memory.h, and memory.c. Edit memory.c only. You may edit the Makefile, but we will grade with our own. You may also add additional files. Hint: You might want to use files, including test files, from previous assignments.

If you're wondering about the rest of the memory.c code (which you don't need to deal with), translateAddress simulates a static, ad hoc TLB. accessDRAM simulates accesses to DRAM. Your cache is virtually addressed. That is, address translation takes place between the cache and DRAM, instead of between the processor and cache. Although physically addressed caches are more common, you are only asked to simulate a virtually addressed cache to minimize your dependence on caffeine during college.

Tasks

1. Implement initMemory to initialize your cache. If your cache doesn't need initialization, then this will be empty. cacheSizeInBlocks, associativity, and blockSizeInWords are set at run-time via command-line arguments. They are error checked for you. If you do not set the arguments, they default to 4, 1, and 4, respectively. Handling associativity > 1 is only for extra credit.

2. Modify accessMemory to simulate caching. Given the cache parameters, you must determine if the memory access will result in a hit or miss. You should then call printCacheAction(HIT) or printCacheAction(MISS). You may simulate caching anyway you want, or not at all, as long as you call printCacheAction correctly. Currently, the framework simply goes straight to DRAM and reports a printCacheAction(NONE).

Here are the cache parameters:
direct-mapped
unified data (instructions and data share one cache)
size determined at run-time
associativity determined at run-time (extra credit)
block size determined at run-time
write-through
allocate-on-write (writes should copy the block from DRAM to the cache, and call printCacheAction)

You can simulate this any way you want, but the easiest way is probably just to add a data structure which resembles a cache. As always, choose your data structure wisely.

Running

Update

A new version of the framework is out. Although it differs significantly from the previous framework, the interface between the cache and the rest of the system remains mostly unchanged. To update to the new framework, simply copy your current memory.c somewhere safe. Then, copy the new framework. Copy and paste your old initMemory, accessMemory, helper functions, and external variables to the new memory.c. That's it.

The most significant change is that there are no longer any external variables for cacheSizeInBlocks, associativity, and blockSizeInWords. Instead, they are passed as arguments to initMemory. If your code depends on them, you can keep your external variables:

static cacheSizeInBlocks, associativity, blockSizeInWords;

void initMemory(unsigned csize, unsigned assoc, unsigned bsize){
  ...
  cacheSizeInBlocks = csize;
  associativity = assoc;
  blockSizeInWords = bsize;
  ...
}

Grading

2.0	Effort
0.5	You should not use stdio.h in memory.c. You should not use printf, fprintf, vprintf, or vfprintf. You may use the other standard libraries, of course.
0.5	Reasonably commented code. It's your job to figure out what that means.
6.0	Other issues related to correctness

Grading will involve automated computer testing, so be good.

Estimated conceptual difficulty: 2/5
Estimated temporal difficulty: 1/5

If that's not enough for you, you can go for some extra credit.

Are you diehard?

Are you hardcore?

You may submit either a FIFO or an LRU solution, but not both. If you submit an N-way solution, you do not also receive points for handling fully associative. In other words, you only get one submission.

These extra credit things aren't really that hardcore; they're pretty easy if you're looking to round up some points.

Finally, there's a secret opportunity to earn an extra +0.25 points, but that's a secret...
Hint update: The secret extra credit has now been attained by someone or something. See if you can get it too!

Due date: Fri17Nov2000, 23:59:59.

Feedback