Universität des Saarlandes

Project : Timing Validation for Hard Real-Time Systems

The purpose of the timinig validation of real-time systems is to guarantee that the set of all tasks that make up the system is schedulable, i.e. meets the given deadlines. This is checked by a schedulability analysis. Such an analysis needs as inputs the worst case execution times (WCETs) of all tasks in the system, their periods, minimal distances of sporadic task invocations etc. Since caches and pipelines are the most determining components for the execution time of a program on a modern CPU, the cache and pipeline behavior must be analyzed to accurately compute an upper bound for the WCET of a task.

A tool for Timing Validation has been developed by the University of the Saarland Embedded Systems (USES) group and AbsInt Angewandte Informatik GmbH. It performs a static analysis of a real-time program to determine the cache and pipeline behavior. Their results are then fed into the worst case execution path analysis, which is used to compute the WCET.

Each analysis is based on a specification of the hardware architecture, e.g. a cache model for the cache analysis, and a pipeline model for the pipeline analysis. They work directly on the machine code level, i.e. the executable program itself. The user has to provide annotations about execution counts of loops to the analysis.

Two timing validation tools have been developed in the course of DAEDALUS, one for the Motorola ColdFire 5307 and one for the Motorola PowerPC 755. Both have been positively evaluated on benchmarks provided by EADS Airbus.

About Saarland University

The Compiler Design Laboratory at Saarland University has experience and competence in all areas of compilation. Lately, research has concentrated on static program analysis, in particular for predicting program behavior on hardware with caches, pipelines, and branch prediction units, and for analyzing properties of heap allocated objects, and on code generation for intraprocessor-parallel targets and DSPs.