{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T14:25:57Z","timestamp":1773843957909,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>\n            Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed\n            <jats:italic>s<\/jats:italic>\n            is\n            <jats:italic>P<\/jats:italic>\n            (\n            <jats:italic>s<\/jats:italic>\n            ) =\n            <jats:italic>s<\/jats:italic>\n            <jats:sup>\u03b1<\/jats:sup>\n            for some constant \u03b1 &gt; 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2\n            <jats:sup>\u03b1 \u2212 1<\/jats:sup>\n            \u03b1\n            <jats:sup>\u03b1<\/jats:sup>\n            -competitive with respect to energy. We provide a tight \u03b1\n            <jats:sup>\u03b1<\/jats:sup>\n            bound on the competitive ratio of OA with respect to energy.\n          <\/jats:p>\n          <jats:p>\n            We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1\/\n            <jats:italic>b<\/jats:italic>\n            , where\n            <jats:italic>b<\/jats:italic>\n            is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is\n            <jats:italic>e<\/jats:italic>\n            -competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for \u03b1 \u22655.\n          <\/jats:p>\n          <jats:p>Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm.<\/jats:p>","DOI":"10.1145\/1206035.1206038","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":266,"title":["Speed scaling to manage energy and temperature"],"prefix":"10.1145","volume":"54","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Tracy","family":"Kimbrel","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"University of Pittsburgh, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apple. 2005. Why apple chose intel. http:\/\/www.business2.com\/b2\/web\/articles\/0 17863 1084781 00.html.  Apple. 2005. Why apple chose intel. http:\/\/www.business2.com\/b2\/web\/articles\/0 17863 1084781 00.html."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.24"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge MA.   Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.888701"},{"key":"e_1_2_1_5_1","volume-title":"Hard Real-Time Computing Systems","author":"Buttazzo G.","unstructured":"Buttazzo , G. 1997. Hard Real-Time Computing Systems . Kluwer . Buttazzo, G. 1997. Hard Real-Time Computing Systems. Kluwer."},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_7_1","unstructured":"Crusoe. 2002. Crusoe tm550\/tm5800 thermal design guide. http:\/\/crusoe.com\/crusoe_docs\/TM5800_ThermDesGuide_6-18-02.pdf.  Crusoe. 2002. Crusoe tm550\/tm5800 thermal design guide. http:\/\/crusoe.com\/crusoe_docs\/TM5800_ThermDesGuide_6-18-02.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/822076.822438"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-6.3.163"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02547518"},{"key":"e_1_2_1_11_1","unstructured":"Hardy G. H. Littlewood J. E. and Polya G. 1952. Inequalities. Cambridge University Press Cambridge MA.  Hardy G. H. Littlewood J. E. and Polya G. 1952. Inequalities. Cambridge University Press Cambridge MA."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 37--46","author":"Irani S.","unstructured":"Irani , S. , Gupta , R. K. , and Shukla , S . 2003. Algorithms for Power Savings . In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 37--46 . Irani, S., Gupta, R. K., and Shukla, S. 2003. Algorithms for Power Savings. In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 37--46."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775867"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7910-6"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the National Academy of Sciences USA.","volume":"103","author":"Li M.","unstructured":"Li , M. , Yao , A. C. , and Yao , F. F . 2006b. Discrete and continuous min-energy schedules for variable voltage processors . In Proceedings of the National Academy of Sciences USA. Vol. 103 . 3983--3987. Li, M., Yao, A. C., and Yao, F. F. 2006b. Discrete and continuous min-energy schedules for variable voltage processors. In Proceedings of the National Academy of Sciences USA. Vol. 103. 3983--3987."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/050629434"},{"key":"e_1_2_1_18_1","volume-title":"New York Times (May 17","author":"Markoff J.","year":"2004","unstructured":"Markoff , J. 2004 . Intel's big shift after hitting technical wall , New York Times (May 17 , 2004). http:\/\/www.nytimes.com\/2004\/05\/17\/business\/17intel.html?ex=1400212800&en=482e58801aa02ede&ei=5007&partner=USERLAND. Markoff, J. 2004. Intel's big shift after hitting technical wall, New York Times (May 17, 2004). http:\/\/www.nytimes.com\/2004\/05\/17\/business\/17intel.html?ex=1400212800&en=482e58801aa02ede&ei=5007&partner=USERLAND."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.917539"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Nestorov Y. 2003. Introductory lectures on convex programming.  Nestorov Y. 2003. Introductory lectures on convex programming.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"e_1_2_1_21_1","unstructured":"Sergent J. E. and Krum A. 1998. Thermal Management Handbook. McGraw-Hill New York.  Sergent J. E. and Krum A. 1998. Thermal Management Handbook. McGraw-Hill New York."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/859618.859620"},{"key":"e_1_2_1_23_1","volume-title":"Variational Methods in Optimization","author":"Smith D. R.","unstructured":"Smith , D. R. 1974. Variational Methods in Optimization . Prentice-Hall , Englewood Cliffs, NJ . Smith, D. R. 1974. Variational Methods in Optimization. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/277044.277227"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE Syposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Yao F.","unstructured":"Yao , F. , Demers , A. , and Shenker , S . 1995. A scheduling model for reduced CPU energy . In Proceedings of the IEEE Syposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 374--382. Yao, F., Demers, A., and Shenker, S. 1995. A scheduling model for reduced CPU energy. In Proceedings of the IEEE Syposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 374--382."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860183"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206035.1206038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1206035.1206038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:31Z","timestamp":1750278151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206035.1206038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1206035.1206038"],"URL":"https:\/\/doi.org\/10.1145\/1206035.1206038","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}