Responsables : Alix MUNIER KORDON, Alix.Munier(at)lip6(.)fr, Olivier MARCHETTI, Olivier.Marchetti(at)lip6(.)fr et Jean-Marc DELOSME delosme(at)ibisc.univ-evry(.)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.

On considère ici une application décrite sous la forme d’un SDF. De manière simplifiée, une architecture cible est constituée de m processeurs identiques qui communiquent entre eux par une mémoire partagée. Ainsi, si deux programmes communiquent et sont exécutés sur un même processeur, la FIFO utilisée pour cette communication sera implantée en mémoire locale du processeur correspondant. Dans le cas contraire, les transferts se feront par la mémoire partagée. Le problème consiste à placer les processus sur les processeurs et à calculer un ordonnancement qui maximise le débit de l’application. 

Le but de ce stage est de modéliser et étudier la résolution de ce problème en utilisant des techniques d’optimisation combinatoire (Complexité du problème, sous-cas polynomiaux, recherche d’algorithmes approchés et heuristiques). On pourra limiter (ou non) l’étude aux ordonnancements périodiques d’un SDF [2]. D’autre part, une étude bibliographique sur les problèmes d’ordonnancement à temps de communication [3] semble indispensable.

Pré-requis : de bonnes connaissances en théorie des graphes et algorithmique sont indispensables.

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 4 à 6 mois.

Bibliographie :

[1] Edward A. Lee and David G. Messerschmitt. Synchronous data flow.IEEE Proceedings of the IEEE, 75(9), 1987

[2] Abir Benabid, Claire Hanen, Olivier Marchetti, and Alix Munier Kordon. Periodic schedules for unitary timed weighted event graphs. In Conference ROADEF’08, pages 17–31,Clermont-Ferrand, 2008. Presses Universitaires de l’Universite Blaise Pascal.

[3]Chrétienne Ph., Picouleau C., Scheduling with communication delays: a survey, Scheduling Theory and its Applications,P. Chretienne, E.G. Coman, J.K. Lenstra, Z. Liu (Eds), John Wiley Ltd 1995.