Understanding CPU Cache: Types, Structure, and Performance Optimization

Why a CPU Cache is Needed

Modern processors use a memory hierarchy (registers, caches, main memory, disks) where each level differs in speed, cost, and capacity. Typical latency (in clock cycles) is roughly L1 = 4, L2 = 11, L3 = 24, main memory = 167. Because main memory is orders of magnitude slower than the CPU, a small fast cache placed between the CPU and memory reduces average memory latency and improves overall performance.

Cache Hierarchy and Cache Lines

Most CPUs provide three cache levels. L1 is split into a private data cache and a private instruction cache per core. L2 is also private to each core, while L3 is shared among all cores on the chip. The CPU fetches memory in fixed‑size blocks called cache lines (typically 64 bytes). Accessing one address loads the entire line, exploiting spatial locality.

Cache Organization Types

Direct‑Mapped Cache

A direct‑mapped cache maps each memory address to exactly one cache line using three fields:

Tag – identifies the memory block.

Index – selects the cache line.

Offset – selects the byte within the line.

On a lookup the Index selects a line, the stored Tag is compared with the address Tag; a match yields a hit, otherwise a miss.

Example: with 8 cache lines, addresses 0x00, 0x40 and 0x80 share the same Index and therefore map to the same line, causing possible thrashing when accessed repeatedly.

Set‑Associative (Multi‑Way) Cache

In a set‑associative cache the Index selects a set that contains multiple lines (ways). For a two‑way set the Index points to two candidate lines; the Tag of each is compared and a hit occurs if either matches. This reduces thrashing compared with a direct‑mapped design.

Example: 8 lines organized as 4 sets of 2 ways. A virtual address with Tag = 0x19 and Index = 1 finds two candidates; the second line’s Tag matches, so the access hits.

If all ways in a set are occupied, a replacement policy (e.g., PLRU, NRU, FIFO, round‑robin) chooses which line to evict.

Fully‑Associative Cache

A fully‑associative cache places all lines in a single set; there is no Index field. On a lookup the Tag of every line is compared in parallel. This eliminates thrashing but requires the most hardware resources.

Practical Impact: Row‑Major vs Column‑Major Traversal

The following C++ program measures the time to sum a 1024 × 1024 matrix using row‑major and column‑major loops. The row‑major version typically runs in about 2 ms, while the column‑major version takes about 8 ms, illustrating the effect of cache‑line utilization.

const int row = 1024;
const int col = 1024;
int matrix[row][col];
// Row‑major traversal
int sum_row = 0;
for (int r = 0; r < row; ++r) {
    for (int c = 0; c < col; ++c) {
        sum_row += matrix[r][c];
    }
}
// Column‑major traversal
int sum_col = 0;
for (int c = 0; c < col; ++c) {
    for (int r = 0; r < row; ++r) {
        sum_col += matrix[r][c];
    }
}

Row‑major access benefits from spatial locality: consecutive elements reside in the same cache line, leading to high hit rates. Column‑major access jumps to a different row each iteration, causing frequent cache misses and slower execution.

Conclusion

Understanding the cache hierarchy, line size, and organization (direct‑mapped, set‑associative, fully‑associative) enables developers to write cache‑friendly code. Simple changes such as iterating over data in memory order can yield order‑of‑magnitude performance improvements.