Nissim Francez, Michael Rodeh
IEEE Transactions on Software Engineering
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.
Nissim Francez, Michael Rodeh
IEEE Transactions on Software Engineering
David Bernstein, Izidor Gertner
ACM Transactions on Programming Languages and Systems (TOPLAS)
David Steinberg, Michael Rodeh
Information Processing Letters
Alon Itai, Michael Rodeh
Journal of Algorithms