"Memory Hierarchy: Cache & Main Memory" — Practice

Question 1

A direct-mapped cache has 128 lines of 16 bytes each, on a machine with 32-bit byte addresses. How many tag bits are needed?

Accepted Answer

A

Question 2

A cache has free lines available, yet a block is evicted and immediately re-referenced. What kind of miss is this?

Accepted Answer

C

Question 3

A cache has a 2-cycle hit time, a 5 per cent miss rate and an 80-cycle miss penalty. What is the average memory access time?

Accepted Answer

B

Question 4

A 32 KB, 8-way set associative cache has 64-byte blocks and a 32-bit address. Find the tag, index and offset widths, and the total tag storage in bits assuming a write-back cache.

Accepted Answer

Start with the offset, fixed by the block size. 64 bytes needs log base 2 of 64 = 6 bits.

Lines equal cache size divided by block size: 32768 divided by 64 = 512 lines.

Sets equal lines divided by associativity: 512 divided by 8 = 64 sets.

So the index is log base 2 of 64 = 6 bits.

The tag is 32 minus 6 minus 6 = 20 bits. Check: 20 + 6 + 6 = 32, which confirms the split.

For storage overhead, each line carries its 20-bit tag, a valid bit and, because the cache is write-back, a dirty bit. That is 22 bits per line.

With 512 lines, the total overhead is 512 times 22 = 11,264 bits, which is 1,408 bytes.

As a fraction of the 32,768 bytes of data, that is about 4.3 per cent. Note that the tag width fell to 20 bits partly because the large 64-byte block absorbed 6 address bits into the offset; a 16-byte block would have given 22 tag bits across 2048 lines, roughly quadrupling the overhead.

Question 5

A processor has an L1 cache with a 1-cycle hit time and a 6 per cent miss rate, an L2 with a 10-cycle access time and a 30 per cent local miss rate, and a 150-cycle memory access. Compute the AMAT and the global L2 miss rate.

Accepted Answer

The nested formula treats each level's miss penalty as the average access time of the next level.

Start from the bottom. The effective penalty for an L1 miss is the L2 access time plus the L2 local miss rate times the memory time: 10 + 0.30 times 150 = 10 + 45 = 55 cycles.

Now the top level: AMAT = 1 + 0.06 times 55 = 1 + 3.3 = 4.3 cycles.

For the global L2 miss rate, note that only L1 misses reach L2 at all. The fraction of all processor accesses that miss in both levels is 0.06 times 0.30 = 0.018, or 1.8 per cent.

The distinction matters. The local rate of 30 per cent describes how L2 performs on the traffic it sees, which is already filtered by L1 and therefore harder. The global rate of 1.8 per cent describes how often a processor access ends up going all the way to memory.

Using 1.8 per cent in place of 30 per cent inside the nested formula would give an L1 miss penalty of 10 + 0.018 times 150 = 12.7 cycles and an AMAT of 1.76, understating the true figure by more than half.

Question 6

A direct-mapped cache has 8 lines with 1 word per line. Trace the block reference string 0, 8, 0, 8, 16, 0 and count misses, then repeat for a 2-way set associative cache with the same 8 lines and LRU.

Accepted Answer

Direct mapped with 8 lines: block b maps to line b mod 8. Blocks 0, 8 and 16 all map to line 0, since all are multiples of 8.

Reference 0: miss, load 0. Reference 8: miss, evict 0, load 8. Reference 0: miss, evict 8, load 0. Reference 8: miss, evict 0, load 8. Reference 16: miss, evict 8, load 16. Reference 0: miss, evict 16, load 0.

All 6 references miss.

Two-way set associative with 8 lines gives 4 sets of 2 lines. Block b maps to set b mod 4. Blocks 0, 8 and 16 all map to set 0, since all are multiples of 4.

Reference 0: miss, load into set 0. Reference 8: miss, load into the second line of set 0. Reference 0: hit. Reference 8: hit. Reference 16: miss, set 0 is full so LRU evicts 0, the least recently used. Reference 0: miss, evicts 8.

That gives 4 misses.

The improvement from 6 to 4 comes entirely from the two middle references becoming hits, since the set could hold both 0 and 8 simultaneously. The last two still miss because three blocks compete for two lines, which shows the limit: associativity of k tolerates k competing blocks, and a k plus 1 way conflict still thrashes.

Question 7

Explain why LRU cannot exhibit Belady's anomaly, and give the structural property that guarantees it.

Accepted Answer

LRU is a stack algorithm, and stack algorithms have the inclusion property: at every point in the reference string, the set of blocks held with n frames is a subset of the set held with n plus 1 frames.

The reason is that LRU's eviction choice depends only on the reference history, not on the number of frames. With any number of frames, LRU holds exactly the most recently referenced blocks, so a cache of n frames holds the top n of the recency ordering and a cache of n plus 1 frames holds the top n plus 1. The first set is contained in the second by construction.

The consequence follows immediately. If a reference hits with n frames, the block was among the top n most recently used, so it is certainly among the top n plus 1, and it hits with n plus 1 frames too. Adding a frame can therefore only convert misses into hits, never the reverse, and the miss count is monotonically non-increasing in the number of frames.

FIFO has no such property. Its eviction choice depends on load order, and changing the number of frames changes which blocks get evicted at which times, so the contents with n frames need not be a subset of the contents with n plus 1. That is precisely what allows a larger cache to discard a block just before it is needed, producing the anomaly.

The optimal policy is also a stack algorithm, for the analogous reason that it keeps the blocks needed soonest, so it too is immune.

Question 8

A program writes to the same cache line 20 times and then the line is evicted. Compare the memory write traffic under write-through and write-back, and explain when write-through is nevertheless preferable.

Accepted Answer

Under write-through, every write updates both the cache and main memory. Twenty writes therefore generate twenty memory transactions, and the eviction itself generates none, since memory is already current.

Under write-back, the twenty writes update only the cache, setting the dirty bit on the first of them. Memory is untouched until eviction, at which point one block-sized transfer occurs.

The traffic ratio is twenty transactions against one, and for a program with any write locality at all the difference is decisive. This is why write-back dominates in first-level caches.

Write-through is nevertheless preferable in three situations. First, when memory must stay current for another observer: in a multiprocessor with a simple coherence scheme, or where a DMA controller reads memory directly, write-back requires extra machinery to ensure the observer sees the latest value. Second, when eviction latency matters: a write-back eviction of a dirty line must complete before the new block can be loaded, lengthening the miss penalty, whereas a write-through cache can simply discard the line. Third, when the error-detection story matters: a write-through cache holds no unique data, so a cache failure loses nothing.

The write buffer softens the traffic objection considerably, letting the processor continue while writes drain, which is why write-through survives in some second-level and specialised designs.

Question 9

A memory system has 4 banks with a 100 ns bank cycle time and an 8-byte access width. Compute the peak sequential bandwidth under low-order interleaving, and state what happens if a program strides through memory in steps of 4 words.

Accepted Answer

With low-order interleaving, consecutive addresses fall in consecutive banks, so a sequential stream visits bank 0, 1, 2, 3, 0, and so on.

All four banks can be busy simultaneously, so once the access pipeline is full one access completes every 100 divided by 4 = 25 ns.

Peak bandwidth is 8 bytes per 25 ns, which is 320 MB per second, four times the 80 MB per second a single bank would deliver.

Now consider a stride of 4 words. If a word is 8 bytes and there are 4 banks, then the bank index is determined by the address bits just above the byte offset, and stepping by 4 words advances the bank index by 4, which is 0 modulo 4.

Every access therefore lands in the same bank. The other three sit idle, and the achieved bandwidth collapses to single-bank speed, 80 MB per second — a factor of four worse than the sequential case despite identical hardware.

This stride sensitivity is a real effect and is why array traversal order matters for performance. Traversing a two-dimensional array along the wrong axis produces exactly such a stride, and the same reasoning explains why padding an array dimension by one element can restore full bandwidth by breaking the alignment between the stride and the bank count.

Practice — "Memory Hierarchy: Cache & Main Memory"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities