FACTOID # 2: Puerto Rico has roughly the same gross state product as Montana, Wyoming and North Dakota combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > 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 Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Compiler optimization is the process of tuning the output of a compiler to minimise some attribute (or maximise the efficiency) of an executable program. ... An instruction pipeline is a technique used in the design of microprocessors and other digital electronic devices to increase their performance. ...

  • Avoid pipeline stalls by rearranging the order of instructions.
  • Avoid illegal or semantically ambiguous operations (typically involving subtle instruction pipeline timing issues or non-interlocked resources.)

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). In computer architecture, a hazard is a potential problem that can happen in a pipelined processor. ...

Contents

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: In computing, a basic block is a straight-line piece of code without any jumps or jump targets in the middle; jump targets, if any, start a block, and jumps end a block. ... In computer architecture, a hazard is a potential problem that can happen in a pipelined processor. ...

  1. Read after Write (RAW or "True"): Instruction 1 writes a value used later by Instruction 2. Instruction 1 must come first, or Instruction 2 will read the old value instead of the new.
  2. Write after Read (WAR or "Anti"): 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.
  3. Write after Write (WAW or "Output"): 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 I1 to I2 if I1 must come before I2 due to a dependency. Then, any topological sort of this graph is a valid instruction schedule. This article just presents the basic definitions. ... In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of the nodes of the graph such that x comes before y if theres a directed path from x to y in the DAG. An equivalent definition is that each node comes before...


The phase order of Instruction Scheduling

Instruction scheduling may be done either before or after register allocation or both before and after it. The advantage of doing it before register allocation is that this results in maximum parallelism. The disadvantage of doing it before register allocation is that this can result in the register allocator needing to use a number of register exceeding those available. This will cause spill/fill code to be introduced which will reduce the performance of the section of code in question. In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers. ...


If the architecture being scheduled has instruction sequences that have potentially illegal combinations (due to a lack of instruction interlocks) the instructions must be scheduled after register allocation. This second scheduling pass will also improve the placement of the spill/fill code.


If scheduling is only done after register allocation then there will be false dependencies introduced by the register allocation that will limit the amount of instruction motion possible by the scheduler. In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers. ...


Types of Instruction Scheduling

There are several types of instruction scheduling:

  1. Basic Block Scheduling: instructions can't move across basic block boundaries.
  2. Global scheduling: instructions can move across basic block boundaries.
  3. Modulo Scheduling: another name for software pipelining, which is a form of instruction scheduling if properly implemented.

In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. ...

See also

Computer science Portal

  Results from FactBites:
 
Instruction scheduling - Wikipedia, the free encyclopedia (494 words)
Instruction scheduling is typically done on a single basic block.
Instruction scheduling may be done either before or after register allocation or both before and after it.
If scheduling is only done after register allocation then there will be false dependencies introduced by the register allocation that will limit the amount of instruction motion possible by the scheduler.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m