Scheduling expressions on a pipelined processor with a maximal delay of one cycle
- 1 January 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 11 (1) , 57-66
- https://doi.org/10.1145/59287.59291
Abstract
Consider a pipelined machine that can issue instructions every machine cycle. Sometimes, an instruction that uses the result of the instruction preceding it in a pipe must be delayed to ensure that a program computes a right value. We assume that issuing of such instructions is delayed by at most one machine cycle. For such a machine model, given an unbounded number of machine registers and memory locations, an algorithm to find a shortest schedule of the given expression is presented and analyzed. The proposed algorithm is a modification of Coffman-Graham's algorithm [7], which provides an optimal solution to the problem of scheduling tasks on two parallel processors.Keywords
This publication has 11 references indexed in Scilit:
- Approximation algorithms for scheduling arithmetic expressions on pipelined machinesJournal of Algorithms, 1989
- Reduced instruction set computersCommunications of the ACM, 1985
- Postpass Code Optimization of Pipeline ConstraintsACM Transactions on Programming Languages and Systems, 1983
- An Almost-Linear Algorithm for Two-Processor SchedulingJournal of the ACM, 1982
- Deterministic Scheduling with Pipelined ProcessorsIEEE Transactions on Computers, 1980
- Scheduling Trees in Parallel/Pipelined Processing EnvironmentsIEEE Transactions on Computers, 1977
- Code Generation for Expressions with Common SubexpressionsJournal of the ACM, 1977
- Optimal Code Generation for Expression TreesJournal of the ACM, 1976
- Code Generation for a One-Register MachineJournal of the ACM, 1976
- Optimal scheduling for two-processor systemsActa Informatica, 1972