{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:19Z","timestamp":1750221019636,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T00:00:00Z","timestamp":1563408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>Low-Level analysis of Worst Case Execution Time (WCET) is an important field for real-time system validation. It stands between computer architecture and mathematics, as it relies strongly on variants of abstract interpretation. One of the features that causes the largest uncertainty regarding WCET evaluation for low-level analysis of sequential execution on a single processor is taking Cache Memory-related Delays (CMRD) and Cache-related Preemption Delays (CRPD) correctly into account. Research work from the 1990s provides a good basic framework for this problem as long as a task runs without preemption. But when preemption of tasks is allowed, although several formalisms exist, their predictive power is lower and the usual approach relies on analyses of NP-hard problems.<\/jats:p>\n          <jats:p>In this article, we want to show some potential advantages of using a formalism inspired by Quantum Computing (QC) to evaluate CMRDs with preemptions while avoiding the NP-hard problem underneath. The experimental results, with a classic (non-quantum) numerical approach, on a selection of Malardalen benchmark programs display very good accuracy, while the complexity of the evaluation is a low-order polynomial of the number of memory accesses. While it is not yet a fully parallel quantum algorithm, we provide a first roadmap on how to reach such an objective.<\/jats:p>","DOI":"10.1145\/3335549","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:14Z","timestamp":1563542234000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A First Step Toward Using Quantum Computing for Low-level WCETs Estimations"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4604-6453","authenticated-orcid":false,"given":"Stephane","family":"Louise","sequence":"first","affiliation":[{"name":"CEA, LIST, Gif-sur-Yvette, France"}]}],"member":"320","published-online":{"date-parts":[[2019,7,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647165.760063"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.08.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.041"},{"volume-title":"Proceeding of the 2nd Real-Time Technology and Applications Symposium. 204--212","author":"Busquets-Mataix J. V.","key":"e_1_2_1_4_1"},{"volume-title":"PROARTIS: Probabilistically Analysable Real-Time Systems. Research Report RR-7869.","year":"2012","author":"Cazorla Francisco J.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.27"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008186323068"},{"volume-title":"Proceedings of the 10th International Worshop on Worst-Case Execution Time Analysis.","year":"2010","author":"Gustafsson Jan","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.27"},{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE\u201913)","author":"Kosmidis Leonidas","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.689649"},{"volume-title":"Rasprostranenie zakona bol\u2019shih chisel na velichiny, zavisyaschie drug ot druga. Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya 15, 94","year":"1906","author":"Markov A.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2392987.2393001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/944645.944698"},{"volume-title":"Chuang","year":"2011","author":"Nielsen Michael A.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201907)","author":"Puaut I.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2009.30"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.14"},{"key":"e_1_2_1_20_1","unstructured":"M\u00e4lardalen WCET Research Group. 2006. WCET Benchmarks. Retrieved from http:\/\/www.mrtc.mdh.se\/projects\/wcet\/benchmarks.htm.  M\u00e4lardalen WCET Research Group. 2006. WCET Benchmarks. Retrieved from http:\/\/www.mrtc.mdh.se\/projects\/wcet\/benchmarks.htm."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 18th International Workshop on Worst-Case Execution Time Analysis (WCET\u201918)","volume":"63","author":"Shah Darshit","year":"2018"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/956418.956619"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3335549","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3335549","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:19Z","timestamp":1750206379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3335549"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,18]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3335549"],"URL":"https:\/\/doi.org\/10.1145\/3335549","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2019,7,18]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}