F. Brandner, S Hepp, A. Jordan:
"Criticality: static profiling for real-time programs";
With the increasing performance demand in real-time systems it becomes
more and more important to provide feedback to programmers and software develop-
ment tools on the performance-relevant code parts of a real-time program. So far, this
information was limited to an estimation of the worst-case execution time (WCET)
and its associated worst-case execution path (WCEP) only. However, both, the WCET
and the WCEP, only provide partial information. Only code parts that are on one of
the WCEPs are indicated to the programmer. No information is provided for all other
code parts. To give a comprehensive view covering the entire code base, tools in the
spirit of program profiling are required.
This work proposes an efficient approach to compute worst-case timing informa-
tion for all code parts of a program using a complementary metric, called criticality.
Every statement of a program is assigned a criticality value, expressing how criti-
cal the code is with respect to the global WCET. This gives valuable information how
close the worst execution path passing through a specific program part is to the global
WCEP. We formally define the criticality metric and investigate some of its properties
with respect to dominance in control-flow graphs. Exploiting some of those proper-
ties, we propose an algorithm that reduces the overhead of computing the metric to
cover complete programs. We also investigate ways to efficiently find only those code
parts whose criticality is above a given threshold.
Experiments using well-established real-time benchmark programs show an inter-
esting distribution of the criticality values, revealing considerable amounts of highly
critical as well as uncritical code. The metric thus provides ideal information to pro-
grammers and software development tools to optimize the worst-case execution time
of these programs.
Criticality, Worst-case execution time, Program profiling
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.