Optimisation de codes correcteurs d'effacements par application de transformées polynomiales / Jonathan Detchart ; sous la direction de Jérôme Lacan et de Emmanuel Lochin

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Équations polynomiales

Architecture -- Informatique

Classification Dewey : 000

Lacan, Jérôme (19..-....) (Directeur de thèse / thesis advisor)

Lochin, Emmanuel (Directeur de thèse / thesis advisor)

Augot, Daniel (Président du jury de soutenance / praeses)

Normand, Nicolas (Rapporteur de la thèse / thesis reporter)

Roca, Vincent (Membre du jury / opponent)

Institut supérieur de l'aéronautique et de l'espace (Toulouse ; 2007-....) (Organisme de soutenance / degree-grantor)

École doctorale Mathématiques, informatique et télécommunications (Toulouse) (Ecole doctorale associée à la thèse / doctoral school)

Équipe d'accueil doctoral Modélisation et ingénierie des systèmes (Toulouse, Haute-Garonne) (Equipe de recherche associée à la thèse / thesis associated research team)

Institut supérieur de l'aéronautique et de l'espace (Toulouse, Haute-Garonne). Département d’ingénierie des systèmes complexes (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Les codes correcteurs d’effacements sont aujourd’hui une solution bien connueutilisée pour fiabiliser les protocoles de communication ou le stockage distribué desdonnées. La plupart de ces codes sont basés sur l’arithmétique des corps finis, définissantl’addition et la multiplication sur un ensemble fini d’éléments, nécessitantsouvent des opérations complexes à réaliser. En raison de besoins en performancetoujours plus importants, ces codes ont fait l’objet de nombreuses recherches dans lebut d’obtenir de meilleures vitesses d’exécution, tout en ayant la meilleure capacitéde correction possible. Nous proposons une méthode permettant de transformer les éléments de certains corps finis en éléments d’un anneau afin d’y effectuer toutes les opérations dans lebut de simplifier à la fois le processus de codage et de décodage des codes correcteursd’effacements, sans aucun compromis sur les capacités de correction. Nous présentonségalement une technique de réordonnancement des opérations, permettant deréduire davantage le nombre d’opérations nécessaires au codage grâce à certainespropriétés propres aux anneaux utilisés. Enfin, nous analysons les performances decette méthode sur plusieurs architectures matérielles, et détaillons une implémentationsimple, basée uniquement sur des instructions xor et s’adaptant beaucoupplus efficacement que les autres implémentations à un environnement d’exécutionmassivement parallèle.

Résumé / Abstract : Erasure codes are widely used to cope with failures for nearly all of today’snetworks communications and storage systems. Most of these codes are based onfinite field arithmetic, defining the addition and the multiplication over a set offinite elements. These operations can be very complex to perform. As a matter offact, codes performance improvements are still an up to date topic considering thecurrent data growth explosion. We propose a method to transform the elements of some finite fields into ring elements and perform the operations in this ring to simplify both coding and decoding of erasure codes, without any threshold on the correction capacities.We also present a scheduling technique allowing to reduce the number of operations thanks to some particular properties of the ring structure. Finally, we analyse the performance ofsuch a method considering several hardware architectures and detail a simple implementation, using only xor operations, fully scalable over a multicore environment.