RAM and Cache Layout

#include <sys/mman.h>

int foo(void) {
	void *ptr=(void *)0x3cafef00d000;

	void *retptr=mmap(ptr,4096, PROT_WRITE|PROT_READ, 
		MAP_PRIVATE|MAP_ANONYMOUS,-1,0);
	std::cout<<"Did mmap, got back ptr "<<retptr<<"\n";

	int *ip=(int *)ptr;
	std::cout<<"Writing data...\n";
	*ip=7;
	std::cout<<"Reading data...\n";
	return *ip;
}
(Try this in NetRun now!)

Modern Memory Hardware

• The Load/Store buffer matches pending loads to pending stores, bypassing everything else entirely.
• The Translation Lookaside Buffer (TLB) caches the page table, accelerating virtual to physical address translation.  Some caches are indexed by virtual address, which reduces the pressure on the TLB, but then you need to figure out what to do about context switches.
  
• The level 1 cache (L1) is tiny, typically a few dozen kilobytes, but fast, typically a few nanoseconds.  It's made fast by being simple (i.e., stupid), typically direct mapped.  Each core typically has its own L1.
  
• The level 2 cache (L2) is typically a few megabytes, and only a bit slower than L1.  L2 typically is shared between cores, although some machines push this off to a L3 cache.
• The memory controller figures out how to talk across the memory access bus.
• The Dynamic Random Access Memory (DRAM) chips are huge, measured in gigabytes, but impossibly slow, taking 50+ nanoseconds to do a random access.  They're actually much better at streaming accesses, which is ironic considering their name!

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 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)
  

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!)

Memory-Carried Superscalar Dependencies

const int n=1000;
int arr[n];
int i;
for (i=0;i<n;i++)
	arr[i]*=i;
return arr[0];

(Try this in NetRun now!)

const int n=1000;
int arr[n];
int i;
for (i=0;i<n;i++)
	arr[0]*=i;
return arr[0];

(Try this in NetRun now!)

Empirical 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!

2D Arrays implemented as 1D Arrays

int arr[4][3];
int foo(void) {
	arr[0][0]=0xA0B0;
	arr[0][1]=0xA0B1;
	arr[0][2]=0xA0B2;
	arr[1][0]=0xA1B0;
	arr[2][0]=0xA2B0;
	arr[3][0]=0xA3B0;
	return 0;
}

• "j is the fast index", since as you walk through the 1D array, the 2D value of j changes fast (every step), but i changes more slowly.
• "the array is column-major" (if i is the column number, like I've drawn the table above, a whole row is contiguous in memory), *or* "the array is row-major" (if i is the row number, like the transpose of my figure, a whole row is contiguous in memory).  Note that whether you call an array row- or column-major depends on what you *define* as the rows or columns!

enum {sx=512};
enum {sy=512};
double img[sx*sy];

int inc_img(void) {
        for (int x=0;x<sx;x++)
	for (int y=0;y<sy;y++)
		img[x+y*sx]++;
	return 0;
}

int foo(void) {
	double t=time_function(inc_img);
	printf("%.3f ns/pixel\n",t/(sx*sy)*1.0e9);
	return 0;
}
(Executable NetRun Link)

• Avoiding the power-of-two-jumps that screw up a set-associative cache (see below), by changing "sx" to 512+4.  This alone speeds the program up to 15ns/pixel.

• Making "img" smaller, by changing it to a "char" (1 byte) instead of "double" (8 bytes).  This speeds the program up to 6ns/pixel (try it!).
• Making the access more regular, by either interchanging the x and y loops, or by changing how the array is indexed (so it's "img[x*sy+y]").  This speeds the program up to 4ns/pixel.
  
• Doing both--small data with regular access.  This speeds the program up to about 1ns/pixel--a 70x improvement!

Caching In Parallel: 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)

Snoopy Cache Coherence Protocol

Non-Uniform Memory Access (NUMA): Scalable Cache Coherence

Software Distributed Shared Memory (SDSM)