This article examines dynamic energy consumption caused by data during software execution on deeply embedded microprocessors, which can be significant on some devices. In worst-case energy consumption analysis, energy models are used to find the most costly execution path. Taking each instruction’s worst-case energy produces a safe but overly pessimistic upper bound. Algorithms for safe and tight bounds would be desirable. We show that finding exact worst-case energy is NP-hard, and that tight bounds cannot be approximated with guaranteed safety. We conclude that any energy model targeting tightness must either sacrifice safety or accept overapproximation proportional to data-dependent energy.
Despite this, there are scenarios where WCET is subject to timing anomalies @cite_16 . These arise when a seemingly shorter execution path later results in an overall increase in time. A cache miss may cause the worst execution time locally, but this state may later preclude a subsequent scenario that, with a global view, would in fact be the worst-case.
@cite_16
1499210710 2076285066 2509925782 2104626020
Previous timing analysis methods have assumed that the worst-case instruction execution time necessarily corresponds to the worst-case behavior. We show that this assumption is wrong in dynamically scheduled processors. A cache miss, for example, can in some cases result in a shorter execution time than a cache hit. Many examples of such timing anomalies are provided. We first provide necessary conditions when timing anomalies can show up and identify what architectural features that may cause such anomalies. We also show that analyzing the effect of these anomalies with known techniques results in prohibitive computational complexities. Instead, we propose some simple code modification techniques to make it impossible for any anomalies to occur. These modifications make it possible to estimate WCET by known techniques. Our evaluation shows that the pessimism imposed by these techniques is fairly limited; it is less than 27 for the programs in our benchmark suite. The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools1 and research prototypes. Establishing Worst Case Execution Times (WCET) using Measurement-Based Timing Analysis (MBTA) is only effective if we have reasonable confidence that we have fed the worst case execution trace into the analysis. Therefore for certification, the quality of these traces is of paramount importance. This paper aims to investigate how search algorithms can be used to automatically, and reliably, generate test cases so that appropriate execution traces are available to support MBTA. The work carried out in this paper uses a standard search algorithm and created a number of fitness functions to target the generation of 'good data'. The results are then input into a commercial measurement-based WCET analysis tool. The new fitness functions focus on achieving a combination of full branch coverage and a high number of loop counts, or partial path coverage, however are shown to achieve reliable approximations of the WCET particularly when combined with an MBTA tool. The code items used for the analysis included off the shelf benchmarks, as well as industrial safety-critical aircraft engine control software. The architecture of tools for the determination of worst case execution times (WCETs) as well as the precision of the results of WCET analyses strongly depend on the architecture of the employed processor. The cache replacement strategy influences the results of cache behavior prediction; out-of-order execution and control speculation introduce interferences between processor components, e.g., caches, pipelines, and branch prediction units. These interferences forbid modular designs of WCET tools, which would execute the subtasks of WCET analysis consecutively. Instead, complex integrated designs are needed, resulting in high demand for memory space and analysis time. We have implemented WCET tools for a series of increasingly complex processors: SuperSPARC, Motorola ColdFire 5307, and Motorola PowerPC 755. In this paper, we describe the designs of these tools, report our results and the lessons learned, and give some advice as to the predictability of processor architectures.