Instruction scheduling

Encyclopedia : I : IN : INS : Instruction scheduling

In computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines. Put more simply, without changing the meaning of the code, it tries to

avoid pipeline stalls by rearranging the order of instructions.
order the instructions to avoid duplicated memory access

The pipeline stalls can be caused by structural hazards(processor resource limit), data hazards (output of one instruction needed by another instruction) and control hazards (branching).

Data hazards

Instruction scheduling is typically done on a single basic block. In order to determine whether rearranging the block's instructions in a certain way preserves the behavior of that block, we need the concept of a data dependency. There are three types of dependencies, which also happen to be the three data hazards:

Read after Write (RAW): Instruction 1 writes a value used by later Instruction 2. Instruction 1 must come first, or Instruction 2 will read the old value instead of the new.
Write after Read (WAR): Instruction 1 reads a location that is later overwritten by Instruction 2. Instruction 1 must come first, or it will read the new value instead of the old.
Write after Write (WAW): Two instructions both write the same location. They must occur in their original order.

To make sure we respect these three types of dependencies, we construct a dependency graph, which is a directed graph where each vertex is an instruction and there is an edge from I₁ to I₂ if I₁ must come before I₂ due to a dependency. Then, any topological sort of this graph is a valid instruction schedule.

Instruction scheduling

Data hazards

See also