GATE CS - COMPUTER ORGANIZATION:Memory Hierarchy and Cache

Memory Hierarchy and Cache for GATE CS

GATE COA cache questions are usually numerical: tag/index/offset bits, which block maps where, hit or miss, or effective access time. Start every problem by writing the address split.

Hierarchy and locality

Registers → L1/L2/L3 cache → main memory → disk. Caches work because of temporal (reuse soon) and spatial (nearby addresses) locality.

Address split (do this first)

For a machine address of A bits, block/line size B bytes, and S sets:

• Offset = log₂(B)
• Index = log₂(S)
• Tag = A − index − offset

Direct-mapped: S = number of cache lines.

N-way set-associative: S = (cache size in lines) / N.

Worked: direct-mapped

Cache: 4 KB, line size 16 B, 32-bit byte addresses, direct-mapped.

• Lines = 4096 / 16 = 256 → index bits = 8
• Offset = log₂(16) = 4
• Tag = 32 − 8 − 4 = 20

Memory address 0x0000F0A4:

offset = low 4 bits, index = next 8, tag = top 20.

Block maps to set/line = index; compare tag + valid bit for hit.

Conflict miss example: lines 0–7 in a tiny 8-line direct-mapped cache; blocks 10 and 18 both map to 10 mod 8 = 2 — they thrash each other.

Mapping overview

Replacement in a set: LRU, FIFO, Random — GATE states the policy when it matters. Write policies: write-through vs write-back (+ dirty bit).

Memory Hierarchy

Levels (Fastest to Slowest)

1. Registers: Fastest, smallest, most expensive
2. Cache (L1, L2, L3): Very fast, small, expensive
3. Main Memory (RAM): Medium speed, medium size, medium cost
4. Secondary Storage (Disk): Slow, large, cheap

Principle of Locality

Temporal Locality: Recently accessed items likely to be accessed again.

Spatial Locality: Items near recently accessed items likely to be accessed.

Exploited by:

• Cache (temporal and spatial)
• Prefetching (spatial)

Cache Memory

Cache is a small, fast memory that stores frequently accessed data.

Cache Organization

Cache Parameters

• Block Size (Line Size): Size of data transferred
• Cache Size: Total cache capacity
• Associativity: Number of blocks per set
• Number of Sets: Cache size / (Block size × Associativity)

Cache Mapping Techniques

1. Direct Mapped Cache

Each memory block maps to exactly one cache block.

Mapping: Block number mod (Number of cache blocks)

Advantages:

• Simple hardware
• Fast access

Disadvantages:

• Conflict misses
• Poor utilization

Example:

• Cache has 8 blocks (0-7)
• Memory block 10 maps to block 10 mod 8 = 2
• Memory block 18 maps to block 18 mod 8 = 2 (conflict!)

2. Fully Associative Cache

Any memory block can go to any cache block.

Advantages:

• No conflict misses
• Best utilization

Disadvantages:

• Complex hardware (needs search)
• Slower access

3. Set Associative Cache

Cache divided into sets. Each set has multiple blocks (ways).

Mapping: Block number mod (Number of sets)

Example: 4-way set associative

• Cache has 4 sets
• Each set has 4 blocks
• Memory block maps to a set, can go to any block in that set

Advantages:

• Balance between direct mapped and fully associative
• Good performance

Disadvantages:

• More complex than direct mapped

Cache Replacement Policies

When cache is full, which block to replace?

1. LRU (Least Recently Used)

Replace block not used for longest time.

Advantages:

• Good performance
• Exploits temporal locality

Disadvantages:

• Complex to implement
• Requires tracking

2. FIFO (First In First Out)

Replace oldest block.

Advantages:

• Simple implementation

Disadvantages:

• May replace frequently used block

3. Random

Replace random block.

Advantages:

• Very simple

Disadvantages:

• Poor performance

Cache Write Policies

Write-Through

Write to both cache and memory immediately.

Advantages:

• Memory always consistent
• Simple

Disadvantages:

• Slower (every write goes to memory)

Write-Back

Write only to cache. Write to memory when block is replaced.

Advantages:

• Faster (fewer memory writes)
• Better performance

Disadvantages:

• More complex
• Memory may be inconsistent

Cache Performance

Hit Rate: Fraction of accesses that are hits.

Miss Rate: Fraction of accesses that are misses. (Miss Rate = 1 - Hit Rate)

Average Access Time:

• T_avg = Hit Rate × T_cache + Miss Rate × (T_cache + T_memory)

Example:

• T_cache = 1ns
• T_memory = 100ns
• Hit Rate = 0.95
• T_avg = 0.95 × 1 + 0.05 × (1 + 100) = 0.95 + 5.05 = 6ns

Virtual Memory

Virtual memory allows programs larger than physical memory.

Address Translation

Virtual Address → Physical Address

Components:

• Page Number: Part of virtual address
• Page Offset: Part of virtual address
• Frame Number: From page table
• Frame Offset: Same as page offset

Physical Address = (Frame Number × Page Size) + Offset

TLB (Translation Lookaside Buffer)

Cache for page table entries.

TLB Hit: Fast translation (no page table access)

TLB Miss: Must access page table

Effective Access Time:

• EAT = TLB_time + Memory_time × (1 + TLB_miss_rate × Page_table_accesses)