Machine Structures. Summer 2006, UC Berkeley
Project 4: Cache Simulator
TA in charge: Michael (cs61c-tb@imail)
Due date: Tuesday, August 15, 2006 at 11:59pm

Last Updated: Saturday, August 15, 2006 at 01:54pm

Updates


Purpose

In this project, you will be implementing the cache logic of a MIPS simulator, called TIPS. Most of the code for TIPS has been implemented for you, except the cache logic.


Setup

To copy tips to your home directory, enter the following commands:

  % cd
  % mkdir proj4
  % cd proj4
  % cp ~cs61c/proj4/* .

To compile and execute TIPS, do the following:

  % gmake
  % ./tips

The given code has a default cache size of 0, because it has no cache logic written into it yet. After you build and run TIPS, you can configure the cache by clicking on the "Config Cache" button at the lower left of the interface. After configuring the cache, the GUI should update showing you a cache similar to the parameters you have entered.


GUI Walkthrough

The GUI has been designed to be straight-forward. There are four main components to the GUI interface: register display, execution log, cache display, and control panel.

 

A description of each of the GUI widgets are described as follows:

  1. Register display -- detailed view of the current state of the registers
  2. Execution log -- log of actions by TIPS. Messages can be displayed in this box using the append_log() function.
  3. Cache display -- current snapshot of the state of the cache. The meaning of the column headings on each unit should be obvious.
    • Blk - block number
    • V - valid bit
    • D - dirty bit
    • LRU - LRU data
    • Tag - Tag for the block
    • Numbers - offset
  4. Config Cache -- configure the cache parameters
  5. Load Program -- loads a dump file for execution
  6. Step -- execute one instruction
  7. Run -- automate execution
  8. CPU -- reset the PC and reinit registers
  9. Cache -- flush the cache
  10. Output -- clear the execution log
  11. Quit -- exit TIPS


Task

To complete this project, you must complete the accessMemory() function in cachelogic.c. This function is the gateway to accessing actual memory, represented by the accessDRAM() function. Thus, the behavior of accessMemory() function should be a cache that will call the accessDRAM() function as needed.

To ensure a variety of caches can be simulated, you will be required to dynamically support 5 properties:

More information about the variables you will be working with and the functions at your disposal with can be ascertained by looking over tips.h.

You should keep the following things in mind when formulating the code to do the task at hand:


Getting Started

Look over what is mentioned in tips.h and cachelogic.c. tips.h gives you an overview of how the program was put together. A section of that file has been marked as something you should read to get an idea of what functions you should be calling as well as the variables you are working with. cachelogic.c contains a slightly more detailed explanation of what you should be writing in accessMemory() function.

The cache data structure is divided into three levels:

There are two methods to access the LRU information of a block. The first method is via lru.value, a field that will hold LRU information in integer format. The other method is via lru.data, a field that will hold LRU information represented in another format (as its type is of void*, which means it can be a pointer to anything). You are free to use either methods to represent the LRU, just as long as the LRU behaves in a deterministic fashion (i.e. no two blocks (when both are valid) will ever be candiates for replacement at the same time).

In a nutshell, the accessMemory() function is a function that facilitates communication between the CPU and DRAM. The code within the accessMemory() function manipulates the cache data structure defined in tips.h.


Creating Dump Files for Testing

TIPS contains a subset of the MIPS R2000 processor instruction set. As a result, it accepts MIPS code dumped by spim. The dump file can be loaded into the program by clicking on the "Load Program" button.

Dumpfiles should be created using spim. The following command sequence will ensure you make a compatible dumpfile for TIPS. The delayed-branches flag is VERY important to get branches to work properly with TIPS.

  cs61c@nova [22] ~/proj5 > spim -delayed_branches
  SPIM Version 7.2.1 of August 28, 2005
  Copyright 1990-2004 by James R. Larus (larus@cs.wisc.edu).
  All Rights Reserved.
  See the file README for a full copyright notice.
  Loaded: /usr/spim/exceptions.s
  Loaded: /usr/spim/cs61c-io.s
  (spim) load "test.s"
  (spim) dump "test.dump"
  Dumped 6 words starting at 0x0040006c to file test.dump
  (spim) exit
If spim 7.2.1 is giving odd dump files (i.e. dump files larger than your own code), then you can use spimsal to create your dumpfiles. You can start spimsal by just typing the name of the program (no need to add the delayed-branches flag). Remember if you are using spimsal, you need to use __start: as the start point of your assembly file when you load it. Otherwise, you will get an error.


Frequently Asked Questions

Q: What are the definitions of associativity and set?
A: Associativity is the number of cache blocks where a given memory block can be placed into using the memory block's index.

Set is the collection of blocks associatied with the SAME index. The number of unique indexes is equal to the number of sets you have.

Q: How do I know my cache is working correctly?
A: An oracle will be provided in the project folder. The name of the oracle is tips_oracle.

Q: Is an oracle available for my home computer?
A: There are also an oracle available for Cygwin/Windows and Ubuntu (WIP).

Q: I am updating the cache in my function, but the GUI isn't doing anything. What is going on?
A: The GUI needs to be told of when changes are made to the cache. As a result, the GUI functions at your disposal are mentioned in tips.h. The function that merely updates the display is the refresh_cache_display() function.

Q: How much of the GUI behavior do I have to copy?
A: No, you do not have to copy any of the GUI behavior (i.e. the flashes, the messages, etc). But you do have to implement the cache logic in cachelogic.c

Q: Should I follow the LRU algorithm seen in COD?
A: No, you should not follow the LRU algorithm in COD. The LRU algorithm in COD is an approximation LRU algorithm, which produces ties between valid blocks that are candidates for replacement. As a result, it is suggested you should use a true LRU algorithm, where there is a unique ranking between valid blocks. In other words, there should never be any randomness in your LRU replacement policy, nor should it always default to kicking just one block out in the event of a "tie" (two LRU values being the same for two valid blocks--blocks with valid bit set to 1).

Q: Do I have to use numbers for my LRU algorithm?
A: No, you do not have to use numbers for your LRU algorithm. If you want to use something else (such as time structs), use the lru.data to be the pointer to this data. Make sure you update init_lru() function and lru_to_string() function.

Q: Are the addresses in this project byte addressed or word addressed?
A: They are byte addressed.

Q: What do you mean by unit of transfer between cache and physical memory is in blocks?
A: This means if you have blocks in your cache with a size of 4 words, you must always move data to and from physical memory in units of 4 words. There should never be a time in which the amount of data you move to physical memory from cache be less or greather than the block size of the cache.

Q: Can I add more files to the project?
A: You can, but we are only going to be using cachelogic.c from your submission when we test your submission.

Q: Can I work from home without Exceed?
A: Yes, there is a "No GUI" mode for TIPS that can be activated by adding the -nogui flag when starting up TIPS. To navigate the "No GUI" interface, type "help" on the prompt after starting up TIPS

Q: Can I work from home without using SSH?
A: Yes, the Makefile in the proj4 folder comes with lines that allow compilation with Cygwin/Windows or Linux automatically.

Q: Can I start TIPS with a dump file already loaded?
A: Yes, TIPS will interpret the last argument on the command line as a name of a file. If you want to start up TIPS with a dump file named test23.dump, you can type the following:

  % ./tips test23.dump

Q: I typed in make and it says there is an error in the Makefile. What's wrong?
A: Use gmake

Q: I ran gmake and I can't compile this project on Cygwin/Windows because of *some reason*. What do I have to do to get it to compile on Cygwin/Windows?
A: This project's GUI interface is built on GTK+. Compiling this project on Cygwin/Windows requires you at least install pkg-config, atk, gtk, glib, and pango libraries (all available via Cygwin's setup program). Information about specifics of the general GTK+ installation can be found here.

Q: What are the specific directions of getting this project compilable on Cygwin/Windows?
A: Try the following, assuming you already have a Cygwin/Window installation with x11 and gcc installed:

  1. Download and start Cygwin's setup program
  2. On the 'Select Packages' portion of the install, enable the following packages to install: atk-devel, glib-devel, gtk+-devel, gtk2-x11-devel, pango-devel, and pkg-config. If you haven't installed Cygwin previously, you will also need xterm, xorg-x11-devel, gcc, gdb, make, and emacs.
  3. Install those selected packages
  4. Exit from the setup program
  5. Download Bitstream Vera fonts from here. Save the ZIP or the tarball in some place you can get to.
  6. Extract all the fonts to /usr/share/fonts, (formerly C:\cygwin\usr\share\fonts)
  7. Start up the X11 server -- you must have X11 running for the GUI to display
If you follow these directions, a simple make should compile the project, where you can then just type tips

Q: Can I use other compilers on Windows?
A: All the project files are configured for use Sparc/Solaris or Cygwin/Windows. If you want to use other compilers (i.e. Microsoft Visual Studio), you will have to find the libraries usable with those compilers and make the appropriate modifications. Remember, you must make sure your program compiles on the lab computers in 271 Soda.

Q: Do I have to figure out answers to "Things to Ponder" section for getting full credit on this project?
A: No, but they can give you a break when you need one.


Submission

You will only be required to submit one file, cachelogic.c. You can submit a README if you wish to convey a message to your reader when grading this project. Thus, all your code MUST be in cachelogic.c. When we test your project, we will be using our own files (including the Makefile) except for cachelogic.c.


Bug Submission/GUI Suggestions

TIPS originally was written several years ago to work with a GUI API known as Tcl/Tk. Because TIPS has been redesigned from the bottom up, bugs fixed in the previous version of the GUI interface may have been reintroduced or bugs may exist in the code itself. If you find a bug, the staff (i.e. the TA in charge) would appreciate it if the bug was brought to his attention via email or the newsgroup. Therefore, if you find a bug in the oracle or in the interface, or if you have suggestions to improve the interface, please contact the TA in charge.


Things to ponder