Abstract
We study online job scheduling on a processor that can vary its speed dynamically to manage its power. We attempt to extend the recent success in analyzing total unweighted flow time plus energy to total weighted flow time plus energy. We first consider the non-clairvoyant setting where the size of a job is only known when the job finishes. We show an online algorithm WLAPS that is 8α 2-competitive for weighted flow time plus energy under the traditional power model, which assumes the power P(s) to run the processor at speed s to be s α for some α> 1. More interestingly, for any arbitrary power function P(s), WLAPS remains competitive when given a more energy-efficient processor; precisely, WLAPS is \(16(1+\frac{1}{\epsilon})^2\)-competitive when using a processor that, given the power P(s), can run at speed (1 + ε)s for some ε> 0. Without such speedup, no non-clairvoyant algorithm can be O(1)-competitive for an arbitrary power function [8]. For the clairvoyant setting (where the size of a job is known at release time), previous results on minimizing weighted flow time plus energy rely on scaling the speed continuously over time [5-7]. The analysis of WLAPS has inspired us to devise a clairvoyant algorithm LLB which can transform any continuous speed scaling algorithm to one that scales the speed at discrete times only. Under an arbitrary power function, LLB can give an \(4(1+\frac{1}{\epsilon})\)-competitive algorithm using a processor with (1 + ε)-speedup.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Albers, S., Fujiwara, H.: Energy-efficient algorithms for flow time minimization. ACM Transactions on Algorithms 3(4), 49 (2007)
Andrew, L., Wierman, A., Tang, A.: Optimal speed scaling under arbitrary power functions. ACM SIGMETRICS Performance Evaluation Review 37(2), 39–41 (2009)
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)
Bansal, N., Chan, H.L.: Weighted flow time does not admit O(1)-competitive algorithms. In: Proc. SODA, pp. 1238–1244 (2009)
Bansal, N., Chan, H.L., Lam, T.W., Lee, L.K.: Scheduling for speed bounded processors. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 409–420. Springer, Heidelberg (2008)
Bansal, N., Chan, H.L., Pruhs, K.: Speed scaling with an arbitrary power function. In: Proc. SODA, pp. 693–701 (2009)
Bansal, N., Pruhs, K., Stein, C.: Speed scaling for weighted flow time. SIAM Journal on Computing 39(4), 1294–1308 (2009)
Chan, H.L., Edmonds, J., Lam, T.W., Lee, L.K., Marchetti-Spaccamela, A., Pruhs, K.: Nonclairvoyant speed scaling for flow and energy. In: Proc. STACS, pp. 255–264 (2009)
Chan, H.L., Edmonds, J., Pruhs, K.: Speed scaling of processes with arbitrary speedup curves on a multiprocessor. In: Proc. SPAA, pp. 1–10 (2009)
Chan, S.H., Lam, T.W., Lee, L.K., Ting, H.F., Zhang, P.: Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors. In: Proc. CATS, pp. 3–10 (2010)
Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. Journal of the ACM 50(4), 551–567 (2003)
Lam, T.W., Lee, L.K., Ting, H.F., To, I., Wong, P.: Sleep with guilt and work faster to minimize flow plus energy. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 665–676. Springer, Heidelberg (2009)
Lam, T.W., Lee, L.K., To, I., Wong, P.: Competitive non-migratory scheduling for flow time and energy. In: Proc. SPAA, pp. 256–264 (2008)
Lam, T.W., Lee, L.K., To, I., Wong, P.: Speed scaling functions for flow time scheduling based on active job count. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 647–659. Springer, Heidelberg (2008)
Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theoretical Computer Science 130(1), 17–47 (1994)
Mudge, T.: Power: A first-class architectural design constraint. IEEE Computer 34(4), 52–58 (2001)
Steele, J.M.: The Cauchy-Schwarz master class: An introduction to the art of mathematical inequalities, p. 136. Cambridge University Press, Cambridge (2004)
Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proc. FOCS, pp. 374–382 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, SH., Lam, TW., Lee, LK. (2010). Non-clairvoyant Speed Scaling for Weighted Flow Time. In: de Berg, M., Meyer, U. (eds) Algorithms – ESA 2010. ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15775-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-15775-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15774-5
Online ISBN: 978-3-642-15775-2
eBook Packages: Computer ScienceComputer Science (R0)