Publication
ACM Transactions on Programming Languages and Systems (TOPLAS)
Paper

Scheduling expressions on a pipelined processor with a maximal delay of one cycle

Download paper

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. © 1989, ACM. All rights reserved.

Date

01 Jan 1989

Publication

ACM Transactions on Programming Languages and Systems (TOPLAS)

Authors

Resources

Share