Self-checkedTier 1 12 min readcoa.cache-performance

Cache performance and multilevel caches

What a cache costs in time: average memory access time, memory stall cycles and CPI, local and global miss rates, two-level caches, split caches, the effect of block size and associativity, and how to improve a cache.

Why it exists

A cache that misses rarely makes memory look fast; one that misses often makes the processor wait. How much it waits is a calculation: how many accesses, how many of them miss, and what each miss costs. The same calculation answers design questions: is a bigger block worth its longer fill time, does the second cache level pay for itself, what does a faster core gain when memory is unchanged? GATE asks for the average access time, the CPI including memory stalls, the effect of a second level, and the comparison of two designs.

Prerequisites

Cache memory mapping

You need the cache organisation of cache mapping and the formula for average access time from the memory hierarchy.

Precise definitions

Average memory access time.

$\text{AMAT} = \text{hit time} + \text{miss rate} \times \text{miss penalty}.$

Memory stall cycles and CPU time.

$\text{stall cycles per instruction} = \frac{\text{memory accesses}}{\text{instruction}} \times \text{miss rate} \times \text{miss penalty},$

$\text{CPI} = \text{CPI}_{\text{base}} + \text{stall cycles per instruction},\qquad \text{CPU time} = \text{IC} \times \text{CPI} \times \text{clock period}.$

Every instruction makes at least one memory access (its fetch); loads and stores add data accesses, so "accesses per instruction" is typically 1.2 to 1.5.

Two-level cache with local miss rates.

$\text{AMAT} = t_{L1} + m_1\,(t_{L2} + m_2\, t_{\text{mem}}).$

$m_1$ and $m_2$ are local miss rates (misses of the level divided by the accesses that reach it). The global miss rate of L2 is $m_1 m_2$ (its misses per CPU access). The L2 is usually bigger, slower and has a high local miss rate (many of the accesses that reach it are the hard ones), so its local rate is a poor measure of its quality; the global rate is the useful one.

Split caches. Separate instruction and data caches (Harvard style) let an instruction fetch and a data access happen at the same time. The overall miss rate is the weighted average: with 75% instruction fetches missing at 2% and 25% data accesses missing at 6%, the combined rate is $0.75 \times 0.02 + 0.25 \times 0.06 = 3\%$ .

Block size. Larger blocks exploit spatial locality (fewer misses for sequential access: with one word per cycle after an 8-cycle start-up the sequential miss rate is $4/B$ for 4-byte words) but raise the miss penalty (more words to fetch) and, for a fixed cache size, mean fewer blocks (more conflicts). The best block size minimises AMAT and is neither the smallest nor the largest.

Associativity. Higher associativity removes conflict misses but lengthens the hit time (more comparators and a wider multiplexer) and costs more hardware. It pays only if the saved miss time exceeds the added hit time.

Ways to improve a cache. Reduce the miss rate (larger cache, larger blocks to a point, higher associativity, prefetching, compiler loop reordering), reduce the miss penalty (a second-level cache, critical-word-first, read priority over writes, write buffers) or reduce the hit time (small and simple first-level cache, avoiding address translation on the hit path).

The 3C model (compulsory, capacity, conflict misses) tells which remedy fits: bigger blocks for compulsory, bigger cache for capacity, more associativity for conflict.

How it works

Back to the 14-read sequence on the direct-mapped cache: the animation keeps the running totals. With a hit time of 1 and a miss penalty of 10 cycles it has taken 84 cycles for 14 accesses, an average of 6, which is $1 + 0.5 \times 10$ . The 2-way version has 6 misses instead of 7, so $14 + 6 \times 10 = 74$ cycles, an average of 5.29 cycles, if the 2-way hit time is the same; with a longer hit time the advantage can disappear.

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

The C program evaluates the formulas of this page.

#include <stdio.h>
 
static double amat(double hit, double miss_rate, double penalty) { return hit + miss_rate * penalty; }
 
int main(void) {
    /* one level */
    printf("one cache: AMAT = 1.0 + 0.05 x 20 = %.2f cycles\n", amat(1, 0.05, 20));
    /* two levels with local miss rates: L1 hit 1, local miss 5%; L2 hit 10, local miss 20%; memory 100 */
    double h1 = 1, m1 = 0.05, h2 = 10, m2 = 0.20, mem = 100;
    double penalty1 = h2 + m2 * mem;
    printf("two levels: L1 miss penalty = %.0f + %.2f x %.0f = %.0f cycles, AMAT = %.2f cycles\n", h2, m2, mem, penalty1, amat(h1, m1, penalty1));
    printf("global miss rate of L2 = %.2f x %.2f = %.3f (local miss rate %.2f)\n", m1, m2, m1 * m2, m2);
    /* CPI with memory stalls */
    double base = 1.5, refs = 1.3, miss = 0.04, penalty = 50;
    double stalls = refs * miss * penalty;
    printf("stall cycles per instruction = %.1f x %.2f x %.0f = %.2f; CPI = %.2f; %.2f times slower than with a perfect cache\n", refs, miss, penalty, stalls, base + stalls, (base + stalls) / base);
    /* a faster core does not speed up memory */
    printf("core CPI %.1f -> 1.0 with the same memory stalls: CPI %.2f -> %.2f, speed-up only %.2f (not %.2f)\n", base, base + stalls, 1.0 + stalls, (base + stalls) / (1.0 + stalls), base / 1.0);
    /* split instruction and data caches */
    printf("overall miss rate of split caches (75%% of accesses at 2%%, 25%% at 6%%) = %.3f\n", 0.75 * 0.02 + 0.25 * 0.06);
    /* block size: sequential access of 4-byte words; one miss per block; penalty = 8 cycles + one cycle per word of the block */
    for (int block = 4; block <= 64; block *= 4)
        printf("block %2d bytes: miss rate %.4f, penalty %2d cycles, AMAT = %.2f\n", block, 4.0 / block, 8 + block / 4, amat(1, 4.0 / block, 8 + block / 4));
    /* is higher associativity worth it? */
    printf("direct mapped (hit 1.00, miss 5%%): AMAT %.2f; 2-way (hit 1.10, miss 4%%): AMAT %.2f cycles; penalty 50\n", amat(1.0, 0.05, 50), amat(1.1, 0.04, 50));
    /* adding an L2 */
    double without = amat(1, 0.05, 100), with = amat(1, 0.05, 10 + 0.20 * 100);
    printf("without L2: AMAT %.2f, with L2: AMAT %.2f, speed-up %.2f\n", without, with, without / with);
    return 0;
}

one cache: AMAT = 1.0 + 0.05 x 20 = 2.00 cycles
two levels: L1 miss penalty = 10 + 0.20 x 100 = 30 cycles, AMAT = 2.50 cycles
global miss rate of L2 = 0.05 x 0.20 = 0.010 (local miss rate 0.20)
stall cycles per instruction = 1.3 x 0.04 x 50 = 2.60; CPI = 4.10; 2.73 times slower than with a perfect cache
core CPI 1.5 -> 1.0 with the same memory stalls: CPI 4.10 -> 3.60, speed-up only 1.14 (not 1.50)
overall miss rate of split caches (75% of accesses at 2%, 25% at 6%) = 0.030
block  4 bytes: miss rate 1.0000, penalty  9 cycles, AMAT = 10.00
block 16 bytes: miss rate 0.2500, penalty 12 cycles, AMAT = 4.00
block 64 bytes: miss rate 0.0625, penalty 24 cycles, AMAT = 2.50
direct mapped (hit 1.00, miss 5%): AMAT 3.50; 2-way (hit 1.10, miss 4%): AMAT 3.10 cycles; penalty 50
without L2: AMAT 6.00, with L2: AMAT 2.50, speed-up 2.40

Worked examples

EX 1One cache

Easy

Hit time 1 cycle, miss rate 5%, miss penalty 20 cycles: $\text{AMAT} = 1 + 0.05 \times 20 = 2$ cycles. A reduction of the miss rate to 4% gives $1.8$ , a reduction of the miss penalty to 15 gives $1.75$ . Both the miss rate and the penalty matter; they multiply.

EX 2CPI with stalls

Easy

Base CPI 1.5 (all accesses hit), 1.3 memory accesses per instruction, miss rate 4%, miss penalty 50 cycles. Stall cycles per instruction $= 1.3 \times 0.04 \times 50 = 2.6$ , so CPI $= 1.5 + 2.6 = 4.1$ : the processor spends 63% of its time waiting for memory, and is $4.1/1.5 = 2.73$ times slower than with a perfect cache.

EX 3A faster core does not help much

Medium

The core is improved so that the base CPI drops from 1.5 to 1.0, with the same cache and memory. The new CPI is $1.0 + 2.6 = 3.6$ and the speed-up is $4.1 / 3.6 = 1.14$ , not $1.5/1.0 = 1.5$ . The stall cycles do not shrink, so they take a larger share of the time. This is Amdahl's law applied to memory (performance).

EX 4Adding a second level

Medium

L1: hit 1 cycle, local miss rate 5%. Memory: 100 cycles. Without L2: $\text{AMAT} = 1 + 0.05 \times 100 = 6$ cycles. With an L2 of hit time 10 and local miss rate 20%: the L1 miss penalty becomes $10 + 0.20 \times 100 = 30$ cycles and $\text{AMAT} = 1 + 0.05 \times 30 = 2.5$ cycles: a speed-up of $6/2.5 = 2.4$ . The global miss rate of the L2 is $0.05 \times 0.20 = 1\%$ although its local miss rate is 20%.

EX 5Block size trade-off

Medium

Sequential access of 4-byte words, miss penalty = 8 cycles + 1 cycle per word of the block, hit time 1 cycle (a stated model). Block 4 bytes: miss rate 100%, penalty 9, AMAT 10.00. Block 16 bytes: miss rate 25%, penalty 12, AMAT 4.00. Block 64 bytes: miss rate 6.25%, penalty 24, AMAT 2.50. For this purely sequential pattern bigger is better; for a program with little spatial locality the penalty growth would dominate and the best block would be smaller.

EX 6Is 2-way associativity worth it?

GATE level

Direct mapped: hit time 1.00 cycle, miss rate 5%. 2-way: hit time 1.10 cycles (10% longer), miss rate 4%. Miss penalty 50 cycles. $\text{AMAT}_{\text{direct}} = 1 + 0.05 \times 50 = 3.5$ ; $\text{AMAT}_{\text{2-way}} = 1.1 + 0.04 \times 50 = 3.1$ . The 2-way cache wins here. If the 2-way hit time were 30% longer (1.30) its AMAT would be 3.30, still below 3.5. At a small miss penalty of 10 cycles the comparison reverses: direct mapped $1 + 0.05 \times 10 = 1.5$ against 2-way $1.1 + 0.04 \times 10 = 1.5$ , a tie, and for smaller penalties the direct-mapped cache wins.

Cheat box

AMAT = hit time + miss rate $\times$ miss penalty. Two levels: $t_{L1} + m_1(t_{L2} + m_2 t_{mem})$ with local rates.
Global L2 miss rate $= m_1 m_2$ .
Stall cycles per instruction = accesses per instruction $\times$ miss rate $\times$ penalty. CPI = base + stalls. CPU time = IC $\times$ CPI $\times$ period.
Split cache overall miss rate = weighted average by access fractions.
Larger block: fewer compulsory misses, higher penalty, more conflicts. More ways: fewer conflict misses, longer hit time.
Faster core with unchanged memory: speed-up is limited by the stall cycles.

Traps and GATE patterns

Connections

Builds on

Cache memory mapping

Unlocks

Memory hierarchy and performance (AMAT)uses Cache memory mappinguses Cache replacement and write policiesuses Pipeline speedup and CPI calculationsanalogous to Performance: CPI, MIPS and Amdahl's lawuses TLB and effective access timeanalogous to

Across subjects

No cross-subject links yet.

Within this subject

Performance: CPI, MIPS and Amdahl's lawuses Pipeline speedup and CPI calculationsuses Memory hierarchy and performance (AMAT)uses Cache replacement and write policiesuses

The cache organisation that fixes the miss rates is in cache mapping and replacement and write policies. The formulas for CPI and speed-up are the same as in pipeline speed-up and CPI calculations and Amdahl's law: memory stalls are one more term in the CPI. The averages come from the memory hierarchy.

PYQs

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

GATE 2025 · NATQ4 · page 495 of the book

Given a computing system with two levels of cache
(L1 and L2) and a main memory. The first level (L1)
cache access time is 1 nanosecond (ns) and the "hit
rate" for L1 cache is 90% while the processor is
accessing the data from L1 cache. Whereas, for the
second level (L2) cache, the "hit rate" is 80% and the
"miss penalty" for transferring data from L2 cache to
L1 cache is 10 ns. The "miss penalty" for the data to
be transferred from main memory to L2 cache is 100
ns.
Then the average memory access time in this system
in nanoseconds is
. (rounded off to one
decimal place)

GATE 2025 · NATQ6 · page 496 of the book

A computer has a memory hierarchy consisting of
two-level cache (L1 and L2) and a main memory.
If the processor needs to access data from memory,
it first looks into L1 cache. If the data is not found
in L1 cache, it goes to L2 cache. If it fails to get the
data from L2 cache, it goes to main memory, where
the data is definitely available. Hit rates and access
times of various memory units are shown in the
figure. The average memory access time in
nanoseconds (ns) is
. (rounded off to two
decimal places)

GATE 2024 · NATQ8 · page 496 of the book

A given program has 25% load/store instructions.
Suppose the ideal CPI (cycles per instruction)
without any memory stalls is 2. The program
exhibits 2% miss rate on instruction cache and 8%
miss rate on data cache. The miss penalty is 100
cycles. The speedup (rounded off to two decimal
places) achieved with a perfect cache (i.e., with NO
data or instruction cache misses) is

GATE 2022 · NAT · 1 markQ12 · page 497 of the book

A cache memory that has a hit rate of 0.8 has an
access latency 10 ns and miss penalty 100 ns.
Optimization is done on the cache to reduce the
miss rate. However, the optimization results in an
increase of cache access latency to 15 ns, whereas
the miss penalty is not affected The minimum hit
rate (rounded off to two decimal places) needed
after the optimization such that it should not
increase the average memory access time
is
.

GATE 2020 · NATQ18 · page 498 of the book

A direct mapped cache memory of 1 MB has a
block size of 256 bytes. The cache has an access
time of 3 ns and a hit rate of 94%. During a cache
miss, it takes 20 ns to bring the first word of a
block from the main memory, while each
subsequent word takes 5 ns. The word size is 64
bits. The average memory access time in ns (round
off to 1 decimal place) is
.

GATE 2019 · NAT · 2 marksQ19 · page 498 of the book

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 2017 · NATQ23 · page 498 of the book

The read access times and the hit ratios for different
caches in a memory hierarchy are as given below.
Cache
Read access
time (in
nanoseconds)
Ht ratio
I-cache
2
0.8
D-cache
2
0.9
L2-cache
8
0.9
The read access time of main memory is 90
nanoseconds. Assume that the caches use the
referred word-first read policy and the write back
policy. Assume that all the caches are direct mapped
caches. Assume that the dirty bit is always 0 for all
the blocks in the caches. In execution of a program,
60% of memory reads are for instruction fetch and
40% are for memory operand fetch. The average
read access time in nanoseconds (up to 2 decimal
places) is
.
Computer Organization and Architecture

GATE 2017 · MCQQ24 · page 499 of the book

In a two-level cache system, the access times of L1
and L2 1 and 8 clock cycles, respectively. The
miss penalty from the L2 cache to main memory is
18 clock cycles. The miss rate of L1 cache is twice
that of L2. The average memory access
time(AMAT) of this cache system is 2 cycles. The
miss rates of L1 and L2 respectively are:

(a)0.111 and 0.056
(b)0.056 and 0.111
(c)0.0892 and 0.1784
(d)0.1784 and 0.0892

GATE 2017 · NATQ27 · page 499 of the book

Consider a two-level cache hierarchy with L1 and
L2 caches. An application incurs 1.4 memory
accesses per instruction on average. For this
application, the miss rate of L1 cache 0.1, the L2
cache experiences, on average, 7 misses per 1000
instructions. The miss rate of L2 expressed correct to
two decimal places is
.

GATE 2016 · NATQ28 · page 499 of the book

A file system uses an in-memory cache to cache disk
blocks. The miss rate of the cache is shown in the
figure. The latency to read a block from the cache is
1 ms and to read a block from the disk is 10 ms.
Assume that the cost of checking whether a block
exists in the cache is negligible. Available cache
sizes are in multiples of 10 MB.

The smallest cache size required to ensure an
average read latency of less than 6 ms is

MB.

GATE 2015 · NATQ31 · page 500 of the book

Assume that for a certain processor, a read request
takes 50 nanoseconds on a cache miss and 5
nanoseconds on a cache hit. Suppose while
running a program, it was observed that 80% of
the processor's read requests result in a cache hit.
The average read access time in nanoseconds is

.

GATE 2014 · NATQ32 · page 500 of the book

The memory access time is 1 nanosecond for a
read operation with a hit in cache, 5 nanoseconds
for a read operation with a miss in cache, 2
nanoseconds for a write operation with a hit in
cache and 10 nanoseconds for a write operation
with a miss in cache. Execution of a sequence of
instructions involves 100 instruction fetch
operations, 60 memory operand read operations
and 40 memory operand write operations. The
cache hit-ratio is 0.9. The average memory access
time (in nanoseconds) in executing the sequence
of instructions is

.

GATE 2010 · MCQ · 2 marksQ42 · page 501 of the book

A computer system has an L1 cache, an L2 cache,
and a main memory unit connected as shown below.
The block size in L1 cache is 4 words. The block
size in L2 cache is 16 words. The memory access
times are 2 nanoseconds. 20 nanoseconds and 200
nanoseconds for L1 cache, L2 cache and main
memory unit respectively.

When there is a miss in both L1 cache and L2 cache,
first a block is transferred from main memory
to L2 cache, and then a block is transferred
from L2 cache to L1 cache. What is the total time
taken for these transfers?

(a)222 nanoseconds
(b)888 nanoseconds
(c)902 nanoseconds
(d)968 nanoseconds
(a)n/N
(b)1/N
(c)1/A
(d)k/n
(a)11
(b)14
(c)16
(d)27 Computer Organization and Architecture

GATE 2010 · MCQ · 2 marksQ43 · page 502 of the book

A computer system has an L1 cache, an L2 cache,
and a main memory unit connected as shown
below. The block size in L1 cache is 4 words. The
block size in L2 cache is 16 words. The memory
access times are 2 nanoseconds. 20 nanoseconds
and 200 nanoseconds for L1 cache, L2 cache and
main memory unit respectively.

When there is a miss in L1 cache and a hit in L2
cache, a block is transferred from L2 cache to L1
cache. What is the time taken for this transfer?

(a)2 nanoseconds
(b)20 nanoseconds
(c)22 nanoseconds
(d)88 nanoseconds

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 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 · 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 marksQ55 · page 504 of the book

Consider two cache organizations: The first one is a
32 KB 2-way set associative with 32-byte block size.
The second one is of the same size but directly
mapped. The size of an address is 32 bits in both
cases. A 2-to-1 multiplexer has latency of 0.6 ns
while a k-bit comparator has a latency of k/10 ns.
The hit latency of the set associative organization is
h1 while that of the direct mapped one is h2.
The value of h1 is :

(a)2.4 ns
(b)2.3 ns
(c)1.8 ns
(d)1.7 ns Computer Organization and Architecture

GATE 2006 · MCQQ56 · page 505 of the book

Consider two cache organizations: The first one is
a 32 KB 2-way set associative with 32-byte block
size. The second one is of the same size but
directly mapped. The size of an address is 32 bits
in both cases. A 2-to-1 multiplexer has latency of
0.6 ns while a k-bit comparator has a latency of
k/10 ns. The hit latency of the set associative
organization is h1 while that of the direct mapped
one is h2.
The value of h2 is :

(a)2.4 ns
(b)2.3 ns
(c)1.8 ns
(d)1.7 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

Self-check

Question 1

Base CPI 1.0, 1.4 memory accesses per instruction, miss rate 3%, penalty 40 cycles. What is the CPI?

Show answer

Stalls $= 1.4 \times 0.03 \times 40 = 1.68$ ; CPI $= 2.68$ .

Question 2

L1 local miss rate 10%, L2 local miss rate 30%, L2 hit time 8, memory 80, L1 hit time 2 (all cycles). What is the AMAT?

Show answer

$2 + 0.1\,(8 + 0.3 \times 80) = 2 + 0.1 \times 32 = 5.2$ cycles.

Question 3

The global miss rate of an L2 cache is 1% and the L1 miss rate is 4%. What is the local miss rate of L2?

Show answer

$1\% / 4\% = 25\%$ .

Question 4

Doubling the block size halves the miss rate but doubles the miss penalty (from 20 to 40 cycles), the hit time is 1 and the miss rate was 8%. Which is better?

Show answer

Before: $1 + 0.08 \times 20 = 2.6$ . After: $1 + 0.04 \times 40 = 2.6$ . They are equal.

Revision card

One-screen revision

AMAT = hit + miss rate $\times$ penalty. L1 penalty = $t_{L2} + m_2 t_{mem}$ (local rates). Global $= m_1 m_2$ .
CPI = base + accesses/instr $\times$ miss rate $\times$ penalty. Time = IC $\times$ CPI $\times$ period.
Weighted miss rate for split caches. Check hit time when raising associativity or block size.
A faster core with the same memory gains less than its CPI ratio.

References

·Hennessy and Patterson, Computer Organization and Design, Chapter 5 Large and Fast (measuring and improving cache performance, multilevel caches)
·Hennessy and Patterson, Computer Architecture: A Quantitative Approach, Appendix B / Chapter 2 Memory Hierarchy Design (cache performance, six basic optimizations)
·Hamacher, Vranesic, Zaky, Computer Organization, 5th ed., Chapter 8 The Memory System (performance considerations, hit rate and miss penalty)

Verification

All numbers are recomputed in scripts/enum-checks/coa_mem.py (AMAT with one and two levels, stall cycles, CPI, the speed-up of a faster core, the L2 speed-up, the block-size table for sequential access, the associativity comparison, the split-cache miss rate) and printed by the C program (npm run verify:c). The block-size and associativity examples use stated simple models (miss penalty of 8 cycles plus one cycle per word, a 10% longer hit time for 2-way), not measurements of any machine; real trends depend on the program. The cache animations are exact simulations re-run independently in tests/coa-mem-traces.test.ts. 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)

Cache replacement and write policies

I/O interface and programmed I/O