Cache Memory and Hierarchy

Core concepts

• Direct, fully-associative, and k-way set-associative cache mapping
• Physical vs. Virtual indexing and Tagging (Page coloring for aliasing)
• Hierarchical vs. Simultaneous memory access models
• Average Memory Access Time (AMAT) and stall cycles per instruction
• Separate Instruction (I-Cache) and Data (D-Cache) hierarchies
• Write-Through with No-Write Allocate vs. Write-Back with Write Allocate
• Dirty (Modified) bit and Valid bit mechanics during hit/miss/eviction
• Block replacement algorithms (LRU, FIFO) and reference string simulation
• Compulsory (cold), Capacity, and Conflict misses
• Memory interleaving, bank cycle time, and bus bottleneck analysis
• Magnetic disk drive geometry and capacity calculations
• Address decomposition: Tag, Set Index, and Word/Byte Offset fields
• Cache organization: k-way Set-Associative, Direct-Mapped, and Fully-Associative architectures
• Cache tag directory overhead: Tag size, Valid bits, Dirty/Modified bits, and Replacement policy bits
• Set mapping arithmetic using modulo operations (j v)
• Write update policies: Write-through vs. Write-back and dirty bit behavior
• Write miss policies: Write-allocate vs. No-write-allocate pairing and multilevel inclusivity
• Address division into Tag, Set/Line Index, and Block Offset
• Direct-mapped vs. P-way set-associative cache geometry
• Metadata bits per line (Tag bits, Valid bit, Modified/Dirty bit in write-back cache)
• Hexadecimal address bit-slicing and masking to extract index and tag
• Byte addressability vs. word length distinctions
• Address line partitioning (Chip Select decoding vs. Internal Memory Address)
• Decoder logic (Active High/Active Low Chip Select)
• Non-contiguous bit decoding (interleaving / stride addressing caused by middle-bit chip selection)
• Starting and ending addresses of memory modules
• Memory matrix organization (rows vs columns of RAM chips)
• Hierarchical address decoder construction using enable inputs
• DRAM row-by-row refresh timing, refresh period, and bandwidth overhead
• Address decoder sizing (k : 2k) versus Multiplexer routing (k : 1)
• Code word / control word bit allocation for memory/register select
• Multi-level memory hierarchy (L1, L2, Main Memory) AMAT and miss rates
• Cycles Per Instruction (CPI) per instruction class
• Total clock cycle computation from instruction mix
• CPU execution time and clock period relationship
• Unit conversion between seconds and nanoseconds
• Fully associative, direct, and set-associative cache mapping
• Physical address breakdown (Tag, Index, Block Offset)
• Byte-addressable memory organization
• Memory chip interfacing and address decoding
• Active-high and active-low chip select logic
• Hexadecimal-to-binary address range conversion
• CPU Execution Time equation
• Cycles Per Instruction (CPI)
• Clock frequency (f) vs Clock cycle time ( = 1/f)
• Instruction count invariance across identical instruction sets and inputs
• Relative performance percentage scaling

Recurring question patterns

• Cache Address Field Decomposition and Tag Sizing

  common · NAT · 2 marks · 2026, 2025, 2023, 2021

  Given physical address size, cache capacity, block size, and associativity (or variations where one parameter is unknown or parameterized by variables), calculate the width of Tag, Set Index, or Offset bits, or total tag memory required.

• Multi-Level Cache AMAT and CPI Stall Analysis

  common · NAT · 2 marks · 2025, 2024, 2022, 2017

  Given L1/L2 access times, local/global hit rates, and main memory miss penalties (often separated into I-cache and D-cache or read/write distributions), calculate AMAT, effective CPI, or minimum required hit rate after optimization.

• Address Trace Simulation and Cache Conflict/Hit Analysis

  common · MSQ · 2 marks · 2026, 2022, 2017, 2014

  Given a sequence of hex addresses or block numbers accessed in a loop over a specific cache organization, trace compulsory vs conflict misses, hit/miss outcomes for specific references, and final cache contents.

• Write Policy Conceptual Analysis

  occasional · MSQ · 2 marks · 2024, 2022

  Evaluate architectural assertions regarding Write-Back vs. Write-Through policies, dirty bit necessity, eviction penalties on read/write misses, and memory bus traffic.

• Memory Interleaving and Secondary Storage Geometry

  occasional · NAT · 2 marks · 2024, 2016, 2014

  Calculate throughput/initiation rates in multi-module interleaved memory systems or solve for disk geometry parameters (cylinders, surfaces, sectors) from capacity constraints.

• Cache Address Breakdown and Tag Directory Size Calculation

  common · MCQ · 2 marks · 2012

  Given physical address size, cache capacity, associativity, and block size, calculate the number of tag bits and the total size in bits/Kbits of the tag directory (including status bits like valid, modified/dirty, replacement bits).

• Algebraic Block-to-Line/Set Mapping Formulation

  occasional · MCQ · 1 marks · 2013

  Formulating the exact cache line index range or set index algebraically for a memory block $j$ in a $k$-way set associative cache with $v$ sets where lines are ordered consecutively.

• Cache Write and Allocation Policy Analysis

  occasional · MCQ · 2 marks · 2021

  Multi-statement verification evaluating properties of write-through vs. write-back policies (dirty line handling, writebacks on read/write misses) and their pairings with write-allocate vs. no-write-allocate policies in single/multilevel caches.

• Hexadecimal Address Mapping and Set/Line Index Extraction

  common · MCQ · 2 marks · 2020, 2015

  Given physical memory size, cache parameters (cache size, associativity, block size), and one or more hexadecimal addresses, determine field bit-widths (Tag, Index, Offset) and identify which set/line the addresses map to or extract their exact hexadecimal Tag and Index values.

• Cache Controller Metadata and Tag Directory Size Calculation

  occasional · MCQ · 2 marks · 2011

  Given cache capacity, block size, address length, and mapping scheme along with status bits (valid bit, dirty/modified bit for write-back), determine the total storage required for metadata (tag directory size).

• Decoder-Based Chip Select and Address Mapping

  rare · MCQ · 2 marks · 2023

  A system memory of size $N$ is built using smaller memory blocks selected by a decoder driven by a subset of system address lines. Candidates determine the starting/ending addresses or address range of specific memory chips based on which bit positions drive the decoder versus the chip internal address lines.

• Memory Chip Expansion and Decoder Tree Design

  occasional · MCQ · 2 marks · 2013

  Constructing a target memory capacity and word length using smaller RAM/ROM chips, determining row/column organization, and calculating the exact number of smaller decoders (with enable lines) required to form the address decoding tree.

• DRAM Refresh Overhead and Bandwidth Availability

  occasional · NAT · 1 marks · 2018

  Given the number of memory cell rows in a DRAM chip, time per row refresh operation, and refresh period, calculating the total refresh time overhead and the remaining percentage of time available for read/write operations.

• Memory & Register Interfacing Logic Identification

  occasional · MCQ · 2 marks · 2022

  Determining the required addressing components (e.g., $n:2^n$ decoders) and data path routing units (e.g., $k:1$ multiplexers) for interfacing distinct memory segments and register files given word sizes and instruction/code word layouts.

• Hierarchical Average Memory Access Time (AMAT)

  occasional · NAT · 2 marks · 2025

  Computing the overall AMAT across a multi-level hierarchy (L1 cache, L2 cache, Main Memory) given access times, hit rates, or miss penalties at each level in simultaneous or hierarchical access configurations.

• Instruction Mix and Clock Cycle Time Calculation

  common · NAT · 2 marks · 2025

  Given an instruction breakdown by category with respective CPIs/cycle counts and total execution time, compute the total clock cycles and solve for the clock cycle duration (in ns) or clock frequency (in MHz/GHz).

• Cache Address Field Division

  common · MCQ · 1 marks · 2019

  Given cache parameters (cache size, block size, associativity) and main memory address width, compute the number of bits allocated to Tag, Set/Index, and Word/Byte offset fields.

• Chip Select Address Decoding

  common · MCQ · 1 marks · 2019

  Given a logic gate circuit (e.g., AND/NAND with inverted inputs) driving the Chip Select (CS) line using higher-order address lines, determine the enabled memory address range in hexadecimal.

• Comparative CPU Performance & Execution Time Ratio

  common · NAT · 2 marks · 2014

  Two processors executing the same instruction set/program with relative differences in execution time and CPI are compared to compute an unknown processor metric (such as clock frequency or cycle time).

Formulas GATE uses

Examiner traps in Cache Memory and Hierarchy

• Confusing word addressability with byte addressability (e.g., assuming 1 address = 1 byte when word size is given as 2 or 4 bytes).
• Misinterpreting local miss rate vs. global miss rate in multi-level caches (e.g., using misses per 1000 instructions as local miss rate without dividing by L1 misses).
• Adding L1 access time twice when formula uses hierarchical format vs miss penalty format.
• Assuming Write-Through caches have dirty bits, or forgetting that dirty blocks in Write-Back are only written back upon eviction (not on the initial write hit).
• Forgetting that compulsory misses occur strictly on the first global reference to a distinct block, not on subsequent conflicts in a looped trace.
• Forgetting that increasing associativity k 2k keeps Tag + Index constant, thus increasing tag bits by 1 bit and reducing index bits by 1 bit.
• Multiplying tag directory entry size by number of sets instead of total number of cache lines (blocks).
• Confusing number of sets v with associativity k in modulo mapping (j v vs j k).
• Overlooking extra status bits (multiple valid bits, dirty bits, replacement bits) when computing tag directory size.
• Assuming write-allocate must strictly be paired with write-through (in reality, write-allocate is standard for write-back).
• Forgetting that write-through caches never hold dirty lines, so evictions never trigger dirty writebacks.
• Confusing word length (e.g. 32-bit architecture) with the physical address size when main memory size is explicitly specified (e.g., 16 MB implies a 24-bit address, not 32-bit).
• Dividing cache size by set associativity before dividing by block size (or forgetting to divide total lines by P-way associativity to get set count).
• Misaligning hexadecimal digits when the set index or tag does not align on 4-bit nibble boundaries, requiring manual binary extraction of intermediate bits.
• Forgetting to multiply the metadata per line by the total number of lines (instead of number of sets) when calculating total tag directory size.
• Assuming the decoder is always connected to the Most Significant Bits (MSBs), which leads to standard contiguous block starting addresses like (0, 1024, 2048, 3072).
• Ignoring the weights of the specific bit positions connected to the decoder inputs (e.g., treating bit IA3 as weight 1 instead of weight 23 = 8).
• Confusing the order of decoder input selection lines (e.g., A1 vs A0 connections causing swapped outputs).
• Forgetting the top-level enable decoder in decoder trees (e.g., counting only the 4 second-level decoders instead of 1 + 4 = 5 decoders in 2013).
• Confusing the number of total chips with the number of row selection outputs when sizing the decoder tree.
• Multiplying DRAM refresh time by the total number of chips instead of the number of internal rows in a single chip refreshed simultaneously (2018).
• Misinterpreting given L2/Main Memory access times as incremental access times versus cumulative miss penalties (2025).
• Confusing multiplexers (k:1 data selector) with decoders (k:2k address line expander) when identifying datapath block diagrams (2022).
• Unit conversion errors between seconds, nanoseconds (10-9 s), and clock frequency (GHz/MHz)
• Failing to multiply individual instruction class counts by their specific CPIs before summing
• Confusing total instruction count with total cycle count
• Assuming index bits exist in a fully associative cache (forgetting that fully associative implies 0 index bits / 1 set).
• Confusing total cache lines with sets when dealing with different associativity levels.
• Incorrectly interpreting active-low (bubble) inputs on logic gates when computing fixed high-order address bits.
• Off-by-one errors in binary-to-hexadecimal grouping when converting the maximum address (all 1s in unconstrained lines).
• Inverting the frequency ratio: forgetting that execution time is inversely proportional to clock frequency (T 1/f).
• Miscalculating percentage decrease vs increase (e.g., taking 25\% less time as dividing by 1.25 instead of multiplying by 0.75).
• Assuming instruction count changes when identical ISAs and inputs are explicitly stated.

How questions are asked

• NAT: Calculate tag field bit width from cache/memory sizing parameters
• NAT: Compute multi-level AMAT or effective CPI with stall penalties
• MSQ: Trace hex memory references in a loop to identify hit/miss/eviction states
• MSQ: Identify correct/incorrect statements regarding Write-Back vs. Write-Through cache policies
• NAT: Reverse-engineer cache size or associativity from mapping constraints on given address values
• NAT: Multi-module interleaved memory initiation count in a given time window
• Address field bit width calculation
• Tag directory memory overhead calculation
• Algebraic formula selection for line/set mapping
• Multi-statement evaluation on write policies and multi-level cache behavior
• Calculate total tag/metadata memory overhead in bits/bytes
• Find Tag and Line Index values in hexadecimal for a given address
• Match given multiple hexadecimal addresses to identical or different cache sets
• Schematic diagram analysis with decoder and memory block connections
• Determining starting/ending decimal or hexadecimal addresses for memory modules
• Count component units (decoders, chips) to build a larger target memory
• Calculate time overhead or available bandwidth percentage (NAT)
• Block diagram component identification matching control word bits
• Multi-level AMAT calculation with hit rates and access times
• Table-based instruction mix NAT calculation
• Clock period derivation from program execution time
• Calculate Tag/Index/Offset bit counts from cache specifications
• Determine hexadecimal address range from a logic gate diagram
• Comparative parameter calculation from percentage differences (NAT)

Paper trends

• Shift from straightforward 1-mark address splitting MCQs to multi-variable parameterized equations and MSQ-based address sequence tracing.

  2026, 2025, 2024, 2023, 2022, 2021

• Increased focus on non-trivial boundary analysis, such as inferring maximum cache size or indexing bounds directly from hex bit patterns.

  2026

• Consistent dominance of NAT and MSQ formats over standard 4-option MCQs for memory organization questions.

  2026, 2025, 2024, 2022, 2021

• Shift from linked numerical calculation questions (tag bit widths and directory overhead) to formal algebraic mapping properties and multi-statement conceptual evaluations of multi-level cache write hierarchies.

  2021, 2013, 2012

• Focus transitioned from direct-mapped total tag directory size calculations to set-associative multi-address bitwise extraction requiring hex-to-binary bit shifting.

  2020, 2015, 2011

• Memory interfacing appeared in recent years (2023) focusing on non-contiguous or intermediate address line selection (e.g., IA4 and IA3) driving the decoder rather than the traditional MSBs, testing deep binary address decoding rather than rote memorization.

  2023

• Shift from purely discrete combinational memory expansion design (2013) to numerical performance analysis involving DRAM refresh cycles (2018) and multi-level cache AMAT (2025).

  2025, 2018, 2013

• Adoption of block diagrams and system architectural figures to test component identification and data flow across registers/memory (2022, 2025).

  2025, 2022

• Even split between 2-mark conceptual MCQs and precise numerical NAT questions with tight tolerances.

  2025, 2022, 2018

• Recent examinations focus on exact numerical computation (NAT format) involving execution time, instruction mix tables, and unit conversions (seconds to nanoseconds).

  2025

• In 2019, questions tested both architectural mapping rules (fully associative cache bit allocations) and hardware interfacing logic (chip-select logic gates) at the 1-mark level.

  2019

• Questions on CPU performance use numerical percentage variations in execution time and CPI to evaluate exact clock frequencies via NAT format.

  2014

Difficulty notes