Abstract
Data-flow models of computation (MoC) have been proposed to ease the design, programming, and validation of applications made of filters that exchange streams of data through communication links (see e.g., SDF [1]). Parametric data-flow MoCs (like PRDF [2]) have been proposed as a good trade-off between expressivity and analyzability. Recently, the SPADES team at INRIA Grenoble has proposed the Boolean Parametric Data-Flow MoC (BPDF) [3] that offers both parametric consumption and production rates, and the possibility to reconfigure dynamically the data-flow graph. We have also obtained results on the symbolic analysis of latency, throughput, and buffer sizes of parametric data-flow graphs [4].
In this PhD thesis, we will study the use of parametric dataflow MoCs to the design and analysis of Internet of Things (IoT) and Software Defined Radio (SDR) applications. Their common aspect is that computations are performed over streams of data, hence the data-flow model of computation is relevant [5] [6].
The goal is to propose a platform, a methodology, and tools for the design of IoT and SDR applications. The underlying MoC will have to allow the specification of complex scenarios (related to the control flow, the variability of exchanged data, the graph topology), while the application model must remain oblivious of the target execution infrastructure. The runtime system will have to coordinate the execution of applications and adapt their schedule dynamically. The main challenges are:
-
Dynamicity: The topology of the data-flow graph specifying the application must be allowed to vary at runtime. Specifically, the rates at which the data tokens are produced and consumed by the filters must vary, as well as the control flow and the execution resources availability. Accordingly, the schedule of the tasks onto the execution resources must be dynamic. This makes the performance evaluation of the system all the more difficult, be it for latency, throughput, buffer sizes, energy consumption, …
-
Programming and execution environment: The programming language and the runtime must allow the designer to insert the blocks of computation (i.e., the filters of the dataflow graph), to specify their constraints (i.e., their execution time and energy consumption), and how they are connected to the other blocks. IoT raises new issues for the design of MoCs, including how to handle unreliable communications and the re-emission of data, and opens the possibility of new criteria of analysis and optimisation (e.g., bandwidth instead of buffer sizes).
Planning
-
Bibliographical review on the existing models of computation.
-
Study of the specific needs for SDR and IoT (through relevant case studies).
-
Proposing a new model of computation adapted to the needs identified in step 2. A possibility will be to extend an existing MoC (for instance BPDF).
-
Implementing in a prototype tool the chosen MoC and its associated runtime environment, and validating it on a case study.
Context
The thesis will take place in the Orange Lab Chatillon (near Paris) and the INRIA SPADES team, in Grenoble, France. The SPADES team conducts research on programming dependable embedded systems. As part of that effort, the team develops new formal component models, programming languages and associated tools for verification, analysis or synthesis.
Gross yearly salary
29.738 euros (1st and 2nd years), 34.136 euros (third year), including health care coverage.
Requirements
-
MS degree in computer science.
-
Knowledge of programming languages and models of computation and/or formal methods (semantics, verification, static analysis, …). and/or scheduling and distributed algorithms.
-
A high degree of autonomy and involvement in work. Team working and collaboration.
