Mar 06 2017

Focus on a joint research project: RIPPES

RIPPES (2013-2015)

Rigorous programming of predictable embedded systems

Principal Investigators: 

  • Dr. Alain Girault, SPADES project-team, Inria Grenoble Rhône-Alpes
  • Prof. Edward Lee, EECS Department, University of California Berkeley

Research objectives:

Embedded systems are deployed on many-core chips with architectural features that render program execution extremely efficient but also highly unpredictable (e.g., caches, out-of-order execution, branch prediction). This unpredictability makes it almost impossible to guarantee that the constraints are met, or when they are, it is at the cost of huge over-approximations. The goal of RIPPES is to achieve both predictability and adaptivity.

Scientific achievements:

The VC-1 video decoder implemented in the BPDF model of computation

Contributions of RIPPES have been twofold. First, RIPPES has proposed a new parametric data-flow model of computation, called BPDF (Boolean Parametric Data Flow). BPDF combines integer parameters so that actors can adapt dynamically their input and output rates, and Boolean parameters so that edges can be disabled dynamically. This makes BPDF ideally suited to program modern video codec and software defined radio applications. In contrast with existing parametric model of computations, BPDF offers static analyses for soundness, liveness, schedulability, throughput calculation, and buffer size assessment. The second contribution of the team concerns Precision Timed Machines (PRET). The PRET philosophy is to propose both a programming language and a processor such that source code written in this language can be compiled into object code whose execution time on the PRET processor can be both very precise (i.e., the over-approximation between the real worst-case execution time — WCRT — and the computed one must be as small as possible) and still good compared to the average-case execution time — ACRT — of the same source code on a regular modern processor. The team has proposed the ForeC programming language, which is an extension of C with synchronous concurrency constructs to provide a deterministic execution on multi-core chips. Several PRET processors have been proposed by the RIPPES partners, for instance the FlexPRET processor, which is multithreaded such that critical threads are perfectly time predictable (i.e., their ACRT is equal to their WCRT) while non-critical threads are executed on a best effort basis to improve the average performances

Publications and Awards:

  • 2 Journal articles & 5 Conference papers.

Selected publication:

IS. Andalam, P.S. Roop, A. Girault and C. Traulsen, “A predictable framework for safety-critical embedded systems”, IEEE Trans. on Computers, 63(7): 1600-1612, July 2014.

 Follow up:

Work on parametric data-flow models of computation has continued after the end of the RIPPES associated team, resulting in three publications:

  • A. Bouakaz, P. Fradet and A. Girault, “Symbolic analyses of dataflow graphs”, ACM Trans. on Design Automation of Electronic Systems, 22(2), January 2017.
  • A. Bouakaz, P. Fradet and A. Girault, “A survey of parametric dataflow models of computation”, ACM Trans. on Design Automation of Electronic Systems, 22(2), January 2017.
  • A. Bouakaz, P. Fradet and A. Girault, “Symbolic buffer sizing for throughput-optimal scheduling of dataflow graphs”, in IEEE Real-Time Embedded Technology and Applications Symposium (RTAS’16), Vienna, Austria, April 2016.

Discussions are going on with Orange within the IOLab to start a PhD on related topics.

Moreover, regarding the time predictability research axis of RIPPES, a journal publication in under evaluation on the ForeC programming language and its semantics.