Exploiting Instruction-Level Parallelism (ILP)

Exploiting Instruction‒Level Parallelism (ILP)

• We have seen that Instruction‒Level Parallelism (ILP) refers to a processor's ability to execute multiple instructions simultaneously. Programs naturally contain operations that are independent of each other and exploiting ILP means identifying these independent instructions and executing them in parallel to improve overall performance.

• Modern computer systems use a combination of hardware and software techniques to exploit ILP. These techniques help reduce stalls, increase throughput and make better use of CPU resources.

1. Hardware‒based Techniques for Exploiting ILP

Superscalar architecture:

■ A superscalar processor issues and executes multiple instructions per clock cycle.

 ♦ The hardware dynamically selects independent instructions.

 ♦ It supports parallel pipelines.

 ♦ Example : Most modern CPUs (Intel, ARM, AMD).

Dynamic scheduling

■ Dynamic scheduling allows the CPU to reorder instructions at runtime to avoid pipeline stalls.

 ♦ Eliminates hazards caused by dependencies.

 ♦ Uses structures like the Tomasulo algorithm.

Out‒of‒order execution

■ The processor executes instructions as soon as their operands are available, not free strictly in program order.

 ♦ Greatly improves ILP.

 ♦ Works with register renaming, reservation stations and ROB.

Register renaming

■ Hardware assigns physical registers to remove false dependencies (WAR, WAW).

 ♦ Prevents pipeline stalls.

 ♦ Usually implemented using a rename table and Reorder Buffer (ROB).

Branch prediction

■ Branch predictors try to guess the outcome of conditional branches before they execute.

 ♦ Reduces control hazards.

 ♦ Enables more instructions to be fetched and executed in parallel.

Speculation

■ The CPU executes instructions ahead of time based on predicted paths.

 ♦ Works with branch prediction.

 ♦ If the prediction is correct, performance increases.

 ♦ If incorrect → results are discarded using ROB.

Reorder Buffer (ROB)

■ A hardware structure used to:

 ♦ Commit instructions in order,

 ♦ Support precise exceptions,

 ♦ Store speculative results.

 ♦ It enables out‒of‒order execution while maintaining program correctness.

2. Software‒based Techniques for Exploiting ILP

Compiler scheduling

■ Compilers try to rearrange instructions during compilation to reduce stalls. This is called static scheduling.

VLIW (Very Long Instruction Word)

■ In VLIW processors, the compiler packs multiple independent instructions into a single long word.

 ♦ Parallelism is decided at compile time, not by hardware.

 ♦ Hardware is simpler but requires intelligent compilers.

Software speculation

■ Compilers may speculatively move instructions above branches and rely on hardware to handle exceptions.

Software register renaming

■ Some architectures allow compilers to assign registers to avoid artificial dependencies.

3. Techniques using Both Software and Hardware

Multiple Issue

■ Hardware‒based in superscalar systems

■ Software‒based in VLIW. This allows several instructions to be issued per cycle.

Speculation

■ Implemented by both hardware (branch predictors, ROB) and compilers (moving instructions).

Register Renaming

■ Mainly hardware‒based, but compilers can also perform register allocation to reduce dependencies.

Review Questions

1. What is Instruction‒Level Parallelism (ILP)? Explain why exploiting ILP is important in improving processor performance.

2. Explain various techniques for exploiting ILP.