Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule

by Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs

Theory of Computing, Volume 8(9), pp. 209-229, 2012

Bibliography with links to cited articles

[1]   Susanne Albers: Energy-efficient algorithms. Comm. ACM, 53(5):86–96, 2010. [doi:10.1145/1735223.1735245]

[2]   Susanne Albers, Fabian Müller, and Swen Schmelzer: Speed scaling on parallel processors. In Proc. 19th Ann. ACM Symp. on Parallel Algorithms and Architectures (SPAA’07), pp. 289–298. ACM Press, 2007. [doi:10.1145/1248377.1248424]

[3]   Nikhil Bansal, David P. Bunde, Ho-Leung Chan, and Kirk Pruhs: Average rate speed scaling. In Proc. 8th Latin Amer. Symp. on Theoretical Informatics (LATIN’08), pp. 240–251. Springer, 2008. [ACM:1792939]

[4]   Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs: Speed scaling with a solar cell. Theoret. Comput. Sci., 410(45):4580–4587, 2009. Preliminary version in AAIM’08. [doi:10.1016/j.tcs.2009.07.004]

[5]   Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs: Dynamic speed scaling to manage energy and temperature. In Proc. 45th FOCS, pp. 520–529. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.24]

[6]   Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs: Speed scaling to manage energy and temperature. J. ACM, 54(1):3:1–3:39, March 2007. [doi:10.1145/1206035.1206038]

[7]   Nikhil Bansal, Kirk Pruhs, and Clifford Stein: Speed scaling for weighted flow time. SIAM J. Comput., 39(4):1294–1308, 2009. Preliminary version in SODA’07. [doi:10.1137/08072125X]

[8]   David M. Brooks, Pradip Bose, Stanley E. Schuster, Hans Jacobson, Prabhakar N. Kudva, Alper Buyuktosunoglu, John-David Wellman, Victor Zyuban, Manish Gupta, and Peter W. Cook: Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6):26–44, 2000. [doi:10.1109/40.888701]

[9]   Ho-Leung Chan, Wun-Tat Chan, Tak-Wah Lam, Lap-Kei Lee, Kin-Sum Mak, and Prudence W. H. Wong: Energy efficient online deadline scheduling. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 795–804. ACM Press, 2007. [ACM:1283468]

[10]   Sandy Irani and Kirk R. Pruhs: Algorithmic problems in power management. SIGACT News, 36(2):63–76, 2005. [doi:10.1145/1067309.1067324]

[11]   Woo-Cheol Kwon and Taewhan Kim: Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Trans. Embed. Comput. Syst., 4(1):211–230, February 2005. Preliminary version in DAC’03. [doi:10.1145/1053271.1053280]

[12]   Minming Li, Becky Jie Liu, and Frances F. Yao: Min-energy voltage allocation for tree-structured tasks. J. Combinatorial Optimization, 11(3):305–319, 2006. [doi:10.1007/11533719_30]

[13]   Minming Li, Andrew C. Yao, and Frances F. Yao: Discrete and continuous min-energy schedules for variable voltage processors. In Proc. Nat. Acad. Sci. USA, volume 103, pp. 3983–3987, 2006.

[14]   Minming Li and Frances F. Yao: An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput., 35:658–671, 2005. [doi:10.1137/050629434]

[15]   Kirk Pruhs: Competitive online scheduling for server systems. SIGMETRICS Perform. Eval. Rev., 34(4):52–58, 2007. [doi:10.1145/1243401.1243411]

[16]   Frances Yao, Alan Demers, and Scott Shenker: A scheduling model for reduced CPU energy. In Proc. 36th FOCS, pp. 374–382. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492493]

[17]   Han-Saem Yun and Jihong Kim: On energy-optimal voltage scheduling for fixed-priority hard real-time systems. ACM Trans. Embedded Computing Systems, 2(3):393–430, 2003. [doi:10.1145/860176.860183]