instruction scheduling

Also found in: Wikipedia.

instruction scheduling

The compiler phase that orders instructions on a pipelined, superscalar, or VLIW architecture so as to maximise the number of function units operating in parallel and to minimise the time they spend waiting for each other.

Examples are filling a delay slot; interspersing floating-point instructions with integer instructions to keep both units operating; making adjacent instructions independent, e.g. one which writes a register and another which reads from it; separating memory writes to avoid filling the write buffer.

Norman P. Jouppi and David W. Wall, "Available Instruction-Level Parallelism for Superscalar and Superpipelined Processors", Proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 272--282, 1989.

[The SPARC Architecture Manual, v8, ISBN 0-13-825001-4]
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
[11] have exploited a concept of virtual cluster to assist the instruction scheduling for clustered architecture.
The main contributions of this work are (1) force-balanced-two-phase (FBTP) instruction scheduling algorithm to minimize unnecessary inter-cluster data communications and balance the distribution of the access to global register file among the whole execution time; (2) localization-enhanced (LE) register allocation mechanism to minimize unnecessary global register allocation.
New contributors provide additional insight to chapters on register allocation, software pipelining, instruction scheduling, and type systems.
Instruction librarians from the Reference Department take the Library Instruction Scheduling Form, which lists contact information for the faculty member bringing in the class, the number of students expected, where this class will be taught, and the content of the session.
The second part, Advanced Topics, which includes the compilation of object-oriented and functional languages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization for cache-memory hierarchies, can be used for a second-semester or graduate course.
Instruction scheduling, a key phase in most optimizing compilers, is an optimization that exploits instruction-level parallelism (ILP) in modern processors.
The analyst described the Sun architecture as similar to a superscalar design, except that the MAJC compiler would be handling the chip's instruction scheduling rather than it being done in hardware.
Because it is a VLIW, instruction scheduling shifts to the compiler, reducing the cost and complexity of the silicon.
Additionally, this representation is used by the compiler to perform target-specific transformations, including register allocation, instruction scheduling, and branch prediction.
Topics include instruction scheduling with release times and deadlines on ILP processors, data freshness and overload handling in embedded systems, relaxed correctness for firm real-time databases, and operating system support for procedural abstraction in embedded systems.
The problem is that two "equivalent" computations may map to different instruction sequences in different parts of a program, due to differences in register usage and branch labels, instruction scheduling, and profile-directed code layout to improve instruction cache utilization [Pettis and Hansen 1990].
General Terms: Algorithms, Experimentation, Languages Additional Key Words and Phrases: Global instruction scheduling, instruction-level parallelism, software pipelining, speculative code motion, superscalar, VLIW

Full browser ?