Medium ●●

🏛️ Memory Hierarchy & Main Memory

Why it matters: Chip-count, address-line, interleaving and virtual-memory (EAT with TLB) problems show up regularly.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 7 done.

Formulas

Memory size
2^(address bits) × (bits per word)
Chips needed
(total words / chip words) × (total width / chip width)
Decoder
extra address bits = log₂(#chips in the depth direction)
Pages / frames
#pages = virtual space / page size · #frames = physical memory / page size
Page table size
= #pages × PTE size
VA split
VA = page number (VPN) + offset (log₂ page size)
EAT with TLB (1-level PT)
EAT = h(t + m) + (1 − h)(t + 2m) [t = TLB time, m = memory time]
EAT with page faults
EAT = (1 − p)·EAT_mem + p·(fault service time)
Interleaved bandwidth
≈ M words per access time T for M banks (ideal, sequential access)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Number of chips / address lines / decoder size
Build 1M×32 memory from 256K×8 chips: chips = 16, decoder lines etc.
★★★
Page table size / address translation bits
Given virtual & physical sizes and page size, compute PTE count, VPN/offset bits (shared with OS).
★★★
EAT with TLB and/or page faults
Hit ratio h, TLB time, memory time, maybe two-level page table (+m per extra level).
★★★
Interleaving / memory cycle statements
Which interleaving gives parallelism; total time to fetch a block from M banks.
★★★
SRAM/DRAM, refresh, hierarchy conceptual
One-liner true/false.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

16 real questions from the official GATE CSE papers (2012 to 2023), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

16 questions · 0 correct of 0 attempted · marks 0 / 26

Year:
GATE 2023 · Q42MCQ2 marks
A 4 kilobyte byte-addressable memory is realized using four 1 KB memory blocks. Two input address lines (IA4 and IA3) are connected to the chip select (CS) of these memory blocks through a decoder (inputs A1 = IA4 as MSB, A0 = IA3 as LSB; outputs Q0..Q3 drive the CS of blocks X1..X4). The remaining ten input address lines from IA11–IA0 (except IA4, IA3) feed the 10-bit address port of the blocks. CS is active high. The input memory addresses (IA11–IA0), in decimal, for the starting locations (Addr = 0) of each block X1, X2, X3, X4 are among the options. Which one is CORRECT?
GATE 2023 · Q58NAT2 marks
Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The value of L is ______.
GATE 2022 · Q38MCQ2 marks
Which one of the following statements is FALSE?
GATE 2020 · Q20NAT1 mark
If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m + n is ______.
GATE 2020 · Q53NAT2 marks
Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal place) is ______.
GATE 2019 Set 2 · Q2MCQ1 mark
The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by A15 to A0. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal? (Figure: a 5-input AND gate with inputs A15, A14, A13 (inverted), A12 (inverted) and A11; its output is CS.)
GATE 2019 Set 2 · Q33MCQ2 marks
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?
GATE 2019 Set 2 · Q45NAT2 marks
A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is ______ × 106 bytes/sec.
GATE 2018 · Q23NAT1 mark
A 32-bit wide main memory unit with a capacity of 1 GB is built using 256M × 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is 214. The time taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2 milliseconds. The percentage (rounded to the closest integer) of the time available for performing the memory read/write operations in the main memory unit is ______.
GATE 2016 Set 1 · Q9NAT1 mark
A processor can support a maximum memory of 4 GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the processor is at least ______ bits.
GATE 2016 Set 1 · Q47NAT2 marks
Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ______ megabytes.
GATE 2015 Set 1 · Q12NAT1 mark
Consider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is ______.
GATE 2013 Code A · Q46MCQ2 marks
A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8). The number of 2 × 4 decoders with enable line needed to construct a 16K × 16 RAM from 1K × 8 RAM is
GATE 2013 Code A · Q52MCQ2 marks
A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes. What is the size of a page in KB in this computer?
GATE 2013 Code A · Q53MCQ2 marks
(Same machine as the previous question: 46-bit virtual address, 8 KB pages, and a 1 MB 16-way set associative virtually indexed physically tagged cache with 64-byte blocks.) What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?
GATE 2012 Code A · Q19MCQ1 mark
The amount of ROM needed to implement a 4 bit multiplier is

Extra practice (GATE-style)

More questions in the same formats, each with a full solution. These are original questions written to follow the patterns above, not past-paper questions.

5 questions · 0 correct of 0 attempted · marks 0 / 7

Q1NAT1 mark
The number of 256K × 8 memory chips needed to build a 1M × 16 memory is ____.
Q2NAT2 marks
TLB hit ratio 90%, TLB access 10 ns, memory access 100 ns, single-level page table. The effective access time (ns) is ____.
Q3NAT1 mark
32-bit virtual addresses, 16 KB pages and 4-byte page-table entries with a single-level page table. The page table size in KB is ____.
Q4NAT2 marks
Two-level page table, TLB hit ratio 80%, TLB time 5 ns, memory 100 ns. The effective access time (ns) is ____.
Q5MCQ1 mark
Which statement is true?

Common traps

TLB miss costs one extra memory access per page-table level.
Virtual memory questions may be tagged OS, the formulas are the same.