About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Approximation algorithms for scheduling arithmetic expressions on pipelined machines
Abstract
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.