Multithreaded Execution

1. The 2006 Democratic majority in the US Congress. (New names, lots of hype, but zero measureable effect.)
   
2. The worst 1950's rumors about communist spies infiltrating honest American institutions.  (Reliable components slowly going bad without anybody knowing... until it's too late!)
   
3. The worst rumors about global warming coming true.  (Plagues of locusts, drought, heat, and major lifestyle changes for everybody.)
   
4. A meteorite similar to that which drove the dinosaurs extinct.  (Slow suffocating starvation for 90%+ of earth's life.)
   
5. The second coming.  (Dead shall rise, seas shall boil, new Jerusalem on a new Earth.)
   

1. Whatever happens, there's still going to be C++-lookin' code, if for no other reason than the huge quantity of the C++ that's out there already!  The names may change, and the way the code is called may change a lot, but deep down tons of sequential "variable=value;" code will not change.  It's the code that calls your deep-down application code that's likely to change a lot.
   
2. Multiple things happening at once means you have to worry about "race conditions", where two (or more) pieces of code "race" to see which one finishes first.  You have to worry about three (nondeterministic!) possibilities: A finishes first, B finishes first, or a tie.  Maybe two of these cases are really rare.  But either one might cause your code to blow up!  (Crash, fail, silently give the wrong answer to a crucial query...)
   
3. Parallel programming is a new lifestyle.  You've got to worry about things you didn't have to worry about before.  Concurrency makes some formerly-moral stuff (like static variables) immoral, and can make some formerly immoral stuff (like public members) moral, because the situation has changed.
4. Many perfectly innocent serial programs will slowly wither and die, because they don't take advantage of parallelism.  They will have the embarrasingly limited, dated feeling of command-line DOS applications (8 character limit),FAT32 partitions (4GB file limit), or software-rendered 3D games (ugly and slow).  Few users will mourn their passing.
   
5. Parallel programming really has the potential to change everything.  Just the hardware ranges from staid stuff like SSE to multicore to distributed to GPU to FPGA.  FPGA's don't even run C++ code, dangit.  It's the end of the world!  (As we know it... and I feel fine.)
   

• "Andy giveth, and Bill taketh away."  That is, Andrew Grove, Intel, keeps building faster and faster CPUs.  Bill Gates, Microsoft, keeps building slower and slower (yet better and better!) software.
  
• "Concurrency is the next major revolution in how we write software."  That is, by 2015 purely sequential code will have the same retro feeling that COBOL has today.
• "Probably the greatest cost of concurrency is that concurrency really is hard: The programming model, meaning the model in the programmer’s head that he needs to reason reliably about his program, is much harder than it is for sequential control flow."  That is, human reasoning is sequential.  Execution is parallel.  Horrible things can crawl into our universe through this gap!
• "For example, Intel is talking about someday producing 100-core chips; a single-threaded application can exploit at most 1/100 of such a chip’s potential throughput."  90% of commercial applications today are single-threaded.  They will either adapt or die out.
• "just because it takes one woman nine months to produce a baby doesn’t imply that nine women could produce one baby in one month."  So if the problem is "make one baby", parallelism is useless.  But if you change the problem to "make 1 million babies", suddenly you have million-way parallelism.
• "A few rare classes of applications are naturally parallelizable, but most aren’t."  In other words, occasionally it's obvious how to run in parallel, and actually running in parallel is easy.  Usually, though, you have to rethink and reformulate the basic algorithm used to solve the problem.  I'd add that "A few rare applications are impossible to parallelize, but given enough effort, most aren't."
  

Kinds of Parallel Computers

• One ALU, one set of registers: serial computer (single processor).
• Multiple ALUs, one decoder & one set of registers: Single Instruction Multiple Data (SIMD), like SSE.
  
• One ALU, several sets of registers: Symmetric Multi-Threading (SMT) or HyperThreading.  This is only a tiny amount of additional chip area, but increases ALU utilization way more than wider superscalar execution.  ALU contention limits the parallelism to perhaps 4-way on modern CPUs, but can reach 64-fold on GPUs.
  
• Several different CPUs, one shared RAM area: Symmetric Multi-Processing (SMP) or Multi-Core.  2 cores is entirely standard today, 4 cores are on the way, and commercial SMP nodes with 16 or 32 way access exist.  SMP can also combine with SMT for absurd numbers of threads: e.g., a typical GPU is 128-way SMP, with a total of 8192-way SMT.
• Several CPUs, each with local RAM, but with a nonlocal RAM interconnect: Non-Uniform Memory Architecture (NUMA).  Unlike SMP, where all RAM is equal, in a NUMA, it's faster to go to your own RAM (60ns) compared to some other CPU's RAM (1000ns).
  
• Several complete nodes, connected with network: Cluster or Massively Parallel Processor (MPP).  This is the only architecture known to scale to hundreds of thousands of CPUs--nothing is shared except the network.  If all the computers are running the same program, as is typical to solve tightly coupled problems, it's called Single Program Multiple Data (SPMD).  The Internet is a huge and very very loosely coupled MPP, because all the computers on the internet are running different programs at different times for different reasons.
  

Kinds of Program Control Flows

1. Functions, where things execute one at a time.  Hopefully you're familiar with normal functions.
• Registers: by convention, some are saved (must restore value for caller), some are scratch (can freely overwrite)
• Stack: organized by convention into "stack frames"
• Memory: shared between all functions
• Files: shared between all functions
  
2. User-level threads, where you save and restore processor registers yourself, usually via an explicit "swap" subroutine call.  Also called "coroutines" or "user/userspace threads", or (by Sun Java folks) "green threads".  Check out my little "minithread" example code  (Directory, Zip, Tar-gzip).   The key routine is just the "mth_swap" subroutine, which saves an old set of registers and loads up a new one, and the core of this is just:
       mov [rax],rsp  ; Save the old stack pointer
       mov rsp, [rcx] ; Load up the new stack pointer
     Typical examples include Netscape Threads, or any of a thousand tiny projects mostly relying on setjmp/longjmp or "makecontext/swapcontext".  Each thread has its own stack, usually just allocated with "malloc", but shares the rest of memory with other user-level threads.
• Registers: explicitly saved and restored by a "swap" routine.
• Stack: each user-level thread has a separate stack region in memory.
• Memory & Files: shared between all threads.
  
3. Kernel-level threads, or just "threads", are where the OS saves and restores processor registers to switch threads at interrupt time.  Also called "native threads". The most common example is OpenMP or pthreads.  There's actually a hybrid of kernel and user-level threads where you save and restore processor registers yourself (not in the OS), but you do it inside a signal handler during an interrupt.
• Registers: implicitly saved and restored by the OS when it decides to switch threads.
• Stack: separate regions of memory for each thread.
• Memory & Files: usually shared between all threads.
4. Processes, where the OS swaps out all of memory and all I/O connections in addition to the registers.  This is what you usually think of as a "program".
• Registers: implicitly saved and restored by the OS when it decides to switch processes.
• Stack & memory: completely separate memory area for each process.
• Files: open files are local to a process (I open a file, it's not open for you), but data in files is shared between all processes.
  
5. Virtual Machines, where the OS itself and everything in it is swapped out. QEMU is a pretty typical example.  A virtual machine is usually treated as an ordinary process inside the outer ("host") OS.
• Registers, stack, memory, files, disks, and even CPUs are all private to a virtual machine.
  

Creating Different Program Control Flows

Simple Kernel Threads

#include <pthread.h>

void doWork(const char *caller) {
	std::cout<<caller<<"\n";
}
void *fnA(void *arg) {
	for (int i=0;i<3;i++) doWork("A");
	return 0;
}
void *fnB(void *arg) {
	for (int i=0;i<3;i++) doWork("B");
	return 0;
}
int foo(void) {
	pthread_t B; 
	pthread_create(&B,0,fnB,0); /* make a thread B, to run fnB */
	fnA(0); 
	void *Bret;
	pthread_join(B,&Bret);  /* wait until B finishes */
	return 0;
}

A
A
A
B
B
B

AB

AB

AB

B
B
B
A
A
A

AB
A
A

B
B

AB

B
B
A
A

The danger of threads

int shared=0;
void inc(void) {
	int i=shared;
	i++;
	shared=i;
}

#include <pthread.h>

int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000;i++)
		sum++;
}
void *fnA(void *arg) {
	for (int i=0;i<3;i++) doWork();
	return 0;
}
void *fnB(void *arg) {
	for (int i=0;i<3;i++) doWork();
	return 0;
}
int foo(void) {
	sum=0;
	pthread_t B; 
	pthread_create(&B,0,fnB,0); 
	fnA(0); 
	void *Bret;
	pthread_join(B,&Bret); 
	return sum;
}

Thread Safety with "volatile"

volatile int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000;i++)
		sum++;
}

Thread Safety with "lock" Instruction Prefix

volatile int sum=0;  /*<- Careful!  This variable is shared between threads! */
void doWork(void) {
	for (int i=0;i<1000;i++)
		__asm__ ( "lock incl (sum)" );
}

Thread Safety With Mutexes

int sum=0;  /*<- Careful!  This variable is shared between threads! */
pthread_mutex_t sum_lock=PTHREAD_MUTEX_INITIALIZER;
void doWork(void) {
	pthread_mutex_lock(&sum_lock);
	for (int i=0;i<1000;i++)
		sum++;
	pthread_mutex_unlock(&sum_lock);
}

• Mutex aquisition is kinda slow, like 60ns per lock.  This means you want to lock and unlock as rarely as possible.
• Nobody else can do the stuff protected by the lock while you've got it.  This means you want to leave the lock locked as short a time as possible.
• It's possible to try to re-lock a lock you've locked.  This means you're waiting for yourself to unlock it!  (mutex reentrancy)
• It's possible to wait on one lock while you hold another lock.  If the guy that holds that lock is waiting for your lock, you're both "deadlocked".
  

Parallel interface: pthreads

	// ... prepare program to be run in pieces ...
	// Run the pieces as separate threads:
	pthread_t *thr=new pthread_t[n];
	for (int i=0;i<n;i++) {
		worker *w=new ... i'th piece of work ...
		pthread_create(&thr[i],0,work,w);
	}
	// Wait until all pieces are finished (until work routine returns)
	for (int i=0;i<n;i++) {
		void *ret;
		pthread_join(thr[i],&ret);
	}

Parallel interface: processes

#include <unistd.h> /* for fork */
#include <sys/mman.h> /* for mmap */
#include <sys/wait.h> /* for wait */

// Return len bytes of RAM that will automagically be shared after a fork().
void *shared_malloc(int len) {
	void *p=mmap(0,len, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANON, -1,0);
	if (p==(void *)-1) printf("mmap failed!\n");
	return p;
}
void shared_free(void *p,int len) {
	munmap(p,len);
}

...
	// ... prepare program to be run in pieces ...
	// ... call shared_malloc for memory shared between pieces ...
	// Run the pieces as separate processes:
	int *pid=new int[n];
	for (int i=0;i<n;i++) {
		worker *w=new ... i'th piece of work ...
		pid[i]=fork();
		if (pid[i]==0) { /* I'm the child laborer */
			work(w);
			exit(0);
		}
	}
	// Wait until all pieces are finished (until children exit)
	for (int i=0;i<n;i++) {
		int ret;
		waitpid(pid[i],&ret,0);
	}