Parallel Processing with Threads & Processes

Kinds of Parallel Computers

• One ALU, one set of registers: serial computer (single processor).
• 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 (1us).
  
• 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 really 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 for an example (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 [eax],esp  ; Save the old stack pointer
       mov esp, [ecx] ; 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 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"--we covered it last class.
• 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!

The Problem With Threads--Example: THERAC-25 Race Condition

• Enter an 8-second magnet calibration cycle, and then
  
• Remove the metal target used to generate X-Rays
  

Parallelism Using Threads (UNIX)

	// ... 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);
	}

Parallelism Using 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);
	}