4/12 - Locality of Reference

Principle of Locality: Many Programs tend to use data and instructions with addresses near or equal to those they have used recently.

Temporal locality: Recently referenced items are likely to be referenced again in the near future
Spatial locality: Items with nearby addresses tend to be referenced close together in time

Data Layout - order in which items are laid out in memory / disk

Data Access Pattern: order in which a prgram has to access items in memory

Hardware Efficiency: how close actual execution runtime is to best possible runtime, improved w/ careful data layout and access patterns

Example: matrix multiplication

Suppose data layout in DRAM is in row-major order

$$ C_{n \space by\space m} = A_{n \space by\space p}B_{p\space by\space m} $$

DRAM: A[1;] A[2;] … B[1;] B[2;] …

Caches A[1;] B[1;]

for i = 1 to n
	for j = 1 to m
		for k = 1 to p
			C[i][j] += A[i][k] * B[k][j]

not efficient
prefetching + caching meabns full row based on innermost loop is brought to cache
A[i][.] hits but B[k][j] misses (not in cache) → each * operation is a stall

Solution

for i = 1 to n
	for j = 1 to m
		for k = 1 to p
			C[i][j] += A[i][k] * B[k][j]