|
|
|
|
|
|
|
STEM |
|
|
Real-time systems pose special challenges to compilers and their run-time systems. Generated code should fulfill fixed time deadlines. These deadlines are often quite short, necessitating very efficient code on fast hardware, for example multi-processors or super-scalar digital signal processors (DSPs). Automatic memory management is a useful technique that helps to prevent many bugs which otherwise would be hard to find in programs. Unfortunately, existing garbage collection techniques are known to have unpredictable behavior and can thus not be used in real time systems.
One of the problems being studied in this research project is how to make garbage collection available for real time programmers by making the garbage collection predictable and fast. There are some systems that manage this, but they either require special hardware or are very limited. The approach used is to move work from run-time to compile time. This will decrease the work of the garbage collector, thus making it possible to use methods which are more predictable, e.g. RT-Reference Counting which is a modified variation of the standard reference counting technique. The initial implementation is currently integrated in a real-time Java environment (RT-Java) where more extensive analysis will be conducted. The outcome of the analysis will be used for improvements of both fundamental algorithms and the implementation.
In order to achieve high performance on parallel or superscalar hardware, parallelization and code scheduling techniques are being investigated. Code which is the result of physical modeling or block oriented modeling, is often on a single assignment form, which simplifies the scheduling problem. Therefore, we are currently studying code scheduling techniques for single assignment code from Modelica and real-time Java, taking communication costs into account and allowing duplication of code. A major goal of this project is to achieve significant speed-up to keep the short deadlines needed in hard real-time systems.
When generating code for time-critical applications, all subproblems of code generation, such as instruction selection, register allocation, and instruction scheduling, should be considered together, both with a local and a global scope of program optimization. In contrast to standard compilers, the code generator can here spend much larger resources of space and time on static optimizations. Especially when compiling for irregular target architectures (such as many DSPs), the code generation subproblems can no longer be treated in separate, consecutive phases of the compiler back-end, but must instead be solved as a single, integrated optimization problem. In a recently started project, we plan to devise new static optimization techniques for integrated code generation based on dynamic programming and compare these to state-of-the-art approaches such as those based on integer linear programming.
Difficult problems encountered when constructing and analyzing large, real-time software systems are often of a temporal nature. Complex reasoning tasks arise since one have to reason about simultaneous and concurrent actions whose order relationships are recorded by unsynchronized clocks. This project aims at providing algorithmic tools for efficient handling of temporal problems in the development of industrial-scale software systems. The main goal is to investigate how temporal problems under complex time models can be efficiently solved and to apply the results to complex software systems, e.g., real-time and/or distributed systems. Since we expect that many of the encountered problems will be computationally hard, we will also investigate the applicability of relaxation methods and approximation techniques.
Graduate students: Tobias Ritzau (lic 1999), Peter Aronsson, Andrzej
Bednarski, and Mattias Broxvall.
Supervisors: Peter Fritzson, Peter Jonsson, Uwe Assmann and Christoph Kessler.