SymTA/P

Motivation

Accurate software running time and power analysis are key to optimized system synthesis. In general, imprecise estimation of software execution costs (such as running time and power) increases design risk or leads to inefficient designs. Profiling and simulation are the state-of-the-art in industry, but since exhaustive simulation is impractical, simulation results can only cover part of the system behavior. Static analysis is a more complicated but attractive alternative. It provides lower and upper bounds reflecting data dependent control flow as well as data dependent statement execution cost. In the past, these bounds were wide due to a lack of efficient control flow analysis and architecture modeling techniques. Significant progress in both areas has made formal analysis practical.

Execution Cost Analysis

Intervals for software execution cost depend to a certain extend on the process control flow which depends on process input data. Previous static analysis approaches determine the execution cost of single basic blocks and find a shortest and a longest path defining their execution counts which delivers a lower and an upper bound for the program execution cost. These bounds are very wide because the approaches do not distinguish between input data dependent control flow and program structuring aids. Large parts of typical embedded system program segments have a single program path only. An FIR filter is a simple example and a Fast Fourier Transform is a more complex one. There is only one path executed for any input pattern, even though this path may wrap around many loops, conditional statements and even function calls which are used for program structuring and compacting. Execution cost of these embedded single feasible paths can be determined by simulation delivering exact execution counts of basic blocks and overlapping basic block execution penalties such as the conservative assumption of pipeline stalls.

Execution cost of the software processes and, hence, of the overall system are context dependent. Input data may be given by a context which defines more program segments with single paths. This results in tighter, context dependent execution cost intervals of the processes. SYMTA includes the possibility to explore different target architectures in a very flexible way because off-the-shelf processor simulators and emulation kits can be used to measure execution cost for program segments.

Application

The figure above shows a simplified set of processes implementing the wireless IP standard on a pico cellular base station. The solid lines represent the paths on which different data packets are routed through the process network. Important questions of the system architect can be the power consumption for sending a data packet or the time to set up a connection in the base station for high-level system validation. This should take the system context into account, since for each packet type and destination the processes react with a different control flow. Simulation is always possible and statistical power and timing analysis are feasible, but the first approach is not reliable and the second is just a rough approximation. The SYMTA analysis approach provides reliable and narrow software execution cost intervals for context dependent process execution that is evaluated by the analysis tool.

Current and future research focuses on the analysis of instruction and data cache behavior. Caches in the target architecture usually increase the performance of the system because they bridge the gap between processor speed and memory access time. It is hard to guarantee to meet real time constraints because caches can also decrease the performance of the processor. When cache behavior cannot be predicted at all, a cache miss has to be assumed for every memory access which makes the use of the cache obsolete. So it is often not used in time critical embedded systems. We identify program segments with single feasible paths that enable us to use trace based cache simulators for the given address sequences. Standard data flow analysis is used to predict cache behavior across control structures that depend on input data.

Experimental results show the superiority of our approach in the research community. Designer guided automation of the analysis tool flow will provide mature, industry-strength timing and power estimation tools in the near future.