University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science

EECS 61C, Spring 2007

Project 4

Due Friday, April 27, 2007 @ 11:59:59pm

TA in charge: Brian Nguyen (bhnguyen@gmail.com)
Note that this is the email you want to use if you want me to actually reply!


04/25/07 @ 4:30AM: REFRESH YOUR FILES - See red notice below (click here)
Do not compile on cory please -- no CS projects should be compiled on cory, use a real CS server (try pulsar.cs)

I will hold extra office hours, Friday ~8:00PM in 271 lab until midnight (or until I'm tired).


GUI Updates

Other Notes/Updates


Contents


Brief Introduction

This project will give you intimate knowledge of cache logic through implementation of, you guessed it, cache logic. We will be providing you a MIPS simulator called TIPS (Thousands of Instructions Per Second), that will be able to run MIPS instructions. However, the cache logic is broken (read: conveniently non-existant)!

Your job is to implement the cache logic behind the cache so that TIPS can make use of the many benefits cache entails. You may choose to complete this project either by your self or with one other partner.

If you choose to do this project individually, you know how many slip days you have left so skip the next paragraph.

However, if you choose to do this project with another person, each of your individual slip days counts as 1/2 a group slip day. So in order for your group to use a slip day for this project, either both members need to have 1 slip day remaining, or one member must have 2 slip days remaining.

An oracle will be provided so you can compare your solution with ours.


Setup on Inst Machines


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 are:
    • Blk - block number
    • V - valid bit
    • D - dirty bit
    • LRU - LRU data
    • Tag - Tag for the block
    • Numbers (00, 04, etc.) - offset in the cache block data
  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 reinitialize registers
  9. Cache -- flush the cache
  10. Output -- clear the execution log
  11. Quit -- exit TIPS

There is also a text-based version of the GUI for those who want to work from home. You can access it with the following call:

  $ ./tips -nogui

Type help at the TIPS prompt to get a list of commands usable in this mode.


Your 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 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).


Organization of the memory funtions in TIPS

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.

All your code MUST be contained in cachelogic.c - specifically in accessMemory() and possibly the LRU functions in cachelogic.c, depending on how you go about implementing LRU. You may add helper functions as long as you do not need to modify any code outside of cachelogic.c. Do not change other code other than cachelogic.c. Do not change the prototypes of existing functions. If you haven't got the point yet, modify only the body of the functions given to you, with helper functions if needed.


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.

Dump files 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.3. of August 28, 2006
  Copyright 1990-2004 by James R. Larus (larus@cs.wisc.edu).
  Console enhancement by Michael Le (cs61c-ta@imail.eecs.berkeley.edu).
  All Rights Reserved.
  See the file README for a full copyright notice.
  Loaded: /home/ff/cs61c/share/spim/exceptions.s
  (spim) load "test.s"
  File loaded successfully.
  (spim) dump "test.dump"
  Dumped 6 words starting at 0x0040006c to file test.dump
  (spim) exit

If spim 7.3 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.


Questions to Answer

Answer the following questions in the README file. You can safely assume that all associative caches in these questions use an LRU replacement policy.

Question 1:

For this question, assume 1KiB of addressable memory, 64B of L1 cache with 8B blocks. You will probably find it useful to draw the cache as you work through this problem.

The code in question:

	#define ARRAY_SIZE 64
int total = 0;
char * array = malloc(ARRAY_SIZE * sizeof(char)); /* Line 1 */ // Note: chars are 1-byte wide
for(int x = 0; x < ARRAY_SIZE; x++) array[x] = x; /* Line 2 */
for(int x = 0; x < ARRAY_SIZE; x++) total += array[x]; /* Line 3 */
for(int x = 0; x < ARRAY_SIZE; x++) total += array[x]; /* Line 4 */

a. Assume the cache is direct-mapped and array is a pointer to the memory at offset 0b1001111000, what is the ratio of cache hits to cache misses while Line 4 is being executed?

b. Assume the cache is fully associative and array is a pointer to the memory at offset 0b1001111000, what is the ratio of cache hits to cache misses while Line 4 is being executed?

c. Assume the cache is direct-mapped and array is a pointer to the memory at offset 0b1001111101, what is the ratio of cache hits to cache misses while Line 4 is being executed?

d. Assume the cache is fully associative and array is a pointer to the memory at offset 0b1001111101, what is the ratio of cache hits to cache misses while Line 4 is being executed?

e. Do these results surprise you? Why or why not? Explain what's going on. What would happen if the cache were 2-way set associative? 4-way?

Question 2:

Describe a situation in which a 2-way set associative cache would out-perform a fully associative cache. Vice-versa? You should describe these situations in relation to the attributes of the cache. (i.e. accesses are made to fill every block of the cache, hitting memory block-size apart each time...) Otherwise, the examples can be as contrived as you wish.

Question 3:

Explain the differences between write-through and write-back caches, and when/why one might be preferred over the other.

Question 4:

Suppose for a moment that virtual memory was included in this project. How would you expect the input to accessMemory() to change? (in other words, what type of information should the cache now receive in order to do its thing?) YOU ARE NOT EXPECTED TO IMPLEMENT THIS.

Question 5:

Briefly describe the changes you would have to make to your implementations in this project to implement an L2 cache. Assume you're given a second cache struct. How would your L1 cache implementation change? How, if at all, would your L2 cache implementation need to be different from your original cache implementation? YOU ARE NOT EXPECTED TO IMPLEMENT THIS.


Submitting Your Solution

Repeated for emphasis: All your code MUST be contained in cachelogic.c (this is the only file you submit)

In testing your project, we will use all of our own files (including the Makefile) EXCEPT for your submitted cachelogic.c

A README file should be submitted with your answers to the questions above and also if there is anything you need to inform the reader about your project.

Only one person per group will need to submit since the submission process will ask for your partner's login. If both members of the group submits, the newest copy of the submission will be the one we grade.


Bugs and Suggestions

If you think you have found a bug in the TIPS GUI/oracle/code, please let the staff (i.e. the TA in charge) know via email or the newsgroup. Likewise, feel free to let us know of any suggestions you have. If time permits, bugs and suggestions will be addressed in updated files for this project if necessary.


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: Is an oracle available for my home computer?
A: There are oracles available for
Cygwin/Windows and Linux.

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. 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: 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 greater than the block size of the cache.

Q: Can I add more files to the project?
A: You can but there's no point unless it's just testing code. We will ignore all other files you send except for cachelogic.c. Meaning we will NOT use any additional files. Do NOT put any code needed by your cachelogic.c (including header files and such) in any other file other than cachelogic.c. If that's not clear, simply, just do all your work in cachelogic.c please -- your grade will appreciate not being a 0.

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 the packages mentioned in "Setup on Windows Machines (Cygwin)." Information about specifics of the general GTK+ installation can be found here.

Q: Can I use other compilers on Windows?
A: All the project files are configured for use on 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.


Setup on Windows Machines (Cygwin)


Setup on Other Machines

If you've made it this far in the semester with Linux, you should be able to build things already and have the necessary libraries needed to compile the project.

If you are using a Debian based distribution (Ubuntu), you will need to grab the following packages:

$ sudo aptitude update && sudo aptitude install build-essential libgtk2.0-dev

If that's not enough (you get implicit declaration of sprintf), you may also need to look at the output of "uname -a" and look for a string like "Linux 2.6.15-28-686". Take note of the bolded numbers (your arch) and do:

$ sudo aptitude install linux-headers-arch

Mac OS X users: You win. I have no clue. Please enlighten me.