Efficient instruction scheduling for a pipelined architecture (with retrospective)

Steven S. Muchnick, Phillip B. Gibbons

TL;DR

This paper presents an efficient compiler algorithm for optimizing instruction scheduling in pipelined architectures. By using a directed acyclic graph (DAG) to represent dependencies and a heuristic selection method without lookahead, the algorithm significantly reduces pipeline interlocks with a practical O(n²) worst-case runtime, making code run faster on modern processors.

What Problem Does This Paper Address?

Modern processors use pipelining to execute instructions concurrently, leading to faster execution. However, this can cause "pipeline hazards" where an instruction needs a result or resource that isn't yet available from a preceding instruction. These hazards force the pipeline to stall, slowing down execution. While hardware can detect and resolve some hazards, it's expensive and limited. Software-based solutions, particularly during compilation, are more practical. This paper tackles the challenge of reordering instructions within a basic block (a sequence of code without branches) to minimize these pipeline stalls, aiming for an efficient and effective compiler-level solution.

Methods

The core of the paper's approach is a two-step process applied to each basic block:

  1. Dependency DAG Construction: The algorithm first constructs a directed acyclic graph (DAG) where nodes represent instructions and edges represent dependencies. An edge from instruction A to instruction B means A must execute before B. This DAG captures register, memory, and processor state dependencies. A key innovation here is that their DAGs serialize definitions vs. definitions of the same resource, which prevents scheduling deadlocks and simplifies the scheduling process. They also handle carry/borrow bits specially by creating subgraphs.
  2. Heuristic Scheduling without Lookahead: Once the DAG is built, the algorithm schedules instructions by selecting from "candidate" instructions (those whose predecessors have been scheduled). The selection is guided by two main heuristics:
  3. Prioritize instructions that won't interlock with the previously scheduled instruction.
  4. When choices exist, pick instructions that are most likely to cause interlocks with future instructions. This "pair-wise" approach aims to schedule problematic instructions early when more options are available. Crucially, this selection method does not require looking ahead at instructions not yet candidates, which significantly reduces the algorithm's worst-case runtime complexity.

Datasets

Not discussed in the paper. The paper uses a sample code sequence (Figure 1) and refers to the "Acker benchmark" and "Sieve benchmark" for evaluating the effectiveness of their algorithm.

Key Insights and Ideas

  • DAGs for Deadlock Prevention: Serializing definitions vs. definitions in the dependency DAG is a clever way to guarantee that there's always a schedulable instruction, thus avoiding scheduling deadlocks and eliminating the need for lookahead.
  • Heuristics for Practical Efficiency: The paper demonstrates that a carefully chosen set of static heuristics, focusing on immediate interlock potential and future choices, can achieve good results without the computational cost of lookahead.
  • Balancing Compiler Passes: The effectiveness of the algorithm is shown to be influenced by other compiler passes, particularly register allocation and aliasing analysis. Better aliasing information significantly improves the results.
  • Generalizability of DAGs: The dependency DAGs are presented as useful for other code optimizations beyond instruction scheduling, such as code hoisting and loop-invariant code motion.

Key Results

  • The algorithm reduces pipeline interlocks significantly. For the sample code in Figure 1, it reduces four interlocks to one.
  • On the Acker benchmark, the algorithm removes 15 out of 19 avoidable interlocks without inserting "no-ops."
  • For many proposed machine implementations, it removes 100% of avoidable interlocks.
  • The worst-case runtime complexity is O(n²), where n is the number of instructions in a basic block. In practice, the runtime is observed to be linear.
  • The algorithm's effectiveness is sensitive to assumptions about memory referencing; better aliasing information improves results.

Limitations and Future Work

  • Scope: The current algorithm operates only within basic blocks. Extending it to handle scheduling across basic blocks, especially for architectures with long pipelines or multiple execution units, is a significant area for future work. Techniques like trace scheduling are mentioned as relevant.
  • Average Case Analysis: The authors suggest developing a model for an average instruction sequence to predict the algorithm's expected runtime more accurately.
  • Multi-cycle Hazards: While the algorithm can be extended to handle multi-cycle pipeline hazards, this increases its complexity.
  • Carry/Borrow Subgraphs: While useful for computationally intensive programs, these subgraphs don't significantly improve scheduling for most programs.

Summary updated

Abstract

As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least O(n4). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an O(n2) worst-case runtime.
BibTeX
@inproceedings{muchnick1986efficient,
  author = {Steven S. Muchnick and Phillip B. Gibbons},
  title = {{Efficient instruction scheduling for a pipelined architecture (with retrospective)}},
  booktitle = {Best of PLDI},
  year = {1986},
  doi = {10.1145/989393.989413},
}
Figure