Static scheduling of hard real-time code with instruction-level timing accuracy

In hard real-time systems, a timing fault may yield catastrophic results. Dynamic scheduling provides the flexibility to compensate for unexpected events at runtime; however, scheduling overhead at runtime is relatively large, constraining both the accuracy of the timing and the complexity of the scheduling analysis. In contrast, static scheduling need not have any runtime overhead. Thus, it has the potential to guarantee the precise time at which each instruction implementing a control action will execute. This paper presents a new approach to the problem of analyzing high-level language code, augmented by arbitrary before and after timing constraints, to provide a valid static schedule. Our technique is based on instruction-level compiler code scheduling and timing analysis, and can ensure the timing of control operations to within a single instruction clock cycle. Because the search space for a valid static schedule is very large, a novel adaptive genetic search algorithm was developed.