Reconfigurable embedded computing opens many interesting possibilities for efficiency and reliability improvement. Still, it is necessary to verify whether the reconfigurable embedded computer system fulfills its timing requirements. Purely static worst-case execution time (WCET) analysis is not the best choice for verifying the timing behavior of reconfigurable embedded computer systems, as frequent re-modeling of different hardware configurations is not practicable. We describe measurement-based timing analysis as an approach that is better applicable for reconfigurable applications. Measurement-based timing analysis is a hybrid approach that combines static program analysis techniques, borrowed from static WCET analysis, with empirical learning of the application’s timing behavior by performing systematic measurements. But even the MBTA approach is challenged by the reconfigurable computing paradigm by the need for adequate coverage of the reconfigurable fabric.
TopIntroduction
Embedded computer systems have to meet the real-time requirements imposed by their environment. To ensure that an embedded computer system can meet its deadlines, an upper bound of the execution time of all components must be known (Kirner & Puschner, 2005)(Wilhelm, et al., 2008). Because the determination of the actual worst-case execution time (WCET) is a hard problem, estimates are usually used.
For safety-critical applications these estimates have to be safe, i.e., they must not underestimate the actual WCET. Such safe estimates are usually obtained through static WCET analysis. Depending on the complexity of the analyzed system, these analyses tend to introduce a high pessimism, i.e. the obtained estimates are overestimations. Moreover, the method depends on the availability of precise hardware models. The construction of such models is usually expensive, error-prone, and requires the availability of a complete hardware specification.
In soft real-time systems the miss of a deadline is assumed not to have catastrophic consequences. Due to a higher cost pressure compared to hard real-time systems, high hardware utilization is a top priority for soft real-time systems. In response to these needs, measurement-based timing analysis that employ a hybrid approach of systematic execution-time measurements and static program analysis has emerged, aiming for a good tradeoff between precision and flexibility (Wilhelm, et al., 2008)(Kirner, Wenzel, Rieder, & Puschner, 2006)(Bernat, Colin, & Petters, 2002). A primary strength of the approach is the relatively low retargeting effort when the new target hardware becomes available.
By timing analysis we mean the analysis of the execution time of a given program in a specific computational hardware environment. A real-time application can be a very complex system, where many individual computational tasks are concurrently running in a distributed system consisting of several computational nodes that communicate over a network infrastructure (Kopetz, 1997). Within such a system, it is the duty of the task scheduler to assign the computational resources to the individual tasks in such a way that the system can deliver its service in a timely manner. However, to fulfill its planning task, the scheduler must know the computational requirements of each task in advance.
Practical scheduling algorithms require information about the WCET of each task, where a task is defined as the execution of a sequential program that starts with reading some input data and terminates with the production of some output data.
The current state-of-the-art in WCET analysis is to examine tasks individually. This means that present analysis methods cannot handle blocking tasks (sometimes called complex tasks) that can be delayed by other tasks or external events. Rather, the fields of WCET analysis and scheduling usually adopt the concept of a simple task that cannot be blocked by outside events. As a consequence, the execution time of an individual task becomes independent of the interaction with other tasks and the outside world, and can be analyzed in isolation. It should be noted that it is, to a certain extent, possible to implement the behavior of a complex task by a set of simple tasks that communicate only via their input and output states.
Figure 1 illustrates the problem of analyzing the execution time of an individual task: Depending on the actual input that a task obtains when it is started, its execution time can vary. The figure depicts how a frequency distribution of execution times over all possible inputs can look like. There is a large concentration of mass on the left hand side, representing typical execution times. When running the program with random data, the observed execution time will likely be found in this range of the execution time spectrum. However, the figure also indicates a small, but relevant set of settings that yield a considerably higher execution time. Because they occur in relatively few situations, they are hard to trigger by random testing.
Figure 1. Example of a timing distribution. There is a large concentration of mass on the left hand side, representing typical execution times. Still, a few cases of considerable higher execution times can be spotted on the right hand side.