Computer Architecture (BSc CSIT, CSC208): the questions likely to come

Cache Memory

Cache memory is a small, high-speed memory placed between the CPU and main memory (RAM). It stores copies of frequently accessed instructions and data so that the CPU can access them faster than fetching from slower main memory. It works on the principle of locality of reference (temporal and spatial locality).

When the CPU needs a word, it first checks the cache:

• Cache hit — the word is found in cache (fast access).
• Cache miss — the word is not in cache, so it is fetched from main memory and a block is copied into cache.

The ratio of hits to total references is the hit ratio, a key measure of cache performance.

Main memory is divided into blocks and cache into lines of the same size. A mapping function decides which main-memory block goes to which cache line.

Cache Mapping Techniques

1. Direct Mapping

Each main-memory block maps to exactly one fixed cache line, given by:

The physical address is split into three fields:

• Word selects the byte/word within a block.
• Line selects the cache line directly.
• Tag is stored with the line and compared to verify the right block.

Diagram (in words): Each cache line has a tag field and a data block. The line field of the address indexes one line; its stored tag is compared with the address tag — equal means hit.

Advantage: Simple and cheap (one comparison). Disadvantage: High conflict misses — two blocks mapping to the same line repeatedly evict each other.

2. Associative (Fully Associative) Mapping

A main-memory block can be placed in any cache line. The address has only two fields:

The tag must be compared with the tags of all cache lines simultaneously (using associative/content-addressable memory).

Diagram (in words): All cache-line tags are searched in parallel by comparators; any match is a hit.

Advantage: Most flexible, lowest conflict misses, best hit ratio. Disadvantage: Expensive hardware (many comparators) and needs a replacement algorithm (LRU/FIFO).

3. Set-Associative Mapping

A compromise between the two. The cache is divided into sets, each containing $k$ lines (a k-way set-associative cache). A block maps to one fixed set but can occupy any line within that set:

The address has three fields:

Diagram (in words): The set field indexes one set; the tag is compared in parallel with the $k$ lines of that set only.

Advantage: Lower conflict misses than direct mapping and far cheaper than fully associative ($k$ comparators only). Most real caches use 2-way, 4-way or 8-way set-associative mapping.

Summary

Direct mapping is the special case $k=1$; fully associative is the case where the whole cache is one set. Set-associative balances cost and performance.