Self-checkedTier 1 13 min readcoa.cache-mapping

Cache memory mapping

How a block of memory is placed in the cache: direct, fully associative and set-associative mapping, the tag, index and offset fields, the size of the tag store, hit detection, and the three kinds of misses.

Why it exists

A cache holds copies of a small part of main memory. Whenever the processor gives an address, the hardware must answer two questions very quickly: is a copy of this word in the cache? and if so, where? Searching every line one by one would be as slow as the memory itself, so the placement of memory blocks into cache lines follows a fixed rule, the mapping, which narrows the search to one line (direct mapping), a few lines (set-associative), or all (fully associative). The mapping rule is also why some programs run fast and others, doing the same work in a different order, run far slower. GATE asks for the address fields, the number of lines, sets and tag bits, the size of the cache in bits, whether an access hits, and the number of misses of a given address sequence.

Prerequisites

Memory hierarchy and performance (AMAT)

You need the idea of hit, miss, block and miss penalty from the memory hierarchy.

Precise definitions

Block (line). The unit of transfer between the cache and the next level. A block of $B$ bytes is aligned: its first address is a multiple of $B$ . The block number of an address is $\lfloor \text{address} / B \rfloor$ .

Address fields. For an address of $a$ bits, a block of $B = 2^{o}$ bytes and a cache of $S = 2^{i}$ sets:

$\underbrace{\text{tag}}_{a - i - o}\ \big|\ \underbrace{\text{index}}_{i}\ \big|\ \underbrace{\text{offset}}_{o}$

The offset selects the byte inside the block, the index selects the set, and the tag is stored with the line to identify which block of memory currently sits there.

Geometry. Cache size $C$ bytes, block size $B$ , associativity $W$ (ways): number of lines $L = C / B$ , number of sets $S = L / W$ , index bits $i = \log_2 S$ , offset bits $o = \log_2 B$ , tag bits $a - i - o$ .

The three mappings.

Mapping	Ways $W$	Sets $S$	A block may go to	Index bits
Direct mapped	1	$L$	exactly one line, $\text{block} \bmod L$	$\log_2 L$
$W$ -way set associative	$W$	$L / W$	any of $W$ lines in set $\text{block} \bmod S$	$\log_2 (L/W)$
Fully associative	$L$	1	any line	0

Lookup. Use the index to find the set; compare the tag of the address with the valid line tags of the set (in parallel: $W$ comparators); a match is a hit, and the offset selects the byte (a $W$ -to-1 multiplexer picks the matching way). A line also has a valid bit (is there anything in it) and, for write-back caches, a dirty bit.

Size of the tag store. Each line stores a tag and a valid bit (and a dirty bit if used). For a 16 KB direct-mapped cache with 64-byte lines and 32-bit addresses: 256 lines, tag $= 32 - 8 - 6 = 18$ bits, so the tag store is $256 \times (18 + 1) = 4864$ bits (5120 with a dirty bit). The total cache is data plus tag store: $131072 + 5120$ bits.

Associativity changes the fields, not the capacity. For the same size and block size, doubling the associativity halves the number of sets, removes one index bit and adds one tag bit. 16 KB, 64-byte lines: direct mapped has 18 tag bits and 8 index bits; 4-way has 20 and 6; fully associative has 26 and 0.

The three kinds of miss (3C model).

Compulsory (cold): the first access to a block; unavoidable (a bigger block helps by prefetching neighbours).
Capacity: the block was evicted because the program uses more blocks than the cache holds (also misses in a fully associative cache of the same size).
Conflict: the block was evicted because too many blocks map to the same set (misses in this cache but would hit in a fully associative cache of the same size); higher associativity removes them.

How it works

Eight lines of four bytes (a small 32-byte cache) serve the 14 reads 0, 1, 2, 3, 4, 5, 32, 33, 0, 4, 36, 8, 9, 40 with 8-bit addresses. Step through the direct-mapped cache. Notice (1) the spatial hits at 1, 2, 3 and 5 after the first access to each block, (2) address 32 maps to the same line as address 0 (they differ only in the tag) and replaces it, and (3) the later access to 0 is a conflict miss: a fully associative cache of the same size would have kept it.

Direct-mapped cache: 8 lines of 4 bytes: start

Cache simulated, not typed

8 sets x 1 way, direct mapped. Hit time 1, miss penalty 10 cycles.

hits

misses

hit rate

avg cycles per access

memory reads

memory writes

set	way 0
0	empty
1	empty
2	empty
3	empty
4	empty
5	empty
6	empty
7	empty

Step 1

A direct-mapped cache with 8 lines of 4 bytes and 8-bit addresses: 2 offset bits, 3 index bits, 3 tag bits. Each memory block can live in exactly one line, chosen by the index bits.

1 / 15

computed by script: exact simulation of the cache, one access per step. python3 scripts/gen-coa-mem-traces.py

The same 8 lines arranged as 2-way set associative (4 sets) avoid the conflict: blocks 0 and 8 both fit in set 0.

2-way set-associative cache: 4 sets of 2 lines: start

Cache simulated, not typed

4 sets x 2 ways, LRU. Hit time 1, miss penalty 10 cycles.

hits

misses

hit rate

avg cycles per access

memory reads

memory writes

set	way 0	way 1
0	empty	empty
1	empty	empty
2	empty	empty
3	empty	empty

Step 1

The same 8 lines arranged as 4 sets of 2 ways: 2 offset bits, 2 index bits, 4 tag bits. A block may sit in either way of its set; LRU chooses the victim when both are valid.

1 / 15

computed by script: exact simulation of the cache, one access per step. python3 scripts/gen-coa-mem-traces.py

Worked examples

EX 1A cache simulator and a matrix traversal

Easy

The C program simulates a set-associative LRU cache. It reproduces the three runs of the animations (the letters show hit h or miss M for each of the 14 reads), and then walks a $64 \times 64$ array of 4-byte integers through a 1 KB cache with 64-byte lines, once row by row and once column by column.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* a set-associative cache with LRU replacement; addresses are byte addresses */
typedef struct {
    int sets, ways, offset_bits;
    long *block;           /* block number stored in each line, -1 when invalid */
    long *used;            /* time of the last use */
    long clock, hits, misses;
} Cache;
 
static Cache *cache_new(int sets, int ways, int offset_bits) {
    Cache *c = malloc(sizeof *c);
    c->sets = sets; c->ways = ways; c->offset_bits = offset_bits;
    c->block = malloc(sizeof(long) * (size_t)(sets * ways));
    c->used = calloc((size_t)(sets * ways), sizeof(long));
    for (int i = 0; i < sets * ways; i++) c->block[i] = -1;
    c->clock = c->hits = c->misses = 0;
    return c;
}
 
static void cache_free(Cache *c) { free(c->block); free(c->used); free(c); }
 
static int cache_access(Cache *c, long addr) {
    long block = addr >> c->offset_bits;
    int set = (int)(block % c->sets);
    long *b = c->block + set * c->ways, *u = c->used + set * c->ways;
    c->clock++;
    for (int w = 0; w < c->ways; w++)
        if (b[w] == block) { u[w] = c->clock; c->hits++; return 1; }
    int victim = 0;
    for (int w = 0; w < c->ways; w++) {
        if (b[w] < 0) { victim = w; break; }                    /* a free line is used first */
        if (u[w] < u[victim]) victim = w;                       /* otherwise the least recently used */
    }
    b[victim] = block; u[victim] = c->clock; c->misses++;
    return 0;
}
 
static void sequence(const char *name, int sets, int ways) {
    static const int seq[14] = { 0, 1, 2, 3, 4, 5, 32, 33, 0, 4, 36, 8, 9, 40 };
    Cache *c = cache_new(sets, ways, 2);
    char marks[15];
    for (int i = 0; i < 14; i++) marks[i] = cache_access(c, seq[i]) ? 'h' : 'M';
    marks[14] = 0;
    printf("%-28s %s  hits %ld, misses %ld\n", name, marks, c->hits, c->misses);
    cache_free(c);
}
 
static void matrix(const char *name, int ways, int column_major) {
    int n = 64;
    Cache *c = cache_new(1024 / 64 / ways, ways, 6);            /* 1 KB cache with 64-byte lines */
    for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++) {
            int i = column_major ? b : a, j = column_major ? a : b;
            cache_access(c, ((long)i * n + j) * 4);             /* element (i, j) of a 64 x 64 array of 4-byte ints */
        }
    printf("%-34s hits %ld of %ld (miss rate %.4f)\n", name, c->hits, c->hits + c->misses, (double)c->misses / (double)(c->hits + c->misses));
    cache_free(c);
}
 
int main(void) {
    sequence("direct mapped, 8 lines", 8, 1);
    sequence("2-way, 4 sets", 4, 2);
    sequence("fully associative, 8 lines", 1, 8);
    matrix("row by row, direct mapped", 1, 0);
    matrix("column by column, direct mapped", 1, 1);
    matrix("column by column, 4-way", 4, 1);
    return 0;
}

direct mapped, 8 lines       MhhhMhMhMhMMhM  hits 7, misses 7
2-way, 4 sets                MhhhMhMhhhMMhM  hits 8, misses 6
fully associative, 8 lines   MhhhMhMhhhMMhM  hits 8, misses 6
row by row, direct mapped          hits 3840 of 4096 (miss rate 0.0625)
column by column, direct mapped    hits 0 of 4096 (miss rate 1.0000)
column by column, 4-way            hits 0 of 4096 (miss rate 1.0000)

Reading it. Direct mapped: 7 hits, 7 misses; 2-way and fully associative: 8 hits, 6 misses (only the 6 compulsory misses remain). Row by row each 64-byte line holds 16 integers, so only 1 access in 16 misses: 3840 hits of 4096. Column by column consecutive accesses are 256 bytes apart, a different line each time; the 64 lines of a column do not fit in the 16 lines of the cache, so every access misses, even with 4 ways. Same data, same program size, different order: miss rate 6.25% against 100%.

EX 2Address fields

Easy

A cache of 16 KB, 64-byte blocks, 32-bit addresses. Direct mapped: 256 lines, offset 6, index 8, tag 18. 4-way: 64 sets, offset 6, index 6, tag 20. Fully associative: offset 6, index 0, tag 26. For the small cache of the animations (32 bytes, 4-byte blocks, 8-bit addresses): direct mapped 8 lines, offset 2, index 3, tag 3; 2-way: 4 sets, index 2, tag 4.

EX 3Where does an address go?

Medium

In the 32-byte direct-mapped cache, the address 36 is $00100100_2$ : offset $00$ , index $001$ , tag $001$ . Block number $9$ , set (line) $9 \bmod 8 = 1$ . The line holds block 1 (addresses 4 to 7) from earlier, with tag $000$ ; the tags differ, so it is a miss that replaces block 1. In the 2-way cache the same address has index $01$ (4 sets) and tag $0010$ ; set 1 holds block 1 in one way, so block 9 takes the other way and nothing is replaced.

EX 4Classify the misses

Medium

For the direct-mapped run: the misses on addresses 0, 4, 32, 36, 8 and 40 are the first accesses to blocks 0, 1, 8, 9, 2, 10: six compulsory misses. The access to 0 after 32 is a conflict miss: block 0 had been evicted by block 8 (same line) although the cache has free lines elsewhere. There are no capacity misses (only 6 distinct blocks are used and the cache has 8 lines). In the 2-way and fully associative caches there are only the 6 compulsory misses.

EX 5Size of a cache in bits

GATE level

A 4-way set-associative cache has 32 KB of data, 32-byte blocks, 32-bit addresses, with a valid bit and a dirty bit per line. Lines $= 32768 / 32 = 1024$ ; sets $= 1024 / 4 = 256$ ; offset 5, index 8, tag $32 - 8 - 5 = 19$ . Tag store: $1024 \times (19 + 2) = 21504$ bits. Data: $32768 \times 8 = 262144$ bits. Total $283648$ bits, about 8% more than the data alone. Comparators: 4 (one per way); the data multiplexer is 4-to-1.

EX 6Why the order of loops matters

GATE level

For a $64 \times 64$ array of ints stored row by row (row-major, as in C), element $(i, j)$ is at byte $4(64 i + j)$ . Looping with $j$ inside touches consecutive addresses (spatial locality). Looping with $i$ inside touches addresses 256 bytes apart, so the lines used by one column are $64$ different lines. When the array is small enough that all its lines fit and do not conflict (for example $16 \times 16$ ints in the same cache: 16 lines of 64 bytes, one row per line), both orders have the same miss rate (16 compulsory misses in 256 accesses, 6.25%); the penalty of the wrong order appears when the working set exceeds the cache.

Cheat box

Address = tag | index | offset. Offset bits $= \log_2 B$ ; index bits $= \log_2 (\text{sets})$ ; tag bits $= a - i - o$ .
Lines $= C / B$ ; sets $= \text{lines} / W$ . Direct mapped: sets = lines. Fully associative: 1 set, no index.
Block goes to set $\text{block} \bmod \text{sets}$ . Hit: valid and tag equal in some way of that set.
Doubling the ways: one index bit fewer, one tag bit more. Comparators $= W$ .
Tag store $=$ lines $\times$ (tag + valid [+ dirty]) bits.
Misses: compulsory (first use), capacity (cache too small), conflict (too many blocks in one set).
Spatial locality: consecutive addresses in the same block hit. Loop order can turn 6% misses into 100%.

Traps and GATE patterns

Connections

Builds on

Memory hierarchy and performance (AMAT)

Unlocks

Memory hierarchy and performance (AMAT)uses Cache replacement and write policiesPrerequisite of Cache replacement and write policiesuses Cache performance and multilevel cachesPrerequisite of Forwarding, stalls and branch predictionanalogous to Multilevel, inverted and hashed page tablesanalogous to Multidimensional arrays and address calculationanalogous to

Across subjects

Arrays and indexinguses Multidimensional arrays and address calculationuses

Within this subject

Cache replacement and write policiesuses Cache performance and multilevel cachesuses Memory hierarchy and performance (AMAT)uses

Journeys that pass through here

A C program, from source to exit · Cache

What the cache does when a set is full and when the processor writes is the topic of replacement and write policies; the cost of the misses is in cache performance. The loop-order effect is the hardware reason behind the row-major layout of multidimensional arrays and the access patterns of arrays. The cache itself is a level of the hierarchy.

PYQs

42 previous year questions from your book. I re-solved each one myself (37 by running or simulating, 5 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · MCQQ1 · page 495 of the book

The size of the physical address space of a
processor is 232 bytes. The capacity of a cache
memory unit is 223 bytes. The cache block size is
128 bytes. The cache memory unit can be built as
a direct mapped cache or as a K-way set-
associative cache, where K = 2L and L ∈ {1, 2, 3}.
Let the length of the TAG field be M bits for the
direct mapped cache, and N bits for the set-
associative cache.
Which one of the following options is true?

(a)N = M + L
(b)N = M - L
(c)N = M + K
(d)N = M – K

GATE 2026 · MSQQ2 · page 495 of the book

Consider a system with a processor and a 4 KB
direct mapped cache with block size of 16 bytes.
The system has a 16 MB physical memory. Four
words P, Q, R, and S are accessed by the
processor in the same order 10 times. That is,
there are a total of 40 memory references in the
sequence P, Q, R, S, P, Q, R, S,... Assume that the
cache memory is initially empty. The physical
addresses of the words are given below (1 word =
1 byte).
P: 0X845B32, Q: 0X845B26, R: 0X845B36,
S: 0X846B32
Which of the following statements is/are true?
Note: 1 K = 210 and 1M = 220

(a)Every access to P results in a cache miss
(b)Every access to R results in a cache hit
(c)Every access to Q results in a cache miss
(d)Except the first access to S, all subsequent accesses to S result in cache hits

GATE 2026 · NATQ3 · page 495 of the book

Consider a system with 1 MB physical memory and
a word length of 1 byte. The system uses a direct
mapped cache, with block numbers starting from 0.
The word with physical address 0XA2C28 is
mapped to the cache block number (176)10. The
maximum possible size of the cache (in KB) for this
configuration is
. (answer in integer)
Note: 1K = 210 and 1M = 220

GATE 2025 · MCQQ5 · page 495 of the book

For a direct-mapped cache, 4 bits are used for the tag
field and 12 bits are used to index into a cache block.
The size of each cache block is one byte. Assume that
there is no other information stored for each cache
block.
Which ONE of the following is the CORRECT option
for the sizes of the main memory and the cache
memory
in
this
system
(byte
addressable),
respectively?

(a)64 KB and 4 KB
(b)128 KB and 16 KB
(c)64 KB and 8 KB
(d)128 KB and 6 KB Computer Organization and Architecture

GATE 2025 · MCQQ7 · page 496 of the book

Consider a memory system with 1M bytes of main
memory and 16K bytes of cache memory. Assume
that the processor generates a 20-bit memory
address, and the cache block size is 16 bytes. If the
cache uses direct mapping, how many bits will be
required to store all the tag values? [Assume
memory is byte addressable, 1K = 210, 1M = 220.]

(a)6 × 210
(b)8 × 210
(c)212
(d)214

GATE 2023 · NAT · 2 marksQ10 · page 496 of the book

An 8-way set associative cache of size 64 KB (1 KB
= 1024 bytes) is used in a system with a 32-bit
address. The address is sub-divided into TAG,
INDEX, and BLOCK OFFSET.
The number of bits in the TAG is
.

GATE 2022 · MSQQ11 · page 496 of the book

Consider a system with a 2 KB direct-mapped data
cache with a block size of 64 bytes. The system has a
physical address space of 64 KB and a word length of
16 bits. During the execution of a program, four data
words P, Q, R, and S are accessed in that order 10
times (i.e., PQRS...). Hence, there are 40 accesses to
Computer Organization and Architecture

the data cache altogether. Assume that the data
cache is initially empty and no other data words are
accessed by the program. The addresses of the first
bytes of P, Q, R, and S are 0XA248, 0XC28A,
0XCA8A, and 0XA262, respectively. For the
execution of the above program, which of the
following statements is/are TRUE with respect to
the data cache?

(a)Every access to S is a hit.
(b)Once P is brought to the cache it is never evicted.
(c)At the end of the execution-only R and S reside in the cache.
(d)Every access to R evicts Q from the cache.

GATE 2021 · NATQ15 · page 497 of the book

Consider a set-associative cache of size 2KB
(1KB=210 bytes) with cache block size of 64 bytes.
Assume that the cache is byte-addressable and a 32 -
bit address is used for accessing the cache. If the
width of the tag field is 22 bits, the associativity of
the cache is
.

GATE 2021 · NATQ16 · page 497 of the book

Consider a computer system with a byte-addressable
primary memory of size 232 bytes. Assume the
computer system has a direct-mapped cache of size
32 KB (1 KB = 210 bytes), and each cache block is of
size 64 bytes.
The size of the tag field is
bits.

GATE 2020 · MCQ · 2 marksQ17 · page 497 of the book

A computer system with a word length of 32 bits has
a 16 MB byte- addressable main memory and a 64
KB, 4-way set associative cache memory with a
block size of 256 bytes. Consider the following four
physical addresses represented in hexadecimal
notation.
A1=0x42C8A4,
A2=0x546888,
A3=0x6A289C,
A4=0x5E4880
Which one of the following is TRUE?
Computer Organization and Architecture

(a)A1 and A4 are mapped to different cache sets
(b)A2 and A3 are mapped to the same cache set.
(c)A3 and A4 are mapped to the same cache set.
(d)A1 and A3 are mapped to the same cache set.

GATE 2019 · MCQ · 1 markQ20 · page 498 of the book

A certain processor uses a fully associative cache
of size 16 kB. The cache block size is 16 bytes.
Assume that the main memory is byte addressable
and uses a 32-bit address. How many bits are
required for the Tag and the Index fields
respectively in the addresses generated by the
processor?

(a)24 bits and 0 bits
(b)28 bits and 4 bits
(c)24 bits and 4 bits
(d)28 bits and 0 bits

GATE 2018 · MCQ · 2 marksQ21 · page 498 of the book

The size of the physical address space of a processor
is 2P bytes. The word length is 2W bytes. The
capacity of cache memory is 2N bytes. The size of
each cache block is 2M words. For a K-way set-
associative cache memory, the length (in number of
bits) of the tag field is

(a)P - N - log2K
(b)P - N + log2K
(c)P - N - M - W - log2K
(d)P - N - M - W + log2K

GATE 2017 · NATQ22 · page 498 of the book

Consider a machine with a byte addressable main
memory of 232 bytes divided into blocks of size 32
bytes. Assume that a direct mapped cache having
512 cache lines is used with this machine. The size
of the tag field in bits is
.

GATE 2017 · NATQ25 · page 499 of the book

A cache memory unit with capacity of N words
and block size of B words is to be designed. If it is
designed as a direct mapped cache, the length of
the TAG field is 10 bits. If the cache unit is now
designed as a 16-way set-associative cache, the
length of the TAG field is
bits.

GATE 2017 · NATQ26 · page 499 of the book

Consider a 2-way set associative cache with 256
blocks and use LRU replacement, initially the
cache is empty. Conflict misses are those misses
which occur due to the contention of multiple
blocks for the same cache set. Compulsory misses
occur due to first time access to the block. The
following sequence of accesses to memory blocks.

{0,128,256,128,0,128,256,128,1,129,257,129,1,12
9,257,129}

is repeated 10 times. The number of conflict
misses experienced by the cache is
.

GATE 2016 · NATQ29 · page 499 of the book

The width of the physical address on a machine is 40
bits. The width of the tag field in a 512KB 8-way set
associative cache is
bits.

GATE 2015 · MCQQ30 · page 499 of the book

Consider a machine with a byte addressable main
memory of 220 bytes, block size of 16 bytes and a
direct mapped cache having 212 cache lines. Let the
addresses of two consecutive bytes in main memory
be (E201F)16 and (E2020)16. What are the tag and
Computer Organization and Architecture

cache line address (in hex) for main memory
address (E201F)16?

(a)E, 201
(b)F, 201
(c)E, E20
(d)2, 01F

GATE 2014 · MCQQ33 · page 500 of the book

If the associativity of a processor cache is doubled
while keeping the capacity and block size
unchanged, which one of the following is
guaranteed to be NOT affected?

(a)Width of tag comparator
(b)Width of set index decoder
(c)Width of way selection multiplexor
(d)Width of processor to main memory data bus

GATE 2014 · MCQQ34 · page 500 of the book

In designing a computer's cache system, the cache
block (or cache line) size is an important parameter.
Which one of the following statements is correct in
this context?

(a)A smaller block size implies better spatial locality
(b)A smaller block size implies a smaller cache tag and hence lower cache tag overhead
(c)A smaller block size implies a larger cache tag and hence lower cache hit time
(d)A smaller block size incurs a lower cache miss penalty

GATE 2014 · NATQ35 · page 500 of the book

A 4-way set-associative cache memory unit with a
capacity of 16 KB is built using a block size of 8
words. The word length is 32 bits. The size of the
physical address space is 4 GB. The number of bits
for the TAG field is
.

GATE 2014 · MCQQ37 · page 500 of the book

An access sequence of cache block addresses is of
length N and contains n unique block addresses. The
number of unique block addresses between two
consecutive accesses to the same block address is
bounded above K. What is the miss ratio if the
access sequence is passed through a cache of
associativity A≥k exercising least-recently-used
Computer Organization and Architecture

replacement policy?
The number of bits in the tag field of an address is

(a)n/N
(a)11
(b)1/N
(b)14
(c)1/A
(c)16
(d)k/n
(d)27

GATE 2013 · MCQ · 1 markQ38 · page 501 of the book

In a k-way set associative cache, the cache is
divided into v sets, each of which consists of k
lines. The lines of a set are placed in sequence one
after another. The lines in set s are sequenced
before the lines in set (s+1). The main memory
blocks are numbered 0 onwards. The main
memory block numbered j must be mapped to any
one of the cache lines from

(a)(j mod v) *k to (j mod v) *k + (k-1)
(b)(j mod v) to (j mod v) +(k-1)
(c)(j mod k) to (j mod k) +(v-1)
(d)(j mod k) *v to (j mod k) *v + (v-1)

GATE 2012 · MCQ · 2 marksQ39 · page 501 of the book

A computer has a 256 -KByte, 4 -way set
associative, write back data cache with block size
of 32 Bytes. The processor sends 32 bit addresses
to the cache controller. Each cache tag directory
entry contains, in addition to address tag, 2 valid
bits, 1 modified bit and 1 replacement bit.
The size of the cache tag directory is:

(a)160 Kbits
(b)136 Kbits
(c)40 Kbits
(d)32 Kbits

GATE 2012 · MCQ · 2 marksQ40 · page 501 of the book

A computer has a 256-KByte, 4-way set
associative, write back data cache with block size
of 32-Bytes. The processor sends 32-bit addresses
to the cache controller. Each cache tag directory
entry contains, in addition to address tag, 2 valid
bits, 1 modified bit and 1 replacement bit.

GATE 2011 · MCQ · 2 marksQ41 · page 501 of the book

An 8KB direct mapped write-back cache is organized
as multiple blocks, each of size 32-bytes. The
processor generates 32-bit addresses. The cache
controller maintains the tag information for each
cache block consisting of the following.
1 Valid bit, 1 Modified bit as many bits as the
minimum needed to identify the memory block
mapped in the cache.
What is the total size of memory needed at the cache
controller to store metadata (tags) for the cache?

(a)4864 bits
(b)6144 bits
(c)6656 bits
(d)5376 bits

GATE 2009 · MCQ · 2 marksQ44 · page 502 of the book

Consider a 4-way set associative cache (initially
empty) with total 16 cache blocks. The main
memory consists of 256 blocks and the request
for memory blocks are in the following order:
0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155.
Which one of the following memory block will
NOT be in cache if LRU replacement policy is
used?

(a)3
(b)8
(c)129
(d)216

GATE 2008 · MCQ · 2 marksQ45 · page 502 of the book

For inclusion to hold between two cache levels L1
and L2 in a multilevel cache hierarchy, which of
the following are necessary?
1. L1 must be a write-through cache
2. L2 must be a write-through cache
3. The associativity of L2 must be greater than that
of L1
4. The L2 cache must be at least as large as the L1
cache

(a)4 only
(b)1 and 2 only
(c)1, 2 and 4 only
(d)1, 2, 3 and 4

GATE 2008 · MCQ · 2 marksQ46 · page 502 of the book

Consider a machine with a 2 -way set associative data
cache of size 64 Kbytes and block size 16 bytes. The
cache is managed using 32 bit virtual addresses and
the page size is 4 Kbytes . A program to be run on
this machine begins as follows:

double ARR[1024][1024];
int i, j;

for(i = 0; i < 1024; i++)
for(j= 0; j < 1024; j++)
ARR[i][j] = 0.0;

The size of double is 8Bytes. Array ARR is located
in memory starting at the beginning of virtual page
0 xFF000 and stored in row major order. The
cache is initially empty and no pre-fetching is
done. The only data memory references made by
the program are those to array ARR.
The total size of the tags in the cache directory is:

(a)32 Kbits
(b)34 Kbits
(c)64 Kbits
(d)68 Kbits Computer Organization and Architecture

GATE 2008 · MCQ · 2 marksQ47 · page 503 of the book

Consider a machine with a 2 -way set associative
data cache of size 64 Kbytes and block size 16
bytes. The cache is managed using 32 bit virtual
addresses and the page size is 4 Kbytes . A
program to be run on this machine begins as
follows:
double ARR[1024][1024];
int i, j;

for(i = 0; i < 1024; i++)
for(j= 0; j < 1024; j++)
ARR[i][j] = 0.0;

The size of double is 8Bytes. Array ARR is
located in memory starting at the beginning of
virtual page 0 xFF000 and stored in row major
order. The cache is initially empty and no pre-
fetching is done. The only data memory
references made by the program are those to
array ARR.
Which of the following array elements have the
same cache index as ARR[0][0] ?

(a)ARR[0][4]
(b)ARR[4][0]
(c)ARR[0][5]
(d)ARR[5][0]

GATE 2008 · MCQQ48 · page 503 of the book

Consider a machine with a 2 -way set associative
data cache of size 64 Kbytes and block size 16
bytes. The cache is managed using 32 bit virtual
addresses and the page size is 4 Kbytes . A
program to be run on this machine begins as
follows:
double ARR[1024][1024];
int i, j;
for(i = 0; i < 1024; i++)
for( = 0; j < 1024; j++)

The size of double is 8 bytes. Array ARR is
located in memory starting at the beginning of
virtual page 0 xFF000 and stored in row major
order. The cache is initially empty and no pre-
fetching is done. The only data memory references
made by the program are those to array ARR.
The cache hit ratio for this initialization loop is:

(a)0%
(b)25%
(c)50%
(d)75%

GATE 2008 · MCQ · 2 marksQ49 · page 503 of the book

Consider a computer with a 4-ways set-associative
mapped cache of the following characteristics: a
total of 1 MB of main memory, a word size of 1
byte, a block size of 128 words and a cache size of 8
KB.
The number of bits in the TAG, SET and WORD
fields, respectively are:

(a)7, 6, 7
(b)8, 5, 7
(c)8, 6, 6
(d)9, 4, 7

GATE 2008 · MCQ · 2 marksQ50 · page 503 of the book

Consider a computer with a 4-ways set-associative
mapped cache of the following characteristics: a
total of 1 MB of main memory, a word size of 1
byte, a block size of 128 words and a cache size of 8
KB. While accessing the memory location 0C795H
by the CPU, the contents of the TAG field of the
corresponding cache line is:

(a)000011000
(b)110001111
(c)00011000
(d)110010101 ARR[i][j] = 0.0; Computer Organization and Architecture

GATE 2007 · MCQ · 2 marksQ51 · page 504 of the book

Consider a machine with a byte addressable main
memory of 216 bytes. Assume that a direct
mapped data cache consisting of 32 lines of 64
bytes each is used in the system. A 50 × 50 two-
dimensional array of bytes is stored in the main
memory starting from memory location 1100 H .
Assume that the data cache is initially empty. The
complete array is accessed twice. Assume that the
contents of the data cache do not change in
between the two accesses.
Which of the following lines of the data cache will
be replaced by new blocks in accessing the array
for the second time?

(a)line 4 to line 11
(b)line 4 to line 12
(c)line 0 to line 7
(d)line 0 to line 8

GATE 2007 · MCQQ52 · page 504 of the book

Consider a 4-way set associative cache consisting
of 128 lines with a line size of 64 words. The CPU
generates a 20-bit address of a word in main
memory. The numbers of bits in the TAG, SET,
and WORD fields are respectively:

(a)9, 6, 5
(b)7, 7, 6
(c)7, 5, 8
(d)9, 5, 6

GATE 2007 · MCQ · 2 marksQ53 · page 504 of the book

Consider a machine with a byte addressable main
memory of 216 bytes. Assume that a direct mapped
data cache consisting of 32 lines of 64 bytes each
is used in the system. A 50 × 50 two-dimensional
array of 1 byte is stored in the main memory
starting from memory location 1100H. The data
cache is initially empty.
The complete array is accessed twice. Assume that
the contents of the data cache do not change in
between the two accesses.
How many data cache misses will occur in total?

(a)48
(b)50
(c)56
(d)59

GATE 2006 · MCQ · 2 marksQ54 · page 504 of the book

A CPU has a cache with block size 64 bytes. The
main memory has k banks, each bank being c bytes
wide. Consecutive c-byte chunks are mapped on
consecutive banks, with wrap-around All the k
banks can be accessed in parallel, but two accesses
to the same bank must be serialized. A cache block
access may involve multiple iterations of parallel
bank accesses depending on the amount of data
obtained by accessing all the k banks in parallel.
Each iteration requires decoding the bank numbers
to be accessed in parallel and this takes k/2 ns. The
latency of one bank access is 80 ns.
If c = 2 and k = 24, then the latency of retrieving a
cache block starting at address zero from main
memory is:

(a)92 ns
(b)104 ns
(c)172 ns
(d)184 ns

GATE 2006 · MCQQ57 · page 505 of the book

A CPU has a 32KB direct mapped cache with
128 byte-block size.Suppose A is two
dimensional array of size 512 × 512 with
elements that occupy 8 -bytes each.Consider
the following two C code segments, P1 and P2
.
P1:
for(i=0; i<512 ; i++)

{
for (j=0;j<512; j++)
}
x +=A[i][j]
}

P2:

for(i=0; i<512 ; i++)

{

for ( j=0:j<512:j++ )
{
x +=A[j][i]
1
P1 and P2 are executed independently with the
same initial state,namely,the array A is not in
the cache and i, j , x are in registers.Let the
number of cache misses experienced by P1 be M1
and that for P2 be M2 .
The value of the ratio M1 :
M2

(a)0
(b)1 16
(c)1 8
(d)16

GATE 2006 · MCQQ58 · page 505 of the book

A CPU has a 32KB direct mapped cache with 128
byte-block size.Suppose A is two dimensional
array of size 512 × 512 with elements that occupy
8 -bytes each.Consider the following two C
code segments, P1 and P2 .
P1:
for(i=0; i<512 ; i++)

{
for (j=0;j<512; j++)
}
x +=A[i][j]
}
P2:
for(i=0; i<512 ; i++)

{

for ( j=0:j<512:j++ )
{
x +=A[j][i]
1
Computer Organization and Architecture

P1 and P2 are executed independently with the
same initial state,namely,the array A is not in
the cache and i, j , x are in registers.Let the
number of cache misses experienced by P1 be
M1 and that for P2 be M2 .
The value of M1:

(a)0
(b)2048
(c)16384
(d)262144

GATE 2005 · MCQQ59 · page 506 of the book

Consider a direct mapped cache of size 32 KB
with block size 32 bytes. The CPU generates 32-
bit addresses. The number of bits needed for cache
indexing and the number of tag bits are
respectively:

(a)10, 17
(b)10, 22
(c)15, 17
(d)5, 17

GATE 2005 · MCQ · 2 marksQ60 · page 506 of the book

Consider a 2-way set associative cache memory
with 4 sets and total 8 cache blocks (0–7) and
main memory with 128 blocks (0–127). Which
memory blocks will be present in the cache after
the following sequence of memory block
references if LRU policy is used for cache block
replacement? If initially the cache did not have
any memory block from the current job?

0 5 3 9 7 0 16 55

(a)0 3 5 7 16 55
(b)0 3 5 7 9 16 55
(c)0 5 7 9 16 55
(d)3 5 7 9 16 55

GATE 2005 · MCQQ61 · page 506 of the book

A computer system has a level-1 instruction cache
(I-cache), a level-1 data cache (D-cache) and a level-
2 cache (L2-cache) with the following
specifications:

Cache
Capacity
Mapping
method
Block
size
I-cache
4K words
Direct mapping
4 Words
D-cache
4K words
2-way set-
associative
mapping
4 Words
L2-cache
64K
words
4-way set-
associative
mapping
16 Words

Capacity Mapping method Block size I-cache 4K
words Direct mapping 4 Words D-cache 4K words
2-way set-associative mapping 4 Words L2-cache
64K words 4-way set-associative mapping 16 Words

The length of the physical address of a word in the
main memory is 30 bits. The capacity of the tag
memory in the I-cache, D-cache and L2-cache is,
respectively,

(a)1K × 18-bit, 1K × 19-bit, 4K × 16-bit
(b)1K × 16-bit, 1K × 19-bit, 4K × 18-bit
(c)1K × 16-bit, 512 × 18-bit, 1K × 16-bit
(d)1K × 18-bit, 512 × 18-bit, 1K × 18-bit Computer Organization and Architecture

year not read yetQ36 · page 345 of the book

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 minimum number of page colors needed
to guarantee that no two synonyms map to different
sets in the processor cache of this computer?

(a)2
(b)4
(c)8
(d)16

Self-check

Question 1

A 64 KB 2-way set-associative cache with 32-byte blocks and 32-bit addresses. How many sets, and how many tag bits?

Show answer

Lines $= 65536/32 = 2048$ ; sets $= 2048/2 = 1024$ ; offset 5, index 10, tag $32 - 10 - 5 = 17$ bits.

Question 2

In a direct-mapped cache with 16 lines of 8 bytes, which line does byte address 200 use?

Show answer

Block $= \lfloor 200/8 \rfloor = 25$ ; line $= 25 \bmod 16 = 9$ .

Question 3

Which kind of miss is removed by making a cache fully associative while keeping its size?

Show answer

Conflict misses (compulsory and capacity misses remain).

Question 4

How many comparators does a 8-way set-associative cache need?

Show answer

8, one for each way of the selected set.

Revision card

One-screen revision

tag | index | offset: offset $\log_2 B$ , index $\log_2 (\text{sets})$ , tag the rest.
Direct: 1 way. $W$ -way: sets = lines / $W$ . Fully: 1 set.
Hit: valid and tag match in the set. $W$ comparators.
Tag store = lines $\times$ (tag + 1 [+ 1]). Misses: compulsory, capacity, conflict.
Same size, more ways: fewer index bits, more tag bits.

References

·Hennessy and Patterson, Computer Organization and Design, Chapter 5 Large and Fast (the basics of caches, measuring and improving cache performance)
·Hamacher, Vranesic, Zaky, Computer Organization, 5th ed., Chapter 8 The Memory System (cache memories, mapping functions)
·Morris Mano, Computer System Architecture, 3rd ed., Chapter 12 Memory Organization (cache memory: associative, direct and set-associative mapping)

Verification

Every animation is an exact simulation of the cache re-run by an independent implementation in tests/coa-mem-traces.test.ts (hits, misses, memory traffic and the contents of every line after every access, plus the address fields and cycle counts). The field-size formulas and tag-store sizes are recomputed in scripts/enum-checks/coa_mem.py; the matrix-traversal miss counts (3840 of 4096 hits row by row, 0 column by column) are produced by that script and by the C simulator on the page (npm run verify:c). The 3C classification uses a fully associative LRU cache of the same size as the reference (the usual definition). Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Memory interfacing and address decoding

Cache replacement and write policies