Lab: Build a Cache

Assigned

Wednesday, Nov 28, 2018

Due

Friday, Dec 7, 2018 by 10:30pm

Submitting

Upload your cache.circ file to gradescope. You do not need to submit your test sequence from part D, but make sure you have this signed off before the lab deadline.

Overview

In this lab, you will implement a direct-mapped cache for read-only memory in Logisim.

Part A

The memory system you are implementing will use eight bit addresses and a four-entry cache with four-byte cache lines. Before starting your implementation, answer the following questions:

1. Which address bits will be used for the byte offset in this cache?
2. Which address bits will be used for the cache index?
3. Which address bits will be used for the cache tag?
4. How do you know when there is a cache miss? Write this out as an expression that evaluates to true if and only if a cache miss has occurred. Don’t forget about the cache’s initial state, when all valid bits are set to zero.

Have the instructor or a mentor approve your answers before moving on to the next part of the lab.

Part B

For this part of the lab you will implement a single entry for the direct-mapped cache. To start, download the cache.circ and cache-test.circ starter circuit files.

The file cache-test.circ contains an instance of your cache connected to a read-only memory element, a clock, an address input, and data output. This component will be useful in a later part of the lab.

For now, open cache.circ in Logisim and double-click the “cache-entry” subcircuit to open it. Remember that you can start Logisim with the following shell command:

$ java -jar /home/curtsinger/bin/logisim.jar &

Cache Entry Inputs

The “cache-entry” subcircuit implements a single entry in a cache. The subcircuit in the provided Logisim file has the following inputs:

data_in

If there is a cache miss, the “main” cache subcircuit will read the requested address in memory and pass the data in to this port on the cache entry. The entry should store this value on the clock input’s rising edge.

tag

The “main” subcircuit will pass in the tag for the address currently being accessed. If this does not match the tag of the currently cached value, there must be a cache miss. When the cache is updated to store new data, use this as the tag associated with the new data.

clock

When the clock raises, the cache entry should update its contents to store the data passed in on the data_in input and the tag. Reading from the cache entry is always enabled.

Cache Entry Outputs

The subcircuit also has the following outputs:

data_out

Send the data stored in this cache entry to the output at all times.

miss

If this cache entry does not have a match for the requested tag, set this output to one. This will tell the “main” cache to read memory and update the entry with the new tag and data.

To complete this part of the lab you will need to implement a cache entry in this subcircuit. You will need registers to hold

• the valid bit,
• the tag for the currently-cached data, and
• the 32-bit cached data (the cache line).

Make sure your cache entry correctly reports a miss, and will store both the data input and tag on the clock input’s falling edge. We want these registers to update on the falling edge rather than the rising edge to allow time for the ROM read to occur while the clock input is high. At the end of the high clock signal, the registers should store the value from ROM. Warning: The default for registers in Logisim is to store on the rising edge. Do not forget to change your registers to update on the falling edge.

Do not add any additional inputs or outputs to this subcircuit or edit the subcircuit’s appearance.

Ask the instructor or a mentor to sign off on this part of the lab before moving on.

Part C

Once you have completed your “cache-entry” subcircuit, you can use it to build your complete cache. To implement caching behavior, the “main” subcircuit is designed to sit in front of a ROM element. (You can see an example use of this cache in the cache-test.circ circuit.) While the “main” subcircuit has been operationally “completed” for you, it does not yet implement a cache; instead, it passes along all requests to memory.

Using the Cache Test Harness

Open the cache-test.circ file. You should see the following components:

An Address input

This is the address you are loading from.

A Clock

The cache accepts the read request any time the clock is high.

A Data output

This output shows the result of the read.

A ROM element

This read-only-memory has some values pre-loaded, and serves as the next level in the memory hierarchy below the cache.

An LED

This LED turns on any time the requested address is loaded from memory. As the cache is currently implemented, all requests will go to memory. Your completed cache should only access memory when you request an address that is not already cached.

You should use this circuit to test your cache implementation as you complete it. Note that you will likely need to close and re-open cache-test.circ each time you edit your cache.circ implementation.

Implement the Cache

If you look in the “main” subcircuit of cache.circ, you should see some basic components already in place. First, let’s look at the main cache inputs and output:

address input

This is the address that we’re trying to load through the cache.

read enable input

If set, perform the read. This input is currently passed on to the ROM. Your implementation should use this input to trigger reads from ROM when needed, and update the appropriate cache entry if there was a cache miss.

data_out output

This output returns the byte of data requested with the address input. The “main” subcircuit is responsible for extracting the appropriate byte from the 32-bit line returned from ROM or held in a cache entry.

In addition to these primary connections for the cache, the “main” subcircuit has three pins to interface with the ROM element:

ROM read address output

The cache sends a six-bit address to the ROM to request data when there is a cache miss. The ROM address is only six bits because each access returns four bytes of data, whereas our eight-bit addresses return a single byte of data.

ROM read enable output

When the cache needs to read from ROM it must turn this output on. You should not turn this output on for accesses that hit in the cache. This output is currently wired so the cache always reads from ROM (which means it really isn’t a cache).

ROM data in input

After reading the ROM, the cache receives the requested data on this input. This value should be cached in the appropriate entry and passed on to the output. The provided circuit just breaks this input into bytes and passes the appropriate byte on to the data output. (Note that the zero byte is the bottom row of the display.)

Before completing your cache you will need to delete the wire connecting the read enable input to the ROM read enable output. The other components can stay in place, although you may need to move or modify them slightly. Do not add any additional inputs or outputs to this subcircuit or edit the subcircuit’s appearance.

Use four copies of your “cache-entry” subcircuit to implement a four-entry direct-mapped cache:

• You will need to use a splitter to break the requested address into its tag, index, and byte offset components.
• Use the index to select between your four cache entries, and pass the tag in to each of the entries.
• When there is a miss and the read enable input is on, request data from ROM by turning on the ROM read enable output. When the read enable input falls, the registers in the selected cache entry will store the value read from ROM.
• You should only pass this clock signal to the selected cache entry, since this will overwrite the cache entry’s contents.
• Once you have output from the appropriate cache entry, use the byte offset bits from the address to select a byte from the 32-bit cache line; the multiplexor in the provided subcircuit already does this, so you may want to reuse the provided components.

You do not need to have anyone sign off on this part of the lab; instead, move on to the next part where you will design an access sequence to test your cache implementation.

Part D

Now that you have a (hopefully) working cache, you will need to design an exhaustive test for the cache. It is not enough just to verify that your cache returns the correct data; it must also access memory at the appropriate times. For example, if you access an address twice in a row, the cache should only access memory the first time.

Write down a series of memory accesses that you can perform using the cache-test.circ test harness to verify that your cache has the following properties:

1. A cache miss, whether due to an empty cache or mismatched tag, results in a ROM access.
2. Cached data is returned without accessing ROM when there is a cache hit.
3. Bytes within the same cache line are cached together.
4. Accesses to addresses that map to one cache index do not overwrite or invalidate data cached in entries for the other indices.

Write out your access pattern as well as the expected behavior for each access:

• does the access result in a ROM read or not?
• how does the state of the cache change (if at all?)
• which property above is demonstrated?

Verify that your cache has the expected behavior. When you have completed your tests, ask the instructor or a mentor to sign off on your tests. Be prepared to re-run your tests, and to explain how your access sequence demonstrates each of the four properties above.