Threads: Why and Why Not

CS 321 2007 Lecture, Dr. Lawlor

Why Threads?

Why do we even care about threads, or parallelism in general? The reason is that computer technology is currently at something of a historical crossroads. Since the 1950's, computers have gotten both bigger and bigger (more circuitry) and faster and faster (more computing per unit time). Tons of stuff has changed--relays to vacuum tubes to silicon chips. But strangely, a computer in 1956 was programmed in about the same way as a computer in 2006--for example, both of them could run ordinary programs written in Fortran.

The main trick that's gotten us this far is "adding circuitry to speed up the CPU". For example, look at the difference between a ripple carry addition circuit and a "lookahead" circuit. Ripple carry is simple and small (meaning less circuits) but slow. Lookahead is faster, but more complicated (more circuitry).

As silicon technology allows you to produce more circuitry per dollar, a chip company has two choices--you can produce a cheaper product that performs the same, or you can produce a faster product that costs the same. Intel would much rather sell 10 million $100 CPUs than 100 million $1 CPUs. The mantra of CPU companies has thus been "more circuitry for more speed".

So far, "speed" has meant a combination of high clock rate and lots of work done per clock cycle. It used to be (back in the 386 era) that the CPU was clocked at about the same speed as the RAM (around 10MHz), and the CPU didn't really get much done every clock (a typical instruction would take 3 or 4 clock cycles to complete). Both clock rates (MHz/GHz) and the amount of work accomplished per clock cycle (Instructions Per Clock, or IPC) have gone way up--today's machines run at GHz, and actually finish several instructions every clock cycle. They require a huge amount of complexity to do this--huge caches, "branch prediction", "register renaming", "speculative execution", and so on.

And so for the last 50 years, this approach has worked pretty well. Unfortunately, it's no longer sustainable. The classic "too many GHz" CPU was the Pentium 4, which sacrificed everything for clock rate. Even the Pentium 4 peaked at 3.8GHz, which is fast enough that the speed of light starts to become a serious problem--light travels 3 inches in 0.25 nanoseconds; electricity travels 2 inches, and the round trip time is 1 inch, which is about the size of a 25mm die!

There is an old and useful solution to this problem--rather than use additional circuitry to make one CPU faster, make more CPUs. People have been predicting this switch since at least the late 1980's (David Mitchell, The Transputer: The Time Is Now, 1989). IBM first sold "dual core" PowerPC chips in 2005 (970MP: two CPUs, one piece of silicon). AMD also released the dual-core Athlon X2 in 2005. Intel finally introduced a dual-core chip with their Core Duo in early 2006, and in November 2006 released the four-core Core2 Quad. They're busily working away at 16 and 32-CPU chips, since they understand the technology and economics underlying this trend.

The bottom line is that modern machines have multiple CPUs. A single, single-threaded Fortran/C/C++/Java/C# program cannot take advantage of a multi-CPU machine.

So you have several options:

Give up multiple CPUs--this is currenly only a 50%-75% performance hit, but it's increasing. Eventually a single-CPU program will seem silly and quaint, like a DOS program's 640K memory limit.
Use multiple processes, and deal with the fact that the processes have to explicitly communicate.
Use multiple threads, and deal with the threads "fighting over" shared resources like global variables.
Write a wrapper around the multi-CPUness. The nicest wrapper is to write your code in a "naturally parallel" fashion, where each piece operates independently and potentially in parallel. Then you can decide between threads and processes.

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

The THERAC-25was a piece of medical equipment capable of generating either a high-strength electron beam through a target to generate X-Rays, or scanning a much weaker raw electron beam over the surface of a cancer patient. When you chose "Electron" mode, the software would begin this process:

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

When you chose "X-Ray" mode, the software would crank up the electron beam strength and insert the piece of metal used to generate X-Rays. If you chose "Electron" mode (starting the calibration cycle) and then within 8 seconds went back and chose "X-Ray" mode, the end of the Electron mode setup would remove the crucial piece of metal needed for X-Ray mode, but then send a high-strength electron beam directly into the patient. At least two people died as a direct result of this problem, and several more were permanently maimed.

The problem is just "simple" multithreaded locking--the two modes should have been exclusive, but because they were both running at the same time (directly from the keyboard interrupt) on the same machine they could interleave in a strange way. Allow me to be more clear:

MULTITHREAD BUGS HAVE KILLED PEOPLE.

For goodness sake, don't let your software kill people!