Description
Date depot: 1 janvier 1900
Titre: Dimensionnement des Mémoires pour les Applications de Traitement de Flux de Données
Directrice de thèse:
Alix MUNIER (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
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'événements généralisés temporisés (TMWEG) et graphes cyclo-static dataflow (CSDFG).
Nous considérons dans un premier temps les TMWEGs. 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 TMWEGs à structure arborescente et aux TMWEGs 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 TMWEG 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 (Min-Max LP) afin de répartir les phases sur une période. Ce Min-Max LP 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.
Mots clefs : Dimensionnement des mémoires, applications de traitement de flux de données, graphe d'événements généralisé temporisé, cyclo-static dataflow, vivacité, garantie de débit, odonnancement cyclique, ordonnancement périodique, programmation linéaire en nombres entiers, programmation linéaire Min-Max.
Doctorant.e: Benazouz Mohamed