Approximation algorithms for scheduling arithmetic expressions on pipelined machines

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.