CSE 378 Homework #6: Caches

Due: Friday, 3/11/2005

---

Assignment Goals

• Understand the mechanics of main memory caching through its implementation.
• Understand cache policy design issues through exploration of the design space.

Additionally, you'll get some experience with:

• Programming in C++
• Microsoft Visual Studio
• Modifying the Cebollita OS

And, for the preternaturally observant, it will be possible to glean something about how plug-ins work.

You'll do all of this in the context of the single cycle machine you built for HW5.

---

Overview

In the homeworks up to now we have ignored the fact that accessing memory is really, really slow. In fact, on modern processors it can take 100's to 1000's of cycles to fetch a word from main memory. In contrast, the machine organizations we have looked at implicitly assume that memory can be accessed in less than a cycle. Your HW5 machine fetches an instruction every cycle, for instance, and may also read or write a word of memory in that same cycle.

This assignment brings some greater realism to the data path. We now assume that going to main memory costs multiple cycles. To try to overcome the long memory access times we create two caches, one holding instructions and the other data. The main goal of this assignment is to understand how such caches work, and how design decisions about them affect performance. The class text, and the classes, will tell you more about caches.

As a practical matter, we introduce caches into your HW5 SMOK model by replacing its IF and MemoryInterface components with two new components, an ICache and a DCache (respectively). There are four (somewhat inter-dependent) parts to this, of differing levels of complexity:

• [Substantive] You will write C++ code that implements the behavior of the new cache component types. Your code will then be "injected" into the SMOK simulator, allowing the user (you) to create instances of those cache components as part of your model.

• [Trivial] Your code allows you to create new instances of cache components in your SMOK model (just like you can create ALU or MUX components, say). You'll replace the IF component in your HW5 model with a new ICache component, and the MemoryInterface component with a new DCache component.

• [Trivial to Moderate] Besides introducing the cache components, you have to extend your SMOK machine data path to deal with cache misses. In particular, the machine must stall until the data becomes available. (Because your machine is a single-cycle implementation, this is fairly easy.)

• [Moderate] Because the BlockController does DMA transfers (writes directly into memory), an issue of coherence arises -- if the cache contains entries for addresses written by the BlockController those entries will have incorrect values. As is often the case, the solution is to make it the software's problem. In particular, the hardware must implement a new instruction, flush offset($base), whose execution causes both caches to invalidate the cache entry for that address (if present in the cache). The OS must be modified so that each time it asks the BlockController to read a disk block (into memory), it executes flush instructions that cover the memory written.

Having done all that, you'll be ready for the final tasks:

• [Substantive] You will try to quantify the performance impact of different cache design decisions by implementing them and then running a benchmark suite of programs on your machine and collecting performance statistics. You'll use a combination of experimentation and reasoning to guide a search for "the best" cache design, subject to some constraints on implementation cost.

• [Substantive] Write an appropriately long (or short) report summarizing your methodology, your experimental results, and your conclusions about what combination of cache design choices is best.

---

Organizing the Work as a Set of Tasks

Having finished homework 5, finishing homework 6 is only a simple, seven task plan away. That plan is here.

---

Teamwork

Unlike past assignments, it is relatively easy to split up the work on this assignment, allowing each partner to make progress largely in parallel with the other. For one thing, there are two distinct caches to implement (the ICache and the DCache). Because the ICache is much simpler (no writes), the partner that takes it on might also be put in charge of implementing stalling and flushing. (That's just a suggestion, though.)

Also, as the bulk of what you're doing is C++ coding, it would be natural to use source control (cvs). This page, from Homework 3, gives the basic idea. As added encouragement, I'm distributing the initial set of files using per-team cvs repositories. You can ignore the repository after that if you like (but I wouldn't).

---

Files

• You should run the latest version of SMOK (V7.1.8). It has been installed for lab machines in the usual place (O:\nt\courses\cse378\smok\SMOK). If you created a shortcut should come up the next time you use it. On other machines, download it from the SMOK download page.

• You will need the latest version of Cebollita, which contains the code required to build the benchmarking shell. Get it from the Cebollita download page.

• The initial, degenerate ICache and DCache implementations have been placed in a cvs repository that belongs to your group (unless you changed the permissions on your repository directory to prohibit group writes, and so prevented me from copying the files to your repository). Fetch them from there:

  $ cvs -d :ext:login@attu:/projects/instr/05wi/cse378/cse378XXX/CVSRepository checkout smokCacheProject
  

  where "login" is your attu username and "XXX" is your group (e.g., a, b, etc.).

• Late addition:A zip of the original source file distribution is here.