Instruction-Level Parallelism & Out-of-Order Execution

instruction-level parallelism

Imagine a to-do list of small chores. Some chores depend on each other — you must brew the coffee before you can drink it — but many do not: watering a plant and checking the mail have nothing to do with each other, so a second pair of hands could do them at the same time. Instruction-level parallelism (ILP) is exactly this idea applied to the instructions inside one program: among the stream of instructions a single CPU is running, how many could in principle execute at the same instant because they do not depend on each other's results?

Concretely, suppose a program contains: (1) a = b + c, (2) d = e + f, (3) g = a + d. Instructions (1) and (2) are independent — neither needs the other's output — so a machine with two adders could do both in the same cycle. Instruction (3) must wait for both, because it reads a and d. The amount of ILP here is small but real: two of the three operations overlap. ILP is the raw material that superscalar issue, pipelining, and out-of-order execution all try to harvest. A program with lots of independent work has high ILP; a tightly chained calculation where each step feeds the next has almost none.

The honest point is that ILP is a property of the program, not just the hardware. Hardware (out-of-order engines, multiple execution units) and the compiler (scheduling, unrolling loops) can expose and exploit ILP, but they cannot create parallelism that the algorithm does not contain. A long dependence chain caps how fast you can possibly go no matter how wide the machine. This ceiling — the limits of ILP — is one of the deep reasons the industry eventually turned to multiple cores instead of ever-wider single cores.

Summing an array as total += a[i] in a simple loop has very low ILP — each add depends on the previous total. Splitting it into four partial sums (s0,s1,s2,s3) that are combined at the end exposes ILP: the four chains are independent and can overlap.

Independent instructions overlap; a chain of dependent ones cannot, no matter how wide the hardware.

ILP is not a knob you set; it is how much independent work the code already has. Marketing that promises a 'wider' core makes everything faster is misleading — code with a long dependence chain ignores the extra width entirely.

Also called
ILP