Supervision : Alix MUNIER

Modèles pour l'optimisation de la simulation au cycle près de systèmes synchrones

Cette thèse traite de fonctions de coûts de graphes orientés sans circuit destinées à modéliser simplement la mémoire d'une machine lors de l'exécution d'un programme. L'objectif final est d'accélérer le fonctionnement de programmes de simulation au cycle près de systèmes synchrones en améliorant la gestion de la mémoire lors de leur exécution.
Dans cette thèse, nous définissons deux fonctions de coût, appelées DSC (Directed Sum Cut) et UCS (Uniform Cost Stack), ainsi que les problèmes d'optimisation correspondants. Nous montrons tout d'abord que l'obtention d'une solution optimale est un problème difficile pour les deux fonctions, dès les graphes de profondeur deux. Nous présentons ensuite des algorithmes permettant d'obtenir des solutions optimales en temps polynômial pour certaines classes de graphes: les anti-arborescences, les arborescences, certains graphes série- parallèles, et finalement les ordres intervalles. Nous concluons en présentant les résultats d'expériences pratiques montrant que nos modèles permettent d'obtenir des accélérations de temps de simulation.

2003-2009 Publications

• 2009
  • S. Achouri, T. Bossart, A. Munier‑Kordon : “A Polynomial algorithm for minDSC on series-parallel graphs”, RAIRO - Operations Research, vol. 43 (2), pp. 145-156, (EDP Sciences) (2009)
• 2007
  • T. Bossart, A. Munier‑Kordon, F. Sourd : “Memory Management Optimization Problems for Integrated Circuit Simulators”, Discrete Applied Mathematics, vol. 155 (14), pp. 1795-1811, (Elsevier) (2007)
• 2006
  • T. Bossart : “Modèles pour l’optimisation de la simulation au cycle près de systèmes synchrones”, thesis, phd defence 11/27/2006, supervision Munier, Alix (2006)
• 2003
  • T. Bossart, A. Munier‑Kordon, F. Sourd : “Optimisation de l’utilisation de la mémoire pour un simulateur de circuits”, 5^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2003), Avignon, France, pp. 393-394 (2003)