Experiments with a program timing tool based on source-level timing schema

Abstract

A timing tool has been implemented for a subset of C as an initial experiment in validating a methodology for predicting the deterministic execution times of programs. The tool is based on formal timing schema that are defined for each source level construct (procedures, statements, expressions). The tool accepts a program and bounds for each loop, and produces predictions for best and worst case execution times. Two versions of the tool were written, using two extremes of granularity for the atomic elements of the timing schema. Within the constraints of the target architecture and compiler, measured execution times for a variety of simple constructs and programs agree with times predicted by the tool. The implementation decomposes naturally into a system-independent part, which is believed to be determined by the 'timing semantics' of the language, and a lower-level system-dependent portion. The experiments validate the general timing schema approach but also point out a number of problems and possible refinements.<>