Intel Threading Building Blocks

Relaxed Sequential Execution

Most parallel programs can run sequentially but will benefit from parallelism when it is present. However, it is very possible to design programs that require parallelism for correct behavior.

Consider a variable swap: A=B and B=A. If we start with A=14 and B=30, do we end with A=30 and B=14 or with A=30 and B=30? If the two assignments can be forced to run in parallel, we get the swap to occur. If that is what we expect, that code must be run in parallel.

This trivial example gives you a hint of what it means to require parallelism and strong synchronization. But such tight synchronization is not the only way to force parallelism. Nontrivial examples tend to be algorithms such as producer-consumer programs that must have two or more threads. For instance, consider a bounded container with a capacity for only two items and a program that has one thread doing PUT PUT PUT and another thread doing GET GET GET, each doing their actions only in triples. Such a program requires interleaving (concurrency).

A program that requires concurrency is more difficult to debug. That is why Threading Building Blocks (and many other concurrent systems, such as OpenMP) assume that a program has a valid sequential execution.

Threading Building Blocks implements a relaxed sequential execution model. The word relaxed refers to the notion that serial programs are actually overly constrained by implicit serial dependencies (such as the program counter) and that the concurrent library ...