Hierarchical Timing Language


Abstract

Hierarchical Timing Language (HTL) is a hierarchical coordination language for distributed, hard real-time applications. HTL programs determine portable and predictable real-time behavior of periodic software tasks running on a possibly distributed system of host computers. An HTL program specifies task-to-host mappings, task frequencies, mode switching, and I/O times and dependencies but not task implementations, which are assumed to be done in some general purpose language such as C or Java. A task in HTL is essentially sequential code that reads input, computes, and writes output. HTL offers two fully hierarchical programming constructs: (sequential, conditional, parallel) composition of tasks as well as refinement of abstract into concrete tasks. An abstract task has a frequency, specific I/O times and dependencies, and a worst-case execution time (WCET) but no implementation. An abstract task is a temporally conservative placeholder for a concrete task with an implementation. A concrete task refines an abstract task if the concrete task has the same frequency but more time to compute, i.e., relaxed I/O times and dependencies, and less WCET than the abstract task. The result is that a concrete HTL program is time-safe (schedulable) if it refines a time-safe abstract HTL program. In general, checking refinement in HTL is exponentially faster than checking time safety (schedulability). However, abstract HTL programs are temporally conservative approximations of concrete HTL programs, i.e., there are abstract HTL programs that are not time-safe but for which time-safe refinements exist