Memory Hierarchy and Cache

DRAM Hardware

Levels of Cache

	for (i=0;i<max;i++) { /* jump around in buffer, incrementing as we go */
		sum+=buf[loc&mask]++;
		loc+=1234567;
	}

• "L1" cache is the fastest (like 1-5ns) but tiny (100KB or less).
• "L2" cache is slower (7-10ns) but much bigger (up to a meg)
• RAM is painfully slow (100ns or more) but huge (gigs).  On the latest machines, the caches are bigger, and the load/store prediction units are better, so it's getting tougher to measure actual RAM latency.  The 10ns Sandy Bridge numbers above look plausible for CAS latency alone, but total end-to-end latency is higher.
  

Memory Speed

• Good *if* you're accessing a small amount of memory--small enough to stay in cache.  The pieces of memory you use often automatically get copied into fast cache memory.  For example, the top of the stack, recent stuff from the heap, and commonly used globals are almost always in cache, and hence really fast.  Machines only have on the order of 1 meg of cache nowdays.
  
• Good *if* you're accessing memory sequentially--if you access a[i], you then access a[i+1].  This "streaming" access is fast because memory chips don't have to change rows.
  
• Terrible *if* you're accessing a big buffer (too big to fit in cache) in a nonsequential way.  Cached accesses are on the order of 1ns.  Streaming access is also a few ns.  Random access that isn't in the cache is on the order of 100ns!
  

• Make things smaller, or re-use them more often, to take advantage of the cache.
  
• Make your accesses more regular, to get streaming access.
  

• Change your algorithm to improve locality.  Think about how your loops access memory.  Often it's trivial to reorganize your loops so you touch the same data 5 times before hitting the next piece of data (temporal locality); or so you access arrays sequentially (spatial locality).  Sometimes an algorithm that's theoretically more efficient will be slower than another algorithm with more instructions but better locality!
  
• Change your data structure to improve locality.  For example, you might change linked lists into arrays.  The trouble with linked lists is that links are allocated at random separate locations; but an array will be contiguous in memory (spatial locality).
• Change your input data to improve locality.  For example, processing data in small pieces (1KB) will usually have better temporal locality than huge chunks (1GB).  Of course, if your pieces are too small, sometimes your program will slow down because of the per-piece overhead!

Why you care: Set-associative Cache Mapping

enum {n=1024*1024};
char arr[n]; 

int foo(void) {
	arr[0]++;
	arr[12345]++;
	return 0;
}

(Try this in NetRun now!)

enum {n=1024*1024};
char arr[n]; 

int foo(void) {
	arr[0]++;
	arr[65536]++;
	return 0;
}

(Try this in NetRun now!)

Why you care: Multicore Cache Coherence and Cache Thrashing

enum {n=2}; /* number of threads */
enum {m=1000*1000}; /* number of times to access the int */
int offset=1; /* distance, in ints, between threads' accesses */
volatile int arr[1025];
void hammer_on_int(volatile int *ptr) {
	for (int i=0;i<m;i++)
		(*ptr)++;
}
int multi_hammer(void) {
#pragma omp parallel for
        for (int thread=0;thread<n;thread++) {
        	hammer_on_int(&arr[thread*offset]);
        }
	return 0;
}
int foo(void) {
	for (offset=1;offset<=1024;offset*=2)
		printf("%d-byte offset took %.3f ns/++\n",
			sizeof(int)*offset,time_function(multi_hammer)*1.0e9/m);
	return 0;
}

(Try this in NetRun now!)

4-byte offset took 19.437 ns/++
8-byte offset took 19.304 ns/++
16-byte offset took 20.442 ns/++
32-byte offset took 22.939 ns/++
64-byte offset took 2.615 ns/++
128-byte offset took 2.601 ns/++
256-byte offset took 2.598 ns/++
512-byte offset took 2.572 ns/++
1024-byte offset took 2.857 ns/++
2048-byte offset took 2.664 ns/++
4096-byte offset took 2.571 ns/++
Program complete.  Return 0 (0x0)