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 条

[11]

Dalsgaard A.E., Olesen M.C., Toft M., Rydhof H.R., Guldstrand L.K., METAMOC: Modular execution time analysis using model checking, Proc. of the 10th Int'l Workshop on Worst-Case Execution Time Analysis, pp. 113-123, (2010)

[12]

Gustavsson A., Ermedahl A., Lisper B., Pettersson P., Towards WCET analysis of multicore aarchitectures using UPPAAL, Proc. of the 10th Int'l Workshop on Worst-Case Execution Time Analysis, pp. 101-112, (2010)

[13]

Larsen K.G., Pettersson P., Yi W., UPPAAL in a nutshell, Int'l Journal on Software Tools for Technology Transfer, 1, 2, pp. 134-152, (1997)

[14]

Cousot P., Cousot R., Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proc. of the 4th ACM SIGACT-SIGPLAN Symp. on Principles of Programming Languages, pp. 238-252, (1997)

[15]

Ferdinand C., Cache behavior prediction for real-time systems, (1997)

[16]

Theiling H., Ferdinand C., Wilhelm R., Fast and precise WCET prediction by separated cache and path analyses, Real-Time Systems, 18, 2-3, pp. 157-179, (2000)

[17]

Cullmann C., Cache persistence analysis: A novel approach theory and practice, Proc. of the 2011 SIGPLAN/SIGBED Conf. on Languages, Compilers and Tools for Embedded Systems, pp. 121-130, (2011)

[18]

Huynh B.K., Ju L., Roychoudhury A., Scope-Aware data cache analysis for WCET estimation, Proc. of the 17th IEEE Real-Time and Embedded Technology and Applications Symp., pp. 203-212, (2011)

[19]

Lu M.S., Yi W., Guan N., Yu G., Combining abstract interpretation with model checking for timing analysis of multicore software, Proc. of the 31st IEEE Real-Time Systems Symp., pp. 339-349, (2010)

[20]

White R.T., Healy C.A., Whalley D.B., Mueller F., Harmon M.G., Timing analysis for data caches and set-associative caches, Proc. of the 3rd IEEE Real-Time Technology and Applications Symp., pp. 192-202, (1997)

← 1 2 3 4 5 6 →