David Steinberg, Michael Rodeh
Information Processing Letters
Consider a processor which can issue one instruction every machine cycle, but can use its result only d + 1 machine cycles after it has been issued. It is shown that an upper bound for the completion time of an arbitrary list schedule for arbitrary expressions, with possibly common subexpressions, on such machines is greater than the optimum by a factor of 2 - 1 (d + 1). Then a class of scheduling algorithms, called level algorithms, is defined and analyzed. These algorithms sometimes yield bad schedules which can be made arbitrarily close to the upper bound of list schedules. By extending the leveling algorithm, using the lexicographic order criterion similar to that of Coffman-Graham's algorithm, a better result of 2 - 2 (d + 1) is derived. This bound is asymptotically tight. © 1989.
David Steinberg, Michael Rodeh
Information Processing Letters
Michael Rodeh, Vaughan R. Pratt, et al.
Journal of the ACM
David Bernstein, Michael Rodeh
PLDI 1991
Nurit Dor, Michael Rodeh, et al.
PLDI 2003