Science Fair Project Encyclopedia
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, it tries to rearrange the order of instructions so that a value is not used right after it is computed, which causes pipeline stalls, without changing the meaning of the code.
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 an undirected graph where each vertex is an instruction and there is an edge from I1 to I2 if I1 must come before I2 due to a dependency. Then, any topological sort of this graph is a valid instruction scheduling.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details