Instruction pipelining and out-of-order execution

Processors overlap and reorder the steps of many instructions (fetching ahead, predicting branches, running whatever is ready) to finish several per clock tick; a key source of CPU speed beyond raw clock rate.

Chips & processorsHardware
  1. 1961

    First version

    IBM Stretch team (Stephen Dunwell, John Cocke, Harwood Kolsky; lookahead proposed by Gene Amdahl and John Backus)

    Image: The wub · CC BY-SA 4.0 · Wikimedia Commons
  2. 1964
    CDC 6600 scoreboard

    CDC 6600 scoreboard

    Ten functional units work in parallel; a 'scoreboard' lets later instructions run as soon as their inputs are ready.

    Image: Steve Jurvetson from Menlo Park, USA · CC BY 2.0 · Wikimedia Commons
  3. 1967
    Tomasulo's algorithm (IBM System/360 Model 91)

    Tomasulo's algorithm (IBM System/360 Model 91)

    Register renaming removes false dependencies between instructions, enabling fuller out-of-order execution.

    Image: Marcin Wichary from San Francisco, Calif. · CC BY 2.0 · Wikimedia Commons
  4. 1995
    Out-of-order x86 (Intel Pentium Pro)

    Out-of-order x86 (Intel Pentium Pro)

    Speculative out-of-order execution with a 40-entry reorder buffer comes to x86, the blueprint for later PC and server CPUs.

    Image: Capitalistcakes · CC0 · Wikimedia Commons

Contested: Zuse's Z1 (1939) and Z3 (1941) already overlapped simple steps, and the University of Illinois' ILLIAC II is credited alongside Stretch as a seminal pipelined design.

See it on the timeline