Scheduling Real-Time Streaming Applications onto an Embedded Multiprocessor

There was a time when the access to a computer was a luxury shared by few. A single computing machine owned by an university or business would service many users, each of which would carefully prepare the programs he or she wished to submit to the machine. After doing the submission, the user would have to wait until the machine could find the time in its busy schedule to process that particular program, and deliver the desired results.

We present and analyze the requirements of our problem and design a Software Framework (SF) that addresses all of them. We start the chapter by defining terminology and describing our hardware architecture model. We then inventorize the requirements that the SF must address. This is followed by a discussion of the chosen Model of Computation and the overall resource management strategy, including the choice of local schedulers and task synchronization techniques. From this, we identify the main software components of the solution and present an overview of the complete SF, including the compilation chain and the runtime support. We then give a quick overview of components such as the programming language and code generator, which will not be discussed in further detail in this book. We compare our proposal with related work and close the chapter by stating our conclusions.

In the previous chapters, we justified our choice for data flow as the basis of a model of computation for embedded real-time streaming applications running on a multiprocessor. There are many flavors of data flow. The ones that are interesting for our stated goals are mostly the variants that exhibit behavior which is independent of data values, because of their analytical properties and the variants with deterministic, data value dependent behavior, because of their expressivity. In this chapter, we present notation for data flow models that we will use throughout the book, and the properties of several data flow computation models that are relevant to our stated goal. This is reference material. It can, for the most, be found elsewhere in the literature [10, 57, 80, 81].

In Chap. 2, we concluded that, due to the application requirements we are aiming at, we cannot schedule jobs statically. There are several reasons for this: first, actors have variable execution times, second, the execution of the graph is performed across the multiprocessor, and it may be difficult to guarantee that all processors are synchronized at all times, and also, we cannot statically schedule together two independent transceiver jobs. Therefore, synchronization in our implementation is, at the essence, self-timed: a data flow actor fires immediately whenever its firing conditions are met.

In our approach to Software-Defined Radio, a radio transceiver is a concurrent software program expressed by means of a data flow graph. In this chapter, we show how such a data flow graph can be partially scheduled at compile time to a heterogeneous multiprocessor platform, in such a way that guarantees of Hard Real-Time performance can be given.

In the process of choosing a Data Flow (DF) programming model for describing an application, one must make a difficult trade off between expressiveness and analytical properties. At one extreme, a Dynamic Data-flow (DDF) model is expressive enough to mimic the behavior of a Turing machine [10], but lacks many useful analytical properties; for instance, for an arbitrary DDF graph it may be impossible to verify if it is free of deadlocks, or if it can execute for indefinite time on bounded buffer space [10]. On the other hand, Static Data flow (StDF) variants (such as Multi-Rate DF [57], Single-Rate DF [80], or Cyclo-Static DF [9]) allow for powerful analysis, such as the verification of deadlock-freedom, determination of maximum achievable throughput, and verification of latency and throughput constraints, but have limited expressivity: all actors must work with fixed data rates, i.e., all quantities of data sent/received per actor firing cannot be dependent on the values of the input data. Because of these limitations, StDF models tend to be reserved for application domains where task activation is data-driven, data rates regular, and real-time guarantees required.

In this chapter, we discuss the algorithms that the resource manager must implement to try to find a mapping for a transceiver instance (a job) at runtime, and decide whether the job can be executed or not.

The demonstrator prototype presented in this chapter was part of a larger demonstrator built by Nokia, NXP and ST-Ericsson, where our baseband software framework is integrated with the Radio Computer functional architecture proposed in [1]. It shows how the concepts we proposed can be worked out into an execution platform, even when the hardware was not designed to meet some of the requirements of our software framework. It also shows how the custom components of our software framework can be implemented while re-using a substantial amount of existing off-the-shelf software.

We live in a planet overflown with information, where billions of wirelessly connected devices constantly send and receive data to each other. Wireless connectivity is enabled through several different radio standards. Devices need to handle this diversity, and, at times, must support several of these standards simultaneously.