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 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 493–500 (1997)
Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: IEEE Syposium on Foundations of Computer Science, pp. 520–529 (2004)
Bansal, N., Pruhs, K.: Speed scaling to manage temperature. In: Symposium on Theoretical Aspects of Computer Science, pp. 460–471 (2005)
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. Journal of Algorithms 41, 212–224 (2001)
Chen, J.-J., Kuo, T.-W., Lu, H.-I.: Power-saving scheduling for weakly dynamic voltage scaling devices. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 338–349. Springer, Heidelberg (2005)
Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 581–590 (1997)
Graham, R.L.: Bounds for certain multiprocessor anomalies. Bell System Techical Journal 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. Annals of Discrete Mathematics 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. In: SIGACT News (2005)
Kwon, W.-C., Kim, T.: Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Transactions on Embedded Computing Systems (TECS) 4(1), 211–230 (2005)
Li, M., Liu, B.J., Yao, F.F.: Min-energy voltage allocation for tree-structured tasks. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 283–296. Springer, Heidelberg (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: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 14–25. Springer, Heidelberg (2004)
Frances Yao, F., Demers, A.J., Shenker, S.: A scheduling model for reduced cpu energy. In: IEEE Syposium 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 Transactions on Embedded Computing Systems 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
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pruhs, K., van Stee, R., Uthaisombut, P. (2006). Speed Scaling of Tasks with Precedence Constraints. In: Erlebach, T., Persinao, G. (eds) Approximation and Online Algorithms. WAOA 2005. Lecture Notes in Computer Science, vol 3879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11671411_24
Download citation
DOI: https://doi.org/10.1007/11671411_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32207-8
Online ISBN: 978-3-540-32208-5
eBook Packages: Computer ScienceComputer Science (R0)