Literatura académica sobre el tema "Vectorisation (informatique)"

Dans ce mémoire, nous présentons une méthode cohérente de lecture automatique de schémas électroniques. Cette méthode repose sur trois principaux traitements : vectorisation, segmentation, reconnaissance. La vectorisation utilise une méthode de propagation directionnelle de la distance (PDD), de nature morphologique, qui permet de détecter les segments rectilignes. Cette méthode produit une fragmentation en composantes directionnelles principales. Elle est complétée par une approximation polygonale. Une opération complémentaire, appelée post-vectorisation, achevé le travail, soit en joignant, soit en éliminant, soit en fusionnant certains vecteurs, selon le contexte graphique. Plusieurs niveaux de segmentation sont nécessaires dans notre étude : une segmentation de l'image binaire en couche graphique et couche texte, puis une segmentation de la couche graphique en couche composants et couche connexions, enfin une segmentation intra-couche de la couche composants qui permet d'isoler les composants. La segmentation en couche texte et en couche graphique repose sur la PDD seule. Les deux autres segmentations sont interactives. Elles reposent sur des caractéristiques des vecteurs : géométriques (longueur, orientation, épaisseur), et structurelles (statut et genre des points d'extrémités et des vecteurs). Elles mettent en regard l'image vectorisée et l'image brute. La méthode de reconnaissance, qui opère sur l'image des composants, utilise des modèles de Markov caches du premier ordre. Les observations sont des caractéristiques extraites de la représentation vectorielle. La phase de reconnaissance, phase finale du lecteur automatique que nous avons conçu, a fait ses preuves et peut constituer ainsi la passerelle vers la reprise par un logiciel de CAO d'électronique. Nous avons développé un logiciel prototypique complet, qui a permis de tester la validité des procédures exposées dans cette thèse, et de vérifier la faisabilité de notre approche.

Ce travail présente trois contributions aux domaines de la vectorisation des CPU et de l'apprentissage automatique. La première contribution est un algorithme pour calculer une moyenne avec des valeurs en virgule flottante de demi-précision. Dans ce travail réalisé avec un support matériel de demi-précision limité, nous utilisons une bibliothèque logicielle existante pour émuler le calcul de demi-précision. Cela nous permet de comparer la précision numérique de notre algorithme à celle de divers algorithmes couramment utilisés. Enfin, nous effectuons des tests de performance d'exécution en utilisant des valeurs à virgule flottante simples et doubles afin d'anticiper les gains potentiels de l'application de la vectorisation du CPU aux valeurs de demi-précision. Dans l'ensemble, nous constatons que notre algorithme présente des performances numériques légèrement inférieures dans le meilleur des cas en échange de performances numériques nettement supérieures dans le pire des cas, tout en offrant des performances d'exécution similaires à celles d'autres algorithmes. La deuxième contribution est une bibliothèque de calcul en virgule fixe conçue spécifiquement pour la vectorisation du CPU. Les bibliothèques existantes ne reposent pas sur l'auto-vectorisation du compilateur, qui ne parvient pas à vectoriser les opérations arithmétiques de multiplication et de division. De plus, ces deux opérations nécessitent des opérations de cast qui réduisent la vectorisabilité et ont un réel coût de calcul. Pour remédier à ce problème, nous présentons un format de stockage de données en virgule fixe qui ne nécessite aucune opération de cast pour effectuer des opérations arithmétiques. De plus, nous présentons un certain nombre de benchmarks comparant notre implémentation aux bibliothèques existantes et nous présentons la vitesse de vectorisation du CPU sur un certain nombre d'architectures. Dans l'ensemble, nous constatons que notre format en virgule fixe permet des performances d'exécution égales ou supérieures à toutes les bibliothèques comparées. La dernière contribution est un moteur d'inférence de réseau neuronal conçu pour réaliser des expériences en variant les types de données numériques utilisées dans le calcul d'inférence. Ce moteur d'inférence permet un contrôle spécifique à la couche des types de données utilisés pour effectuer l'inférence. Nous utilisons ce niveau de contrôle pour réaliser des expériences visant à déterminer l'agressivité avec laquelle il est possible de réduire la précision numérique utilisée dans l'inférence du réseau neuronal PVANet. Au final, nous déterminons qu'une combinaison des types de données standardisés float16 et bfoat16 est suffisante pour l'ensemble de l'inférence
This work presents three contributions to the fields of CPU vectorization and machine learning. The first contribution is an algorithm for computing an average with half precision floating point values. In this work performed with limited half precision hardware support, we use an existing software library to emulate half precision computation. This allows us to compare the numerical precision of our algorithm to various commonly used algorithms. Finally, we perform runtime performance benchmarks using single and double floating point values in order to anticipate the potential gains from applying CPU vectorization to half precision values. Overall, we find that our algorithm has slightly worse best-case numerical performance in exchange for significantly better worst-case numerical performance, all while providing similar runtime performance to other algorithms. The second contribution is a fixed-point computational library designed specifically for CPU vectorization. Existing libraries fail rely on compiler auto-vectorization, which fail to vectorize arithmetic multiplication and division operations. In addition, these two operations require cast operations which reduce vectorizability and have a real computational cost. To allevieate this, we present a fixed-point data storage format that does not require any cast operations to perform arithmetic operations. In addition, we present a number of benchmarks comparing our implementation to existing libraries and present the CPU vectorization speedup on a number of architectures. Overall, we find that our fixed point format allows runtime performance equal to or better than all compared libraries. The final contribution is a neural network inference engine designed to perform experiments varying the numerical datatypes used in the inference computation. This inference engine allows layer-specific control of which data types are used to perform inference. We use this level of control to perform experiments to determine how aggressively it is possible to reduce the numerical precision used in inferring the PVANet neural network. In the end, we determine that a combination of the standardized float16 and bfloat16 data types is sufficient for the entire inference

L’évolution des supercalculateurs, de leur origine dans les années 60 jusqu’à nos jours, a fait face à 3 révolutions : (i) l’arrivée des transistors pour remplacer les triodes, (ii) l’apparition des calculs vectoriels, et (iii) l’organisation en grappe (clusters). Ces derniers se composent actuellement de processeurs standards qui ont profité de l’accroissement de leur puissance de calcul via une augmentation de la fréquence, la multiplication des cœurs sur la puce et l’élargissement des unités de calcul (jeu d’instructions SIMD). Un exemple récent comportant un grand nombre de cœurs et des unités vectorielles larges (512 bits) est le co-proceseur Intel Xeon Phi. Pour maximiser les performances de calcul sur ces puces en exploitant aux mieux ces instructions SIMD, il est nécessaire de réorganiser le corps des nids de boucles en tenant compte des aspects irréguliers (flot de contrôle et flot de données). Dans ce but, cette thèse propose d’étendre la transformation nommée Deep Jam pour extraire de la régularité d’un code irrégulier et ainsi faciliter la vectorisation. Ce document présente notre extension et son application sur une mini-application d’hydrodynamique multi-matériaux HydroMM. Ces travaux montrent ainsi qu’il est possible d’obtenir un gain de performances significatif sur des codes irréguliers
Since the 60s to the present, the evolution of supercomputers faced three revolutions : (i) the arrival of the transistors to replace triodes, (ii) the appearance of the vector calculations, and (iii) the clusters. These currently consist of standards processors that have benefited of increased computing power via an increase in the frequency, the proliferation of cores on the chip and expansion of computing units (SIMD instruction set). A recent example involving a large number of cores and vector units wide (512-bit) is the co-proceseur Intel Xeon Phi. To maximize computing performance on these chips by better exploiting these SIMD instructions, it is necessary to reorganize the body of the loop nests taking into account irregular aspects (control flow and data flow). To this end, this thesis proposes to extend the transformation named Deep Jam to extract the regularity of an irregular code and facilitate vectorization. This thesis presents our extension and application of a multi-material hydrodynamic mini-application, HydroMM. Thus, these studies show that it is possible to achieve a significant performance gain on uneven codes

L’évolution des supercalculateurs, de leur origine dans les années 60 jusqu’à nos jours, a fait face à 3 révolutions : (i) l’arrivée des transistors pour remplacer les triodes, (ii) l’apparition des calculs vectoriels, et (iii) l’organisation en grappe (clusters). Ces derniers se composent actuellement de processeurs standards qui ont profité de l’accroissement de leur puissance de calcul via une augmentation de la fréquence, la multiplication des cœurs sur la puce et l’élargissement des unités de calcul (jeu d’instructions SIMD). Un exemple récent comportant un grand nombre de cœurs et des unités vectorielles larges (512 bits) est le co-proceseur Intel Xeon Phi. Pour maximiser les performances de calcul sur ces puces en exploitant aux mieux ces instructions SIMD, il est nécessaire de réorganiser le corps des nids de boucles en tenant compte des aspects irréguliers (flot de contrôle et flot de données). Dans ce but, cette thèse propose d’étendre la transformation nommée Deep Jam pour extraire de la régularité d’un code irrégulier et ainsi faciliter la vectorisation. Ce document présente notre extension et son application sur une mini-application d’hydrodynamique multi-matériaux HydroMM. Ces travaux montrent ainsi qu’il est possible d’obtenir un gain de performances significatif sur des codes irréguliers
Since the 60s to the present, the evolution of supercomputers faced three revolutions : (i) the arrival of the transistors to replace triodes, (ii) the appearance of the vector calculations, and (iii) the clusters. These currently consist of standards processors that have benefited of increased computing power via an increase in the frequency, the proliferation of cores on the chip and expansion of computing units (SIMD instruction set). A recent example involving a large number of cores and vector units wide (512-bit) is the co-proceseur Intel Xeon Phi. To maximize computing performance on these chips by better exploiting these SIMD instructions, it is necessary to reorganize the body of the loop nests taking into account irregular aspects (control flow and data flow). To this end, this thesis proposes to extend the transformation named Deep Jam to extract the regularity of an irregular code and facilitate vectorization. This thesis presents our extension and application of a multi-material hydrodynamic mini-application, HydroMM. Thus, these studies show that it is possible to achieve a significant performance gain on uneven codes

Le bitslicing est une technique utilisée pour implémenter des primitives cryptographiques efficaces et s'exécutant en temps constant. Cependant, écrire, optimiser, et sécuriser manuellement des programmes bitslicés est une tâche fastidieuse, nécessitant des connaissances en cryptographie, en microarchitecture des processeurs et en attaques par canaux cachés. Afin de remédier à ces difficultés, nous proposons Usuba, un langage dédié permettant d'implémenter des algorithmes de cryptographie symétrique. Usuba permet aux développeurs d'écrire des spécifications de haut niveau sans se soucier de leur parallélisation: un programme Usuba est une description scalaire d'une primitive, à partir de laquelle le compilateur Usuba, Usubac, produit automatiquement un code bitslicé et vectorisé. Afin de produire du code efficace pour les processeurs haut de gamme, Usubac applique plusieurs optimisations spécialement conçues pour les primitives cryptographiques, telles que l'entrelacement et l'ordonnancement d'instructions. Ainsi, le code produit par notre compilateur offre des performances comparables à du code assembleur ou C optimisé à la main. De plus, afin de générer des implémentations sécurisées contre des attaques par canaux cachés, nous proposons deux extensions de Usubac. Lorsque les attaques par analyse de courant sont un risque à considérer, Usubac est capable de protéger les implémentations qu'il produit à l'aide de masquage booléen. Si, additionnellement, des attaques par injection de fautes doivent être prévenues, alors Usubac peut générer du code pour SKIVA, un processeur 32-bit offrant des instructions permettant de combiner des contre-mesures pour du code bitslicé
Bitslicing is a technique commonly used in cryptography to implement high-throughput parallel and constant-time symmetric primitives. However, writing, optimizing and protecting bitsliced implementations by hand are tedious tasks, requiring knowledge in cryptography, CPU microarchitectures and side-channel attacks. The resulting programs tend to be hard to maintain due to their high complexity. To overcome those issues, we propose Usuba, a high-level domain-specific language to write symmetric cryptographic primitives. Usuba allows developers to write high-level specifications of ciphers without worrying about the actual parallelization: an Usuba program is a scalar description of a cipher, from which the Usuba compiler (Usubac) automatically produces vectorized bitsliced code. When targeting high-end Intel CPUs, the Usubac applies several domain-specific optimizations, such as interleaving and custom instruction-scheduling algorithms. We are thus able to match the throughputs of hand-tuned assembly and C implementations of several widely used ciphers. Futhermore, in order to protect cryptographic implementations on embedded devices against side-channel attacks, we extend our compiler in two ways. First, we integrate into Usubac state-of-the-art techniques in higher-order masking to generate implementations that are provably secure against power-analysis attacks. Second, we implement a backend for SKIVA, a custom 32-bit CPU enabling the combination of countermeasures against power-based and timing-based leakage, as well as fault injection

Dans le cadre d'un projet de lecture automatique des cartes scannées de l'institut géographique national (IGN), notre étude consiste à analyser et à interpréter la planche de vert représentant la végétation sur une carte topographique. Il s'agit donc d'extraire et de reconnaitre les objets de cette planche constitués de surfaces (zones de végétation), de lignes (haies ou limites) et de points (arbres et groupes d'arbres isoles) pour alimenter un système d'information géographique (SIG). Une méthode de traitement générique a du être déterminée afin de prendre en compte les deux types de conventions de rédaction de l’IGN (1922 et 1972) qui génèrent des images de textures très différentes pour la représentation des zones de végétation. Une première approche statistique de texture reposant sur des paramètres visuels et sur un arbre dichotomique n'ayant pas donné de résultats satisfaisants, nous avons adopté, dans le cadre d'une approche structurelle de texture, une méthode mixte. Apres pré-traitement de l'image, la méthode est fondée sur trois principales phases : apprentissage pour caractériser la texture, extraction des régions et validation des résultats obtenus. La première phase utilise des règles heuristiques, établies à partir des règles de rédaction cartographique et repose sur la caractérisation des textures (primitives et règles de placement) formant les objets surfaciques. Les deux premières étapes ont du être respectivement adaptées aux zones de hachures et aux zones de poncifs. La troisième phase (extraction des régions) a été elle-même divisée en trois sous-étapes, correspondant à l'extraction des primitives de texture, à leur regroupement, et au calcul du contour des régions. La caractérisation des paramètres de texture permet à notre méthode d'être générique et robuste. L'approche mixte permet de bien gérer les problèmes dus aux bruits de l'image. Enfin, l'analyse des limites des zones a été affinée par l'étude conjointe avec les autres planches-mères, la planche de noir tout particulièrement. Cette méthodologie a permis une interprétation tout à fait satisfaisante de la planche et l'évaluation prouve que le système est fiable et robuste : pas d'erreurs de classification et de faibles erreurs d'omission. Les résultats obtenus montrent qu'il n'est pas nécessaire d'apporter de corrections manuelles.

Cette thèse aborde les difficultés de mise au point de codes multicibles - c'est-à-dire de codes dont les performances sont portables entre différentes cibles matérielles. Nous avons identifié deux principales difficultés à surmonter : l'unification de l'expression du parallélisme d'une part et la nécessité d'adapter le format de stockage des données d'autre part. Afin de mettre au point une version multicible de la bibliothèque d'algèbre linéaire Legolas++ mise au point à EDF R&D, nous avons conçu MTPS (MultiTarget Parallel Skeleton), une bibliothèque dédiée à la mise au point de codes multicible. MTPS permet d'obtenir une implémentation multicible pour les problèmes appliquant une même fonction aux différents éléments d'une collection. MTPS prend alors en charge l'adaptation du format de stockage des données en fonction de l'architecture ciblée. L'intégration des concepts de MTPS dans Legolas++ a conduit à l'obtention d'un prototype multicible de Legolas++. Ce prototype a permis de mettre au point des solveurs dont les performances sont proches de l'optimal sur différentes architectures matérielles.

Ce travail de thèse vise à mettre en place un système d'extraction de réseau routier en milieu urbain à partir d'image satellite à très haute résolution. Dans ce contexte, nous avons proposé deux méthodes de localisation de routes. La première approche est fondée sur la procédure de conversion de l'image vers un format vectoriel. L'originalité de cette approche réside dans l'utilisation d'une méthode géométrique pour assurer le passage vers une représentation vectorielle de l'image d'origine et la mise en place d'un formalisme logique fondé sur un ensemble de critères perceptifs permettant le filtrage de l'information inutile et l'extraction des structures linéaires. Dans la deuxième approche, nous avons proposé un algorithme fondé sur la théorie des ondelettes, il met particulièrement en évidence les deux volets multi-résolution et multi-direction. Nous proposons donc une approche de localisation des routes mettant en jeux l'information fréquentielle multi directionnelle issue de la transformée en ondelette Log-Gabor. Dans l'étape de localisation, nous avons présenté deux détecteurs de routes qui exploitent l'information radiométrique, géométrique et fréquentielle. Cependant, ces informations ne permettent pas un résultat exact et précis. Pour remédier à ce problème, un algorithme de suivi s'avère nécessaire. Nous proposons la reconstruction de réseaux routiers par des courbes NURBS. Cette approche est basée sur un ensemble de points de repères identifiés dans la phase de localisation. Elle propose un nouveau concept, que nous avons désigné par NURBSC, basé sur les contraintes géométriques des formes à approximer. Nous connectons les segments de route identifiés afin d'obtenir des tracés continus propres aux routes.

L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variables
The pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables

Bien penser la structuration de données est primordial pour obtenir de hautes performances, alors que les processeurs actuels perdent un temps considérable à attendre la complétion de transactions mémoires. En particulier les localités spatiales et temporelles de données doivent être optimisées.Cependant, les transformations de structures de données ne sont pas proprement explorées par les compilateurs, en raison de la difficulté que pose l'évaluation de performance des transformations potentielles. De plus,l'optimisation des structures de données est chronophage, sujette à erreur etles transformations à considérer sont trop nombreuses pour être implémentées à la main dans l'optique de trouver une version de code efficace.On propose de guider les programmeurs à travers le processus de restructuration de données grace à un retour utilisateur approfondi, tout d'abord en donnant une description multidimensionnelle de la structure de donnée initiale, faite par une analyse de traces mémoire issues du binaire de l'application de l'utilisateur, dans le but de localiser des problèmes de stride au niveau instruction, indépendemment du langage d'entrée. On choisit de focaliser notre étude sur les transformations de structure de données, traduisibles dans un formalisme proche du C pour favoriser la compréhension de l'utilisateur, que l'on applique et évalue sur deux cas d'étude qui sont des applications réelles,à savoir une simulation d'ondes cardiaques et une simulation de chromodynamique quantique sur réseau, avec différents jeux d'entrées. La prédiction de performance de différentes transformations est conforme à 5% près aux versions réécrites à la main
Careful data layout design is crucial for achieving high performance, as nowadays processors waste a considerable amount of time being stalled by memory transactions, and in particular spacial and temporal locality have to be optimized. However, data layout transformations is an area left largely unexplored by state-of-the-art compilers, due to the difficulty to evaluate the possible performance gains of transformations. Moreover, optimizing data layout is time-consuming, error-prone, and layout transformations are too numerous tobe experimented by hand in hope to discover a high performance version. We propose to guide application programmers through data layout restructuring with an extensive feedback, firstly by providing a comprehensive multidimensional description of the initial layout, built via analysis of memory traces collected from the application binary textit {in fine} aiming at pinpointing problematic strides at the instruction level, independently of theinput language. We choose to focus on layout transformations,translatable to C-formalism to aid user understanding, that we apply and assesson case study composed of two representative multithreaded real-lifeapplications, a cardiac wave simulation and lattice QCD simulation, with different inputs and parameters. The performance prediction of different transformations matches (within 5%) with hand-optimized layout code