Superscalar Issue

A superscalar processor starts more than one instruction per cycle. Where a simple pipeline can at best finish one instruction each cycle, a two-wide or four-wide design can finish two or four, if the program allows it. It sounds like simply copying the pipeline, but the instructions in a group can depend on each other, need the same hardware, or be cut off by a branch. This article explains how a superscalar pipeline works, what limits it, what width really buys on real programs, and why wider designs get expensive so quickly.

11 min read | Intermediate

What You'll Learn

• Explain what instructions per cycle (IPC) means and how width raises it
• List what stops two instructions from being issued together
• Describe what a wider pipeline costs in hardware
• Read measured results for in-order issue at several widths

Past One Instruction per Cycle

A five-stage pipeline has a CPI that can approach 1 but never pass it. A superscalar design goes past that limit by duplicating hardware, so that several instructions move through each stage at once:

Above a CPI of 1, it is easier to use its inverse, IPC, instructions per cycle. A two-wide pipeline, also called dual-issue, has a peak IPC of 2. Note the difference from a deeper pipeline. Deepening raises frequency by doing less per cycle. Going wider does more per cycle. The two can be combined, and all large processors do both. The Performance Equation applies as before, with a lower CPI.

The word issue means sending an instruction to an execution unit. In-order issue means that instructions leave decode in program order: if one must wait, those behind it wait too. This is the simplest kind of superscalar, and this article is about it. Out-of-Order Execution and Register Renaming removes that limit.

What Stops a Pair

Two instructions can only go together if all these hold:

• No data dependence between them. In add a0,a1,a2 followed by sub a3,a0,a4, the sub needs the add's result, which does not exist until the end of the same cycle. It must wait for the next one, as Data Hazards and Forwarding explains.
• Hardware is available. A dual-issue core may have two ALUs but just one load/store unit and one multiplier. Two loads in a row must split. This is a structural hazard.
• Earlier instructions in the group don't change the flow. If the first of a pair is a taken branch, the second must not run.

The logic that checks all this runs in decode, on every cycle, and is called issue logic, or the dual-issue check. It compares the destination of the first instruction with both sources of the second, and it checks the instruction classes. It also needs to check each against instructions already in the pipeline, as a single-issue design does.

Here is a small example on a two-wide design with one load/store unit. These five instructions are not all pairable:

lw   a5,0(a4)     # pair 1: load
addi a4,a4,4      #         independent, goes with it
add  a0,a0,a5     # pair 2: needs a5, a load-use wait of 1 cycle
addi a1,a1,-1     #         independent, goes with it
bnez a1,loop      # pair 3: alone; depends on a1

The five take 4 cycles, including the empty cycle for the load, against 6 cycles on a single-issue design with the same stall. That is an IPC of 1.25, well below the peak of 2. The width is rarely filled.

What Width Buys

An experiment shows how much of the width real programs can use. A model of in-order issue was run on the instruction traces of six small programs. It assumes perfect branch prediction, and that any instructions can go in any slot, up to the width, with a load taking 2 cycles to return. That makes these results an upper bound for in-order issue:

Going from 1 to 2 wide gives a good gain: an IPC of about 1.35 to 1.85. Going from 2 to 4 helps some programs and not others. The checksum gets almost nothing: 1.63 to 1.67. Its instructions form a long chain, each one using the result of the one before, so it can't start them together, however many slots there are. The memory copy also stalls at about 1.75. The matrix and linked-list programs reach nearly 3, though remember that this is a limit, with no branch penalties.

This is the central finding of superscalar design. Programs contain a limited amount of instruction-level parallelism (ILP) within a small window, because of dependences. Doubling the width doesn't come close to doubling the speed.

What Width Costs

Hardware cost grows faster than width, which is why wide designs are so expensive:

• Fetch must deliver several instructions per cycle. They may cross a cache line, or a taken branch may end the group, which leaves empty slots. Getting 4 useful instructions each cycle is a real achievement for a front end.
• Decode needs one decoder per slot. RISC-V's fixed 4-byte format makes that simple. The C extension complicates things, because instruction boundaries are not known until the previous instruction is looked at. x86 is much worse, since its instructions vary from 1 to 15 bytes.
• Register file ports grow with width. Each slot reads two registers and writes one, so a 4-wide design needs 8 read ports and 4 write ports. Area grows with the square of the port count, and it gets slower.
• Forwarding grows faster still. Each result must reach each input of each ALU, so paths grow with the square of the width, and the wires are long. This often limits the clock.
• Issue logic must compare every instruction in the group with every other.

A two-wide core may cost about 1.5 times the area of a one-wide core, and a four-wide core many times more. Power follows area, and more speculation means more wasted energy on wrong paths. PPA Trade-offs and Amdahl's Law gives the method for weighing that. Past 2 wide, a pure in-order design usually isn't worth the trouble: the gain shrinks while the cost climbs. That is why designs of 4 wide or more are almost always out-of-order.

The Compiler Can Help

A compiler that knows the pipeline can rearrange code to create pairs, keeping dependent instructions apart. GCC's -mtune option selects a scheduling model for a target core. This is the same instruction scheduling discussed in What a Compiler Does. On an in-order design it can make a significant difference, since the hardware won't reorder anything by itself.

Some designers went further and moved the whole job into the compiler. A VLIW, very long instruction word, machine has no issue logic at all. The compiler bundles independent operations into one long instruction, and the hardware simply runs them. It works well for digital signal processors, whose code is regular loops. It did less well for general programs, because the compiler can't know how long memory takes, and because each new machine would need recompiled code. Intel's Itanium family was a well-known attempt in this direction, and it did not last.

Macro-Op Fusion

A related trick goes the other way. Some pairs of instructions are so common that a decoder can merge them into one internal operation, such as a compare and a branch on x86, or a lui and addi pair on RISC-V. The pair then uses one slot. Fusion gets some of the gain of a richer instruction set, with a simple base one. ISA Design Choices discusses the idea.

Width and Branches

A wide pipeline makes every branch worse. If 4 instructions enter per cycle, then a 10-cycle misprediction loses up to 40 instruction slots, rather than 10. With a branch every 5 or 6 instructions, the front end must predict more than one branch per cycle, and a taken branch in the middle of a group wastes the rest of the slots. That is why large cores have such strong predictors, as Why Branches Hurt explains. The model above assumed perfect prediction, so real IPC figures are lower.

Asymmetric Pipelines

Real dual-issue cores rarely have two identical pipes. Giving both slots a load/store unit, a multiplier and a branch unit would nearly double the area for little gain, since those instructions rarely come in pairs. So one pipe does everything, and the second handles only simple arithmetic, or a mix chosen from a study of real instruction pairs. Issue logic then sends each instruction to a pipe that can run it. If two memory instructions arrive together, the second waits a cycle. The mix of units is chosen from data on which pairs occur most often, in the spirit of making the common case fast.

Some large cores fetch two predicted groups per cycle, so that a taken branch in the middle of a group no longer wastes the slots after it.

Common Mistakes