Cache Writes

"Write" = "Store"

Multiple copies of data will exist. The same data can be in the L1, L2, L3, Main Memory, and Disk.

When there is a write-hit, there are two options:

• write-through: every write is written immediately to memory. The contents of the cache block is guaranteed to be consistent with memory.
• write-back: If the cache has a valid replica of the block, then only the data in the replica is modified. It defers write to memory until replacement of line.
  • Needs a dirty bit to keep track if the line is different from memory or not. When the block of data is loaded from memory to the cache, it is considered to be "clean." Dirty bit is set to True the moment any data in a replicated block is modified.

When there is a write-miss:

• write-allocate: it loads the access block from memory to the cache. This is useful for access paterns that have spacial or temporal locality. It is good if more writes to the location follow.
• no-write-allocate: writes straight to memory, does not load into cache.

The combination of write-back and no-write allocate is not a meaninful combination because if there is a write-miss, this means the data is not going to cache nor memory. Therefore, the typical combinations are:

• write-through and no-write-allocate: approach for the simplest cache.
• write-back and write-allocate: highest performance. Used in most modern devices.

Cache Performance

In an Intel Core i7 Cache Hierarchy (4th gen haswell) are multicore.

There is a huge difference between a hit and miss. It could be 100x, if you onlt have L1 and main memory.

• a 99% hits is twice as good as 97% when you consider that a cache hit time of 1 cycle can have a miss penalty of 100 cycles.
• the average access time would be 4 cycles for 97% hit (1 cycle + .03 * 100 cycles*) and 2 cycles for 99% hits (1 cycle + .01 * 100 cycles*).

This is why we use "miss rate" rather than "hit rate"

Write Cache Friendly Code

Make the common case go fast. Focus on the inner loops of the core functions.

Minimize the misses in the inner loop. Do this by:

• using repeated references to variables (temporary locality)
• stride-1 reference patterns (spatial locality)

Key idea: our qualitative notion of locality is quantified through our understanding of cache memories.

Matrix Multiplication example

We want to multiply NxN matrcies. The matrix elements are doubles (8 bytes). There are O(N^3) total operations with N reads per source element and N values summed per destination, but may be able to hold in register.

Miss rate for analysis for matrix multiply. Assume: block size = 32B (holds 4 doubles) and N is very large. The cache is not big enough to hold multiple rows.

In C, the layout in memory is as follows:

• c arrays are allocated in row-major order, where each row is contiguous memory locations.
• To step through columns in one row: a for loop will access successive elements:

for (i = 0; i < N; i++)
	sum += a[0][i];

If block size B > sizeof(a_ij) bytes, exploit spatial locality. The miss rate is sizeof(a_ij) bytes / B.

• When you step through rows in one column: the for loop accesses distant elements

for (i = 0; i < N; i++)
	sum += a[i][0];

There is no spatial location so the miss rate is 1.

There are three ways to write this method:

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
	sum = 0.0;
	for (k=0; k<n; k++)
		sum += a[i][k] * b[k][j];
	c[i][j] = sum;
}

• ijk (&jik): 2 loads, 0 stores; misses/iter = 1.25

for (k=0; k<n; k++) {
	for (i=0; i<n; i++) {
		r = a[i][k];
	for (j=0; j<n; j++)
		c[i][j] += r * b[k][j];
	}
}

• kij (&ikj): 2 loads, 1 stores; misses/iter = 0.5

for (j=0; j<n; j++) {
	for (k=0; k<n; k++) {
		r = b[k][j];
		for (i=0; i<n; i++)
			c[i][j] += a[i][k] * r;
	}
}

• jki (&kji): 2 loads, 0 stores; misses/iter = 2.0

Using Blocking

Blocking can improve temporal locality.

The idea is to maximize locality by usin ga data object as often as possible once it's read from memory.

From the same matrix multiplication example: No blocking = (9/8) * n^3 Blocking = 1/(4B) * n^3

The reason for such a dramatic difference is that:

• matrix multiplication has inherent temporal locality:
  • input data: 3n^2, computation 2n^3
  • Every array element used O(n) times!
• but program has to be written properly.