{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:31:25Z","timestamp":1761597085949,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T00:00:00Z","timestamp":1207008000000},"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":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2008,4]]},"abstract":"<jats:p>We present a dynamic voltage scaling (DVS) technique that minimizes system-wide energy consumption for both periodic and sporadic tasks. It is known that a system consists of processors and a number of other components. Energy-aware processors can be run in different speed levels; components like memory and I\/O subsystems and network interface cards can be in a standby state when they are active, but idle. Processor energy optimization solutions are not necessarily efficient from the perspective of systems. Current system-wide energy optimization studies are often limited to periodic tasks with heuristics in getting approximated solutions. In this paper, we develop an exact dynamic programming algorithm for periodic tasks on processors with practical discrete speed levels. The algorithm determines the lower bound of energy expenditure in pseudopolynomial time. An approximation algorithm is proposed to provide performance guarantee with a given bound in polynomial running time. Because of their time efficiency, both the optimization and approximation algorithms can be adapted for online scheduling of sporadic tasks with irregular task releases. We prove that system-wide energy optimization for sporadic tasks is NP-hard in the strong sense. We develop (pseudo-) polynomial-time solutions by exploiting its inherent properties.<\/jats:p>","DOI":"10.1145\/1347375.1347381","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["System-wide energy minimization for real-time tasks"],"prefix":"10.1145","volume":"7","author":[{"given":"Xiliang","family":"Zhong","sequence":"first","affiliation":[{"name":"Wayne State University, Detroit, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng-Zhong","family":"Xu","sequence":"additional","affiliation":[{"name":"Wayne State University, Detroit, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.908988"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086228.1086273"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.25"},{"volume-title":"Proceedings of the International Workshop on Power-Aware Real-time Computing. 24--29","author":"Cheng H.","key":"e_1_2_1_4_1","unstructured":"Cheng , H. and Goddard , S . 2005. Integrated device scheduling and processor voltage scaling for system-wide energy conservation . In Proceedings of the International Workshop on Power-Aware Real-time Computing. 24--29 . Cheng, H. and Goddard, S. 2005. Integrated device scheduling and processor voltage scaling for system-wide energy conservation. In Proceedings of the International Workshop on Power-Aware Real-time Computing. 24--29."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013235.1013327"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382538"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.508319"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(87)90165-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/288548.289105"},{"key":"e_1_2_1_10_1","unstructured":"Intel. Intel-XScale Architecture. http:\/\/www.intel.com\/design\/intelxscale\/.  Intel. Intel-XScale Architecture. http:\/\/www.intel.com\/design\/intelxscale\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013235.1013261"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996650"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer Verlag New York.  Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer Verlag New York.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013235.1013328"},{"key":"e_1_2_1_15_1","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth D.","unstructured":"Knuth , D. 1997. The Art of Computer Programming, Volume 3: Sorting and Searching , 3 rd Ed. Addison-Wesley , Reading, MA . Chapter 5.2--5.3. Knuth, D. 1997. The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Ed. Addison-Wesley, Reading, MA. Chapter 5.2--5.3.","edition":"3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.38"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065742"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774678"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/993396.993400"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2005.40"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2005.851140"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/344166.344530"},{"volume-title":"Proceedings of the IEEE Real-Time Systems Symposium 52--62","author":"Qadi A.","key":"e_1_2_1_23_1","unstructured":"Qadi , A. , Goddard , S. , and Farritor , S . 2003. A dynamic voltage scaling algorithm for sporadic tasks . In Proceedings of the IEEE Real-Time Systems Symposium 52--62 . Qadi, A., Goddard, S., and Farritor, S. 2003. A dynamic voltage scaling algorithm for sporadic tasks. In Proceedings of the IEEE Real-Time Systems Symposium 52--62."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860179"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132357.1132364"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053271.1053277"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077603.1077670"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017767"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151690.1151693"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2005.858175"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233606"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.48"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382539"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065744"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1347375.1347381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1347375.1347381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1347375.1347381"}},"subtitle":["Lower bound and approximation"],"short-title":[],"issued":{"date-parts":[[2008,4]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["10.1145\/1347375.1347381"],"URL":"https:\/\/doi.org\/10.1145\/1347375.1347381","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2008,4]]},"assertion":[{"value":"2005-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}