Bonjour,
j'ai le grand plaisir de vous inviter à la soutenance de ma thèse de doctorat intitulée
"Dimensionnement des Mémoires dans les Applications de Traitement de Flux de Données".
==========
Date et lieu
==========
La soutenance aura lieu à l’Université Pierre et Marie Curie le Vendredi 13 Avril 2012 à 15h00 dans l'Amphithéâtre 45B, au pied de la tour 45 (niveau Jussieu).
Vous êtes également invités au pot qui suivra à la maison de la pédagogie Salle A002.
http://www.upmc.fr/fr/vie_des_campus/handicap/plan_d_acces.html
===========
Jury de thèse
===========
M. Dritan NACE, Professeur de l'Université de Technologie 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 (examinateur)
Mme. Claire HANEN, Professeur de l'Université de Paris Ouest Nanterre la Défense (examinateur)
M. Thierry MICHEL, Docteur Ingénieur de Recherche au Centre R&D Crolles de STMicroelectronics (examinateur)
M. Renaud SIRDEY, Chercheur au Commissariat à l'Energie Atomique CEA (examinateur)
M. Yves SOREL, Directeur de Recherche à l'INRIA Centre de Recherche Rocquencourt (examinateur)
Mme. Alix MUNIER-KORDON, Professeur de l'Université Pierre et Marie Curie (Directeur de thèse)
======
Résumé
======
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.
=======
Abstract
=======
Recent works in Electronic System Level (ESL) design and High-Level Synthesis (HLS) have enabled Design Space Exploration (DSE) in order to meet the growing demand for higher performance while reducing time to market. Several metrics are used during the exploration process; the throughput is a key performance measure when it comes to stream processing applications. Sizes allocated to the buffers that support data streams between the different application tasks is one of the factors that influence the achievable throughput. Several exact and heuristic methods have been proposed to compute buffer capacities that satisfy throughput constraint. However, their exponential complexity and thus their prohibitive run-time make them useless even for some small applications. The aim of this thesis is to provide an analytical approach to optimize buffer capacities under throughput constraint in polynomial time. We adopted for this study two powerful Models of Computation (MoC) for timing analysis of systems behavior: Timed Marked Weighted Event Graphs (TMWEG) and Cyclo-Static DataFlow Graphs (CSDFG).
The first part of this thesis is dedicated to TMWEGs. Assuming that tasks are scheduled periodically, we model the buffer capacities optimization problem under throughput constraint by an Integer Linear Program (ILP). We characterize the trade-offs between the throughput and the capacity of a buffer and we propose a closed-form formula for the computation of the minimum capacity to allocate to a buffer in order to achieve a given throughput. This result is then generalized to derive an optimal solution to the ILP for tree-structured TMWEGs. We also develop an algorithm to build an optimal solution for the case of a cycle TMWEG. In the general case, we propose a 2-approximate polynomial algorithm to solve the ILP. In the second part, we extend results obtained for TMWEGs to CSDFGs. In particular, we propose a sufficient condition for the liveness of a CSDFG that is checkable in polynomial time. The CSDFG model raises the problem of the scheduling of the different phases of a CSDF task. We present a Min-Max Linear Program (Min-Max LP) that derives an optimized periodic phases scheduling per CSDF task in order to minimize buffer capacities. Then, this Min-Max LP is used to relax the periodic schedule semantic, which allows to obtain close to optimal buffer capacities while running in polynomial time.
Despite the restriction to the periodic scheduling policy, our experiments on real case studies show that solutions computed by our polynomial algorithms are of good quality compared to heuristics or exact techniques based on the as-soon-as-possible scheduling policy. In the context of growing use of HLS and ESL design tools, our algorithms that combined increased accuracy and low run-time constitute an important step towards the development of efficient design space exploration tools.
Cordialement,
Mohamed BENAZOUZ
Doctorant LIP6
