ZTE Communications ›› 2024, Vol. 22 ›› Issue (1): 87-94.DOI: 10.12142/ZTECOM.202401010
• Review • Previous Articles Next Articles
LUO Haoran1, HU Shuisong1, WANG Wenyong1(), TANG Yuke2, ZHOU Junwei2
Received:
2023-06-21
Online:
2024-03-29
Published:
2024-03-28
About author:
LUO Haoran received his bachelor's degree from Sichuan University, China. He is pursuing a master's degree at University of Electronic Science and Technology of China (UESTC). Driven by a deep passion for computer science, he actively engages in various academic activities and research projects.Supported by:
LUO Haoran, HU Shuisong, WANG Wenyong, TANG Yuke, ZHOU Junwei. Research on Multi-Core Processor Analysis for WCET Estimation[J]. ZTE Communications, 2024, 22(1): 87-94.
Add to citation manager EndNote|Ris|BibTeX
URL: http://zte.magtechjournal.com/EN/10.12142/ZTECOM.202401010
Comparative Content | Static WCET Analysis | Dynamic WCET Analysis |
---|---|---|
Safety of analysis results | Safe | Unsafe |
Analysis complexity | High | Low |
Adaptability to new architectures | Bad | Good |
Analytical accuracy | Mainly depending on the analysis technique | Mainly depending on the test vector |
User assistance that improves the quality of analysis | Providing additional control flow information | Providing better test vectors |
Table 1 Comparison of static and dynamic WCET analysis methods
Comparative Content | Static WCET Analysis | Dynamic WCET Analysis |
---|---|---|
Safety of analysis results | Safe | Unsafe |
Analysis complexity | High | Low |
Adaptability to new architectures | Bad | Good |
Analytical accuracy | Mainly depending on the analysis technique | Mainly depending on the test vector |
User assistance that improves the quality of analysis | Providing additional control flow information | Providing better test vectors |
Comparative Content | Analysis Based on Address Mapping | Analysis Based on Logical Order | Analysis Based on Model Checking | Analysis Based on Time Series Category |
---|---|---|---|---|
Analysis accuracy | Low | Higher | High | High |
Analysis complexity | Low | High | High | Higher |
Analytical method | Address mapping analysis | Cache conflict graph and logic analysis | Time automaton | Block-based temporal modeling |
Table 2 Comparison of different shared cache conflict analysis methods
Comparative Content | Analysis Based on Address Mapping | Analysis Based on Logical Order | Analysis Based on Model Checking | Analysis Based on Time Series Category |
---|---|---|---|---|
Analysis accuracy | Low | Higher | High | High |
Analysis complexity | Low | High | High | Higher |
Analytical method | Address mapping analysis | Cache conflict graph and logic analysis | Time automaton | Block-based temporal modeling |
Tool | Company | Method | Target Processors | Core Area | ||
---|---|---|---|---|---|---|
Cache | Pipeline | Periphery | ||||
aiT | AbsInt | Static analysis | Am486, IntelDX4, ARM, PowerPC, etc. | I-Cache, D-Cache, direct/SA, LRU, PLRU, pseudo round robin | In-order/ out-of-order | PCI bus |
RapiTime | Rapita Systems | Hybrid-based | - | - | - | - |
XMOS Timing Analyzer | XMOS Ltd. | Measurement-based | XMOS processors | - | - | - |
Table 3 Comparison of commercial multi-core WCET analysis tools
Tool | Company | Method | Target Processors | Core Area | ||
---|---|---|---|---|---|---|
Cache | Pipeline | Periphery | ||||
aiT | AbsInt | Static analysis | Am486, IntelDX4, ARM, PowerPC, etc. | I-Cache, D-Cache, direct/SA, LRU, PLRU, pseudo round robin | In-order/ out-of-order | PCI bus |
RapiTime | Rapita Systems | Hybrid-based | - | - | - | - |
XMOS Timing Analyzer | XMOS Ltd. | Measurement-based | XMOS processors | - | - | - |
Tool | Institution | Method | Target Processors | Core Area | ||
---|---|---|---|---|---|---|
Cache | Pipeline | Periphery | ||||
Chronos | National University of Singapore | Static analysis | SimpleScalar | I-cache, D-cache, Unified cache, Direct/SA, LRU | Multi-issue superscalar, in-order, out-order, dynamic branch prediction | |
Bound-T | Tidorum | Static analysis | SPARC/ERC32, etc. | - | - | IPET |
Heptane | IRISA | Static analysis | - | D-cache, I-cache, | Branch prediction | |
SWEET | Mälardalen Real-Time Research Centre | Static analysis | NECV850E ARM9 | - | - | Flow analysis |
Table 4 Comparison of open-source multi-core WCET analysis tools
Tool | Institution | Method | Target Processors | Core Area | ||
---|---|---|---|---|---|---|
Cache | Pipeline | Periphery | ||||
Chronos | National University of Singapore | Static analysis | SimpleScalar | I-cache, D-cache, Unified cache, Direct/SA, LRU | Multi-issue superscalar, in-order, out-order, dynamic branch prediction | |
Bound-T | Tidorum | Static analysis | SPARC/ERC32, etc. | - | - | IPET |
Heptane | IRISA | Static analysis | - | D-cache, I-cache, | Branch prediction | |
SWEET | Mälardalen Real-Time Research Centre | Static analysis | NECV850E ARM9 | - | - | Flow analysis |
1 | LYU M S, GUAN N, ZHANG Y, et al. A survey of WCET analysis of real-time operating systems [C]//Proc. International Conference on Embedded Software and Systems. IEEE, 2009: 65–72. DOI: 10.1109/ICESS.2009.24 |
2 | LYU M S. Research on worst-case execution time analysis techniques of real-time systems [D]. Shenyang: Northeastern University, 2010 |
3 | HECKMANN R, LANGENBACH M, THESING S, et al. The influence of processor architecture on the design and the results of WCET tools [J]. Proceedings of the IEEE, 2003, 91(7): 1038–1054. DOI: 10.1109/JPROC.2003.814618 |
4 | LI X F, ROYCHOUDHURY A, MITRA T. Modeling out-of-order processors for WCET analysis [J]. Real-time systems, 2006, 34(3): 195–227. DOI: 10.1007/s11241-006-9205-5 |
5 | YAN J, ZHANG W. WCET analysis for multi-core processors with shared L2 instruction caches [C]//Proc. IEEE Real-Time and Embedded Technology and Applications Symposium. IEEE, 2008: 80–89. DOI: 10.1109/RTAS.2008.6 |
6 | LYU M, YI W, GUAN N, et al. Combining abstract interpretation with model checking for timing analysis of multicore software [C]//31st IEEE Real-Time Systems Symposium. IEEE, 2010: 339–349. doi: 10.1109/RTSS.2010.30 . |
7 | ZHU Y A, SHI X C, YAO Y, et al. A WCET analysis method for multi-core processors with multi-tier coherence protocol [J]. Journal of computer research and development, 2023, 60(1): 30–42. DOI: 10.7544/issn1000-1239.202111244 |
8 | CHATTOPADHYAY S, ROYCHOUDHURY A, MITRA T. Modeling shared cache and bus in multi-cores for timing analysis [C]//Proc. 13th International Workshop on Software & Compilers for Embedded Systems. ACM, 2010: 1–10. DOI: 10.1145/1811212.1811220 |
9 | KELTER T, FALK H, MARWEDEL P, et al. Bus-aware multicore WCET analysis through TDMA offset bounds [C]//Proc. 23rd Euromicro Conference on Real-Time Systems. IEEE, 2011: 3–12. DOI: 10.1109/ECRTS.2011.9 |
10 | DEVERGE J F, PUAUT I. Safe measurement-based WCET estimation [C]//5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). OASICS, 2007: 13–16. DOI: 10.4230/OASICS.WCET.2005.808 |
11 | RIEDER B, WENZEL I, STEINHAMMER K, et al. Using a runtime measurement device with measurement-based WCET analysis [C]//Embedded System Design: Topics, Techniques and Trends, Proc. of IFIP TC10 Working Conference: International Embedded Systems Symposium (IESS). Springer, 2007: 15–26. DOI:10.1007/978-0-387-72258-0_2 |
12 | WENZEL I, RIEDER B, KIRNER R, et al. Automatic timing model generation by CFG partitioning and model checking [C]//Design, Automation and Test in Europe. IEEE, 2005: 606-611. DOI: 10.1109/DATE.2005.76 |
13 | DASARI D, NELIS V. An analysis of the impact of bus contention on the WCET in multicores [C]//Proc. IEEE 14th International Conference on High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems. IEEE, 2012: 1450–1457. DOI: 10.1109/HPCC.2012.212 |
14 | CHATTOPADHYAY S, ROYCHOUDHURY A. Unified cache modeling for WCET analysis and layout optimizations [C]//Proc. 30th IEEE Real-Time Systems Symposium. IEEE, 2009: 47–56. DOI: 10.1109/RTSS.2009.20 |
15 | PUSCHNER P, BURNS A. Guest editorial: a review of worst-case execution-time analysis [J]. Real-time systems, 2000, 18(2): 115–128. DOI: 10.1023/A: 1008119029962 |
16 | THEILING H, FERDINAND C, WILHELM R. Fast and precise WCET prediction by separated cache and path analyses [J]. Real-time systems, 2000, 18(2): 157–179. DOI: 10.1023/A: 1008141130870 |
17 | LI X F, LIANG Y, MITRA T, et al. Chronos: a timing analyzer for embedded software [J]. Science of computer programming, 2007, 69(1/2/3): 56–67 |
18 | HUYNH B K, JU L, ROYCHOUDHURY A. Scope-aware data cache analysis for WCET estimation [C]//Proc. 17th IEEE Real-Time and Embedded Technology and Applications Symposium. IEEE, 2011: 203–212. DOI: 10.1109/RTAS.2011.27 |
19 | LIANG Y, DING H P, MITRA T, et al. Timing analysis of concurrent programs running on shared cache multi-cores [J]. Real-time systems, 2012, 48(6): 638–680. DOI: 10.1007/s11241-012-9160-2 |
20 | CHEN F Y, ZHANG D S, WANG Z Y. Static analysis of Run-time inter-thread interferences in shared cache multi-core architectures based on instruction fetching timing [C]//Proc. IEEE International Conference on Computer Science and Automation Engineering. IEEE, 2011: 208–212. DOI: 10.1109/CSAE.2011.5952455 |
21 | CHEN F Y, ZHANG D S, WANG Z Y. Static analysis of run-time inter-core interferences for concurrent programs in shared cache multicore architectures [J]. Applied mechanics and materials, 2012, 198/199: 523–527. DOI: 10.4028/www.scientific.net/AMM.198-199.523 |
22 | CHATTOPADHYAY S, CHONG L K, ROYCHOUDHURY A, et al. A unified WCET analysis framework for multicore platforms [J]. ACM transactions on embedded computing systems, 13(4s): 124. DOI: 10.1145/2584654 |
23 | DAVIS R I, CUCU-GROSJEAN L. A survey of probabilistic timing analysis techniques for real-time systems [J]. Leibniz Transactions on Embedded Systems (LITES), 2019, 6(1): 03:1–03:60. DOI: 10.4230/LITES-v006-i001-a003 |
24 | AbsInt. aiT [EB/OL]. [2023-01-17]. |
25 | Systems Rapita. Rapitime [EB/OL]. [2023-01-17]. |
26 | XMOS Ltd. XMOS [EB/OL]. [2023-01-17]. |
27 | National University of Singapore. Chronos [EB/OL]. [2023-01-17]. |
28 | Ltd Tidorum. Bound-T execution time analyzer [EB/OL]. [2023-01-17]. |
29 | team IRISA. Heptane [EB/OL]. [2023-01-17]. |
30 | MRTC. Swedish execution time analysis tool [EB/OL]. [2023-01-17]. |
No related articles found! |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||