Efficient instruction scheduling for a pipelined architecture (with retrospective)
Lists
Only you see this
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},
}Loading related content...