Multi-core & Multi-threaded: A New Era in Computing

The way we're proposing to guess these values is through a software technique called a "precomputation slice." The compiler includes a spawning instruction in the red code that spawns a speculative thread. The speculative thread starts precomputing the values it will most likely need. This precomputation is done very fast, since it is not required to be correct. The objective is to generate a slice that computes the thread input values correctly most of the time, but with a much smaller overhead than the one required for a safe computation.

When the red thread arrives at the beginning of the yellow one, the precomputed values are validated, and in case of misspeculation the yellow thread is squashed; see Figure 1(b).

[Click image to view at full size]

Figure 1: (b) Precomputation slices help dismiss unlikely dependencies and speculatively compute input values.

This figure also illustrates a speculation on a memory dependence. In this case, there is an ambiguous dependence through pointers P and Q. If the compiler suspects that this dependence does not occur, it can simply ignore it. At runtime, the hardware checks whether this dependence actually occurs; if this is the case, the speculative thread is squashed.

Speculative threads enable the compiler to try all kinds of unsafe, aggressive, optimistic optimizations when generating the precomputation slice. In the end, we end up with a highly optimized code that can precompute these values quickly and still be correct most of the time; see Figure 2.

[Click image to view at full size]

Figure 2: Through a series of "unsafe" optimizations, the compiler generates a very small slice that still compute the thread input values correctly most of the time at a much faster speed.