Loading...

Scheduling to minimize gaps and power consumption

Demaine, E.D ; Sharif University of Technology | 2007

335 Viewed
  1. Type of Document: Article
  2. DOI: 10.1145/1248377.1248385
  3. Publisher: 2007
  4. Abstract:
  5. 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 + 23 α)-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. Copyright 2007 ACM
  6. Keywords:
  7. Algorithms ; Approximation theory ; Calculations ; Dynamic programming ; Electric power utilization ; Program processors ; Scheduling ; Hardness-of-approximation ; Multi-interval gap scheduling ; Power-saving problem ; Sleep state ; Multiprocessing systems
  8. Source: SPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures, San Diego, CA, 9 June 2007 through 11 June 2007 ; 2007 , Pages 46-54 ; 159593667X (ISBN); 9781595936677 (ISBN)
  9. URL: https://dl.acm.org/doi/10.1145/1248377.1248385