Parametric timing analysis

Embedded systems often have real-time constraints. Traditional timing analy sis statically determines the maximum execution time of a task or a program in a real-time system. These systems typically depend on the worst-case ex ecution time of tasks in order to make static scheduling decisions so that tasks can meet their deadlines. Static determination of worst-case executio n times imposes numerous restrictions on real-time programs, which include that the maximum number of iterations of each loop must be known statically . These restrictions can significantly limit the class of programs that wou ld be suitable for a real-time embedded system. This paper describes work-i n-progress that uses static timing analysis to aid in making dynamic schedu ling decisions. For instance, different algorithms with varying levels of a ccuracy may be selected based on the algorithm's predicted worst-case execu tion time and the time allotted for the task We represent the worst-case ex ecution time of a function or a loop as a formula, where the unknown values affecting the execution time are parameterized. This parametric timing ana lysis produces formulas that can then be quickly evaluated at ran-time so d ynamic scheduling decisions can be made with little overhead. Benefits of t his work include expanding the class of applications that can be used in a real-time system, improving the accuracy of dynamic scheduling decisions, a nd more effective utilization of system resources.