Module II: Hierarchical Memory Technology

The Memory Hierarchy is a fundamental architectural concept that organizes storage into multiple levels, each offering a different balance of speed, size, and cost. It exists because no single memory technology can simultaneously satisfy all three requirements of an ideal memory: fast, large, and cheap.

The Core Problem (The Speed-Size-Cost Triangle):

• Fast Memory (SRAM): Used in CPU caches. It is extremely fast (sub-nanosecond access times) but very expensive per bit and physically large per transistor (requires 6 transistors per bit). Building a 16 GB main memory entirely from SRAM would be prohibitively expensive.
• Dense Memory (DRAM): Used for Main Memory (RAM). It is much cheaper per bit (1 transistor + 1 capacitor per bit) and denser, but significantly slower (50-100 ns access times) than SRAM.
• Massive Memory (Disk/SSD): Used for Secondary Storage. It is extremely cheap and can hold terabytes, but is orders of magnitude slower than DRAM (millisecond access for HDD).

The Solution — Memory Hierarchy:

By placing small amounts of fast, expensive memory (registers, L1/L2/L3 caches) close to the CPU and progressively larger, slower, cheaper memory (DRAM, SSD, HDD) farther away, the system creates the illusion of a single memory that is both as fast as SRAM and as large as a hard disk. This illusion works because of the Principle of Locality — programs tend to access only a small fraction of memory at any given time, and that fraction can be kept in the fastest cache layer.

The Hierarchy Levels (Fastest to Slowest):

1. CPU Registers (~0.25 ns, bytes)
2. L1 Cache (~1 ns, 32-64 KB)
3. L2 Cache (~4 ns, 256 KB - 1 MB)
4. L3 Cache (~10 ns, 4-64 MB)
5. Main Memory / DRAM (~50-100 ns, 8-64 GB)
6. SSD (~100 μs, 256 GB - 4 TB)
7. HDD (~10 ms, 1-20 TB)

The Principle of Locality is the empirical observation that programs do not access all memory locations with equal probability. Instead, they tend to access a small, concentrated subset of addresses at any point in time. This principle provides the theoretical foundation for why caches work.

Temporal Locality (Locality in Time):

• Observation: If a memory address is referenced at time t, there is a very high probability it will be referenced again in the near future (at time t + Δ).
• Programming Cause: Loops. A loop counter variable i is read and written every single iteration. Accumulators like sum += A[i] are touched repeatedly. Instruction memory of the loop body is fetched every iteration.
• Cache Justification: Once a data block is brought into the cache on the first access (a compulsory miss), it stays there. All subsequent accesses within the loop are fast cache hits, amortizing the cost of the initial slow memory fetch.

Spatial Locality (Locality in Space):

• Observation: If a memory address X is referenced, then addresses near X (e.g., X+1, X+2, X+4) are very likely to be referenced soon.
• Programming Cause: Sequential array traversal (A[0], A[1], A[2]...), sequential instruction fetching (one instruction after another), and accessing fields of a struct or object laid out contiguously in memory.
• Cache Justification: Caches do not fetch just the single requested byte. They fetch an entire cache block (line), typically 64 bytes. When A[0] is requested, the cache also loads A[1] through approximately A[15] (for 4-byte integers). All subsequent accesses to those elements are instant cache hits.

Conclusion: Without locality, every memory access would be a cache miss, rendering caches useless. It is precisely because programs exhibit strong temporal and spatial locality that a small, fast cache can intercept 90-99% of all memory accesses, dramatically speeding up execution.

The Memory Hierarchy is organized such that as you move closer to the CPU, memory becomes faster but smaller. Conversely, as you move away from the CPU, memory becomes slower but larger and cheaper.

Arrangement (Slowest/Largest → Fastest/Smallest):

Key Principle: Each level acts as a cache for the level below it. L1 caches data from L2, L2 caches data from L3, L3 caches data from DRAM, and DRAM effectively caches data from the SSD/HDD (via Virtual Memory).

Loops are the single most important source of locality in computer programs. They demonstrate both temporal and spatial locality simultaneously.

Example Code:

int sum = 0;
for (int i = 0; i < 1000; i++) {
    sum += A[i];
}
    

Temporal Locality exhibited:

• The variable sum is read and written in every single iteration of the loop (1000 times). After the first access brings sum into the cache, the remaining 999 accesses are all fast cache hits.
• The variable i (the loop counter) is read and incremented every iteration — also a temporal locality pattern.
• The instructions of the loop body (the machine code for sum += A[i], the branch, and the increment) are fetched from instruction memory 1000 times. After the first iteration fetches them into the I-Cache, the next 999 iterations are all instruction cache hits.

Spatial Locality exhibited:

• The array A[i] is accessed sequentially: A[0], A[1], A[2], ..., A[999]. These elements are stored contiguously in memory.
• When the CPU fetches A[0], the cache brings in an entire 64-byte cache block, which also contains A[1] through A[15] (assuming 4-byte integers). This means elements A[1] to A[15] are immediate cache hits without any additional memory requests.
• The instructions of the loop body are also stored sequentially in memory. Fetching the first instruction loads the neighboring instructions into the same cache block.

Net Result: Due to both types of locality, the cache hit rate for this loop is extremely high (often >95%), meaning the CPU rarely has to wait for slow main memory.

Each type of memory technology serves a specific, irreplaceable role in a computer system. No single technology can fulfill all requirements.

1. SRAM (Static Random-Access Memory):

• Role: Used for CPU Caches (L1, L2, L3).
• Technology: Uses 6 transistors per bit in a bistable flip-flop configuration. Data is retained as long as power is on (no refresh needed).
• Importance: Provides ultra-fast access times (~1 ns), which is essential to keep up with the CPU clock speed. Without SRAM caches, the CPU would stall on nearly every memory access, bottlenecking performance.
• Limitation: Extremely expensive and physically large per bit, limiting cache sizes to a few megabytes.

2. DRAM (Dynamic Random-Access Memory):

• Role: Used for Main Memory (the "RAM" users typically refer to).
• Technology: Uses 1 transistor + 1 capacitor per bit. The capacitor charge leaks over time, requiring periodic refresh cycles (every ~64 ms), hence "Dynamic".
• Importance: Offers a good balance of density, cost, and speed. It provides gigabytes of addressable memory (8-64 GB typically) at a reasonable cost, allowing programs and their data to reside in fast, random-access storage.
• Limitation: Much slower than SRAM (~50-100 ns access), and volatile (data lost on power off).

3. Flash Memory (NAND) / SSD:

• Role: Used for Secondary Storage (replacing traditional HDDs).
• Technology: Non-volatile. Uses floating-gate transistors to trap electrons, representing data bits even without power.
• Importance: Provides high-capacity, persistent, non-volatile storage with much faster access times than HDDs (microseconds vs. milliseconds). Critical for OS boot, application storage, and databases.

4. Magnetic Disk (HDD):

• Role: Archival and bulk storage.
• Importance: Provides the cheapest cost per GB for massive datasets (backups, media libraries, cold data). However, mechanical seek times make random access extremely slow (~10 ms).

Locality has a direct and profound impact on cache performance. It is the sole reason caches are effective. Without locality, a cache would have nearly a 0% hit rate and provide no benefit.

Impact on Hit Rate:

• High locality means the CPU repeatedly accesses data that is already in the cache. This directly increases the cache hit rate, which for well-optimized programs on modern processors can exceed 95-99%.
• Poor locality (e.g., random memory access patterns across a large dataset) causes the CPU to constantly request data that is NOT in the cache, resulting in a high miss rate and frequent, slow fetches from main memory.

Impact on Average Memory Access Time (AMAT):

• If the hit rate is 99% (miss rate = 1%), hit time is 1 ns, and miss penalty is 100 ns:
  AMAT = 1 + (0.01 × 100) = 1 + 1 = 2 ns. (Excellent, nearly as fast as the cache itself.)
• If the hit rate drops to 80% (miss rate = 20%) due to poor locality:
  AMAT = 1 + (0.20 × 100) = 1 + 20 = 21 ns. (Over 10× worse.)

Impact on Processor Stalls and CPI:

• Every cache miss forces the CPU pipeline to stall for dozens to hundreds of clock cycles while data is fetched from DRAM. These stalls directly inflate the effective CPI (Cycles Per Instruction).
• Effective CPI = Ideal CPI + Memory Stall Cycles per Instruction
• Programs with high locality minimize memory stall cycles, keeping the effective CPI close to the ideal CPI of 1.0.

Conclusion: Locality is the single most important factor determining cache performance. Compiler writers and programmers invest significant effort in optimizing data layouts and access patterns (e.g., loop tiling, struct-of-arrays vs. array-of-structs) to maximize locality.

The Inclusion Property (also called Multilevel Inclusion) is a design policy for multi-level cache hierarchies that states: every cache block present in a higher-level (closer to CPU) cache must also be present in the lower-level (farther from CPU) cache.

Formal Definition:

If a cache hierarchy has L1 and L2 caches, the inclusion property requires that:

That is, L1 is a strict subset of L2. Anything in L1 must also be in L2. L2 may contain blocks that are NOT in L1.

Implications and Mechanism:

• When L1 fetches a new block: The block is also loaded into L2 (if not already there).
• When L2 evicts a block: The hardware must check if that block also exists in L1. If it does, the block must be invalidated (or written back) from L1 as well. This is called a back-invalidation.
• Cache Coherence Benefit: This is the primary motivation. In a multiprocessor system using a snooping protocol, the coherence hardware only needs to snoop (monitor) the L2 cache. If a block is not in L2, the inclusion property guarantees it is also not in L1. This saves the overhead of snooping both L1 and L2.

Drawback:

The total unique cache capacity is reduced. Since L1 data is duplicated in L2, the effective unique storage is just the size of L2, not L1 + L2. This wastes a portion of the L2 space.

The MESI protocol (also known as the Illinois protocol) is a widely used hardware-based cache coherence protocol for multiprocessor systems. It tracks the state of every cache block to ensure that all processors see a consistent view of shared memory. MESI stands for the four possible states of a cache line:

The Four States:

1. M — Modified:
   • The cache line has been modified (written to) by this processor and is different from main memory.
   • This is the only valid copy of this data in the entire system.
   • The cache is responsible for writing this data back to main memory before any other processor can read it.
2. E — Exclusive:
   • The cache line is present only in this cache and it matches main memory (clean).
   • This processor can promote the state to Modified (write to it) without any bus transaction, because no other cache holds a copy.
3. S — Shared:
   • The cache line is present in this cache and potentially one or more other caches, and it matches main memory (clean).
   • If this processor wants to write to this line, it must first broadcast an Invalidate message on the bus to force all other caches to discard their copies.
4. I — Invalid:
   • The cache line is not valid. It contains stale or no data.
   • Any access to this line requires a full cache miss and a fetch from main memory or another cache.

Key Transitions (Examples):

• Read Miss (I → E or S): Processor reads a block not in its cache. If no other cache has it, the state becomes Exclusive. If another cache has it, both become Shared.
• Write Hit (E → M): Processor writes to a block it exclusively owns. No bus traffic needed; simply transition to Modified.
• Write Hit (S → M): Processor writes to a shared block. It must broadcast an Invalidate on the bus to invalidate all other copies, then transitions to Modified.
• Snoop Hit (M → I/S): Another processor wants to read a block that is Modified in this cache. This cache must supply the data (via bus intervention), write it back to memory, and transition to Shared (or Invalid).

These three policies define the relationship between the contents of different levels in a multi-level cache hierarchy (e.g., L1 and L2). Each has distinct trade-offs.

Key Insight: The choice depends on whether the designer prioritizes coherence simplicity (→ Inclusive) or maximum effective cache capacity (→ Exclusive). Non-Inclusive is a pragmatic middle ground used when neither extreme is desirable.

These are two distinct but related concepts that are essential for correctness in multiprocessor systems. They are often confused but address fundamentally different problems.

Summary: Coherence guarantees that you get the correct value for a single variable. Consistency guarantees the correct order in which updates to multiple variables become visible across processors. Both are necessary for correct parallel programs.

The inclusion property (L1 ⊆ L2) is a deliberate design choice with significant trade-offs.

Advantages:

1. Simplified Cache Coherence: This is the primary motivation. In a multiprocessor system with snooping, coherence requests (e.g., invalidations) from other processors on the shared bus only need to check the L2 cache. If the block is not found in L2, the inclusion property guarantees it is not in L1 either. This avoids the latency and complexity of also probing the smaller, faster L1 cache on every snoop request.
2. External Interface Simplification: The L2 cache acts as a single, unified filter between the processor core and the rest of the memory system. All coherence traffic is handled at L2, keeping the L1 cache dedicated to serving the CPU with minimal interference.
3. Easier Verification: Hardware designers find it easier to verify the correctness of a coherence protocol when the inclusion invariant holds, reducing design bugs.

Disadvantages:

1. Wasted Cache Capacity: All blocks in L1 are duplicated in L2. If L1 is 64 KB and L2 is 256 KB, effectively only 256 KB of unique data can be cached (not 64 + 256 = 320 KB). In an exclusive hierarchy, the full 320 KB would be usable.
2. Back-Invalidation Pollution: When L2 needs to evict a block (to make space), it must check if L1 also has that block. If L1 does, it must be forcibly evicted from L1 as well (back-invalidation). This can evict a block that the CPU is actively using from L1, causing an unnecessary L1 miss and performance degradation.
3. L2 Size Constraint: L2 must be significantly larger than L1 to avoid excessive back-invalidations. The associativity of L2 must also be at least as high as L1's to prevent pathological eviction scenarios.

The write policy determines what happens to main memory when the CPU writes to a cache block. This has a direct and significant impact on how coherence is maintained in multiprocessor systems.

Write-Through Policy:

• Mechanism: Every write to the cache simultaneously writes the data to main memory. The cache and memory are always in sync.
• Effect on Coherence: Main memory always holds the most up-to-date value. If another processor needs the data, it can (in principle) read it from main memory. This simplifies coherence because the "source of truth" is always available.
• Drawback: Generates massive bus traffic. Every single store instruction produces a write transaction on the memory bus. This saturates the shared bus in a multiprocessor system, making it a severe performance bottleneck. A Write Buffer is often used to partially mitigate this by batching writes.

Write-Back Policy:

• Mechanism: Writes are only made to the cache block. The cache block is marked as "dirty" (Modified). Main memory is only updated later, when the dirty block is evicted from the cache.
• Effect on Coherence: Main memory may hold stale data. This makes coherence significantly harder because the most current value of a memory location might reside exclusively in one processor's cache, unknown to all others. Hardware protocols like MESI become essential. When another processor requests the block, the owning cache must intercept the bus request (via snooping) and supply the data directly from its cache (cache-to-cache transfer or intervention).
• Advantage: Drastically reduces bus traffic. Multiple writes to the same block only generate a single memory transaction when the block is eventually evicted. This is crucial for scalability in multiprocessors.

Conclusion: Write-back is the dominant policy in modern multiprocessors because the reduced bus traffic far outweighs the added coherence complexity, which is efficiently handled by hardware protocols like MESI.

An inclusive cache hierarchy (where L1 ⊆ L2) has a very significant and beneficial impact on coherence protocol design, particularly for snooping-based protocols.

The Core Benefit — Snoop Filtering:

• In a bus-based multiprocessor, every coherence request (e.g., "Processor 2 wants to read block X") is broadcast on the shared bus. Every processor must check if it has block X in its cache.
• Without Inclusion: The coherence hardware would need to probe both the L1 and L2 caches of each processor. Since L1 is small and fast but directly serves the CPU pipeline, interrupting L1 for every snoop request causes performance degradation (structural hazards on the L1 port).
• With Inclusion: The coherence hardware only needs to probe the L2 cache (and its associated L2 tag array). If block X is NOT found in L2, the inclusion property mathematically guarantees it is NOT in L1. There is no need to interrupt the L1 cache at all. This keeps the L1 cache solely dedicated to the CPU, free from coherence interference.

Performance Impact:

• L2 caches are larger and slower, and typically have a dedicated port or tag array for snooping. Probing L2 does not interfere with L1-to-CPU traffic.
• This effectively decouples the processor pipeline from the coherence protocol, leading to higher overall throughput and lower latency.

The Tradeoff:

The price paid is the back-invalidation problem: when L2 evicts a block, L1 must also evict it. This can hurt performance if L2 is not sufficiently larger than L1.

Both are hardware mechanisms to ensure that all processors in a shared-memory multiprocessor see a consistent view of memory. They differ fundamentally in how they track which caches hold which blocks.

Snooping-Based Protocols:

• Mechanism: All processors share a common bus. Every cache controller continuously monitors (snoops) all bus transactions. When one processor broadcasts a read or write request, every other cache controller checks if it holds a copy of the requested block and takes appropriate action (invalidate, supply data, etc.).
• Protocols: MESI, MSI, MOESI.
• Advantages: Simple hardware design; low latency for small systems (broadcast is inherently fast).
• Disadvantages: Does not scale beyond ~8-16 processors. The shared bus becomes a bandwidth bottleneck because every transaction must be seen by every processor. Bus arbitration and bandwidth limit the system size.
• Used in: Dual-socket and quad-socket server systems, desktop multi-core processors.

Directory-Based Protocols:

• Mechanism: A distributed or centralized directory keeps track of the state of every memory block — specifically, which caches currently hold a copy. When a processor needs to perform a coherence action, it contacts the directory. The directory sends point-to-point messages only to the specific caches that need to be notified, rather than broadcasting to all.
• Advantages: Highly scalable. Bus bandwidth is not a bottleneck because messages are targeted (unicast), not broadcast. Can scale to hundreds or thousands of processors.
• Disadvantages: Higher latency for individual transactions (requires a message to the directory, then a message from the directory to the relevant cache, then a response back). More complex hardware and more memory overhead to store the directory entries.
• Used in: Large-scale servers, NUMA systems (e.g., AMD EPYC, Intel Xeon with QPI/UPI), supercomputers.

Cache organization determines where a memory block can be placed within the cache. This is one of the most critical cache design decisions.

1. Direct-Mapped Cache:

• Rule: Each memory block maps to exactly one specific cache line.
• Mapping: Cache Line Index = Block Address MOD Number of Cache Blocks.
• Advantage: Simplest hardware. Only one comparison is needed to check for a hit/miss, leading to the fastest hit time.
• Disadvantage: High conflict miss rate. If two frequently used blocks map to the same line, they continuously evict each other (thrashing), even if other cache lines are empty.
• Address Division: | Tag | Index | Block Offset |

2. Fully Associative Cache:

• Rule: A memory block can be placed in any cache line.
• Mapping: No index bits needed. The entire block address is used as the tag.
• Advantage: Lowest conflict miss rate. A block is only evicted when the cache is completely full. Maximum flexibility.
• Disadvantage: Most expensive hardware. Every cache line's tag must be compared simultaneously (in parallel) with the requested address. This requires a large comparator array, making it impractical for large caches.
• Address Division: | Tag | Block Offset |

3. Set-Associative Cache (N-way):

• Rule: The cache is divided into sets. Each set contains N cache lines (N "ways"). A memory block maps to a specific set (using an index), but can be placed in any of the N ways within that set.
• Mapping: Set Index = Block Address MOD Number of Sets.
• Advantage: Best practical compromise. 4-way or 8-way set associativity drastically reduces conflict misses compared to direct-mapped, while requiring far fewer comparators than a fully associative cache.
• Address Division: | Tag | Set Index | Block Offset |

Note: Direct-Mapped is a special case of set-associative with 1 way. Fully Associative is a special case with 1 set containing all lines.

When a cache miss occurs in a set-associative or fully associative cache and the set is full, the cache controller must decide which existing block to evict (replace) to make room for the new block. The replacement policy determines this choice.

1. LRU (Least Recently Used):

• Policy: Evict the block that has not been accessed for the longest time.
• Rationale: Based on temporal locality — a block not used for a long time is unlikely to be needed soon.
• Implementation: Requires tracking access order. For 2-way, a single bit suffices. For N-way (N > 4), hardware complexity grows factorially, making true LRU impractical. Pseudo-LRU approximations (like tree-based PLRU) are commonly used instead.
• Performance: Generally the best performing policy for typical workloads.

2. FIFO (First In, First Out):

• Policy: Evict the block that has been in the cache the longest (oldest arrival), regardless of how recently or frequently it was accessed.
• Rationale: Simple to implement with a circular pointer.
• Drawback: Can evict frequently used blocks that happened to arrive early. Suffers from Belady's anomaly (increasing cache size can sometimes increase miss rate).

3. Random Replacement:

• Policy: Evict a randomly chosen block from the set.
• Rationale: Extremely simple hardware (just a random number generator / counter). No tracking of access history needed at all.
• Performance: Surprisingly competitive with LRU for high-associativity caches (8-way and above). It avoids pathological worst-case patterns that can trap LRU.

4. Optimal (Belady's Algorithm — Theoretical Only):

• Policy: Evict the block that will be accessed farthest in the future.
• Implementation: Impossible to implement in hardware (requires knowledge of the future). Used only as a theoretical benchmark to measure how close practical algorithms come to the ideal.

The choice of replacement policy depends on the hardware constraints and the expected workload behavior.

• LRU is suitable when:
  • The cache associativity is low (2-way or 4-way), where LRU hardware cost is manageable.
  • The workload exhibits strong temporal locality (e.g., loops, recursive algorithms), where recently used data is very likely to be used again.
  • Performance is the top priority and the hardware budget allows for the tracking logic.
• FIFO is suitable when:
  • Hardware simplicity is critical and the budget for replacement logic is minimal.
  • The workload has streaming patterns where data is accessed once and then never again (FIFO naturally evicts the oldest, already-consumed data).
• Random is suitable when:
  • The cache has high associativity (8-way, 16-way), where true LRU is prohibitively expensive in hardware.
  • The workload has unpredictable or adversarial access patterns that could exploit weaknesses in deterministic policies like LRU.
  • In L2 and L3 caches, where the slight performance difference compared to LRU is negligible, but the hardware savings are significant.

Cache performance is evaluated by measuring how effectively the cache intercepts memory requests, preventing them from reaching the slower main memory.

1. Hit Rate (H):

• Definition: The fraction of all memory accesses that are successfully found in the cache (cache hits).
• Hit Rate = Number of Cache Hits / Total Number of Memory Accesses
• A typical well-designed L1 cache achieves a hit rate of 95-99%.

2. Miss Rate (M):

• Definition: The fraction of all memory accesses that are NOT found in the cache (cache misses).
• Miss Rate = 1 - Hit Rate = Number of Cache Misses / Total Number of Memory Accesses
• Misses are categorized using the "Three C's" model:
  • Compulsory Misses: First-ever access to a block (cold miss). Unavoidable.
  • Capacity Misses: The cache is too small to hold all the data the program needs.
  • Conflict Misses: Multiple blocks map to the same cache set and evict each other, even though the cache has unused space elsewhere.

3. Average Memory Access Time (AMAT):

• Definition: The average time required for a memory access, considering both hits and misses.
• AMAT = Hit Time + (Miss Rate × Miss Penalty)
• Hit Time: The time to access the cache and determine if it's a hit (typically 1-4 clock cycles for L1).
• Miss Penalty: The additional time needed to fetch the block from the next level of memory when a miss occurs (typically 50-200 clock cycles for accessing DRAM).
• For multi-level caches: AMAT = Hit Time L1 + Miss Rate L1 × (Hit Time L2 + Miss Rate L2 × Miss Penalty L2).

This is a straightforward application of the AMAT formula.

Given:

• Hit Rate = 90% = 0.90
• Hit Time = 5 ns
• Main Memory Access Time (used as Miss Penalty) = 50 ns

Step 1: Calculate the Miss Rate

Step 2: Apply the AMAT Formula

Conclusion: The Average Memory Access Time is 10 ns.

Interpretation: Even though the cache serves 90% of requests in just 5 ns, the 10% of misses — each costing an additional 50 ns — doubles the average access time to 10 ns. This illustrates why even small improvements in miss rate (e.g., from 10% to 5%) have an outsized impact on AMAT (reducing it from 10 ns to 7.5 ns).

Given:

• Total number of cache blocks = 32
• Associativity (number of ways) = 4

Step 1: Calculate the Number of Sets

Step 2: Explain the Replacement Policy

The replacement policy dictates which of the 4 blocks within a given set is evicted when a new block needs to be loaded into a set that is already full.

• In a Direct-Mapped cache (1-way), there is no choice — the single block in the mapped line is always replaced. No replacement policy needed.
• In this 4-way set-associative cache, each set has 4 blocks. When a miss occurs and the set is full, the hardware must choose one of the 4 blocks to evict. Common policies include:
  • LRU: Evict the least recently used of the 4 blocks. For 4-way, this requires tracking access ordering, which is feasible.
  • Random: Evict a randomly chosen block from the 4 ways. Simpler hardware.
  • FIFO: Evict the block that entered the set earliest.

Address Breakdown:

• Set Index bits: log₂(8) = 3 bits (to select one of 8 sets).
• Block Offset bits: Depends on block size (e.g., if block = 16 bytes → 4 bits).
• Tag bits: Remaining bits of the address.

General approach for solving any direct-mapped cache trace problem for an exam:

Step-by-Step Method:

1. Determine the mapping function: Cache Line = Block Address MOD Number of Cache Lines.
2. Create a table with columns: Access #, Block Address, Cache Line (Index), Tag, Current Cache Contents, Hit/Miss.
3. For each access:
   • Calculate which cache line the block maps to.
   • Check if the current tag in that cache line matches the incoming block's tag.
   • If tags match → HIT.
   • If tags don't match (or line is empty) → MISS. Replace the block in that cache line with the new block.

Example Trace:

Cache: 4 lines (0-3). Block sequence: 0, 8, 0, 6, 8.

Mapping: Line = Block MOD 4.

Result: 0 Hits, 5 Misses. Blocks 0 and 8 constantly thrash because they both map to Line 0. A 2-way set-associative cache would solve this.

Given: Cache size = 4 blocks. Direct-Mapped. Mapping: Cache Line = Block Number mod 4.

Note: In a Direct-Mapped cache, the "replacement policy" is irrelevant because each block has exactly one possible location. There is no choice about which block to evict — the conflicting block is always overwritten.

Result: 5 Hits, 7 Misses.

Given: 2 Sets, each with 2 blocks (2-way). Total = 4 blocks. LRU replacement. Mapping: Set = Block MOD 2.

Sets: Set 0 (holds blocks where Block mod 2 = 0) and Set 1 (holds blocks where Block mod 2 = 1).

Result: 4 Hits, 4 Misses.

Analysis: The first 4 accesses are compulsory misses (cold starts). The next 4 accesses are all hits because the working set (blocks 0, 4, 1, 5) fits perfectly into the 4-block cache. The 2-way associativity prevents the conflict misses that would destroy performance in a direct-mapped cache with this access pattern.