Master 2015 2016
Stages de la spécialité SAR
Modeling and compilation of dataflow graphs in a mixedcriticality context for multicore 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 
Motsclés :  Master SAR, autre qu’ATIAM 
Description
Context : Safetycritical 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 multicore architectures, and to gain in reliability and predictability by the utilization of dataflow models for railroad applications. The realtime community is interested in the dataflow model due to its mathematical foundation. Interesting properties can be proved efficiently at designtime : 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], CycloStatic Dafaflow (CSDF) [1], Affine Dataflow (ADF)[2]. On the other hand, an urge to cope with multicore 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 realtime 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 realtime community has shown a lot of interested in mixedcriticality systems. The main objective will be to combine these three concepts by representing a mixedcriticality system for a multicore 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 multicore architectures. The integration of mode changes, used in mixedcriticality systems, has been implemented in the ScenarioAware Dataflows (SADF) [10]. However this MoC needs extensions in order to be applied in a mixedcriticality 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 binpacking heuristics [7] and other custom function modeling [8]. All these methods try to solve a NPhard problem : allocation of the multicore resources for a SDF assuring bandwidth, memory and execution time constraints. However it would be interesting to extract nonfunctional 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 mixedcriticality 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 mixedcriticality 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 • Realtime 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.
Bibliographie
[1] G. BILSEN, M. ENGELS, R. LAUWEREINS, J. A. PEPERSTRAETE, K. U. LEUVEN, AND K. MERCIERLAAN, Cyclostatic data flow., (1995), pp. 3255–3258. [2] A. BOUAKAZ, J.P. TALPIN, AND J. VITEK, Affine DataFlow Graphs for the Synthesis of Hard RealTime 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 RealTime 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 HardRealTime Streaming with a Dynamic JobMix, 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 throughputconstrained 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 scenarioaware data flow model for combined longrun average and worstcase performance analysis, Fourth ACM and IEEE International Conference on Formal Methods and Models for CoDesign, 2006. MEMOCODE ’06. Proceedings., (2006), pp. 185–194.
 Valid CSS 2.1
 Valid XHTML Basic 1.1
 TripleA conformance Web Content Accessibility Guidelines 2.0
 Valid RSS Atom

Calculé le 27 octobre 2020 à 11h32min
par DidacSPIP
Université Pierre et Marie Curie  Mobile OK
 SPIP