Master 2015 2016
Stages de la spécialité SAR
Modeling and compilation of dataflow graphs in a mixed-criticality context for multi-core architectures.

Lieu : LTCI / Télécom ParisTech, 46 rue Barrault, 75013 Paris
Encadrant : Etienne Borde, Laurent Pautet, RobertoMedina
Dates :01/02/2016 au 31/07/2016
Rémunération :500E/mois
Mots-clés : Master SAR, autre qu’ATIAM


Context : Safety-critical system need to assure a certain degree of reliability and availability : even in the presence of faults, the system should be able to deliver vital functionalities to avoid catastrophic outcomes. This internship is an example of the interest shown by the train industry (ALSTOM) for adopting new technologies : to gain in performance by the introduction of multi-core architectures, and to gain in reliability and predictability by the utilization of dataflow models for railroad applications. The real-time community is interested in the dataflow model due to its mathematical foundation. Interesting properties can be proved efficiently at design-time : liveness, consistency, reachability, throughput. Many Models of Computation (MoC) for dataflow graphs are present in the literature and can be used to model different types of applications : Kahn Process Networks (KPN) [5], Synchronous Dataflow (SDF) [6], Cyclo-Static Dafaflow (CSDF) [1], Affine Dataflow (ADF)[2]. On the other hand, an urge to cope with multi-core architectures appeared for hardreal- time systems. In fact, this type of architecture raises new problems related to communication/blocking time, isolation, resource allocation, etc. Making real-time guarantees hard to be delivered. However, multiprocessors offer great potential as an execution platform and executing different tasks with various criticality levels might be interesting in terms of costs, maintainability and verification. Therefore the real-time community has shown a lot of interested in mixed-criticality systems. The main objective will be to combine these three concepts by representing a mixedcriticality system for a multi-core architecture using the dataflowMoC.

Problematic : This internship focuses in two different problematics : Problem1) modeling a mixedcriticality application using a dataflowMoC and Problem2) compiling/binding these dataflows into the multi-core architectures. The integration of mode changes, used in mixed-criticality systems, has been implemented in the Scenario-Aware Dataflows (SADF) [10]. However this MoC needs extensions in order to be applied in a mixed-criticality context. This will be the first question to solve during the internship. The second problem has been tackled by some works in the literature, with ILP solutions [4], vector bin-packing heuristics [7] and other custom function modeling [8]. All these methods try to solve a NP-hard problem : allocation of the multi-core resources for a SDF assuring bandwidth, memory and execution time constraints. However it would be interesting to extract non-functional properties (e.g. availability, reliability) during/after this binding process.

Internship outcome : The first part of this internship consists in integrating the transformation of mixedcriticality systems to SADF graphs, into the SDF3 [9] framework. SDF3 delivers basic and advanced functionalities like analysis, transformation, generatio and mapping for different types of dataflow graphs : SDF, CSDF and SADF. A mapping between the mixed-criticality specification and the SADF will be integrated into the framework. From there, the framework could be extended to verify different properties in the SADFs modeling mixed-criticality systems, like calculating the probability of failure of the system, verifying availability of critical components, optimization of the mapping functions for the SADF, among other properties that could be found by the candidate.

Required qualifications • Real-time systems theory. • Implementation skills (C++ programming). Administrative informations • Supervisors : Etienne Borde, Laurent Pautet, RobertoMedina. • Working place : Télécom ParisTech - 46 rue Barrault - 75013 Paris. • Salary : 500"/month - 6 months.


[1] G. BILSEN, M. ENGELS, R. LAUWEREINS, J. A. PEPERSTRAETE, K. U. LEUVEN, AND K. MERCIERLAAN, Cyclo-static data flow., (1995), pp. 3255–3258. [2] A. BOUAKAZ, J.-P. TALPIN, AND J. VITEK, Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications, 2012 12th International Conference on Application of Concurrency to System Design, (2012), pp. 183–192. [3] J. BUCK AND E. LEE, SchedulingDynamicDataflowGraphs with BoundedMemory Using the Token FlowModel, Icassp, 1 (1993), pp. 429–432. [4] Y. CHOI, Y. LIN, N. CHONG, S. MAHLKE, AND T. MUDGE, Stream Compilation for Real-Time Embedded Multicore Systems, 2009 International Symposium on Code Generation and Optimization, (2009), pp. 210–220. [5] G. KAHN, The Semantics of a Simple Language for Parallel Programming, (1984). [6] E. LEE AND D. MESSERSCHMITT, Synchronous data flow, Proceedings of the IEEE, 75 (1987), pp. 1235–1245. [7] O. MOREIRA, J.-D. MOL, M. J. BEKOOIJ, AND J. VAN MEERBERGEN,Multiprocessor Resource Allocation for Hard-Real-Time Streaming with a Dynamic Job-Mix, 11th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS’05), (2005), pp. 332–341. [8] S. STUIJK, T. BASTEN, M. C. W. GEILEN, AND H. CORPORAAL, Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs, Proceedings - Design Automation Conference, (2007), pp. 777–782. [9] S. STUIJK, M. C. W. GEILEN, AND T. BASTEN, SDF3 : SDF For Free, in Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings, IEEE Computer Society Press, Los Alamitos, CA, USA, 2006, pp. 276–278. [10] B. THEELEN, M. GEILEN, T. BASTEN, J. VOETEN, S. GHEORGHITA, AND S. STUIJK, A scenario-aware data flow model for combined long-run average and worst-case performance analysis, Fourth ACM and IEEE International Conference on Formal Methods and Models for Co-Design, 2006. MEMOCODE ’06. Proceedings., (2006), pp. 185–194.