Cache Mapping

Cache to Ram Ration

A processor might have 512 KB of Cache and 512 MB of RAM.

There may be 1000 times more RAM than cache.

The cache algorithms have to carefully select the 0.1% of the memory that is likely to be most accessed.

A cache line contains two fields

Data from RAM
The address of the block is called the tag field.

Mapping:

The memory system has to quickly determine if a given address is in the cache.

Three popular methods of mapping addresses to cache locations.

-- Fully Associative
Search the entire cache for an address.
--Direct
Each address has a specific place in the cache.
--Set Associative
Each address can be in any of a small set of cache locations.

Searching Problem
Knowledge of searching

Linear Search O(n)
Binary Search O(log2 (n))
Hashing O(1)
Parallel Search O(n/p)

Associative Mapping
The data from any location in RAM can be stored in any location in cache.

When the processor wants an address, all tag fields in the cache as checked to determine if the data is already in the cache.

Each tag line requires circuitry to compare the desired address with the tag field.

All tag fields are checked in parallel.

Set Associative Mapping

Set associative mapping is a mixture of direct and associative mapping.

The cache lines are grouped into sets.

Replacement policy

When a cache miss occurs, data is copied into some location in cache.

With Set Associative of Fully Associative mapping, the system must decide where to put the data and what values will be replaced.

Cache performance is greatly affected by properly choosing data that is unlikely to referenced again.

Replacement Options
First In First Out (FIFO)
Least Recently Used (LRU)
Pseudo LRU
Random

Comparison of Mapping Fully Associatve

Associate mapping works the best, but is complex to implement. Each tag line requires circuitry to compare the desired address with the tag field.

Some special purpose $, such as the virtual memory Translation Lookaside Buffer (TLB) is an associative cache.

Comparison of Mapping Direct.

Has the lowest performance, but is easiest to implement. Direct is often used for instruction cache.

Sequential addresses fill a cache line and then go to the next cache line.