Survey of Cache analysis for worst-case execution time estimation

被引：0
作者：
Lü, Ming-Song [1 ]
Guan, Nan [1 ]
Wang, Yi [1 ]
机构：
[1] School of Information Science and Engineering, Northeastern University
来源：
Ruan Jian Xue Bao/Journal of Software | 2014年 / 25卷 / 02期
关键词：
Abstract interpretation; Cache analysis; Real-time system; Timing analysis; WCET (worst-case execution time);
D O I：
10.13328/j.cnki.jos.004529
中图分类号：
学科分类号：
摘要：
The main task of real-time system design is to analyze the timing behaviors of a system at design time in order to guarantee that the given timing constraints are met at run time. The key issue is to estimate the Worst-Case Execution Time (WCET) of a program. Typically the WCET is heavily influenced by the hardware features of the target processor, among which Cache is the most influential factor. This article presents a survey on Cache analysis for WCET estimation. It introduces main research problems and challenges in different dimensions, such as the analysis of loops, data caches, multi-level caches, multi-core shared caches, non-LRU replacement policies, etc. The mainstream analysis techniques with their pros and cons are evaluated. An outlook for future research directions of Cache analysis is given in the end. © Copyright 2014, Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：179 / 199
页数：20
相关论文
共 57 条
[1]  
Liu J.W.S., Real-Time Systems, (2000)
[2]  
Wilhelm R., Engblom J., Ermedahl A., Holsti N., Thesing S., Whalley D., Bernat G., Ferdinand C., Heckmann R., Mitra T., Mueller F., Puaut I., Puschner P., Staschulat J., Stenstrom P., The worst-case execution time problem-Overview of methods and survey of tools, ACM Trans. on Embedded Computing Systems, 7, 3, pp. 1-53, (2008)
[3]  
Kirner R., Puschner P., Wenzel I., Measurement-Based worst-case execution time analysis, Proc. of the 3rd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, pp. 7-10, (2005)
[4]  
Patterson D.A., Hennessy J.L., Computer Architecture: A Quantitative Approach, (2011)
[5]  
Li X.F., Roychoudhury A., Mitra T., Modeling out-of-order processors for WCET analysis, Real-Time Systems, 34, 3, pp. 195-227, (2006)
[6]  
Mitra T., Roychoudhury A., A framework to model branch prediction for WCET analysis, Proc. of the 2nd Workshop on Worst Case Execution Time Analysis., pp. 1-4, (2002)
[7]  
Li Y.T.S., Malik S., Performance analysis of embedded software using implicit path enumeration, Proc. of the 32nd ACM/IEEE Design Automation Conf., pp. 456-461, (1995)
[8]  
Clarke E.M., Grumberg O., Peled D.A., Model Checking, (1999)
[9]  
Bengtsson J., Yi W., Timed automata: Semantics, algorithms and tools, Lecture Notes in Computer Science, 3098, pp. 87-124, (2004)
[10]  
Lu M.S., Guan N., Deng Q.X., Yu G., Yi W., McAiT: A timing analyzer for multicore real-time software, Proc. of the 9th Int'l Conf. on Automated Technology for Verification and Analysis, pp. 414-417, (2011)
123456