Team : ALSOC
Departure date : 09/06/2012
Supervision : Alix MUNIER
Dimensionnement des Mémoires dans les Applications de Traitement de Flux de Données
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.
Defence : 04/13/2012 - 15h - Campus jussieu Amphi 45B Jury members : 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