Le 09/01/2012 par alm :

Sujet de stage de Master M2 : Recherche d'un ordonnancement K-périodique efficace de taille minimale pour un Synchronous Data Flow Graph.

Responsables : Bruno Bodin Bruno.Bodin@lip6.fr, Alix Munier Kordon Alix.Munier@lip6.fr

Sujet : La conception de systèmes embarqués est un processus industriel central qui pose de nombreux problèmes d'optimisation. Dans ce contexte, le formalisme des Synchronous Data Fow (en abrégé SDF) introduit en 1987 par Lee et Messerschmitt [1] pour modéliser une application concurrente à exécuter sur une architecture parallèle, est devenu un standard utilisé à la fois dans l'industrie et dans la recherche pour étudier et simuler ces applications. Un SDF est un graphe orienté dont les nœuds 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.

Cette modélisation permet d'effectuer avant l'exécution une analyse statique des programmes pour déterminer si une application fonctionne correctement et si ses performances sont satisfaisantes. Il s'agit alors de construire un ordonnancement réalisable des tâches d'un programme réalisant un ensemble d'objectifs fixés (maximisation du débit, minimisation de la mémoire, de la consommation...).

Dans le contexte de l'embarqué, la taille des ordonnancements est un critère important. Il va donc être nécessaire de privilégier des solutions de taille réduite quitte à dégrader les performances finales. Pour répondre à cette problématique, on s'intéressera à des ordonnancements «K-Periodiques». L'ordonnancement d'une tâche t est décrit par k(t) dates d'exécution des premières occurrences, et une fréquence de fonctionnement. La taille d'un ordonnancement et son débit dépendent alors directement des valeurs k(t) [2].

Pour un certain nombre d'applications de tailles industrielles, le nombre de combinaisons possible des valeurs k(t) dépasse généralement le domaine du raisonnable. Le but de ce stage est d'étudier des stratégies pour rechercher des tailles d'ordonnancement qui maximisent le débit d'une solution tout en minimisant la taille de sa représentation. Les outils mathématiques utilisés sont ceux de la recherche opérationnelle.

Pré-requis : de bonnes connaissances en algorithmique et en recherche opérationnelles sont indispensables, ainsi que la maîtrise d'au moins un langage de programmation (C/C++, Java, Python, OCaml...)

Conditions du stage : le stage doit avoir lieu au département SoC du LIP6, 4 place Jussieu, 75252 Paris cedex 05. Sa durée est de 5 à 6 mois et sera gratifié (approx. 417€/mois). Il sera réalisé en lien avec une société industrielle française dans le domaine de la conception de processeurs multi-cores.

Bibliographie :
[1] Edward A. Lee and David G. Messerschmitt. Synchronous data flow. IEEE Proceedings of the IEEE, 75(9), 1987.
[2] Olivier Marchetti, Alix Munier-Kordon, Cyclic scheduling for the synthesis of embedded systems. In: Y. Robert, F. Vivien (eds.) Introduction to Scheduling, pp. 129–157. CRC Press (2009).