| 摘要: |
| 实时系统时间分析的首要任务是估计程序的最坏情况执行时间(worst-case execution time，简称WCET).程序的WCET 通常受到硬件体系结构的影响，Cache则是其中最为突出的因素之一.对面向WCET计算的Cache分析研究进行了综述，介绍了经典Cache分析框架与Cache分析核心技术，并从循环结构分析、数据Cache分析、多级Cache分析、多核共享Cache分析、非LRU替换策略分析等角度介绍了Cache分析在不同维度上的研究问题与主要挑战，总结了现有技术的优缺点，展望了Cache分析研究的未来发展方向. |
| 关键词: 实时系统 WCET(worst-case execution time) Cache 分析 时间分析 抽象解释 |
| DOI：10.13328/j.cnki.jos.004529 |
| 分类号: |
| 基金项目:国家自然科学基金（61100023, 61300022）；中央高校基本科研业务费（N120404008） |
|
| Survey of Cache Analysis for Worst-Case Execution Time Estimation |
|
LÜ Ming-Song, GUAN Nan, WANG Yi
|
|
School of Information Science and Engineering, Northeastern University, Shenyang 110819, China
|
| Abstract: |
| 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. |
| Key words: real-time system WCET (worst-case execution time) cache analysis timing analysis abstract interpretation |
