Supervision : Alix MUNIER

Dimensionnement des mémoires pour systèmes embarqués

Le problème du dimensionnement des mémoires pour systèmes embarqués consiste à définir la taille à allouer pour chaque mémoire de sorte que la surface globale occupée par ces mémoires soit minimale et que le système embarqué puissent fonctionner sans bloquage lié à un sous dimensionnement de ces mémoires. Nous modélisons ce problème d'optimisation en utilisant le modèle des graphes d'événements généralisés (GEG en abrégé). Nous montrons que ce problème d'optimisation est étroitement lié au problème de vivacité d'un GEG. Nous proposons une transformation des GEG, appelée normalisation, permettant de définir une condition suffisante de vivacité ainsi qu'un algorithme polynomial pour tester cette condition sur des GEG quelconques. Nous proposons des résultats nouveaux de complexité pour des problèmes d'optimisation bi-critère(ie.surface globale/débit du système). Nous développons un algorithme polynomial 2-approché pour la résolution du problème d'optimisation bi-critère du débit maximum intrinsèque.
Mots clefs : Dimensionnement des mémoires, graphe d'événements généralisé temporisé, ordonnancement cyclique, normalisation, vivacité, complexité théorique, algorithme d'approximation.

2005-2012 Publications

• 2012
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for bounded timed weighted event graphs”, IEEE Transactions on Automatic Control, vol. 57 (5), pp. 1222-1232, (Institute of Electrical and Electronics Engineers) (2012)
• 2010
  • M. Benazouz, O. Marchetti, A. Munier‑Kordon, Th. Michel : “A New Method for Minimizing Buffer Sizes for Cyclo-Static Dataflow Graphs.”, ESTIMedia 2010 - 8^th IEEE International Workshop on Embedded Systems for Real-Time Multimedia, Scottsdale, Arizona, United States, pp. 11-20, (IEEE) (2010)
  • O. Marchetti, A. Munier‑Kordon : “Complexity results for bi-criteria cyclic scheduling problems”, Discrete Optimization, vol. 7 (3), pp. 166-180, (Elsevier) (2010)
  • M. Benazouz, O. Marchetti, A. Munier‑Kordon, P. Urard : “A new Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design.”, AICCSA IEEE/ACS International Conference on Computer Systems and Applications, Hammamet, Tunisia, pp. 1-8, (IEEE) (2010)
• 2009
  • O. Marchetti, A. Munier‑Kordon : “A sufficient condition for the liveness of weighted event graphs”, European Journal of Operational Research, vol. 197 (2), pp. 532-540, (Elsevier) (2009)
  • M. Benazouz, O. Marchetti, A. Munier‑Kordon, P. Urard : “A Polynomial Algorithm for the Computation of Buffer Capacities with Throughput Constraint for Embedded System Design”, CIE IEEE International Conference on Computers & Industrial Engineering, Troyes, France, pp. 690-695, (IEEE) (2009)
  • O. Marchetti, A. Munier‑Kordon : “Cyclic Scheduling for the Synthesis of Embedded Systems”, chapter in Introduction to Scheduling, pp. 129-154, (Chapman and Hall/CRC Computational Science), (ISBN: 978-1420072730) (2009)
• 2008
  • O. Marchetti, A. Munier‑Kordon : “Minimizing Place Capacities of Weighted Event Graphs for Enforcing Liveness”, Discrete Event Dynamic Systems, vol. 18 (1), pp. 91-109, (Springer Verlag) (2008)
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for Unitary Timed Weighted Event Graphs”, 9^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008), Clermont-Ferrand, France, pp. 17-31 (2008)
• 2006
  • O. Marchetti : “Dimensionnement des mémoires pour systèmes embarqués”, thesis, phd defence 12/04/2006, supervision Munier, Alix (2006)
  • O. Marchetti, A. Munier‑Kordon : “A polynomial algorithm for a bi-criteria cyclic scheduling problem.”, PlanSIG UK PLANNING AND SCHEDULING Special Interest Group, Nottingham, United Kingdom, pp. 88-96 (2006)
  • O. Marchetti, A. Munier‑Kordon : “Complexity results for bi-criteria cyclic scheduling problems”, RenPar Rencontres Francophones du Parallélisme, Perpignan, France, pp. 17-24 (2006)
• 2005
  • O. Marchetti, A. Munier‑Kordon : “A Sufficient Condition for the Liveness of Weighted Event Graphs”, (2005)
  • O. Marchetti, A. Munier‑Kordon : “Minimizing Places Storage Capacities of a Weighted Event Graph.”, (2005)