BENAZOUZ Mohamed
Direction de recherche : Alix MUNIER
Dimensionnement des Mémoires dans les Applications de Traitement de Flux de Données
Les récents travaux en conception électronique au niveau système (ESL) et la synthèse haut niveau (HLS) ont permis l'essor des techniques d'exploration de l'espace de conception dans le but de satisfaire des exigences croissantes tout en réduisant le temps de mise sur le marché. Plusieurs métriques sont utilisées durant ce processus d'exploration; le débit constitue une des plus importantes mesures de performance d'une application de traitement de flux de données. Un des facteurs qui limite le débit atteint est la taille des mémoires tampons (buffers) assurant l'échange de données entre les différentes tâches d'une application. Des méthodes exactes ou heuristiques ont été proposées ces dernières années pour calculer la taille des buffers sous contrainte de débit. Cependant, elles ne sont pas satisfaisantes du fait de leur temps de calcul prohibitif. Le but de cette thèse est de proposer une approche analytique permettant de résoudre en temps polynomial le problème de dimensionnement des mémoires tampons tout en garantissant d'atteindre un débit préfixé. Deux modèles de calcul (MoC) très répandus ont été retenus pour décrire le parallélisme des tâches et les taux de transfert de données entre elles : Graphes d'Evénements Généralisés Temporisés (GEGT) et Graphes Cyclo-Static DataFlow (CSDFG). Nous considérons dans un premier temps les GEGTs. En supposant que les tâches sont exécutées périodiquement, nous montrons que le problème d'optimisation avec contrainte de débit est un programme linéaire en nombres entiers (PLNE). Après avoir donné une caractérisation complète du problème bi-critère "taille d'un buffer-débit", nous proposons une formule close pour le calcul de la taille minimale à allouer à un buffer unique pour un débit fixé. Ce résultat est alors généralisé afin d'obtenir une solution optimale au PLNE pour des GEGTs à structure arborescente et aux GEGTs cycles. Dans le cas général, nous proposons un algorithme polynomial 2-approché pour résoudre le PLNE. Dans la deuxième partie, nous étendons des résultats obtenus pour le modèle GEGT au modèle CSDFG. En particulier, nous proposons une condition suffisante de vivacité. Nous sommes alors amenés à ordonnancer les phases successives d'une tâche CSDF. Nous présentons un programme linéaire Min-Max (PL Min-Max) afin de répartir les phases sur une période. Ce PL Min-Max est ensuite utilisé pour relâcher la contrainte de périodicité, ce qui accroit sensiblement la précision dans le calcul des tailles suffisantes des buffers. Malgré la restriction aux ordonnancements périodiques, nos expérimentations sur des cas d'études réels montrent que les solutions calculées sont de bonne qualité par rapport aux méthodes heuristiques ou exactes utilisant un ordonnancement au plus tôt. Dans le contexte d'utilisation croissante d'outils HLS et ESL, nos algorithmes qui allient une précision accrue et de faibles temps d'exécution constituent une avancée importante pour le développement d'outils efficaces d'exploration de l'espace de conception.
Soutenance : 13/04/2012
Membres du jury :
M. Dritan NACE, Professeur de l'Université de Compiègne [Rapporteur]
M. Sid TOUATI, Professeur de l' Université Nice Sophia Antipolis [Rapporteur]
Mme. Nathalie DRACH-TEMAM, Professeur de l'Université Pierre et Marie Curie
Mme.Claire HANEN, Professeur de l'Université de Paris Ouest Nanterre la Défense
M. Thierry MICHEL, Docteur Ingénieur de Recherche au Centre R&D Crolles de STMicroelectronics
M. Renaud SIRDEY, Chercheur au Commissariat à l'Energie Atomique CEA
M. Yves SOREL, Directeur de Recherche à l'INRIA Centre de Recherche Rocquencourt
Mme. Alix MUNIER-KORDON, Professeur de l'Université Pierre et Marie Curie
Publications 2009-2023
-
2023
- J. Fontaine, M. Benazouz, L. Zaourar, R. Chotin : “Improving Integrated Circuit Security using Mathematical Model Based on Clique Covering Reformulation”, 9th International Conference on Control, Decision and Information Technologies (CoDiT 2023), 9th International Conference on Control, Decision and Information Technologies, Rome, Italy, pp. 1717-1722, (IEEE) (2023)
-
2022
- J. Fontaine, L. Zaourar, M. Benazouz, R. Chotin : “Recherche de cliques pour un problème de cybersécurité matériel”, 23e édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne, France (2022)
-
2013
- M. Benazouz, A. Munier‑Kordon : “Cyclo-static DataFlow Phases Scheduling Optimization for Buffer Sizes Minimization”, M-SCOPES '13, St. Goar, Germany, pp. 3-12, (ACM) (2013)
- M. Benazouz, A. Munier‑Kordon, Th. Hujsa, B. Bodin : “Liveness evaluation of a cyclo-static DataFlow graph”, The 50th Annual Design Automation Conference, DAC 2013, Austin, United States, pp. 3:1-3:7, (ACM) (2013)
-
2012
- M. Benazouz : “Dimensionnement des Mémoires dans les Applications de Traitement de Flux de Données”, thèse, soutenance 13/04/2012, direction de recherche Munier, Alix (2012)
-
2011
- M. Benazouz, A. Munier‑Kordon : “Cyclo-Static DataFlow Phases Scheduling Optimization for the Throughput Constrained Buffer Sizes Minimization Problem”, (2011)
-
2010
- M. Benazouz, O. Marchetti, A. Munier‑Kordon, Th. Michel : “A New Method for Minimizing Buffer Sizes for Cyclo-Static Dataflow Graphs.”, ESTIMedia 2010 - 8th IEEE International Workshop on Embedded Systems for Real-Time Multimedia, Scottsdale, Arizona, United States, pp. 11-20, (IEEE) (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
- 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)