Code duplication: An assist for global instruction scheduling
David Bernstein, Doron Cohen, et al.
MICRO 1991
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 Bernstein, Doron Cohen, et al.
MICRO 1991
Alon Itai, Michael Rodeh
Journal of Algorithms
David Bernstein, Izidor Gertner
ACM Transactions on Programming Languages and Systems (TOPLAS)
Michael Rodeh, Mooly Sagiv
Journal of the ACM