General informations

Inria Grenoble-Rhne-Alpes, Pop-Art team, 38330 Montbonnot.
6 months
Gwenal Delaval, Alain Girault
Expected skills and background:
design and semantics of programming languages, reactive systems, type systems


Synchronous programming languages [1] are frequently used in the industry for the design of real-time embedded systems. Such languages define deterministic behaviors and lie on formal semantics, making them suitable for the design and implementation of safety critical systems. They are used, for example, in critical domains such as the automotive, avionics, or nuclear industry.

Most of the systems designed with synchronous languages are centralized systems. The parallelism expressed in these languages is a functional one, whose purpose is to ease the design process by providing ideal timing and concurrency constructs to the designers. A synchronous program is then compiled into a sequential program emulating the parallel execution of the functional parallel branches. This sequential program is executed on a single computing resource.

Yet, most embedded systems are composed of several computing resources (named "locations"), for reasons such as performance, dedicated actuators or sensors drivers, or adaptivity of the locations to the tasks they are assigned to (e.g., pure computing tasks vs. control tasks).

This internship lies in the context of past results on automatic distribution of synchronous programs [2,3], on automatic rate desynchronization of synchronous programs [6,7], and on automatic distribution of higher-order synchronous data-flow programs [5].

We are currently designing a new distribution method for synchronous data-flow languages, taking into account the control part of programs, in a more integrated way than in \cite{delaval08b}. The control part of data-flow synchronous programs is usually expressed as clocks, which express the information about presence or absence of data within the discrete scale of time. The clock calculus, allowing to check or compute by inference the clock of every value of a program, can be seen as a specific type system [4]. Our goal is to extend this clock calculus so as to express the location of values (for distribution purpose) as clocks of these values. Then, the operation of distribution itself would rely on this extended clock calculus.

Expected work

Depending on the background and motivations of the student, the expected work can be:


[1] A. Benveniste, P. Caspi, S. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages twelve years later. Proc. of the IEEE, Special issue on embedded systems, 91(1):64-83, January 2003.
[2] P. Caspi, A. Girault, and D. Pilaud. Distributing reactive systems. In 7th International Conference on Parallel and Distributed Computing Systems, PDCS'94, Las Vegas (NV), USA, October 1994. ISCA.
[3] P. Caspi, A. Girault, and D. Pilaud. Automatic distribution of reactive systems for asynchronous networks of processors. IEEE Trans. on Software Engineering, 25(3):416-427, May 1999.
[4] J.-L. Colaço and M. Pouzet. Clocks as first class abstract types. In R. Alur and I. Lee, editors, International Conference on Embedded Software, EMSOFT'03, volume 2855 of LNCS, pages 134-155, Philadelphia (PA), USA, October 2003. Springer-Verlag.
[5] G. Delaval, A. Girault, and M. Pouzet. A type system for the automatic distribution of higher-order synchronous dataflow programs. In International Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES'08, pages 101-110, Tucson (AZ), USA, June 2008. ACM, New-York.
[6] A. Girault and X. Nicollin. Clock-driven automatic distribution of Lustre programs. In R. Alur and I. Lee, editors, International Conference on Embedded Software, EMSOFT'03, volume 2855 of LNCS, pages 206-222, Philadelphia (PA), USA, October 2003. Springer-Verlag.
[7] A. Girault, X. Nicollin, and M. Pouzet. Automatic rate desynchronization of embedded reactive programs. ACM Trans. Embedd. Comput. Syst., 5(3):687-717, August 2006.