检索结果-内蒙古大学图书馆

worst-case execution time analysis-driven object cache design

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2012年第8期24卷 753-771页

作者： Huber, Benedikt Puffitsch, Wolfgang Schoeberl, Martin Vienna Univ Technol Inst Comp Engn A-1040 Vienna Austria Tech Univ Denmark Dept Informat & Math Modeling Copenhagen Denmark

Hard real-time systems need a time-predictable computing platform to enable static worst-case execution time (WCET) analysis. All performance-enhancing features need to be WCET analyzable. However, standard data caches containing heap-allocated data are very hard to analyze statically. In this paper we explore a new object cache design, which is driven by the capabilities of static WCET analysis. Simulations of standard benchmarks estimating the expected average case performance usually drive computer architecture design. The design decisions derived from this methodology do not necessarily result in a WCET analysis-friendly design. Aiming for a time-predictable design, we therefore propose to employ WCET analysis techniques for the design space exploration of processor architectures. We evaluated different object cache configurations using static analysis techniques. The number of field accesses that can be statically classified as hits is considerable. The analyzed number of cache miss cycles is 346% of the access cycles needed without a cache, which agrees with trends obtained using simulations. Standard data caches perform comparably well in the average case, but accesses to heap data result in overly pessimistic WCET estimations. We therefore believe that an early architecture exploration by means of static timing analysis techniques helps to identify configurations suitable for hard real-time systems. Copyright (C) 2011 John Wiley & Sons, Ltd.

关键词： real-time systems time-predictable computer architecture worst-case execution time analysis data cache

来源：评论

学校读者我要写书评

暂无评论

worst-case execution time analysis at Low Cost

引用

IFAC Proceedings Volumes 1997年第15期30卷 17-22页

作者： Peter Puschner Technische Universität Wien Austria

The computation of worst-case execution times (WCETs) of tasks involves the description of possible execution paths on source level, the translation of the program and the path information to the machine level, the timing analysis at the machine level, and the documentation of the timing at the source level. These steps of WCET analysis strongly suggest the cooperation between compilers and machine-level WCET tools, and in fact some prototype compilers/WCET analyzers exist. To this date there exists, however, no commercial compiler that supports WCET analysis. This paper describes a light-weight approach to WCET analysis that does not depend on a specific compiler and thus reduces the dependency on compiler builders. The approach uses a tool to read the path information contained in the source code and map this information onto the assembler program. A low-level WCET analysis tool then computes the desired timing information of the annotated assembler program. Experiments with a simple prototype tool demonstrate the feasibility of the approach for simple programs and a moderately optimizing compiler.

关键词： worst-case execution time analysis execution times Performance analysis Real-time Languages Real-time Computer Systems Real-time Tasks Methodology

来源：评论

学校读者我要写书评

暂无评论

Refinement of worst-case execution time bounds by graph pruning

引用

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2014年第3-4期40卷 155-170页

作者： Brandner, Florian Jordan, Alexander ENSTA Paris Tech Comp Sci & Syst Engn Dept F-91762 Palaiseau France Tech Univ Denmark Embedded Syst Engn Sect DK-2800 Lyngby Denmark

As real-time systems increase in complexity to provide more and more functionality and perform more demanding computations, the problem of statically analyzing the worst-case execution time (WCET) bound of real-time programs is becoming more and more time-consuming and imprecise. The problem stems from the fact that with increasing program size, the number of potentially relevant program and hardware states that need to be considered during WCET analysis increases as well. However, only a relatively small portion of the program actually contributes to the final WCET bound. Large parts of the program are thus irrelevant and are analyzed in vain. In the best case this only leads to increased analysis time. Very often, however, the analysis of irrelevant program parts interferes with the analysis of those program parts that turn out to be relevant. We explore a novel technique based on graph pruning that promises to reduce the analysis overhead and, at the same time, increase the analysis' precision. The basic idea is to eliminate those program parts from the analysis problem that are known to be irrelevant for the final WCET bound. This reduces the analysis overhead, since only a subset of the program and hardware states have to be tracked. Consequently, more aggressive analysis techniques may be applied, effectively reducing the overestimation of the WCET. As a side-effect, interference from irrelevant program parts is eliminated, e.g., on addresses of memory accesses, on loop bounds, or on the cache or processor state. First experiments using a commercial WCET analysis tool show that our approach is feasible in practice and leads to reductions of up to 12% when a standard IPET approach is used for the analysis. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： worst-case execution time analysis Iterative refinement Graph pruning

来源：评论

学校读者我要写书评

暂无评论

Deadlock and WCET analysis of barrier-synchronized concurrent programs

引用

COMPUTING 2021年第5期103卷 749-770页

作者： Mittermayr, Robert Blieberger, Johann Vienna Univ Technol Inst Comp Aided Automat Vienna Austria

Kronecker algebra until now has been applied to concurrent programs that use semaphores and protected objects for synchronization. Like many other programming languages, Ada uses barriers, too. In this paper, we present a new synchronization construct for barriers. By applying this, we are able to statically analyze Ada multi-tasking programs that employ barriers for synchronization issues. It turns out that we can use our existing Kronecker algebra implementation completely unmodified for concurrent program graphs using such barrier synchronization primitives. In addition, we extend a static WCET technique such that our barrier synchronization primitive is supported.

关键词： Barrier synchronization worst-case execution time analysis Deadlocks Kronecker algebra Concurrent systems Multi-threaded programs

来源：评论

学校读者我要写书评

暂无评论

Transforming flow information during code optimization for timing analysis

引用

REAL-time SYSTEMS 2010年第1-2期45卷 72-105页

作者： Kirner, Raimund Puschner, Peter Prantl, Adrian Vienna Univ Technol Inst Tech Informat A-1040 Vienna Austria Vienna Univ Technol Inst Comp Sprachen A-1040 Vienna Austria

The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code. In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level. We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.

关键词： worst-case execution time analysis Real-time languages Compiler optimizations Code transformation Abstract interpretation Graph transformation

来源：评论

学校读者我要写书评

暂无评论

Analyzing the worst-case execution time for Instruction Caches with Prefetching

引用

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS 2008年第1期8卷 1–19页

作者： Yan, Jun Zhang, Wei So Illinois Univ Dept Elect & Comp Engn Carbondale IL 62901 USA

time predictability is one of the most important design considerations for real-time systems. In this article, we study the impact of instruction prefetching on the worst-case performance of instruction caches. We extend the static cache simulation technique to model and compute the worst-case instruction cache performance with prefetching. The evaluation results show that instruction prefetching can benefit both the average-case and worst-case performance;however, the degree of the worst-case performance improvement due to instruction prefetching is less than that of the average-case performance. As a result, the time variation of computing is increased by instruction prefetching. Also, our experimental results indicate that the prefetching distance can significantly impact the worst-case performance of instruction caches with instruction prefetching. Specifically, when the prefetching distance is equal to the L1 miss penalty, the worst-case execution time with instruction prefetching is minimized.

关键词： worst-case execution time analysis hard real-time instruction prefetching instruction caches

来源：评论

学校读者我要写书评

暂无评论

worst-case execution time Calculation for Query-based Monitors by Witness Generation

引用

ACM Transactions on Embedded Computing Systems 2021年第6期20卷 1–36页

作者： Márton Búr Kristóf Marussy Brett H. Meyer Dániel Varró McGill University Quebec Canada Budapest University of Technology and Economics Hungary

Runtime monitoring plays a key role in the assurance of modern intelligent cyber-physical systems, which are frequently data-intensive and safety-critical. While graph queries can serve as an expressive yet formally precise specification language to capture the safety properties of interest, there are no timeliness guarantees for such auto-generated runtime monitoring programs, which prevents their use in a real-time setting. While worst-case execution time (WCET) bounds derived by existing static WCET estimation techniques are safe, they may not be tight as they are unable to exploit domain-specific (semantic) information about the input models. This article presents a semantic-aware WCET analysis method for data-driven monitoring programs derived from graph queries. The method incorporates results obtained from low-level timing analysis into the objective function of a modern graph solver. This allows the systematic generation of input graph models up to a specified size (referred to as witness models) for which the monitor is expected to take the most time to complete. Hence, the estimated execution time of the monitors on these graphs can be considered as safe and tight WCET. Additionally, we perform a set of experiments with query-based programs running on a real-time platform over a set of generated models to investigate the relationship between execution times and their estimates, and we compare WCET estimates produced by our approach with results from two well-known timing analyzers, aiT and OTAWA.

关键词： Real-time systems worst-case execution time analysis graph queries model generation

来源：评论

学校读者我要写书评

暂无评论

Code analysis for temporal predictability

引用

REAL-time SYSTEMS 2006年第3期32卷 253-277页

作者： Gustafsson, J Lisper, B Kirner, R Puschner, P Malardalen Univ Dept Comp Sci & Elect Vasteras Sweden Vienna Univ Technol Inst Informat Technol Vienna Austria

The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development.

关键词： worst-case execution time analysis real-time languages compiler optimizations code transformation abstract interpretation graph transformation

来源：评论

学校读者我要写书评

暂无评论

Persistence-Based Branch Misprediction Bounds for WCET analysis 15

Persistence-Based Branch Misprediction Bounds for WCET Analy...

引用

30th ACM Symposium on Applied Computing (SAC)

作者： Puffitsch, Wolfgang Tech Univ Denmark Dept Appl Math & Comp Sci Lyngby Denmark

ISBN: (纸本)9781450331968

Branch prediction is an important feature of pipelined processors to achieve high performance. However, it can lead to overly pessimistic worst-case execution time (WCET) bounds when being modeled too conservatively. This paper presents bounds on the number of branch mispredictions for local dynamic branch predictors. To handle interferences between branch instructions we use the notion of persistence, a concept that is also found in cache analyses. The bounds apply to branches in general, not only to branches that close a loop. Furthermore, the bounds can be easily integrated into integer linear programming formulations of the WCET problem. An evaluation on a number of benchmarks shows that with these bounds, dynamic branch prediction does not necessarily lead to higher WCET bounds than static prediction schemes.

关键词： worst-case execution time analysis branch prediction

来源：评论

学校读者我要写书评

暂无评论

Data Cache analysis by Counting Integer Points 2021

Data Cache Analysis by Counting Integer Points

引用

29th International Conference on Real-time Networks and Systems (RTNS)

作者： Sotin, Pascal Vermande, Quentin Casse, Hugues IRIT UT2J Toulouse France Ecole Normale Super Paris France IRIT UPS Toulouse France

ISBN: (纸本)9781450390019

The scheduling of reliable real-time systems require a precise and sound analysis of the execution times of their tasks. Part of these execution times is spent fetching data from the main memory to the cache memories. These fetch events occur on cache misses, but cache misses are hard to predict when the program accesses an array. An imprecise cache miss analysis can lead to an imprecise but still sound worst-case execution time (WCET) analysis. In this article we present a framework for deriving an upper bound to the number of times a data-accessing instruction triggers a cache miss. Backed by this framework, we present an analysis that produces numeric or symbolic bounds, by reasoning on a short history of accesses and by counting the number of integer points in a volume with an existing tool (Barvinok). Using such bounds will improve the precision of the estimations delivered by the WCET analyses.

关键词： static analysis data cache analysis formal methods worst-case execution time analysis precondition calculus

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：