Memory Tradeoff

Fastest memory is on the same chip as the CPU, but its not really big (say, 32 KB in L1 cache) Slowest memory is DRAM on different chips, but can be very large (256 GB in compute server).

The goal is to create the illusion that large memory is fast by the idea that we can use small memory as cache for large memory.

• Note: there are levels of cache (L1, L2, L3) as smaller memory mirrors some of the large memory content.

Cache Organization

Direct Mapping

Slot determined from address

It's when each memory block is mapped to a specific slot in the cache, and we use part of the address as index to cache.

Tag	Index	Offset
0010 0011 1101	1100 0001 0011	1010 1111

Since multiple memory blocks are mapped to the same slot, there will be contention. Newly loaded blocks will discard old ones.

Tradeoffs

Benefits from locality is that neighboring memory blocks wil be placed in different cache slots. However, we may have to pre-empt useful cached blocks. We don't know which ones are still useful from this method. So when two useful blocks contend for the same slot, there are many cache misses

Associative Cache

Lookup table for slot

With associative caching, we can place the block anywhere in cache as the block tag now has the full block address in main memory.

Previously, 32-bit memory address gets mapped to:

Tag	Index	Offset
0010 0011 1101	1100 0001 0011	1010 1111

Now,

Tag	Offset
0010 0011 1101 1100 0001 0011	1010 1111

The tag becomes an index.

Example

Say we have a block size of 256 bytes (8 bit offset) and a cache size of 1 MB (4096 slots).

	Tag(24bits)	Valid(1 bit)	Data (256 bytes)
0
1	$d0f012	1	93 f4 8d 19 ...
...
4095

When we read the memory value for address $d0f012,

• Cache miss → load into cache
• data block: $d0f01200-$d0f012ff
• tag $d0f012
• placed somewhere (index 1 in this case).

Tradeoffs

Finding block in cache is expensive → slow, power-hungry

Set-Associative Cache

The compromise of direct and associative mapping.

It uses part of the address to determine a subset of cache, then there are more than one slot for each indexed part of cache.

Organization: For a cache with block size of 256 bytes (8 bit offset) and cache size of 1 MB (1024 sets of 4 slots),

Index	Tag(14bits)	Valid(1bit)	Data(256 bytes)
0
1
...

Cache Read Control

For a 4-way set associative

Caching Strategies

We read in blocks as needed. If cache is full, discard blocks based on one of these strategies:

• randomly
• number of time accessed
• least recently used
• first in, first out.

First in, first out

Consider the order in which cache blocks loaded, the oldest block gets discarded first

• To do this, we need to keep a record of when blocks were loaded.

One strategy is using a timestamp. Each record requires additional timestamp, so that each record now looks like

Index	Tag(14bits)	Valid(1bit)	Timestamp	Data(256 bytes)
0
1

• The tag, valid, and timestamp will make up the "metadata"
• Time would be easily set when the slot is filled, but finding oldest slot requires loop with min calculation.
• The timestamp data would need to be big.

Second strategy is to maintain order. We don't need the actual access time, just the ordering of cache. For instance, for a 4-way associative array, 0 = neweset block and 3 = oldest block, and when a new slot is needed, you find the slot wiht timestamp value 3, use that slot for the new memory block, and increase all timestamp counters by 1.

In summary:

1. discard oldest block
2. load new data
3. increase order counters

Least Recently Used

LRU bases decision on last-use time, not load time. It keeps frequently used blocks longer in the cache.

Need to maintain order that updates with every access (not just misses).

Update order based on:

• Miss: set to 0 and increase other counters
• Hit least recently used: set to 0 and increase other ocunters
• Hit most recently used: no change
• Hit others: increase some counters.

It's actually quite complicated:

• First look up order of accessed block
• Compare each other block's order to that value
• Increasingly costly with higher associativity
• Note: this has to be done every time memory is accessed (along with cache misses).

So, you can approximate LRU through bit shifting.

• Keep an (n-1)-bit map for an n-way associative set.
• Each time a block in a set is accessed,
  • shift all bits to the right
  • set the highest bit of the accessed block
• Slot with value 0 is the candidate for removal.

There may be multiple blocks with order pattern 000, so you should pick one randomly.

• Maybe don't change anything if the most recently used block is used again