La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

Th

Forum 'Emplois' - Sujet créé le 2015-06-04

Sujet de thèse : Etude et implantation d'algorithmes pour
le placement et l'ordonnancement d'applications Dataflow

Encadrants : Jean-François Nezan/Alix Munier Kordon

Sujet de la thèse : La conception de systèmes embarqués est un processus complexe compte-tenu du nombre important de contraintes à respecter liées aux applications, au coût de développement et aux contraintes externes. Les systèmes visés sont des architectures multicoeurs ou manycoeurs. Développer des outils pour la conception pour ces systèmes est ainsi un champs de recherche très actif et qui doit s'attaquer à de nombreux défis.

Les « Synchronous DataFlow »(SDF en bref) [1] et ses extensions sont fréquemment utiliséspour décrire le comportement des applications, notamment dans le domaine du traitement numérique du signal et des images (Telecom, Compression vidéo). Un SDF est un graphe orienté dont les noeuds sont associés à des acteurs (ou tâches) et les arcs représentent des liens de communication (ou buffers). De plus, des poids entiers spécifient la quantité de données produite et
consommée par les acteurs à chacune de leurs exécutions.

L'environnement de développement PREESM développée à l'IETR (l'Institut d'Electronique et de Télécommunications de Rennes) supporte les modèles « PiSDF »[3] qui permettent une description modulaire, hiérarchique et reconfigurable d'une application. Les PiSDF permettent d'élargir de manière significative l'expressivité des SDF. Le problème principal est que l'on ne dispose pas aujourd'hui d'algorithmes de complexité permettant de prendre en charge efficacement
des instances de plusieurs centaines ou milliers d'acteurs.

Le but de cette thèse est de développer un ensemble d'algorithmes dédiés à l'utilisation de graphes PiSDF qui permettent le passage à l'échelle pour des applications de taille importante. On étudiera un ensemble de problèmes de décision qui sont à la base de la majorité des problèmes d'optimisation : test de la vivacité, évaluation du débit maximum d'un PiSDF, calcul d'ordonnacement, évaluation du placement sur une architecture manycoeurs. On en déduira des stratégies d'optimisation qui seront évaluées de manière théorique. L'ensemble des algorithmes sera ensuite implanté sur l'environnement PREESM et évalué de manière expérimentale sur des
classes d'application (HEVC, Embedded vision), ou sur des PiSDF générés aléatoirement. Les plateformes matérielles considérées seont des Keystone Texas Instruments et MPPA Kalray.

Candidatures : Ce sujet est ouvert à des étudiants de M2 avec des bonnes connaissances en algorithmique, programmation et en optimisation combinatoire. Si vous êtes intéressé, envoyer de toute urgence un CV détaillé, une lettre de motivation et vos bulletins de notes de master à Jean-Francois.Nezan@insa-rennes.fr et Alix Munier@lip6.fr.

Conditions de la thèse : La thèse sera localisée au laboratoire IETR de l'INSA de Rennes. Il fera l'objet d'un contrat doctoral dont la rémunération est fixée à 1684,93 euros bruts mensuels pour une activité de recherche seule et 2024,70 euros bruts en cas d'activités complémentaires.

Références
[1] Edward A. Lee and David G. Messerschmitt. Synchronous data flow. Proceeding of the IEEE, vol. 75(no. 9) :pp. 1235–1245, 1987.
[2] Olivier Marchetti and Alix Munier Kordon. Cyclic Scheduling for the Synthesis of Embedded Systems, chapter 6. Introduction to scheduling. Chapman and Hall/CRC Press, November 2009. ISBN : 978-1420072730.
[3] J. Piat, S.S. Bhattacharyya, and M. Raulet. Interface-based hierarchy for synchronous dataflow graphs. In Signal Processing Systems, 2009. SiPS 2009. IEEE Workshop on, pages 145–150, Oct 2009.[/imgs]