Liveness analysis techniques and run-time environment for memory management of dataflow applications / Benjamin Dauphin ; sous la direction de Renaud Pacalet et de Ludovic Apvrille

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Langue / Language : français / French

Catalogue Worldcat

Capacité de traitement

Systèmes embarqués (informatique)

Pacalet, Renaud (19..-....) (Directeur de thèse / thesis advisor)

Apvrille, Ludovic (19..-....) (Directeur de thèse / thesis advisor)

Petrucci, Laure (19..-....) (Président du jury de soutenance / praeses)

Simone, Robert de (1957-....) (Rapporteur de la thèse / thesis reporter)

Nezan, Jean-François (Rapporteur de la thèse / thesis reporter)

Thibault, Samuel (1981-....) (Membre du jury / opponent)

Mancini, Stéphane (19..-.... ; enseignant-chercheur en électronique) (Membre du jury / opponent)

Enrici, Andrea (19..-....) (Membre du jury / opponent)

Institut polytechnique de Paris (Organisme de soutenance / degree-grantor)

École doctorale de l'Institut polytechnique de Paris (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire Traitement et communication de l'information (Paris ; 2003-....) (Laboratoire associé à la thèse / thesis associated laboratory)

Télécom Paris (Palaiseau) (Autre partenaire associé à la thèse / thesis associated third party)

Résumé / Abstract : Cette thèse a été effectuée à Télécom Paris et a été financée par Nokia Bell Labs France. Dans cette thèse sont étudiées différentes techniques visant à la gestion des interblocages et de la saturation des capacités mémoires dans les systèmes embarqués. Ce travail trouve sa motivation dans la complexification de l’architecture des systèmes informatiques au cours des dernières décennies, notamment avec la généralisation des architectures hétérogènes et Non-Uniform Memory Access (NUMA). Cette évolution se constate dans tous types de systèmes informatiques, de l’embarqué sur Multi-Processor System on a Chip (MPSoC) aux systèmes distribués pour le calcul haute performance (High-Performance Computing). Nous nous intéressons en particulier au problème de la saturation des capacités mémoires dans les systèmes embarqués utilisés pour le traitement numérique du signal (Digital Signal Processing). Nos contributions peuvent toutefois être utilisées pour d’autres types d’applications et de plateformes.Cette thèse apporte trois contributions :(1) Nous présentons une technique de prévention des interblocages se basant sur l’étude des cliques dans un type de graphes, les Memory Exclusion Graphs. Ces graphes représentent les buffers alloués en mémoire et leur possibilité d’allocation simultanée.(2) Nous présentons une optimisation de l’analyse de vivacité conventionnellement utilisée pour l’étude de la saturation mémoire, permettant d’analyser des systèmes plus complexes en un temps réduit. (3) Nous avons développé une technique d’évitement des interblocages utilisant les résultats de l’analyse de vivacité. Cette technique d’évitement a été intégrée à un environnement d’exécution expérimental.Nous évaluons la première et la deuxième contribution en les comparant à un outil issu de l’état de l’art.Pour conclure, nous proposons plusieurs pistes de travaux futurs sur la base des contributions de la thèse.

Résumé / Abstract : This thesis has been realized at Télécom Paris and it has been financed by Nokia Bell Labs France. It studies different techniques to handle the issue of deadlocks and memory shortages in computing systems. Its work is motivated by the rise over the past decades of heterogeneous and Non-Uniform Memory Access (NUMA) architectures in all varieties computing systems, from embedded systems running on Multi-Processor Systems on a Chip (MPSoCs) to distributed High-Performance Computing (HPC) systems. We focus more specifically on the issue of memory shortages in embedded systems used for Digital Signal Processing, but our contributions could be applied to different applications and platforms.The contributions of this thesis are threefold:(1) we present a deadlock prevention technique based on the analysis of cliques in Memory Exclusion Graphs, which are graphs representing buffers allocated in memory and whether they might get simultaneously allocated;(2) we present an optimization on the conventional liveness analysis for memory shortages, allowing to execute the liveness analysis in reasonable time for larger systems than previously supported;(3) we developed a deadlock avoidance strategy using results from the liveness analysis, and integrated it into an experimental run-time environment.We evaluate our first and second contributions in comparison to an existing state-of-the-art tool.Finally we propose multiple leads to improve on the contributions of the thesis.