BENAZOUZ Mohamed

Docteur
Équipe : ALSOC
Date de départ : 06/09/2012
https://lip6.fr/Mohamed.Benazouz

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

Date de départ : 06/09/2012

Publications 2009-2023

Mentions légales
Carte du site