Throughput optimization by software pipelining of conditional reservation tables

In the world of embedded real-time applications, the optimization of schedules has been since long a major concern. Indeed such applications are often ruled by hard realtime constraints, meaning that they must compute a correct result in terms of logical computations, but also that this result must be computed before a deadline. In case the result is not computed before the deadline, the consequences to the system can be dramatic, equivalent to or worse than a wrong logical computation.<br> My master thesis work concerns embedded control systems, which are systems in which the software controls a physical process. For such systems, control engineers provide the software development teams with a discretized automatic control specification usually described in Matlab/Simulink, SCADE or other equivalent formalisms. Such applications always have a cyclic/periodic execution model alongwith real-time constraints such as latency/makespan and throughput. These constraints must be respected, as well as the functional specification. The general problem of automatically generating optimal code in this context is NP-complete or undecidable (depending on the formalism used), but various techniques exist for generating efficient implementations. Our work starts from existing techniques allowing the generation of optimized code for one cycle of computation. Such techniques allow the fulfillment of the latency constraints. The present work proposes techniques that optimize the throughput of applications at a constant latency. Thus, it completes existing implementation techniques.<br> Our work is based on the representation of static real-time schedules using conditional reservation tables defining the mapping of computations to computing and communiation resources in time according to the execution conditions. This approach is validated by many industrial standards such as ARINC 653 for avionics and AUTOSAR for automotive industry.<br> On such conditional reservation tables we apply software pipelining techniques inspired from existing work on code optimization for microarchitectures with instructionlevel parallelism (superscalar, VLIW). Our solution to the problem is one (new) kind of software pipelining of ”modulo scheduling” type that respects the real-time requirements of our problem. The originality of the solution we provide, when compared to classical software pipelining techniques, is that:<br> 1. It defines a scheduling model that better supports and takes advantage of the execution conditions attached to each computation, resulting in more compact generated schedules in the end.<br> 2. As in traditional software pipelining, a dependency analysis must be performed. Nevertheless, in our technique, the real-time context allows the optimization of this analysis, which should allow for a shorter analysis time.<br><br> I started my research work by studying a corpus of research articles dedicated to embedded control systems, and more precisely to synchronous systems, and to software pipelining techniques. Those articles were the starting point of a detailed bibliography that I did in order to get good knowledge on the subject, and especially on existing software pipelining techniques. A particular interest was given to modulo scheduling techniques – software pipelining techniques that allow the definition of an optimized schedule of operations by performing simple computations and a dependency analysis – and to predicated execution for conditional branches of applications. This bibliographical study allowed the understanding of the state of the art in this domain, and also put into light the limitations inherent to these techniques, especially when it comes to the real-time constraints that were mentioned earlier.<br> At that point I was able to define a formal model for the representation of pipelined schedules, and to use it in order to define pipelining algorithms. Such algorithms are the key to solving the problem, as they take a (non-pipelined) schedule in input, and output an optimized pipelined version of the schedule that respects all the constraints we want to fulfill. Moreover, alongside the algorithms was developed a memory management technique that tackles all variable reuse problems that arise during pipelining.<br> The formal model for pipelined schedules is embodied in an intermediate representation for both pipelined and non-pipelined implementations, which I defined in order to be able to automate code generation. I then implemented the algorithms using those models, into a prototype written in Objective CaML. The algorithms were tested on real-life cases and showed good results.<br> At the end of the internship, I was able to describe my work and my achievements in a research paper that will be submitted soon, and to present them to the rest of my research team, as well as to other researchers from both the real-time and the software pipelining communities