|
|
|
|
|
Instruction SchedulingIn 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's computed, which causes pipeline stalls, without changing the meaning of the code. Data dependencies 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. This article is currently incomplete. If you know something about instruction scheduling, please help us finish it.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|