Programming IoT and software defined radio with dynamic data-flow models of computation

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
  1. Bibliographical review on the existing models of computation.
  2. Study of the specific needs for SDR and IoT (through relevant case studies).
  3. 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).
  4. 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.
Candidates are invited to send their application via email to Pascal Fradet (pascal.fradet@inria.fr), Alain Girault (alain.girault@inria.fr), and Xavier Nicollin (xavier.nicollin@inria.fr). Please include at least a CV, a short motivation letter and contact information for 2 referees.
References
[1] Synchronous Data Flow, Edward Lee and David Messerschmitt, in Proc. Of the IEEE, 1987.
[2] Parameterized Dataflow Modeling for DSP Systems, B. Bhattacharya and Shuvra Bhattacharyya, IEEE Trans. Sig. Proc. 49, 10 (2001), pp 2408-2421.
[3] BPDF: A Statically Analyzable Dataflow Model with Integer and Boolean Parameters. Vagelis Bebelis, Pascal Fradet, Alain Girault and Bruno Lavigueur, in International Conference on Embedded Software, EMSOFT’13, September 2013.
[4] Symbolic Buffer Sizing for Throughput-Optimal Scheduling of Dataflow Graphs. Adnan Bouakaz, Pascal Fradet and Alain Girault, in Proc. of Real-Time Embedded Technology & Applications Symposium, RTAS’16, April 2016.
[5] The Abstract Task Graph: a methodology for architecture-independent programming of networked sensor systems, 2005 workshop on End-to-end, sense-and-respond systems, applications and services.
[6] Dioptase: a distributed data streaming middleware for the future web of things, Valérie Issarny, Benjamin Billet, Journal of Internet Services and Applications 2014, 5:13.