Throughput optimization by software pipelining of conditional reservation tables

Abstract: In the world of embedded real-time applications, the optimization of scheduleshas been since long a major concern. Indeed such applications are often ruled by hard realtimeconstraints, meaning that they must compute a correct result in terms of logicalcomputations, but also that this result must be computed before a deadline. In case the resultis not computed before the deadline, the consequences to the system can be dramatic,equivalent to or worse than a wrong logical computation.
My master thesis work concerns embedded control systems, which are systemsin which the software controls a physical process. For such systems, control engineers providethe software development teams with a discretized automatic control specification usuallydescribed in Matlab/Simulink, SCADE or other equivalent formalisms. Such applicationsalways have a cyclic/periodic execution model alongwith real-time constraints such aslatency/makespan and throughput. These constraints must be respected, as well as thefunctional specification. The general problem of automatically generating optimal code in thiscontext is NP-complete or undecidable (depending on the formalism used), but varioustechniques exist for generating efficient implementations. Our work starts from existingtechniques allowing the generation of optimized code for one cycle of computation. Suchtechniques allow the fulfillment of the latency constraints. The present work proposestechniques that optimize the throughput of applications at a constant latency. Thus, itcompletes existing implementation techniques.
Our work is based on the representation of static real-time schedules usingconditional reservation tables defining the mapping of computations to computing andcommuniation resources in time according to the execution conditions. This approach isvalidated by many industrial standards such as ARINC 653 for avionics and AUTOSAR forautomotive industry.
On such conditional reservation tables we apply software pipelining techniquesinspired from existing work on code optimization for microarchitectures with instructionlevelparallelism (superscalar, VLIW). Our solution to the problem is one (new) kind ofsoftware pipelining of ”modulo scheduling” type that respects the real-time requirements ofour problem. The originality of the solution we provide, when compared to classical softwarepipelining techniques, is that:
1. It defines a scheduling model that better supports and takes advantage of the executionconditions attached to each computation, resulting in more compact generatedschedules in the end.
2. As in traditional software pipelining, a dependency analysis must be performed.Nevertheless, in our technique, the real-time context allows the optimization of thisanalysis, which should allow for a shorter analysis time.

I started my research work by studying a corpus of research articles dedicated toembedded control systems, and more precisely to synchronous systems, and to softwarepipelining techniques. Those articles were the starting point of a detailed bibliography that Idid in order to get good knowledge on the subject, and especially on existing softwarepipelining techniques. A particular interest was given to modulo scheduling techniques –software pipelining techniques that allow the definition of an optimized schedule ofoperations by performing simple computations and a dependency analysis – and to predicatedexecution for conditional branches of applications. This bibliographical study allowed theunderstanding of the state of the art in this domain, and also put into light the limitationsinherent to these techniques, especially when it comes to the real-time constraints that werementioned earlier.
At that point I was able to define a formal model for the representation ofpipelined schedules, and to use it in order to define pipelining algorithms. Such algorithms arethe key to solving the problem, as they take a (non-pipelined) schedule in input, and output anoptimized pipelined version of the schedule that respects all the constraints we want to fulfill.Moreover, alongside the algorithms was developed a memory management technique thattackles all variable reuse problems that arise during pipelining.
The formal model for pipelined schedules is embodied in an intermediaterepresentation for both pipelined and non-pipelined implementations, which I defined in orderto be able to automate code generation. I then implemented the algorithms using thosemodels, into a prototype written in Objective CaML. The algorithms were tested on real-lifecases and showed good results.
At the end of the internship, I was able to describe my work and myachievements in a research paper that will be submitted soon, and to present them to the restof my research team, as well as to other researchers from both the real-time and the softwarepipelining communities.