Abstract
We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm | prec | C max . We extend the standard 3-field notation and denote this problem as Sm | prec, energy | C max . We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm | prec | C max to obtain a poly-log(m)-approximation algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55–66 (1998)
Bansal, N., Pruhs, K.: Speed scaling to manage temperature. In: Symposium on Theoretical Aspects of Computer Science, pp. 460–471 (2005)
Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: IEEE Symposium on Foundations of Computer Science, pp. 520–529 (2004)
Brooks, D.M., Bose, P., Schuster, S.E., Jacobson, H., Kudva, P.N., Buyuktosunoglu, A., Wellman, J.-D., Zyuban, V., Gupta, M., Cook, P.W.: Power-aware microarchitecture: design and modeling challenges for next-generation microprocessors. IEEE Micro 20(6), 26–44 (2000)
Chekuri, C., Bender, M.A.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms 41, 212–224 (2001)
Chen, J.-J., Kuo, T.-W., Lu, H.-I.: Power-saving scheduling for weakly dynamic voltage scaling devices. In: Workshop on Algorithms and Data Structures, pp. 338–349 (2005)
Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30(2), 323–343 (1999)
Graham, R.L.: Bounds for certain multiprocessor anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)
Graham, R.L., Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)
Gruian, F., Kuchcinski, K.: Lenes: task-scheduling for low-energy systems using variable voltage processors. In: Asia South Pacific—Design Automation Conference, pp. 449–455 (2001)
Irani, S., Pruhs, K.: Algorithmic problems in power management. SIGACT News 32(2), 63–76 (2005)
Kwon, W.-C., Kim, T.: Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Trans. Embed. Comput. Syst. (TECS) 4(1), 211–230 (2005)
Li, M., Liu, B.J., Yao, F.F.: Min-energy voltage allocation for tree-structured tasks. In: 11th International Computing and Combinatorics Conference (COCOON 2005), pp. 283–296 (2005)
Luo, J., Jha, N.K.: Power-conscious joint scheduling of periodic task graphs and aperiodic task graphs in distributed real-time embedded systems. In: International Conference on Computer Aided Design, pp. 357–364 (2000)
Mishra, R., Rastogi, N., Zhu, D., Mossé, D., Melhem, R.G.: Energy aware scheduling for distributed real-time systems. In: International Parallel and Distributed Processing Symposium, p. 21 (2003)
Mudge, T.: Power: a first-class architectural design constraint. Computer 34(4), 52–58 (2001)
Pruhs, K., Uthaisombut, P., Woeginger, G.: Getting the best response for your erg. In: Scandinavian Workshop on Algorithms and Theory, pp. 14–25 (2004)
Yao, F.F., Demers, A.J., Shenker, S.: A scheduling model for reduced cpu energy. In: IEEE Symposium on Foundations of Computer Science (FOCS 1995), pp. 374–382 (1995)
Yun, H.-S., Kim, J.: On energy-optimal voltage scheduling for fixed priority hard real-time systems. ACM Trans. Embed. Comput. Syst. 2(3), 393–430 (2003)
Zhang, Y., Hu, X., Chen, D.Z.: Task scheduling and voltage selection for energy minimization. In: Design Automation Conference, pp. 183–188 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appears in Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005).
Research of K. Pruhs supported in part by NSF grants CCR-0098752, ANI-0123705, CNS-0325353, CCF-0448196, CCF-0514058, and IIS-0534531.
Research of R. van Stee supported by Alexander von Humboldt-Stiftung.
Rights and permissions
About this article
Cite this article
Pruhs, K., van Stee, R. & Uthaisombut, P. Speed Scaling of Tasks with Precedence Constraints. Theory Comput Syst 43, 67–80 (2008). https://doi.org/10.1007/s00224-007-9070-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-007-9070-1