# Throughput optimization by software pipelining of conditional reservation tables

[Examensarbete på avancerad nivå]

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.

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.

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.

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:

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.

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.

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.

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.

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.

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.

Publikationen registrerades 2011-09-21. Den ändrades senast 2013-04-04

CPL ID: 146444

Detta är en tjänst från **Chalmers bibliotek
**