Programs and caches: array layout, loop order, counting misses

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Global L2 miss rate from m₁ and local m₂? from Lesson 4.3.3
• Direct mapping: which line does block j use? from Lesson 4.2.1
• Compulsory, capacity, conflict: define capacity. from Lesson 4.2.4

1 · The Hook

🎣

Two programs zero the same array. One walks it row by row, the other column by column. Same work, same data, yet one can miss 16 times more often. GATE has asked this "loop order" question in many forms; the method is to compute which block each access touches.

2 · Predict First

🤔

int A[64][64] (4-byte ints) is stored row after row. Blocks are 16 bytes. Walking it row by row, how often does a fresh block start? Walking column by column, how far apart are consecutive accesses?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Row by row: a new block every 4 elements (16 / 4), so at most 1 miss per 4 accesses. Column by column: consecutive accesses are one row apart: 64 × 4 = 256 bytes = 16 blocks, so each access lands in a different block.

Array layout

C stores 2-D arrays in row-major order: A[i][j] of an N × M array with element size s is at address = base + (i × M + j) × s. (Fortran uses column-major: base + (j × N + i) × s.)

Row-wise traversal (for i … for j … A[i][j])

Addresses increase by s each step: perfect spatial locality.

• Misses (cold cache, array aligned) = array bytes ÷ block size.
• Miss ratio = s ÷ B (one miss per block of B/s elements).

Column-wise traversal (for j … for i … A[i][j])

Each step jumps M × s bytes (one row). If M × s ≥ B, every access touches a new block.

• The next column (j + 1) reuses those same blocks only if all N blocks of the previous column are still in the cache.
• Whether they are depends on cache size and mapping: rows that are 2ᵏ bytes apart often fall into the same few lines of a direct-mapped cache.

Worked example

int A[64][64] at address 0 (16 KB), 16-byte blocks.

Row-wise: 16 KB / 16 B = 1,024 misses in every cache. Column-wise, direct-mapped: block of A[i][j] = 16i + ⌊j/4⌋. In the 1 KB cache, line = block mod 64, so the 64 rows map onto only 4 lines (0, 16, 32, 48 plus ⌊j/4⌋): blocks evict each other before the next column can reuse them; all 4,096 accesses miss. The 4 KB direct-mapped cache maps them onto 16 lines: still conflicts, still 4,096. A 4 KB fully associative cache keeps all 64 blocks of a column, so columns j + 1 … j + 3 hit: 1,024 misses.

The fix

Loop interchange: make the innermost loop run over the last index (j) for row-major arrays. Blocking (tiling) processes small sub-squares that fit in the cache.

Hit ratio of a sequential pass

Initialising double ARR[1024][1024] row by row with 16-byte blocks: each block holds 2 doubles → miss, hit, miss, hit … hit ratio 50%, whatever the cache size.

4 · Visual

int A[64][64], 16-byte blocks (4 ints per block)

row-wise:     A[0][0] A[0][1] A[0][2] A[0][3] | A[0][4] ...      1 miss per 4
               miss    hit     hit     hit    |  miss

column-wise:  A[0][0]  A[1][0]  A[2][0] ...    each 256 bytes apart = new block
               miss     miss     miss          reuse at column 1 only if 64 blocks survived

5 · Worked Examples

Example 1 Easy

double D[100][100] row-major at address 0. Address of D[3][7]?

Solution

(3 × 100 + 7) × 8 = 2,456.

Example 2 Medium

int A[128][128], 32-byte blocks, cold 8 KB direct-mapped cache. Row-wise misses?

Solution

Array 64 KB; 64 KB / 32 B = 2,048 misses.

Example 3 GATE

Same array and cache, but column-wise. Rows are 512 bytes = 16 blocks apart; the cache has 256 lines. How many misses?

Solution

Block of A[i][j] = 16i + ⌊j/8⌋; line = block mod 256 → only 16 different lines for the 128 rows, so blocks are evicted before reuse: every access misses: 16,384 (8 times the row-wise count).

6 · GATE Traps

⚠️

• Row-major: the last index varies fastest in memory.
• Row-wise miss ratio = element size ÷ block size.
• Column-wise reuse needs all rows' blocks to survive one column: check both capacity and mapping.
• A bigger direct-mapped cache may not help column-wise access if the row stride is a power of two.

7 · Memory Hook

🧠

"Walk the way it's stored." Inner loop over the last index for C arrays.

8 · Connect the Dots

Phase 4 is complete: hierarchy and chips, cache mapping and tracing, write policies, penalties, two levels and real loops. Phase 5 makes the CPU itself faster with pipelining, where cache misses reappear as stalls in the MEM stage.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markRow-wise misses

int A[256][256] (4 bytes each), 64-byte blocks, cold cache, row-wise. Misses?

Numerical answer: ________

Q2NAT2 marksColumn-wise misses

Same array, 16 KB 4-way set-associative cache with 64-byte blocks, column-wise traversal. Rows are 1 KB apart. How many misses?

Numerical answer: ________

Q3NAT1 markHit ratio

A row-wise pass over an array of 4-byte ints with 32-byte blocks (cold cache). Hit ratio?

Numerical answer: ________

Q4NAT2 marksAddress

int M[50][40] row-major at base 1000. Address of M[12][5]?

Numerical answer: ________

Q5MCQ1 markLoop order

For a C array accessed in a doubly nested loop, which ordering usually gives fewer cache misses?

• (A) Outer loop over i (row), inner loop over j (column)
• (B) Outer loop over j (column), inner loop over i (row)
• (C) It depends only on the replacement policy
• (D) Both are always equal

10 · Rule Card

• Row-major: addr = base + (i·M + j)·s. Column-major: base + (j·N + i)·s.
• Row-wise misses = bytes ÷ B; miss ratio = s ÷ B.
• Column-wise: stride M·s; reuse needs all N blocks to survive (size and mapping).
• Fix: loop interchange; blocking (tiling).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

row-major layoutcolumn-major layoutelement address formularow-wise vs column-wise traversalstrideloop interchangeblocking (tiling)

12 · Answer Vault