Scheduling to minimize gaps and power consumption

ABSTRACT

This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of "gaps" in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1 + 2<over>3 α)-approximation, and show that dependence on α is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lg n)-approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(√n)-approximation for maximizing throughput given a hard upper bound on the number of gaps.

REFERENCES

• 1: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.530-539, October 17-19, 2004 [doi>10.1109/FOCS.2004.50]
• 2: Philippe Baptiste, Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.364-367, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109598]
• 3: Luca Benini , Alessandro Bogliolo , Giovanni De Micheli, A survey of design techniques for system-level dynamic power management, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.299-316, June 2000 [doi>10.1109/92.845896]
• 4: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 5: U. Feige, M. Hajiaghayi, S. Khanna, and S. Naor. On approximation of minimum-gap scheduling. Unpublished manuscript, 2006.
• 6: C. A. J. Hurkens , A. Schrijver, On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM Journal on Discrete Mathematics, v.2 n.1, p.68-72, February 1989 [doi>10.1137/0402008]
• 7: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 8: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]
• 10: D. B. West. Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
multiprocessor scheduling, power minimization, sleep state