4.1.1 Pipelined CPUs

Figure: CPUs Old and New
\resizebox{3in}{!}{\includegraphics{cartoons/whippersnapper}}

In the early 1980s, the typical microprocessor fetched an instruction, decoded it, and executed it, typically taking at least three clock cycles to complete one instruction before proceeding to the next. In contrast, the CPU of the late 1990s and early 2000s will be executing many instructions simultaneously, using a deep ``pipeline'' to control the flow of instructions internally to the CPU, this difference being illustrated by Figure [*].

Achieving full performance with a CPU having a long pipeline requires highly predictable control flow through the program. Suitable control flow can be provided by a program that executes primarily in tight loops, for example, programs doing arithmetic on large matrices or vectors. The CPU can then correctly predict that the branch at the end of the loop will be taken in almost all cases. In such programs, the pipeline can be kept full and the CPU can execute at full speed.

Figure: CPU Meets a Pipeline Flush
\resizebox{3in}{!}{\includegraphics{cartoons/pipeline}}

If, on the other hand, the program has many loops with small loop counts, or if the program is object oriented with many virtual objects that can reference many different real objects, all with different implementations for frequently invoked member functions, then it is difficult or even impossible for the CPU to predict where a given branch might lead. The CPU must then either stall waiting for execution to proceed far enough to know for certain where the branch will lead, or guess -- and, in the face of programs with unpredictable control flow, frequently guess wrong. In either case, the pipeline will empty and have to be refilled, leading to stalls that can drastically reduce performance, as fancifully depicted in Figure [*].

Unfortunately, pipeline flushes are not the only hazards in the obstacle course that modern CPUs must run. The next section covers the hazards of referencing memory.

Paul E. McKenney 2011-12-16