page 1  (9 pages)
2to next section

ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems, La Jolla, California, June 1995.

The Cluster Compiler { A Tool for the Design of Time-Triggered

Real-Time Systems

Hermann Kopetz, Roman Nossal

Institut f?ur Technische Informatik, Technical University of Vienna,

Treitlstr. 3/182/1, A-1040 Vienna, Austria

fhk,[email protected]

May 12, 1995


An off-line planning tool that supports the programmer in developing his real-time application is mandatory in the design of time-triggered real-time systems. This paper describes the architecture and the functions of such a tool, the Cluster Compiler, that is in development at our institute. We emphasize on the principle of a strict separation of the local from the global parts of a distributed system and on the consequences for the structure of the design tool arising from this principle.


At present, real-time systems are often designed unsystematically. Conventional software modules are integrated by "real-time specialists" who tune the system parameters (e.g., task priorities, buffer sizes, etc.) during an extensive trial and error period, consuming more than 50% of a project's resources. Why the system performs its functions at the end is sometimes a miracle, even to the "real-time specialists".

To change this deplorable situation we need a proper real-time system architecture, a systematic design methodology, and a set of tools that support the system designer. In the last ten years we have focused our research efforts on the systematic design and developments of a particular class of real-time system architectures, the time-triggered real-time systems [Kop91]. Although we are aware that the time-triggered approach is limited to systems of regular behavior, there is a growing number of applications, e.g., in the domain of automotive electronics, that fit very well to this design paradigm.

In a time-triggered real-time system all computation and communications actions are triggered by the progression of a global time. The recurring global clock tick is the only event which may initiate an action in

such a system. As the occurrence of this event is known a priori the system's actions can be planned off-line.

This off-line planning of communication and processing actions requires extensive tool support. We have realized this during the implementation of timetriggered applications on our MARS architecture. The most important tool support is required for finding the static schedules for the message transmission in the communication system and the task execution in the nodes of the distributed system, and for automatically generating the appropriate data structures for the control of the communication and the operating system in each node. In this paper we present such a planning tool that we call the Cluster Compiler.

The Cluster Compiler combines both aspects of scheduling, i.e., it integrates task and message scheduling into one off-line scheduling tool. As the scheduling problem is known to be NP-hard it is impossible to enumerate all solutions and to design good schedules manually. In the past we have focused on the heuristic search technique IDA* [Kor85] to find appropriate schedules [Foh94]. The cluster compiler is a flexible tool that will also implement other optimization techniques, like genetic algorithms [Hol75, Hou94, Sys91], simulated annealing [Kir83, Nan92, Che95] or tabu search [Glo93, Moo93, Por93].

The Cluster Compiler is the central tool for system design. It has to produce data structures that are consistent within all parts of a time-triggered system implementation, i.e., the protocol software in the communication controllers and the operating system in the nodes. As these data structures control the run-time system functions, they determine the behavior at the interfaces and thus put a number of requirements on the Cluster Compiler.

This paper is organized as follows. After the introduction we give an overview of the time-triggered system architecture that is the target for our Cluster Compiler. In the third section the functions of the Cluster