{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:47:36Z","timestamp":1761648456654,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Community\u2019s","award":["FP7 [FP7\/2007-2013]"],"award-info":[{"award-number":["FP7 [FP7\/2007-2013]"]}]},{"name":"PROXIMA Project","award":["611085"],"award-info":[{"award-number":["611085"]}]},{"DOI":"10.13039\/501100004837","name":"Spanish Ministry of Science and Innovation","doi-asserted-by":"crossref","award":["TIN2015-65316-P"],"award-info":[{"award-number":["TIN2015-65316-P"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"crossref"}]},{"name":"HiPEAC Network of Excellence"},{"name":"Ministry of Economy and Competitiveness under Ramon y Cajal postdoctoral fellowship","award":["RYC-2013-14717"],"award-info":[{"award-number":["RYC-2013-14717"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>Extreme Value Theory (EVT) has been historically used in domains such as finance and hydrology to model worst-case events (e.g., major stock market incidences). EVT takes as input a sample of the distribution of the variable to model and fits the tail of that sample to either the Generalised Extreme Value (GEV) or the Generalised Pareto Distribution (GPD). Recently, EVT has become popular in real-time systems to derive worst-case execution time (WCET) estimates of programs. However, the application of EVT is not straightforward and requires a detailed analysis of, and customisation for, the particular problem at hand. In this article, we tailor the application of EVT to timing analysis. To that end, (1) we analyse the response time of different hardware resources (e.g., cache memories) and identify those that may lead to radically different types of execution time distributions. (2) We show that one of these distributions, known as mixture distribution, causes problems in the use of EVT. In particular, mixture distributions challenge not only properly selecting GEV\/GPD parameters (i.e., location, scale and shape) but also determining the size of the sample to ensure that enough tail values are passed to EVT and that only tail values are used by EVT to fit GEV\/GPD. Failing to select these parameters has a negative impact on the quality of the derived WCET estimates. We tackle these problems, by (3) proposing Measurement-Based Probabilistic Timing Analysis using the Coefficient of Variation (MBPTA-CV), a new mixture-distribution aware, WCET-suited MBPTA method that builds on recent EVT developments in other fields (e.g., finance) to automatically select the distribution parameters that best fit the maxima of the observed execution times. Our results on a simulation environment and a real board show that MBPTA-CV produces high-quality WCET estimates.<\/jats:p>","DOI":"10.1145\/3065924","type":"journal-article","created":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T12:18:36Z","timestamp":1497356316000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Measurement-Based Worst-Case Execution Time Estimation Using the Coefficient of Variation"],"prefix":"10.1145","volume":"22","author":[{"given":"Jaume","family":"Abella","sequence":"first","affiliation":[{"name":"Barcelona Supercomputing Center (BSC), Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Padilla","sequence":"additional","affiliation":[{"name":"Universitat Aut\u00f2noma de Barcelona, Departament de Matem\u00e0tiques, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joan Del","family":"Castillo","sequence":"additional","affiliation":[{"name":"Universitat Aut\u00f2noma de Barcelona, Departament de Matem\u00e0tiques, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco J.","family":"Cazorla","sequence":"additional","affiliation":[{"name":"IIIA-CSIC and BSC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"volume-title":"Proceedings of the International Conference on Risk Analysis (ICRA\u201915)","author":"Abella J.","key":"e_1_2_1_1_1","unstructured":"J. Abella , J. del Castillo , F. J. Cazorla , and M. Padilla . 2015. Extreme value theory in computer sciences: The case of embedded safety-critical systems . In Proceedings of the International Conference on Risk Analysis (ICRA\u201915) . J. Abella, J. del Castillo, F. J. Cazorla, and M. Padilla. 2015. Extreme value theory in computer sciences: The case of embedded safety-critical systems. In Proceedings of the International Conference on Risk Analysis (ICRA\u201915)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.16"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"J. Abella E. Quinones F. Wartel T. Vardanega and F. J. Cazorla. 2014b. Heart of Gold: Making the improbable happen to extend coverage in probabilistic timing analysis. In ECRTS.  J. Abella E. Quinones F. Wartel T. Vardanega and F. J. Cazorla. 2014b. Heart of Gold: Making the improbable happen to extend coverage in probabilistic timing analysis. In ECRTS.","DOI":"10.1109\/ECRTS.2014.33"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"S. Altmeyer and R. I. Davis. 2014. On the correctness optimality and precision of static probabilistic timing analysis. In DATE.  S. Altmeyer and R. I. Davis. 2014. On the correctness optimality and precision of static probabilistic timing analysis. In DATE.","DOI":"10.7873\/DATE.2014.039"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/NEWCAS.2015.7181984"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INDIN.2016.7819140"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2002.1181582"},{"key":"e_1_2_1_8_1","first-page":"2","article-title":"Probabilistic WCET analysis, an approach using copulas","volume":"1","author":"Bernat G.","year":"2005","unstructured":"G. Bernat and M. Newby . 2005 . Probabilistic WCET analysis, an approach using copulas . J. Embed. Comput. 1 , 2 (April 2005), 179--194. G. Bernat and M. Newby. 2005. Probabilistic WCET analysis, an approach using copulas. J. Embed. Comput. 1, 2 (April 2005), 179--194.","journal-title":"J. Embed. Comput."},{"volume-title":"Proceedings of the Worst-Case Execution Time Analysis Workshop.","author":"Betts A.","key":"e_1_2_1_9_1","unstructured":"A. Betts , N. Merriam , and G. Bernat . 2010. Hybrid measurement-based WCET analysis at the source level using object-level traces . In Proceedings of the Worst-Case Execution Time Analysis Workshop. A. Betts, N. Merriam, and G. Bernat. 2010. Hybrid measurement-based WCET analysis at the source level using object-level traces. In Proceedings of the Worst-Case Execution Time Analysis Workshop."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1970.10481180"},{"key":"e_1_2_1_11_1","unstructured":"BSC. 2017. Technical Report UPC-DAC-RR-CAP-2017-3. Retrieved from http:\/\/www.ac.upc.edu\/RR\/2017\/3.pdf.  BSC. 2017. Technical Report UPC-DAC-RR-CAP-2017-3. Retrieved from http:\/\/www.ac.upc.edu\/RR\/2017\/3.pdf."},{"key":"e_1_2_1_12_1","unstructured":"D. Buttle. 2012. ETAS gmbh germany real-time in the prime-time. keynote talk. In ECRTS.  D. Buttle. 2012. ETAS gmbh germany real-time in the prime-time. keynote talk. In ECRTS."},{"key":"e_1_2_1_13_1","first-page":"99","article-title":"Minimum sample size determination for generalized extreme value distribution","volume":"40","author":"Cai Y.","year":"2011","unstructured":"Y. Cai and D. Hames . 2011 . Minimum sample size determination for generalized extreme value distribution . Commun. Stat. Simul. Comput. 40 (2011), 99 -- 110 . Y. Cai and D. Hames. 2011. Minimum sample size determination for generalized extreme value distribution. Commun. Stat. Simul. Comput. 40 (2011), 99--110.","journal-title":"Commun. Stat. Simul. Comput."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465787.2465796"},{"volume-title":"Proceedings of the Worst-Case Execution Time Analysis Workshop.","author":"Cazorla F. J.","key":"e_1_2_1_15_1","unstructured":"F. J. Cazorla , T. Vardanega , E. Quinones , and J. Abella . 2013b. Upper-bounding program execution time with extreme value theory . In Proceedings of the Worst-Case Execution Time Analysis Workshop. F. J. Cazorla, T. Vardanega, E. Quinones, and J. Abella. 2013b. Upper-bounding program execution time with extreme value theory. In Proceedings of the Worst-Case Execution Time Analysis Workshop."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5194\/hess-6-17-2002"},{"volume-title":"May","year":"2013","key":"e_1_2_1_17_1","unstructured":"Cobham Gaisler. NGMP Preliminary Datasheet Version 2.1 , May 2013 . Cobham Gaisler. NGMP Preliminary Datasheet Version 2.1, May 2013."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-3675-0"},{"key":"e_1_2_1_19_1","unstructured":"L. Cucu A. Gogonel and C. Lo. 2013. PROARTIS. D3.6 Probabilistic and Statistical Techniques for Timing Analysis in Multicore. (2013).  L. Cucu A. Gogonel and C. Lo. 2013. PROARTIS. D3.6 Probabilistic and Statistical Techniques for Timing Analysis in Multicore. (2013)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2012.31"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/sjos.12037"},{"key":"e_1_2_1_22_1","unstructured":"G. Edelin. 2009. Embedded systems at THALES: The artemis challenges for an industrial group. In ARTIST.  G. Edelin. 2009. Embedded systems at THALES: The artemis challenges for an industrial group. In ARTIST."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2001.990614"},{"key":"e_1_2_1_24_1","unstructured":"W. Feller. 1996. An Introduction to Probability Theory and Its Applications.  W. Feller. 1996. An Introduction to Probability Theory and Its Applications."},{"volume-title":"Proceedings of the Conference on Mathematical Methods in Reliability: Methodology, Practice and Inference.","author":"Garrido M.","key":"e_1_2_1_25_1","unstructured":"M. Garrido and J. Diebolt . 2000. The ET test, a goodness-of-fit test for the distribution tail . In Proceedings of the Conference on Mathematical Methods in Reliability: Methodology, Practice and Inference. M. Garrido and J. Diebolt. 2000. The ET test, a goodness-of-fit test for the distribution tail. In Proceedings of the Conference on Mathematical Methods in Reliability: Methodology, Practice and Inference."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10614-006-9025-7"},{"volume-title":"Proceedings of the Worst-Case Execution Time Analysis Workshop.","author":"Hansen J.","key":"e_1_2_1_27_1","unstructured":"J. Hansen , S. Hissam , and G. A. Moreno . 2009. Statistical-based WCET estimation and validation . In Proceedings of the Worst-Case Execution Time Analysis Workshop. J. Hansen, S. Hissam, and G. A. Moreno. 2009. Statistical-based WCET estimation and validation. In Proceedings of the Worst-Case Execution Time Analysis Workshop."},{"key":"e_1_2_1_28_1","unstructured":"International Organization for Standardization. 2009. ISO\/DIS 26262. Road Vehicles\u2014Functional Safety.  International Organization for Standardization. 2009. ISO\/DIS 26262. Road Vehicles\u2014Functional Safety."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"J. Jalle L. Kosmidis J. Abella E. Quinones and F. J. Cazorla. 2014. Bus designs for time-probabilistic multicore processors. In DATE.  J. Jalle L. Kosmidis J. Abella E. Quinones and F. J. Cazorla. 2014. Bus designs for time-probabilistic multicore processors. In DATE.","DOI":"10.7873\/DATE.2014.063"},{"key":"e_1_2_1_30_1","unstructured":"JEDEC. 2008. DDR2 SDRAM Specification JEDEC Standard No. JESD79-2E.  JEDEC. 2008. DDR2 SDRAM Specification JEDEC Standard No. JESD79-2E."},{"volume-title":"Proceedings of the Software Technologies for Future Embedded and Ubiquitous Systems Workshop.","author":"Kirner R.","key":"e_1_2_1_31_1","unstructured":"R. Kirner , P. Puschner , and I. Wenzel . 2004. Measurement-based worst-case execution time analysis using automatic test-data generation . In Proceedings of the Software Technologies for Future Embedded and Ubiquitous Systems Workshop. R. Kirner, P. Puschner, and I. Wenzel. 2004. Measurement-based worst-case execution time analysis using automatic test-data generation. In Proceedings of the Software Technologies for Future Embedded and Ubiquitous Systems Workshop."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.7873\/DATE.2013.116"},{"key":"e_1_2_1_33_1","volume-title":"PUB: Path upper-bounding for measurement-based probabilistic timing analysis. In ECRTS.","author":"Kosmidis L.","year":"2014","unstructured":"L. Kosmidis , J. Abella , F. Wartel , E. Quinones , A. Colin , and F. J. Cazorla . 2014 . PUB: Path upper-bounding for measurement-based probabilistic timing analysis. In ECRTS. L. Kosmidis, J. Abella, F. Wartel, E. Quinones, A. Colin, and F. J. Cazorla. 2014. PUB: Path upper-bounding for measurement-based probabilistic timing analysis. In ECRTS."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.7873\/DATE.2013.132"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2014.50"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1142\/p191"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2016.20"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038617.2038619"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.85"},{"volume-title":"Proceedings of the Worst-Case Execution Time Workshop.","author":"Mezzetti E.","key":"e_1_2_1_40_1","unstructured":"E. Mezzetti and T. Vardanega . 2011. On the industrial fitness of WCET analysis . In Proceedings of the Worst-Case Execution Time Workshop. E. Mezzetti and T. Vardanega. 2011. On the industrial fitness of WCET analysis. In Proceedings of the Worst-Case Execution Time Workshop."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2013.6531084"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC.2016.28"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.20"},{"key":"e_1_2_1_44_1","unstructured":"J. Owens. 2015. Delphi automotive the design of innovation that drives tomorrow. keynote talk. In DAC.  J. Owens. 2015. Delphi automotive the design of innovation that drives tomorrow. keynote talk. In DAC."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555764"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2010.2041634"},{"key":"e_1_2_1_47_1","unstructured":"M. Patte and V. Lefftz. 2011. System Impact of Distributed Multi Core Systems. Technical Report Contract 4200023100. European Space Agency.  M. Patte and V. Lefftz. 2011. System Impact of Distributed Multi Core Systems. Technical Report Contract 4200023100. European Space Agency."},{"volume-title":"Proceedings of Euromicro Digital Systems Design.","author":"Paulitsch M.","key":"e_1_2_1_48_1","unstructured":"M. Paulitsch , O. Medina , H. Karray , K. Mueller , D. Muench , and J. Nowotsch . 2015. Mixed-criticality embedded systems\u2014A balance ensuring partitioning and performance . In Proceedings of Euromicro Digital Systems Design. M. Paulitsch, O. Medina, H. Karray, K. Mueller, D. Muench, and J. Nowotsch. 2015. Mixed-criticality embedded systems\u2014A balance ensuring partitioning and performance. In Proceedings of Euromicro Digital Systems Design."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the Worst-Case Execution Time Analysis Workshop.","author":"Petters S. M.","year":"2003","unstructured":"S. M. Petters . 2003 . Comparison of trace generation methods for measurement based WCET analysis . In Proceedings of the Worst-Case Execution Time Analysis Workshop. S. M. Petters. 2003. Comparison of trace generation methods for measurement based WCET analysis. In Proceedings of the Worst-Case Execution Time Analysis Workshop."},{"volume-title":"Characterization of the EEMBC Benchmark Suite","author":"Poovey J.","key":"e_1_2_1_50_1","unstructured":"J. Poovey . 2007. Characterization of the EEMBC Benchmark Suite . North Carolina State University . J. Poovey. 2007. Characterization of the EEMBC Benchmark Suite. North Carolina State University."},{"key":"e_1_2_1_51_1","article-title":"Randomized caches considered harmful in hard real-time systems","volume":"1","author":"Reineke J.","year":"2014","unstructured":"J. Reineke . 2014 . Randomized caches considered harmful in hard real-time systems . Leibniz Trans. Embed. Syst. 1 , 1 (2014), 03:1--03:13. J. Reineke. 2014. Randomized caches considered harmful in hard real-time systems. Leibniz Trans. Embed. Syst. 1, 1 (2014), 03:1--03:13.","journal-title":"Leibniz Trans. Embed. Syst."},{"key":"e_1_2_1_52_1","unstructured":"Society of Automotive Engineers (SAE) International. 2001. Guidelines and methods for conducting the safety assessment process on civil airborne systems and equipment. ARP4761 standard.  Society of Automotive Engineers (SAE) International. 2001. Guidelines and methods for conducting the safety assessment process on civil airborne systems and equipment. ARP4761 standard."},{"volume-title":"Proceedings of the Worst-Case Execution Time Analysis Workshop.","author":"Santinelli L.","key":"e_1_2_1_53_1","unstructured":"L. Santinelli , J. Morio , G. Dufour , and D. Jacquemart . 2014. On the sustainability of the extreme value theory for WCET estimation . In Proceedings of the Worst-Case Execution Time Analysis Workshop. L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart. 2014. On the sustainability of the extreme value theory for WCET estimation. In Proceedings of the Worst-Case Execution Time Analysis Workshop."},{"key":"e_1_2_1_54_1","unstructured":"SoCLib. 2003-2012. Retrieved from http:\/\/www.soclib.fr\/trac\/dev.  SoCLib. 2003-2012. Retrieved from http:\/\/www.soclib.fr\/trac\/dev."},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"F. Wartel etal 2015. Timing analysis of an avionics case study on complex hardware\/software platforms. In DATE.  F. Wartel et al. 2015. Timing analysis of an avionics case study on complex hardware\/software platforms. In DATE.","DOI":"10.7873\/DATE.2015.0189"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88479-8_30"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2005.76"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_1_59_1","volume-title":"EPC: Extended path coverage for measurement-based probabilistic timing analysis. In RTSS.","author":"Ziccardi M.","year":"2015","unstructured":"M. Ziccardi , E. Mezzetti , T. Vardanega , J. Abella , and F. J. Cazorla . 2015 . EPC: Extended path coverage for measurement-based probabilistic timing analysis. In RTSS. M. Ziccardi, E. Mezzetti, T. Vardanega, J. Abella, and F. J. Cazorla. 2015. EPC: Extended path coverage for measurement-based probabilistic timing analysis. In RTSS."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3065924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3065924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:20Z","timestamp":1750273520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3065924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3065924"],"URL":"https:\/\/doi.org\/10.1145\/3065924","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}