CS 200 Project III

Software Adaptive Cache  (SAC)

This is an open-ended research project.  The basic question is whether program-specific, software-managed cache memory can be more effective than current hardware caching schemes.   You need to form a group of two to four people and complete the project in two phases.   Unlike previous projects, you are free to choose your group members, you need to use C/C++ to write programs, you will have all test data from the beginning, and you cannot use any other groups' code.

System Setup

A data-access trace is a sequence of integers.  An integer i means an access to the i'th data element in a program.  It is possible that a program may not access all its elements.

Cache consists of an array of cache elements, each holds one data element.

An instance of adaptive cache consists of two parts: a generic cache module (Cache) and a user-defined function (CacheAccess). The generic module imports CacheAccess to manage placement, search, and replacement of data elements in cache.  CacheAccess performs the management using interface functions of the generic cache module.  The interface functions of Cache include cache read, write, exchange, and report.  CacheAccess cannot change the internal state of Cache without going through these interface functions.  The Cache interface is defined as follows.

Each cache element stores two attributes in class CacheElem.

class CacheElem {
public:
// Index of data element currently stored.  Initially 0.
unsigned addr;
// Optional storage for any user-supplied information, e.g. last access time of the element
unsigned info;
}
Cache::DataAccess is called for each element in a trace.  It invokes user-defined CacheAccess supplied in the contructor. CacheAccess must either find the accessed element in cache or load in the accessed element (through CacheWrite).  Either way, it must return the index of a cache element, in which the accessed element is currently stored. The implementation of Cache::DataAccess is as follows.  Note that you cannot change the implementation of any member functions of Cache class, including DataAccess.
void Cache::DataAccess(unsigned addr) {
unsigned cache_index = CacheAccess(this, addr);
assert(cache[cache_index].addr == addr);
cur_time ++;
}
Given a trace, you can measure the performance of your adaptive cache in three steps. Your CacheAccess function must manage cache placement, search, and replacement completely.  The performance of cache is determined by how well cache is managed by your function.

The following example is a function that implements a direct-mapped cache with 16 cache elements.  Here is an example program using the function.

unsigned CacheAccess(Cache *cache, unsigned addr) {
unsigned index = addr & 0xf;
CacheElem elem = cache->CacheRead(index, 0);
if (elem.addr != addr) cache->CacheWrite(index, addr, 0);
return index;
}

Phase I

Phase II