{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:11:23Z","timestamp":1767262283826,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T00:00:00Z","timestamp":1519084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/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":[[2018,5,31]]},"abstract":"<jats:p>This article examines dynamic energy consumption caused by data during software execution on deeply embedded microprocessors, which can be significant on some devices. In worst-case energy consumption analysis, energy models are used to find the most costly execution path. Taking each instruction\u2019s worst-case energy produces a safe but overly pessimistic upper bound. Algorithms for safe and tight bounds would be desirable. We show that finding exact worst-case energy is NP-hard, and that tight bounds cannot be approximated with guaranteed safety. We conclude that any energy model targeting tightness must either sacrifice safety or accept overapproximation proportional to data-dependent energy.<\/jats:p>","DOI":"10.1145\/3173042","type":"journal-article","created":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T16:45:32Z","timestamp":1519145132000},"page":"1-22","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Limitations of Analyzing Worst-Case Dynamic Energy of Processing"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-4917-5808","authenticated-orcid":false,"given":"Jeremy","family":"Morse","sequence":"first","affiliation":[{"name":"University of Bristol, BRISTOL, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Kerrison","sequence":"additional","affiliation":[{"name":"University of Bristol, BRISTOL, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kerstin","family":"Eder","sequence":"additional","affiliation":[{"name":"University of Bristol, BRISTOL, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,20]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1155\/2001\/82129"},{"volume-title":"Frontiers in Artificial Intelligence and Applications","author":"Biere Armin","key":"e_1_2_1_3_1","unstructured":"Armin Biere , Marijn Heule , Hans van Maaren , and Toby Walsh . 2009. Handbook of Satisfiability : Volume 185 : Frontiers in Artificial Intelligence and Applications . IOS Press , Amsterdam, The Netherlands. 611--632 pages. Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh. 2009. Handbook of Satisfiability: Volume 185: Frontiers in Artificial Intelligence and Applications. IOS Press, Amsterdam, The Netherlands. 611--632 pages."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855840.1855861"},{"key":"e_1_2_1_6_1","volume-title":"13th International Workshop on Worst-Case Execution Time Analysis (OpenAccess Series in Informatics (OASIcs\u201913)","volume":"30","author":"Cazorla Francisco J.","year":"2013","unstructured":"Francisco J. Cazorla , Tullio Vardanega , Eduardo Qui\u00f1ones , and Jaume Abella . 2013 . Upper-bounding program execution time with extreme value theory . In 13th International Workshop on Worst-Case Execution Time Analysis (OpenAccess Series in Informatics (OASIcs\u201913) ), Claire Maiza (Ed.) , Vol. 30 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 64--76. Francisco J. Cazorla, Tullio Vardanega, Eduardo Qui\u00f1ones, and Jaume Abella. 2013. Upper-bounding program execution time with extreme value theory. In 13th International Workshop on Worst-Case Execution Time Analysis (OpenAccess Series in Informatics (OASIcs\u201913)), Claire Maiza (Ed.), Vol. 30. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 64--76."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/VDAT.2008.4542403"},{"key":"e_1_2_1_8_1","volume-title":"On the Complexity of Power Estimation Problems. In International Workshop on Logic Synthesis (IWLS). IEEE, 239--244","author":"Freitas Ana T.","year":"2000","unstructured":"Ana T. Freitas , Horcio C. Neto , and Arlindo L. Oliveira . 2000 . On the Complexity of Power Estimation Problems. In International Workshop on Logic Synthesis (IWLS). IEEE, 239--244 . https:\/\/2.zoppoz.workers.dev:443\/http\/www.iwls.org\/iwls 2000 \/. Ana T. Freitas, Horcio C. Neto, and Arlindo L. Oliveira. 2000. On the Complexity of Power Estimation Problems. In International Workshop on Logic Synthesis (IWLS). IEEE, 239--244. https:\/\/2.zoppoz.workers.dev:443\/http\/www.iwls.org\/iwls2000\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046679"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.604077"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764967.2764974"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSID.2015.68"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1816038.1815968"},{"key":"e_1_2_1_14_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2011","unstructured":"John L. Hennessy and David A . Patterson . 2011 . Computer Architecture : A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers , San Francisco, CA. John L. Hennessy and David A. Patterson. 2011. Computer Architecture: A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers, San Francisco, CA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/263272.263321"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.17"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804034"},{"volume-title":"Proceedings of the 2nd Working Conference on Asynchronous Design Methodologies. IEEE Computer Society","author":"Kearney David","key":"e_1_2_1_18_1","unstructured":"David Kearney and Neil W. Bergmann . 1995. Performance evaluation of asynchronous logic pipelines with data dependent processing delays . In Proceedings of the 2nd Working Conference on Asynchronous Design Methodologies. IEEE Computer Society , Washington, DC, 4--13. David Kearney and Neil W. Bergmann. 1995. Performance evaluation of asynchronous logic pipelines with data dependent processing delays. In Proceedings of the 2nd Working Conference on Asynchronous Design Methodologies. IEEE Computer Society, Washington, DC, 4--13."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700104"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2003.1250885"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1973009.1973031"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2016.20"},{"volume-title":"Inferring Parametric Energy Consumption Functions at Different Software Levels: ISA vs","author":"Liqat Umer","key":"e_1_2_1_23_1","unstructured":"Umer Liqat , Kyriakos Georgiou , Steve Kerrison , Pedro Lopez-Garcia , John P. Gallagher , Manuel V. Hermenegildo , and Kerstin. Eder. 2016. Inferring Parametric Energy Consumption Functions at Different Software Levels: ISA vs . LLVM IR. Springer International Publishing , Cham , 81--100. Umer Liqat, Kyriakos Georgiou, Steve Kerrison, Pedro Lopez-Garcia, John P. Gallagher, Manuel V. Hermenegildo, and Kerstin. Eder. 2016. Inferring Parametric Energy Consumption Functions at Different Software Levels: ISA vs. LLVM IR. Springer International Publishing, Cham, 81--100."},{"key":"e_1_2_1_24_1","volume-title":"23rd International Symposium (LOPSTR\u201913)","volume":"8901","author":"Liqat Umer","year":"2014","unstructured":"Umer Liqat , Steve Kerrison , Alejandro Serrano , Kyriakos Georgiou , Pedro Lopez-Garcia , Neville Grech , Manuel V. Hermenegildo , and Kerstin Eder . 2014 . Energy consumption analysis of programs based on XMOS ISA-level models. In Logic-Based Program Synthesis and Transformation , 23rd International Symposium (LOPSTR\u201913) , Revised Selected Papers (Lecture Notes in Computer Science) , Vol. 8901 . Springer, Cham, 72--90. Umer Liqat, Steve Kerrison, Alejandro Serrano, Kyriakos Georgiou, Pedro Lopez-Garcia, Neville Grech, Manuel V. Hermenegildo, and Kerstin Eder. 2014. Energy consumption analysis of programs based on XMOS ISA-level models. In Logic-Based Program Synthesis and Transformation, 23rd International Symposium (LOPSTR\u201913), Revised Selected Papers (Lecture Notes in Computer Science), Vol. 8901. Springer, Cham, 72--90."},{"volume-title":"Extreme Events in Finance: A Handbook of Extreme Value Theory and Its Applications","author":"Longin Francois","key":"e_1_2_1_25_1","unstructured":"Francois Longin . 2016. Extreme Events in Finance: A Handbook of Extreme Value Theory and Its Applications . Wiley , Hoboken, NJ . Francois Longin. 2016. Extreme Events in Finance: A Handbook of Extreme Value Theory and Its Applications. Wiley, Hoboken, NJ."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/827271.829103"},{"key":"e_1_2_1_27_1","unstructured":"David May. 2013. The XMOS XS1 Architecture. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/http\/www.xmos.com\/published\/xmos-xs1-architecture.  David May. 2013. The XMOS XS1 Architecture. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/http\/www.xmos.com\/published\/xmos-xs1-architecture."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529255.1529262"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656106.2656108"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078659.3078666"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/971216.2813487"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855610.1855613"},{"volume-title":"The Satisfiability Problem: Algorithms and Analyses. Lehmanns Media","author":"Sch\u00f6ning Uwe","key":"e_1_2_1_33_1","unstructured":"Uwe Sch\u00f6ning and Jacobo Tor\u00e1n . 2013. The Satisfiability Problem: Algorithms and Analyses. Lehmanns Media , Berlin, DE . Uwe Sch\u00f6ning and Jacobo Tor\u00e1n. 2013. The Satisfiability Problem: Algorithms and Analyses. Lehmanns Media, Berlin, DE."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2648668.2648758"},{"volume-title":"Proceedings of the 13th International Conference on VLSI Design (VLSID\u201900)","author":"Sinha Amit","key":"e_1_2_1_35_1","unstructured":"Amit Sinha and Anantha P. Chandrakasan . 2000. Energy aware software . In Proceedings of the 13th International Conference on VLSI Design (VLSID\u201900) . IEEE Computer Society, Washington, DC, 50--. https:\/\/2.zoppoz.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id&equals;580736.835252 Amit Sinha and Anantha P. Chandrakasan. 2000. Energy aware software. In Proceedings of the 13th International Conference on VLSI Design (VLSID\u201900). IEEE Computer Society, Washington, DC, 50--. https:\/\/2.zoppoz.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id&equals;580736.835252"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of International Symposium on Power And Timing Modeling, Optimization and Simulation (PATMOS). IEEE Computer Society","author":"Steinke Stefan","year":"2001","unstructured":"Stefan Steinke , Markus Knauer , Lars Wehmeyer , and Peter Marwedel . 2001 . An accurate and fine grain instruction-level energy model supporting software optimizations . In Proceedings of International Symposium on Power And Timing Modeling, Optimization and Simulation (PATMOS). IEEE Computer Society , Washington, DC. Stefan Steinke, Markus Knauer, Lars Wehmeyer, and Peter Marwedel. 2001. An accurate and fine grain instruction-level energy model supporting software optimizations. In Proceedings of International Symposium on Power And Timing Modeling, Optimization and Simulation (PATMOS). IEEE Computer Society, Washington, DC."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000045316.66276.6e"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.335012"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01130407"},{"volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","key":"e_1_2_1_40_1","unstructured":"Vijay V. Vazirani . 2001. Approximation Algorithms . Springer-Verlag New York , New York . 306--311 pages. Vijay V. Vazirani. 2001. Approximation Algorithms. Springer-Verlag New York, New York. 306--311 pages."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.17"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3173042","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3173042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:50Z","timestamp":1750215770000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3173042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,20]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5,31]]}},"alternative-id":["10.1145\/3173042"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3173042","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2018,2,20]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}