aiSee: Cache and Pipeline Analysis

Cache and pipeline analysis results

This graph illustrates the cache and pipeline behavior of a real-time application for PowerPC 755. Each grey subgraph illustrates the behavior of a single assembly instruction. Each red, yellow, or blue subgraph corresponds to a single cache and pipeline state. Each horizontal layer corresponds to one CPU cycle. Vertical branches represent different execution scenarios, e.g. a cache hit and a cache miss at a memory access. The GDL source of the graph was automatically generated by aiT and contains 11994 nodes, 5925 edges and 6121 nested subgraphs. aiSee needs less than 45 seconds to render the whole graph (1.2GHz PC).

In real-time systems, each task has to be completed within a specified time frame in order to ensure that the system works correctly. The consequences of a missed deadline range from simply annoying to disastrous — just imagine a flight control software that does not react in time. It is the duty of the developer to calculate the worst-case execution time (WCET) of each task and thus to guarantee that the tasks will always meet the deadlines specified.

However, computing the WCET is a challenge. Simple testing by repeatedly measuring the execution time of a task is typically not safe: It is often impossible to prove that the conditions determining maximum execution time have been taken into account. And analysis methods that do not consider cache and pipeline behavior typically overestimate the WCET by several orders of magnitude — thus leading to a substantial waste of hardware resources.

aiT WCET Analyzers provide the solution to these problems: They statically analyze a task's intrinsic cache and pipeline behavior based on formal cache and pipeline models. This enables correct and tight upper bounds to be computed for the worst-case execution time. The analysis results are visualized to allow for convenient browsing.

aiT analysis resultsAs an integral part of the Analyzer, aiSee supports the visualization of the worst-case program path (see example). Thanks to the concept of User Actions, it enables interactive inspection of all pipeline and cache states on arbitrary program points. The user simply clicks on a node in the control flow graph and a new aiSee window pops up showing the corresponding set of all possible pipeline and cache states computed on-the-fly by the analyzer.