Back to Search
Start Over
Backtracking-Based Instruction Scheduling to Fill Branch Delay Slots.
- Source :
- International Journal of Parallel Programming; Dec2002, Vol. 30 Issue 6, p397-418, 22p
- Publication Year :
- 2002
-
Abstract
- Conventional schedulers schedule operations in dependence order and never revisit or undo a scheduling decision on any operation. In contrast, backtracking schedulers may unschedule operations and can often generate better schedules. This paper develops and evaluates the backtracking approach to fill branch delay slots. We first present the structure of a generic backtracking scheduling algorithm and prove that it terminates. We then describe two more aggressive backtracking schedulers and evaluate their effectiveness. We conclude that aggressive backtracking-based instruction schedulers can effectively improve schedule quality by eliminating branch delay slots with a small amount of additional computation. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
MATHEMATICAL analysis
MACHINERY
EQUATIONS
LINEAR systems
COMPUTER systems
Subjects
Details
- Language :
- English
- ISSN :
- 08857458
- Volume :
- 30
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- International Journal of Parallel Programming
- Publication Type :
- Academic Journal
- Accession number :
- 17143306
- Full Text :
- https://doi.org/10.1023/A:1020601110391