Memory Organisation and Performance: Cache Mapping, AMAT and Worked GATE Examples

Knowing that cache is faster than main memory is not enough when a question asks for tag, index and offset bits, or when hit rate must become average access time. Address-field calculations, address tracing, performance computation and conflict-miss comparison all use the same system.

Memory hierarchy is a latency compromise

Memory is organised as CPU registers, cache, main memory and secondary storage. Levels nearer the CPU are smaller and faster. Lower levels are larger and slower.

A cache stores fixed-size blocks, also called lines. An access is a hit when its block is present and a miss otherwise. Hit rate is the fraction that hit. Access time checks a level, while miss penalty is the extra time to fetch from the next level.

This works because programs show locality. Temporal locality means recently used data is likely to be reused. Spatial locality means nearby addresses are likely to be used. When a loop reads A[0], A[1], A[2] and A[3], one cache block can bring adjacent array elements together.

Cache capacity gives the lines and address fields

Consider a 32-bit byte-addressable physical address space, a 32 KiB direct-mapped cache and 64-byte blocks. First convert every capacity to a power of two:

• Cache capacity: 32 KiB = 32 x 1024 = 2^15 bytes

• Block size: 64 bytes = 2^6 bytes

• Cache lines: 2^15 / 2^6 = 2^9 = 512

The block offset needs log2(64) = 6 bits because byte addressing must select one of 64 bytes. The line index needs log2(512) = 9 bits. The remaining 32 - 9 - 6 = 17 bits form the tag.

The index selects one cache line, the tag checks which memory block occupies it, and the offset selects a byte within that block. In general, line = memory block number mod number of cache lines. Blocks with equal indices but unequal tags compete for the same line. For the broader treatment of direct, set-associative and fully associative mapping, write policies, tag-directory overhead and multi-level AMAT, use Cache Memory Organization in COA: Mapping, Hit Ratio and Worked Examples. A 32-bit direct-mapped system connects exact address decoding, single-level AMAT and a conflict trace.

Trace address 0x12345678 through the cache

For address 0x12345678, extract the fields arithmetically:

1. Byte offset: address mod 64 = 56 = 0x38.

2. Memory block number: floor(address / 64) = 4,772,185.

3. Line index: 4,772,185 mod 512 = 345.

4. Tag: floor(4,772,185 / 512) = 9,320 = 0x2468.

The split is 00010010001101000 | 101011001 | 111000: the 17-bit tag 0x2468, index 345 and offset 56. Joining them gives 00010010001101000101011001111000, or 0x12345678.

The cache reads line 345 and compares its valid bit and stored 17-bit tag. A match returns byte 56; otherwise, the block is fetched from the next level. The offset never selects a line, and the tag is stored beside it.

Average memory access time from the same system

Now give this cache a 1 ns lookup time, a 95% hit rate and an additional 80 ns miss penalty. The convention matters: every access pays 1 ns, while only a miss pays the extra 80 ns.

The miss rate is 1 - 0.95 = 0.05, so:

AMAT = hit time + miss rate x miss penalty

AMAT = 1 + 0.05 x 80 = 1 + 4 = 5 ns

For a second check, use 1,000 accesses. The 950 hits cost 950 x 1 = 950 ns. The 50 misses cost 50 x (1 + 80) = 50 x 81 = 4,050 ns. Total time is 950 + 4,050 = 5,000 ns, hence 5,000 / 1,000 = 5 ns per access.

Against an 80 ns uncached main-memory baseline, this simplified model gives 80 / 5 = 16x speed-up. If the hit rate falls to 90%, AMAT = 1 + 0.10 x 80 = 9 ns. The additional 5 percentage points of misses add 0.05 x 80 = 4 ns, showing why a large miss penalty makes hit rate crucial.

Cache mapping changes conflict behaviour

Direct mapping permits one location per block and one tag comparison. Set associativity permits several locations within a set and compares several tags. Full associativity permits placement anywhere. Greater associativity can reduce conflict misses, but needs more comparators and replacement logic.

Take a separate four-line cache with one-block entries and the sequence 0, 4, 0, 4, starting empty. Direct mapping sends both blocks to block mod 4 = line 0, so the result is M, M, M, M: zero hits and a 0% hit rate.

In a two-way, two-set cache, both blocks go to block mod 2 = set 0. Its two ways retain both blocks, giving M, M, H, H: two hits and a 50% hit rate. This illustrates a conflict miss. It does not prove that two-way mapping always halves misses.

Traps that break correct-looking solutions

• Treating KiB as decimal. Write 32 KiB = 32 x 1024 = 2^15 bytes first.

• Treating bytes as lines. Use lines = cache bytes / block bytes.

• Changing offset bits with associativity. Offset depends only on block size. For a K-way cache, sets = cache size / (block size x K), so the set-index and tag widths change.

• Mixing AMAT conventions. State whether the miss penalty is additional or already includes lookup time before choosing a formula.

Finally check that field widths sum to the address width, the index range fits the line or set count, and hit plus miss probabilities equal 1.

GATE memory organisation and performance patterns

The official GATE 2026 Computer Science syllabus placed memory hierarchy, including cache, main memory and secondary storage, under Computer Organization and Architecture. This is past-cycle evidence, not a statement about a future notification.

As an attributed pattern example, GATE 2026 CS1 master paper Q38 used a 2^32-byte address space, a 2^23-byte cache and 128-byte blocks, then related direct mapping to K = 2^L-way set associativity. Since 128 = 2^7, the offset is 7 bits. Direct mapping has 2^23 / 2^7 = 2^16 lines, so M = 32 - 16 - 7 = 9 tag bits. The associative cache has 2^(16-L) sets, giving N = 32 - (16 - L) - 7 = 9 + L = M + L.

Recurring forms include address-field calculations, mapping traces, conflict behaviour, associativity and AMAT. Use the GATE CS Exam Preparation category for the wider subject map, or continue COA revision with Floating-Point Representation: IEEE 754 Format.

Short version and next step

• Divide cache bytes by block bytes.

• Take base-2 logarithms for offset and index.

• Assign the remaining address bits to the tag.

• Define the timing convention before computing performance.

For the worked system, 17 tag + 9 index + 6 offset = 32 bits, and AMAT = 5 ns. If you want sequenced COA learning, continue with GATE Guidance by Sanchit Sir. Use the GATE Test Series when you are ready to apply the method under time pressure. More than 50 questions are also available for optional practice on this subtopic.