Instruction-level parallelism: scheduling, superscalar and VLIW

A pipeline overlaps instructions in time, but at best it completes one per cycle. To go faster, a processor must find instructions that do not depend on one another and execute them at the same time. The amount of such independence in a program is its instruction-level parallelism, or ILP. Exploiting ILP has driven processor performance for decades, through compiler scheduling, multiple-issue pipelines, very long instruction words and the out-of-order cores of lesson 6. This lesson covers the approaches that find parallelism before execution, statically, and the simplest hardware that issues more than one instruction per cycle.

Core B, the second NS-5 candidate, is a dual-issue in-order processor: each cycle it can start up to two instructions, provided they are independent and do not both need the single memory port. Its measured CPI of 0.90, below 1.0, is the payoff. Jonah wants to know how close to the ideal of 0.5 it could come on the radar filter, and what the compiler would have to do to get there.

Dependences limit parallelism

Three kinds of dependence constrain the order of instructions. A true data dependence, or read after write, exists when an instruction uses a result an earlier one produces; it reflects the flow of values and cannot be removed, only waited for. A name dependence exists when two instructions use the same register or memory location without any value flowing between them. An antidependence, write after read, occurs when a later instruction writes a register an earlier one reads; an output dependence, write after write, when two instructions write the same register. Name dependences arise because there are only so many register names, and they can be removed by renaming, either by the compiler choosing different registers or by hardware, as lesson 6 shows. Control dependences tie instructions to the branches that decide whether they execute.

These dependences form a graph, and the longest path through it, weighted by instruction latencies, sets a lower bound on execution time however many units the processor has. The available ILP in a block of code is roughly the number of instructions divided by the length of that critical path. Ordinary integer code inside a single basic block, the straight-line code between branches, often has an ILP of only two or three. Finding more requires looking across branches and loop iterations.

Static scheduling and loop unrolling

A compiler that knows the pipeline's latencies can reorder instructions to keep the pipeline busy, as long as it preserves the dependences. Lesson 3 showed the simplest case, moving an independent instruction between a load and its use. Inside a short loop body there is often not enough independent work to fill the gaps, so the compiler enlarges the body by loop unrolling: it replicates the body several times, adjusts the index and the loop test, and gives each copy its own registers. The copies are independent of one another, so the scheduler can interleave them, issuing all the loads first, then all the multiplies, then the adds and stores, hiding each latency behind the other copies' work.

Unrolling also removes overhead. A loop that processes one element per iteration spends instructions on incrementing pointers and testing the end condition every time; unrolled by four, it spends them once per four elements. The costs are larger code, which strains the instruction cache and the NS-5's flash, more registers, which may run out and force spills to memory, and the need for a cleanup loop when the trip count is not a multiple of the unroll factor. Software pipelining is a related technique that overlaps successive iterations in a steady-state loop body without fully replicating it, issuing, for example, the load for iteration i + 2, the multiply for iteration i + 1 and the store for iteration i in the same loop pass.

Multiple issue

A processor that issues more than one instruction per cycle is called multiple-issue, and its ideal CPI is below one. Architects often use the reciprocal, instructions per cycle or IPC, for such machines: a dual-issue core has an ideal IPC of 2. There are two broad families. Superscalar processors fetch a sequential stream of ordinary instructions and decide in hardware, each cycle, how many of the next ones can issue together. Very long instruction word processors leave that decision to the compiler, which packs independent operations into wide instruction words that the hardware issues as a unit.

In-order superscalar processors

The simplest superscalar is a dual-issue in-order pipeline like Core B. It fetches two instructions per cycle, and an issue stage checks a few rules before sending both down the pipeline. The second instruction may not depend on the first, since their results would not be ready in time. The pair must not exceed the available functional units: Core B has two ALUs but one memory port and one multiplier, so two loads cannot go together. And issue is in order, so if the first instruction must wait for an operand, the second waits too, even if it is ready. Each extra issue slot multiplies the hardware for register ports, forwarding paths and hazard checks, which grow roughly with the square of the width, so in-order superscalars rarely exceed two or three wide.

Jonah models the filter loop y[i] = y[i] + c × x[i] to see how much scheduling helps. The model issues instructions in order, up to the machine's width each cycle, stopping when an operand is not ready or when a second memory operation would need the busy port. Loads deliver their value two cycles after issue and multiplies three. It compares the original loop with one unrolled four times and scheduled with all loads first.

# In-order issue timing for a filter loop: single issue vs dual issue, before and after unrolling
LAT = {"lw": 2, "mul": 3, "add": 1, "addi": 1, "sw": 1, "bne": 1}
MEM = {"lw", "sw"}

def cycles(prog, width):
    ready, cyc, i = {}, 0, 0
    while i < len(prog):
        cyc += 1
        issued, mem_used = 0, False
        while i < len(prog) and issued < width:
            op, rd, srcs = prog[i]
            if any(ready.get(r, 0) > cyc for r in srcs): break      # operand not ready: stop (in order)
            if op in MEM and mem_used: break                        # one memory port
            if rd: ready[rd] = cyc + LAT[op]
            mem_used |= op in MEM; issued += 1; i += 1
    return cyc

# y[i] = y[i] + c * x[i] for one element per iteration
loop = [("lw", "t0", ["a0"]), ("lw", "t1", ["a1"]), ("mul", "t2", ["t0", "s0"]),
        ("add", "t3", ["t1", "t2"]), ("sw", None, ["t3", "a1"]),
        ("addi", "a0", ["a0"]), ("addi", "a1", ["a1"]), ("bne", None, ["a0", "a2"])]
# unrolled by 4 and scheduled: loads first, then multiplies, adds, stores
u = []
for k in range(4): u += [("lw", f"x{k}", ["a0"]), ("lw", f"y{k}", ["a1"])]
for k in range(4): u += [("mul", f"m{k}", [f"x{k}", "s0"])]
for k in range(4): u += [("add", f"r{k}", [f"y{k}", f"m{k}"])]
for k in range(4): u += [("sw", None, [f"r{k}", "a1"])]
u += [("addi", "a0", ["a0"]), ("addi", "a1", ["a1"]), ("bne", None, ["a0", "a2"])]

for name, prog, elems in (("original", loop, 1), ("unrolled x4", u, 4)):
    for w in (1, 2):
        c = cycles(prog, w)
        print(f"{name:12s} width {w}: {c:2d} cycles for {elems} element(s) = {c/elems:.2f} cycles/element, IPC {len(prog)/c:.2f}")

original     width 1: 10 cycles for 1 element(s) = 10.00 cycles/element, IPC 0.80
original     width 2:  8 cycles for 1 element(s) = 8.00 cycles/element, IPC 1.00
unrolled x4  width 1: 23 cycles for 4 element(s) = 5.75 cycles/element, IPC 1.00
unrolled x4  width 2: 17 cycles for 4 element(s) = 4.25 cycles/element, IPC 1.35

The original loop takes 10 cycles per element on a single-issue machine and 8 on a dual-issue one: the second issue slot helps little, because almost every instruction waits for the one before. Unrolled and scheduled, the loop needs 5.75 cycles per element with one issue slot and 4.25 with two, and the dual-issue IPC rises from 1.00 to 1.35. The remaining limit is the single memory port: each element needs two loads and a store, so at least three cycles per element are spent on memory, which no amount of scheduling can remove. A second load port, or packed loads that bring in several elements at once, would be needed to go further.

VLIW: letting the compiler decide

A very long instruction word processor exposes its functional units directly. Each instruction word contains a slot for each unit, for example two integer operations, a memory operation, a multiply and a branch, and the hardware issues all slots together without checking dependences. The compiler is responsible for filling the slots with independent operations and for honouring every latency, inserting no-operations where it cannot find work. The hardware is simple and power-efficient, which is why VLIW designs dominate digital signal processors, where loops are regular and the compiler can schedule them well.

VLIW has well-known weaknesses for general-purpose code. Code size grows because empty slots still occupy space, although compression schemes reduce the waste. Compiled code is tied to one machine's latencies and slot counts, so a new implementation may need recompiling. And the compiler cannot know at compile time which loads will miss in the cache or which way data-dependent branches will go, so its schedule is pessimistic or stalls entirely. The most ambitious general-purpose VLIW-style family, built in the late 1990s and 2000s with explicitly parallel instruction encoding, did not win a broad market, partly for these reasons. Dynamic scheduling in hardware, covered next lesson, won the general-purpose market instead.

Limits of instruction-level parallelism

How much ILP exists in real programs? Idealized studies that assume perfect branch prediction, unlimited renaming, perfect memory disambiguation and infinite resources find large amounts in many programs, sometimes hundreds of instructions per cycle. Every realistic limit cuts that down sharply. A window of a few hundred instructions, imperfect prediction, finite registers and real cache latencies bring the achievable IPC on typical integer programs to the range of about two to four on the widest practical cores, and the hardware cost and power of going wider grow faster than the benefit. By the mid-2000s this diminishing return, together with the power wall of lesson 1, pushed the industry toward thread-level parallelism with multiple cores and data-level parallelism with vector units, the subjects of lessons 10 and 11.