{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:17:06Z","timestamp":1759940226428,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,2,1]],"date-time":"2006-02-01T00:00:00Z","timestamp":1138752000000},"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":[[2006,2]]},"abstract":"<jats:p>\n            Energy is a valuable resource in embedded systems as the lifetime of many such systems is constrained by their battery capacity. Recent advances in processor design have added support for dynamic frequency\/voltage scaling (DVS) for saving energy. Recent work on real-time scheduling focuses on saving energy in static as well as dynamic scheduling environments by exploiting idle time and slack because of early task completion for DVS of subsequent tasks. These scheduling algorithms rely on\n            <jats:italic>a priori<\/jats:italic>\n            knowledge of worst-case execution times (WCET) for each task. They assume that DVS has no effect on the worst-case execution cycles (WCEC) of a task and scale the WCET according to the processor frequency. However, for systems with memory hierarchies, the WCEC typically\n            <jats:italic>does<\/jats:italic>\n            change under DVS because of requency modulation. Hence, current assumptions used by DVS schemes result in a highly exaggerated WCET. This paper contributes novel techniques for tight and flexible static timing analysis, particularly well-suited for dynamic scheduling schemes. The technical contributions are as follows: (1) We assess the problem of changing execution cycles owing to scaling techniques. (2) We propose a parametric approach toward bounding the WCET statically with respect to the frequency. Using a parametric model, we can capture the effect of changes in frequency on the WCEC and, thus, accurately model the WCET over any frequency range. (3) We discuss design and implementation of the frequency-aware static timing analysis (FAST) tool based on our prior experience with static timing analysis. (4) We demonstrate in experiments that our FAST tool provides safe upper bounds on the WCET, which are tight. The FAST tool allows us to capture the WCET of six benchmarks using equations that overestimate the WCET by less than 1%. FAST equations can also be used to improve existing DVS scheduling schemes to ensure that the effect of frequency scaling on WCET is considered and that the WCET used is\n            <jats:italic>not<\/jats:italic>\n            exaggerated. (5) We leverage three DVS scheduling schemes by incorporating FAST into them and by showing that the energy consumption further decreases. (6) We compare experimental results using two different energy models to demonstrate or verify the validity of simulation methods. To the best of our knowledge, this study of DVS effects on timing analysis is unprecedented.\n          <\/jats:p>","DOI":"10.1145\/1132357.1132364","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"200-224","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["FAST"],"prefix":"10.1145","volume":"5","author":[{"given":"Kiran","family":"Seth","sequence":"first","affiliation":[{"name":"Qualcomm, Cary, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravindh","family":"Anantaraman","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Mueller","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Rotenberg","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,2]]},"reference":[{"volume-title":"International Symposium on Computer Architecture. 250--261","author":"Anantaraman A.","key":"e_1_2_1_1_1","unstructured":"Anantaraman , A. , Seth , K. , Patil , K. , Rotenberg , E. , and Mueller , F . 2003. Virtual simple architecture (VISA): Exceeding the complexity limit in safe real-time systems . In International Symposium on Computer Architecture. 250--261 . 10.1145\/859618.859659 Anantaraman, A., Seth, K., Patil, K., Rotenberg, E., and Mueller, F. 2003. Virtual simple architecture (VISA): Exceeding the complexity limit in safe real-time systems. In International Symposium on Computer Architecture. 250--261. 10.1145\/859618.859659"},{"volume-title":"IEEE Real-Time Systems Symposium.","author":"Aydin H.","key":"e_1_2_1_2_1","unstructured":"Aydin , H. , Melhem , R. , Mosse , D. , and Mejia-Alvarez , P . 2001. Dynamic and agressive scheduling techniques for power-aware real-time systems . In IEEE Real-Time Systems Symposium. Aydin, H., Melhem, R., Mosse, D., and Mejia-Alvarez, P. 2001. Dynamic and agressive scheduling techniques for power-aware real-time systems. In IEEE Real-Time Systems Symposium."},{"volume-title":"ACM SIGPLAN Conference on Programming Language Design and Implementation. 300--313","author":"Ball T.","key":"e_1_2_1_3_1","unstructured":"Ball , T. and Larus , J. R . 1993. Branch prediction for free . In ACM SIGPLAN Conference on Programming Language Design and Implementation. 300--313 . 10.1145\/155090.155119 Ball, T. and Larus, J. R. 1993. Branch prediction for free. In ACM SIGPLAN Conference on Programming Language Design and Implementation. 300--313. 10.1145\/155090.155119"},{"volume-title":"ACM SIGPLAN Conference on Programming Language Design and Implementation. 329--338","author":"Benitez M. E.","key":"e_1_2_1_4_1","unstructured":"Benitez , M. E. and Davidson , J. W . 1988. A portable global optimizer and linker . In ACM SIGPLAN Conference on Programming Language Design and Implementation. 329--338 . 10.1145\/53990.54023 Benitez, M. E. and Davidson, J. W. 1988. A portable global optimizer and linker. In ACM SIGPLAN Conference on Programming Language Design and Implementation. 329--338. 10.1145\/53990.54023"},{"volume-title":"25th IFAC Workshop on Real-Time Programming.","author":"Bernat G.","key":"e_1_2_1_5_1","unstructured":"Bernat , G. and Burns , A . 2000. An approach to symbolic worst-case execution time analysis . In 25th IFAC Workshop on Real-Time Programming. Bernat, G. and Burns, A. 2000. An approach to symbolic worst-case execution time analysis. In 25th IFAC Workshop on Real-Time Programming."},{"volume-title":"Proceedings of the 27th Annual International Symposium on Computer Architecture. IEEE Computer Society and ACM SIGARCH","author":"Brooks D.","key":"e_1_2_1_6_1","unstructured":"Brooks , D. , Tiwari , V. , and Martonosi , M . 2000. Wattch: A framework for architectural-level power analysis and optimizations . In Proceedings of the 27th Annual International Symposium on Computer Architecture. IEEE Computer Society and ACM SIGARCH , Vancouver, British Columbia, 83--94. 10.1145\/339647.339657 Brooks, D., Tiwari, V., and Martonosi, M. 2000. Wattch: A framework for architectural-level power analysis and optimizations. In Proceedings of the 27th Annual International Symposium on Computer Architecture. IEEE Computer Society and ACM SIGARCH, Vancouver, British Columbia, 83--94. 10.1145\/339647.339657"},{"key":"e_1_2_1_7_1","volume-title":"T. M.","author":"Burger D.","year":"1996","unstructured":"Burger , D. , Austin , T. M. , and Bennett, S. 1996 . Evaluating future microprocessors: The simplescalar tool set. Technical Report CS-TR-1996-1308, (July) University of Wisconsin, Madison. Burger, D., Austin, T. M., and Bennett, S. 1996. Evaluating future microprocessors: The simplescalar tool set. Technical Report CS-TR-1996-1308, (July) University of Wisconsin, Madison."},{"key":"e_1_2_1_8_1","unstructured":"C-Lab. Wcet benchmarks. Available from http:\/\/www.c-lab.de\/home\/en\/download.html.  C-Lab. Wcet benchmarks. Available from http:\/\/www.c-lab.de\/home\/en\/download.html."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1109\/4.126534","article-title":"Low-power cmos digital design","volume":"27","author":"Chandrakasan A.","year":"1992","unstructured":"Chandrakasan , A. , Sheng , S. , and Brodersen , R. W. April , 1992 . Low-power cmos digital design . In IEEE Journal of Solid-State Circuits , vol. 27 , 473 -- 484 . Chandrakasan, A., Sheng, S., and Brodersen, R. W. April, 1992. Low-power cmos digital design. In IEEE Journal of Solid-State Circuits, vol. 27, 473--484.","journal-title":"IEEE Journal of Solid-State Circuits"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365316"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1989.559777"},{"key":"e_1_2_1_12_1","unstructured":"Corp. I. Intel StrongARM processors. http:\/\/www.intel.com\/design\/strong.  Corp. I. Intel StrongARM processors. http:\/\/www.intel.com\/design\/strong."},{"volume-title":"ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02)","author":"Dudani A.","key":"e_1_2_1_13_1","unstructured":"Dudani , A. , Mueller , F. , and Zhu , Y . 2002. Energy-conserving feedback edf scheduling for embedded systems with real-time constraints . In ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02) . 213--222. 10.1145\/513829.513865 Dudani, A., Mueller, F., and Zhu, Y. 2002. Energy-conserving feedback edf scheduling for embedded systems with real-time constraints. In ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02). 213--222. 10.1145\/513829.513865"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Symposium on Low-Power Electronics and Design ISLPED'01","author":"Gruian F.","year":"2001","unstructured":"Gruian , F. 2001 . Hard real-time scheduling for low energy using stochastic data and dvs processors . In Proceedings of the International Symposium on Low-Power Electronics and Design ISLPED'01 . 10.1145\/383082.383092 Gruian, F. 2001. Hard real-time scheduling for low energy using stochastic data and dvs processors. In Proceedings of the International Symposium on Low-Power Electronics and Design ISLPED'01. 10.1145\/383082.383092"},{"volume-title":"IEEE Real-Time Systems Symposium. 288--297","author":"Healy C. A.","key":"e_1_2_1_15_1","unstructured":"Healy , C. A. , Whalley , D. B. , and Harmon , M. G . 1995. Integrating the timing analysis of pipelining and instruction caching . In IEEE Real-Time Systems Symposium. 288--297 . Healy, C. A., Whalley, D. B., and Harmon, M. G. 1995. Integrating the timing analysis of pipelining and instruction caching. In IEEE Real-Time Systems Symposium. 288--297."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.743411"},{"key":"e_1_2_1_17_1","unstructured":"Intel. 2000. Intel XScale Microarchitecture Technical Summary.  Intel. 2000. Intel XScale Microarchitecture Technical Summary."},{"volume-title":"IEEE Real-Time Systems Symposium. 254--263","author":"Li Y.-T. S.","key":"e_1_2_1_18_1","unstructured":"Li , Y.-T. S. , Malik , S. , and Wolfe , A . 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches . In IEEE Real-Time Systems Symposium. 254--263 . Li, Y.-T. S., Malik, S., and Wolfe, A. 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches. In IEEE Real-Time Systems Symposium. 254--263."},{"volume-title":"IEEE Real-Time Systems Symposium. 97--108","author":"Lim S.-S.","key":"e_1_2_1_19_1","unstructured":"Lim , S.-S. , Bae , Y. H. , Jang , G. T. , Rhee , B.-D. , Min , S. L. , Park , C. Y. , Shin , H. , and Kim , C. S . 1994. An accurate worst case timing analysis for RISC processors . In IEEE Real-Time Systems Symposium. 97--108 . Lim, S.-S., Bae, Y. H., Jang, G. T., Rhee, B.-D., Min, S. L., Park, C. Y., Shin, H., and Kim, C. S. 1994. An accurate worst case timing analysis for RISC processors. In IEEE Real-Time Systems Symposium. 97--108."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"volume-title":"Workshop on Compilers and Operating Systems for Low Power.","author":"Mosse D.","key":"e_1_2_1_21_1","unstructured":"Mosse , D. , Aydin , H. , Childers , B. , and Melhem , R . 2000. Compiler-assisted dynamic power-aware scheduling for real-time applications . In Workshop on Compilers and Operating Systems for Low Power. Mosse, D., Aydin, H., Childers, B., and Melhem, R. 2000. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compilers and Operating Systems for Low Power."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008145215849"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01088696"},{"key":"e_1_2_1_24_1","volume-title":"Symposium on Operating Systems Principles. 10","author":"Pillai P.","year":"2034","unstructured":"Pillai , P. and Shin , K . 2001. Real-time dynamic voltage scaling for low-power embedded operating systems . In Symposium on Operating Systems Principles. 10 .1145\/50 2034 .502044 Pillai, P. and Shin, K. 2001. Real-time dynamic voltage scaling for low-power embedded operating systems. In Symposium on Operating Systems Principles. 10.1145\/502034.502044"},{"volume-title":"IEEE Real-Time Systems Symposium. 40--51","author":"Seth K.","key":"e_1_2_1_25_1","unstructured":"Seth , K. , Anantaraman , A. , Mueller , F. , and Rotenberg , E . 2003. Fast: Frequency-aware static timing analysis . In IEEE Real-Time Systems Symposium. 40--51 . Seth, K., Anantaraman, A., Mueller, F., and Rotenberg, E. 2003. Fast: Frequency-aware static timing analysis. In IEEE Real-Time Systems Symposium. 40--51."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/384196.384230"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011132221066"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008190423977"},{"volume-title":"Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED-98)","author":"Zyuban V.","key":"e_1_2_1_29_1","unstructured":"Zyuban , V. and Kogge , P . 1998. The energy complexity of register files . In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED-98) . ACM Press, New York. 305--310. 10.1145\/280756.280943 Zyuban, V. and Kogge, P. 1998. The energy complexity of register files. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED-98). ACM Press, New York. 305--310. 10.1145\/280756.280943"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132357.1132364","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132357.1132364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132357.1132364"}},"subtitle":["Frequency-aware static timing analysis"],"short-title":[],"issued":{"date-parts":[[2006,2]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["10.1145\/1132357.1132364"],"URL":"https:\/\/doi.org\/10.1145\/1132357.1132364","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2006,2]]},"assertion":[{"value":"2006-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}