Transformations and analysis of parallel real time programs

The problem of schedulability analysis of a set of real time programs form a NP complete problem. The exponential complexity of analysis is a direct result of the complexity in the real time programs, as a combinatorial explosion takes place when trying to determine access patterns of shared resources. Thus, to transform the original programs to a less complex form, while preserving its timing characteristics, is the only viable solution. By using such transformations to reduce the complexity of real time programs, it is possible to schedulability analyze programs at compile time efficiently, without adding an unnecessary overhead to the compilation time. A set of suitable transformations and run time scheduling algorithms are introduced and implemented in C++. A library of transformations and analysis routines are provided. The library routines can be used to build prototype schedulability analyzers for testing various analysis techniques. These transformations and the scheduling algorithm will be an integral part of the real time compiler for the real time language RTL. The RTL compiler will not only produce fast and efficient code for an arbitrarily specified real time hardware architecture, but also will provide the worst case timing characteristics for the programs