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-existent)!

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

If you choose to do this project individually, your slip days will work as normal. If you do it with a partner, as long as your partner has a slip day, your group may take a slip day.

An oracle has been provided so you can compare your solution with ours. You can find the nova oracle at ~cs61c/code/proj4/tips_oracle_nova.

• The LRU behavior might seem a little weird. You don't have to have the same LRU values as the oracle, but you should be picking the same block the oracle does when it does select the LRU block. The main requirement for LRU is that when every block in a set is valid, there is always a unique block that is the least recently used.

Setup on Inst Machines

• Copy the contents of ~cs61c/code/proj4 to a suitable location in your home directory.
  
  

  $ cp -r ~cs61c/code/proj4/ ~/proj4

  
  
• To compile and run TIPS:
  
  

  $ gmake

  $ ./tips

  
  
• As was mentioned before, the initial TIPS code has a default cache size of 0 since there is no cache logic present. You can configure the cache by clicking on the "Config Cache" button at the lower left of the interface.

GUI Walkthrough

The GUI was designed to be straightforward. 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: Register display -- detailed view of the current state of the registers Execution log -- log of actions by TIPS. Messages can be displayed in this box using the append_log() function. 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 Config Cache -- configure the cache parameters Load Program -- loads a dump file for execution Step -- execute one instruction Run -- automate execution CPU -- reset the PC and reinitialize registers Cache -- flush the cache Output -- clear the execution log Quit -- exit TIPS

There is also a text-based version of the GUI for those who prefer it. You can run 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 will handle accessing actual memory, using the accessDRAM() function. Thus, the code in the accessMemory() function will behave as a cache that will call the accessDRAM() function as needed (for cache misses).

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

• Associativity (ranges from 1 to 5)
• Number of unique indexes (2ⁿ where n ranges from 0 to 4)
• Block size (2ⁿ bytes where n ranges from 2 to 5)
• Replacement Policy (LRU and Random)
• Memory Synchronization Policy (Write Back and Write Through)

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:

• accessDRAM() requires a byte pointer when it is called.
• There are 4 bytes in 1 word.
• The tag information must be right aligned. For example, if the tag is only 25 bits for a given cache configuration, the top 7 bits must always be 0.
• When you are moving things between cache and physical memory, a BLOCK is transferred, NOT just a word nor a byte. Thus, if the block size is 16 bytes, when you want to move data from cache to memory (or vice versa) you must make sure 16 bytes travel between the cache and physical memory on your accessDRAM() function call.
• Write Through policy requires the ENTIRE block be transferred to physical memory on a write operation.
• To move data to and from a cache block, the memcpy() function should be used. The function prototype of memcpy() is defined as follows:
  
  

  void* memcpy(void* dest, void* src, size_t amount);

  where dest is the destination pointer, src is the memory 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.

Getting Started

Look over tips.h and cachelogic.c. tips.h gives you an overview of how the cache simulator is put together. A section of that file has been marked as important, so read it to get an idea of what functions and variables you will be using. cachelogic.c contains a slightly more detailed explanation of what you will be writing in the accessMemory() function.

The cache data structure is divided into three levels:

• The first level of entry is selecting which set you want. For example, cache[2] states that you are going to be accessing the 3rd set of the cache. This level is regulated by set_count.
• The next level is selecting the block you want in the set. That is specified by the block field. For example, cache[2].block[4] accesses the 5th block of the 3rd set. In the block is the tag, valid bit, dirty bit, and lru information. This level is regulated by the associativity of the cache.
• The final level of entry is selecting which bytes of the block do you want retrieve or modify. The data contained in a block is represented by the data field of that block. Using the offset, a particular byte can be referenced.

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 (its type is void*, which means it can be a pointer to anything). You are free to use either method to represent the LRU information, so long as the LRU behaves in a deterministic fashion (i.e. no two valid blocks will ever be candidates for replacement at the same time).

Organization of the memory functions in TIPS

In a nutshell, the accessMemory() function is a function that acts as a communication layer 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 (depending on how you implement the LRU algorithm). You may add helper functions as long as you do not modify any code outside of cachelogic.c. Do not change any file other than cachelogic.c. Do not change the prototypes of existing functions. To summarize, you can modify only the body of the given functions or add helper functions (if needed) all within cachelogic.c.

Creating Dump Files for Testing

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

Dump files can be created in several ways. If you are working on the inst machines, you can use the script included in the project files:

	./assemble_mips input.s output.dump

Submitting Your Solution

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

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

When you're ready to submit, cd into your project directory, and submit using the following command: submit proj4.

Only one person per group will need to submit; the submission process will ask for your partner's login. If both members of the group submit, we will grade the last submission.

Frequently Asked Questions

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

Set is the collection of blocks associated 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: Oracles have been put up for Cygwin/Windows and OS X.

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 informed when changes are made to the cache. The GUI functions at your disposal are mentioned in tips.h.

Q: How much of the GUI behavior do I have to copy?
A: You will only be graded on your implementation of the cache logic in cachelogic.c. You do not have to include the GUI update function calls if you don't want to, but they will help you visually understand how caching works. GUI functionality is not required! It is there for your convenience only. Ignore it entirely if you want.

Q: Should I follow the LRU algorithm seen in P&H?
A: No, you should not follow the LRU algorithm in P&H. The LRU algorithm in P&H 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 lru.data as the pointer to this data. Make sure you update the init_lru() function and the 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 we will not be able to test your solution in the autograder. We will ignore all files you submit except for cachelogic.c. Do NOT put any code needed by your cachelogic.c (including header files and such) in any external file. If that's not clear, edit only cachelogic.c please -- your grade will appreciate not being a 0.

Q: Can I work from home without the GUI?
A: Yes, there is a "No GUI" mode for TIPS that can be activated by adding the -nogui flag on the command line when starting TIPS. For instructions, 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 will allow compilation on Cygwin/Windows and OS X 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

Setup on Windows Machines (Cygwin)

Setup on OS X

Setup on Linux

If you've made it this far in the semester with Linux, you should have the necessary compilers and libraries needed to compile the project. However, to ensure that you have the correct GUI libraries, you might need to install a few new packages.

If you are using a Debian based distribution (like Ubuntu):

If you're still getting errors, you may need to install another package. 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:

If you're on a different distribution, look in your package management system for the appropriate packages.