Machine
Structures. Fall 2006, UC Berkeley
Project 4:
Cache Simulator ($$$!)
A
project that really makes “cents.” … Yeah, I’m a dork.
TA
in charge: David Eitan Poll (cs61c-tp@imail.eecs.berkeley.edu)
Due date: Wednesday, December 6, 2005 11:59pm
In this project, we provide an entire MIPS instruction set simulator called TIPS (thousands of instructions per second). This one has a graphical user interface (GUI) a little like xspim. The big feature of our simulator, though, is that it has a cache - which you have to write.
For this project, you may work in groups of no more than 2 people. Only one student needs to submit the project (the submission will ask for partners’ logins), but if both submit, the most recent submission will be the one we grade.
If you do Proj4 individually, slip days are the same as before.
If you do Proj4 in a group, each of your individual slip days counts as 1/2 a group slip day. That means if your group wants an entire slip day, both members need to have 1, or one member needs 2.
Table of Contents
Creating Dump Files for
Testing
Bug
Submission/GUI Suggestions
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.
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:
|
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:
void*
memcpy(void* dest, void* src, size_t amount);
where
dest is the desination of where
things should be copied, src is the source to be copied,
and amount is the number of bytes to
copy. A more detailed description of this function can be found in K&R.
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.
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-tp@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.
Answer
the following questions in the README file. You can safely assume that all
associative caches in these questions use an LRU replacement policy.
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 0b1011101000, 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 0b1011101000, 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 0b1011101010, 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 0b1011101010, 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?
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.
3. Explain the differences between write-through and write-back caches, and when/why one might be preferred over the other.
4. Suppose for a moment that VMs were included in this project. How would you expect the input to accessMemory to change? (in other words, what information should the cache now receive in order to do its thing?) YOU ARE NOT EXPECTED TO IMPLEMENT THIS.
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.
First, read tips.h. The comments and declarations there describe the API you need to use for your code.
All your code should go in cachelogic.c. In fact, it all has to get called in initMemory, flushcache, and accessMemory. Read the comments in each function to see what it needs to do. You can add other functions in cachelogic.c only to help you. Don't change anything else in the code, including the prototypes of the functions whose bodies you're writing.
To make the GUI work, your code needs to call some functions when certain actions take place. tips.h describes these functions.
(Same as above… repeated for emphasis)
For this project, you may work in groups of no more than 2 people. Only one student needs to submit the project (the submission will ask for partners’ logins), but if both submit, the most recent submission will be the one we grade.
If you do Proj4 individually, slip days are the same as before.
If you do Proj4 in a group, each of your individual slip days counts as 1/2 a group slip day. That means if your group wants an entire slip day, both members need to have 1, or one member needs 2.
Follow the instructions in cachelogic.c to finish the required functions. You may want to test your code with dump files besides the samples we gave you.
All your code must be in cachelogic.c. When we test your project, we will use all our own files (including the makefile) except for cachelogic.c.
You should also submit your README file with your responses to the questions above. You may also use the README if you need to inform the reader of something regarding your project, just make sure that it is clear where the questions are answered.
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:
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
. /usr/share/fonts
, (formerly
C:\cygwin\usr\share\fonts) 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.
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.
The irony that this is a “cash” (cache) project and the simulator is called “tips” is not lost on me. If for some reason you’ve got a good pun for caches (or really any topic we’ve covered since the midterm), e-mail it to me at cs61c-tp@imail.eecs.berkeley.edu. Who knows, maybe it’ll end up as (part of) the title of a question on the final!