Parallelism for dummies

If you have not lived under a rock, you have probably heard that the clock frequencies of our CPUs haven't increased in years, and they probably won't in the next ones. This speed barrier, imposed by the limits to miniaturization, is the driving force behind many words we hear every day: concurrency, distributed computing, dual core, scalability, functional programming...

Yet what is parallelization? How the clock frequency wall impacts the average programmer? In this article we take a look at several facts and misconceptions about the topic, from a beginner's point of view.

At the instruction level

CPUs with more than one functional unit (let's say more circuits) may exploit their redundant capabilities by issuing and executing more than one execution at the time. These capabilities are transparent to the programmer, who just writes sequential code like he has always done; this model is called superscalar processor.

Yet if you have ever written some lines of assembly, you know that machine-level instructions are similar to every higher-level imperative languages, in the way they have functional dependencies between each other:

mov ax, bx #good old 8086 assembly
add ax, 42 #cannot dispatch it to the ALU simultaneously

Conflicts on registers and memory locations are very common in near instructions, so that they can't be parallelized automatically. It would be very nice, since everyone will just throw them sequential programs and get a speedup linear with the number of cores. Yet this kind of performance gain is limited, especially since it must be performed on-the-fly by the processor: static compiler-based optimizations would require to manage hundreds of different binary versions (for example a version for each number of cores).

Take away point: the good old sequence of assembly instructions is gaining another level of abstraction, consisting in out-of-order execution and in general in scheduling over different cores.

At the thread level

We cannot increase the clock frequency, and we cannot automatically execute instructions in parallel due to their dependencies. Thus, the next step is to require the programmer to write parallel programs; the resulting code may take different forms:

• multiple threads which works over a shared memory, and sinchronize with locks or similar systems. This concurrency model has been implemented for decades in order to exploit a single-core CPU while some thread blocked waiting for input, and is probably one of the most popular causes of failure in programs due to race conditions, starvation, deadlocks...
• multiple processes, which differ by threads for the absence of shared memory, but not very much in implementation. They communicate via explicit messages and are commonly juggled continuously in time-sharing by every OS written after 1980.
• an actor model, like the one of Erlang, where actors substitute processes as the basic unit of computation (there's a whole mathematical theory behind concurrency based on actors).

Take away point: multiple independent units of computation are better leveraged if you throw away the abstraction level of a single execution flow and incorporate them in a programming model.

At the cluster level

When even a powerful machine doesn't cut it, replicating an application over a cluster is the only mean to increase performance or support more users simultaneously. Other reasons for moving to the parallel use of multiple machines are just their costs (N inexpensive servers costs less than a single server N times faster) and the built-in redundancy of this model. Many web applications, for example, distribute HTTP requests across a cluster of servers so that in case of a failure only 1/N users are affected before recovery takes place.

Yet parallelize an application over multiple machines is not banal. For a stateless part, like an HTTP server executing PHP code, is just a matter of copying files and balancing the requests; for a stateful component like a database, entire books have been written on the problem.

Take away point: throwing more hardware at the problem is a good idea, but it isn't always going to magically solve it.

Amdahl's law

In fact, when talking about parallelism, the first example is always an embarassingly parallel problem, like rendering a bunch of frames or simply summing the elements of a large array.

But not all problems are like that: in general, the time needed for an algorithm is divided into two parts, the sequential and parallel fractions. Parallelism can decrease the time needed for the P fraction, but cannot do anything for the S one.

The simple formula for the speedup by introducing N independent processors is:

1/((1-P) + P/S)

If you apply it simply to the execution time, you get that a time T on a single execution unit becomes:

T' = PT/N + (1-P)T

Tthe sequential fraction will never become shorter, no matter how many processors or machines you add.

Take away point: static analysis is no good in parallelism as in profiling; you must find out if a fraction of your code is large enough to gain significant performance before parallelizing it.

Conclusion

Parallelism is a difficult problem, that we're trying to solve at every level from the CPU instruction to the room full of servers. Our programming models may change in the future to exploit it, yet not every problem is prone to be solved by this model. Now you have started your journey into it...