During the 2016 fall quarter, I wrote a cache simulator while taking computer architecture. Here is a (late) post documenting it.

Theory

In order to deal with the problem that faster memory is also more expensive most computers use a hierarchy of increasingly large but slow memories. The system attempts to store values that it will need soon in higher levels of memory in increase efficiency. This process is called caching.

There are many caching schemes available with various tradeoffs. This simulator allows you to experiment with several potential parameters to a cache and then run a number of simulated memory accesses. You can then see various properties of these accesses, such as if they resulted in a cache hit or if the cache would have needed to delegate to the next level in the memory hierarchy.

You can access it at https://cs.williamritson.com/#/cache

Configuration

You can configure most of the simulators options in the top left card. Be warned, many of these values will cause odd or undefined behavior if they are not set to powers of 2.

Address Size

The address size is how large a memory address the machine uses. This controls how many different possible locations it can store a unit of memory. For example, a 32-bit machine has 2³² = 4,294,967,296 possible unique addresses. This means that it uses byte addressing it can at most utilize about 4 gigabytes of space. Of course, that is the main memory, the cache will likely be much smaller. This is usually either 16, 32 or 64 bits in real machines.

Minimum Addressable Unit

The minimum addressable unit is the smallest unit of memory that gets a unique address within the system. For example if it is one byte then the system is called byte addressable. That would imply it is possible for the system to address a single byte, but not an individual bit. Many systems are also word or half-word addressable (in this simulator a word is always four bytes and a half-word always 2).

Cache Size

The cache size is the total amount of memory available to the cache. This is usually much smaller than the amount of total system memory. Larger caches are generally better, all things being equal, but may come with tradeoffs in terms of speed or price.

Block Size

The block size refers to how much memory the cache loads in at one time. This is usually bigger than the minimum addressable unit meaning that the cache loads in a chunk of memory which is referred to by multiple addresses at the same time. This allows the cache to take advantage of special locality, the principle that data is often read sequentially (eg in the case of an array). Larger block sizes mean that less blocks can be stored but there is a greater chance of special locality.

Blocks per Set

Because a cache is not as large as main memory it must have a way of deciding where to store blocks and when to replace them. Thus, blocks are arranged into sets and hashed into them by their address. Many blocks will map to the same set. In a directly mapped cache (set size of one) each set only stores one block and immediately vacates it if another needs to take its place. But sets may be larger allowing multiple blocks to be stored within. They will then only vacate a block when they are out of room and they will do it by the replacement policy (next section)

Replacement policy Use LRU Policy)

Caches that use set sizes greater than one must have a mechanism for determining which block to vacate from a set in order to make room for a new one. This Is called the replacement policy. This simulator allows two different replacement policies LRU or least recently used and FIFO or first in first out. In LRU the block that was used farthest in the past is vacated. In FIFO the first block into the cache is the first one vacated.

Memory Accesses

Once you have configured the cache you still need to create a series of memory accesses to test it. There are only two real parameters here. Address and whether or not the access is a write. The address determines where the memory will end up in cache. Whether or not it is a write determines if it will modify the memory within the cache.

Interpreting results.

Once you have entered in all the accesses you want to preformed and hit the “run simulation” button results will appear in the results card. Here are the meanings of each row.

Address – The address of the accessed memory

Request Type – Whether the access was a read or write

Cacheline Index – The index of the block within the cache.

Hit or Miss? – An access is a hit if the desired memory was found in cache otherwise it is a miss.

Modified – This is 1 if the memory in the cache has been modified (by a write)

Tag - This is the section of the address used to resolve which of the several possible blocks that could map to a set was actually mapped to that set.

Data - This is the address of the block of memory to which contains the addressed memory.

Caused Replace - True if adding the block to the cache required another block to be removed from the cache.

Write Back to memory? – True if the cache must write back to memory. This happens when a modified block has to be vacated from the cache.