An Optimal Instruction Scheduler for Superscalar Processor

Hong Chich Chou, Chung-Ping Chung

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


Performance in superscalar processing strongly depends on the compiler's ability to generate codes that can be executed by hardware in an optimal or near optimal order. Generating optimal code is an NP-complete problem. However, there is a need for highly optimized code, such as in superscalar or real-time systems. In this paper, an instruction scheduling scheme for optimizing a program trace is proposed. Optimized code can be arrived at without much redundant work, if some important features in code are well explored and utilized in scheduling. To formalize the task, two abstract models, one for a superscalar processor and the other for a program trace, are given. These two models reflect most of the characteristics of the scheduling problem. The interrelations between instructions and partial schedules are thoroughly studied, and dominance and equivalence relations on them are defined. These relations are then used to reduce the solution space and eventually help to produce optimal schedules. The results of experiments that show the promise of the proposed scheme are also presented.

Original languageEnglish
Pages (from-to)303-313
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
StatePublished - 1 Jan 1995


  • NP-completeness
  • optimization
  • Pipeline processors
  • prune and search
  • sequencing and scheduling

Fingerprint Dive into the research topics of 'An Optimal Instruction Scheduler for Superscalar Processor'. Together they form a unique fingerprint.

Cite this