Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
A Cross-Temporal Robotic Dance Performance: Dancing with a Humanoid Robot and Artificial Life
No full textInternational audienceWe present a case study exploring the integration of artificial, autonomous, and interactive artifacts into the realm of choreography. Specifically, we assessed our experimentation on the HRP-4 humanoid robot and an evolving virtual ecosystem, utilized as characters and dynamic scenography in a dance performance. Our research sheds light on the mechanisms enabling dynamic interplay between human beings and artificial entities, with a specific emphasis on the significance of crosstemporal dialogues. Additionally, we demonstrate the potential of autonomous interactive systems in fostering improvisational co-creation in the process of stage development
Indirect Job-Shop coding using rank: application to QAOA (IQAOA)
No full textThe Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned challenges in scheduling. It is characterized as a disjunctive problem, wherein a solution is fully depicted through an oriented disjunctive graph, with earliest starting times computed using a longest path algorithm. The complexity of solving this problem arises in part from the requirement that disjunctive graphs representing solutions must be acyclic. Consequently, enumerating these graphs is feasible for small-scale instances only. A significant advancement in this field, credited to (Bierwith, 1995), is the introduction of the 'vector by repetition' (commonly known as Bierwith's vector). Notably, this vector possesses the property that it can be mapped to an acyclic disjunctive graph, thereby enabling the mapping of a vector to a solution. This property has facilitated the development of highly efficient resolution schemes, as it allows the enumeration of solutions only i.e. acyclic disjunctive graphs. Our objective is to demonstrate how Bierwith's vector can be integrated into a Quantum Approximate Optimization Algorithm (QAOA) to tackle the job-shop problem using a novel quantum approach
Techniques Avancées D'analyse De Performance Pour Évaluer L'efficacité Des Accélérateurs Graphiques Pour Les Applications
No full textThe rising complexity of Artificial Intelligence (AI) applications significantly increases the demand for computing power to execute and train Machine Learning (ML) models, thus boosting the energy consumption of data centers. GPUs, enhanced by developments like tensor cores (2017), have become the preferred architecture. Building more efficient ML computing systems relies on a deep understanding of the limits of both parts of a tightly coupled hardware/software paradigm. However, the high abstraction of ML frameworks and the closed-source, proprietary design of state-of-the-art GPU architectures obscure the execution process and make performance evaluation tedious.The main goal of this thesis is to provide new methodologies to evaluate performance and energy bottlenecks of GPU-accelerated ML workloads. Existing profiling solutions are limited in three ways. First, ML framework profiling tools are designed to assist the development of ML models but do not give insights into the runtime execution of the ML framework. While these profiling tools provide high-level metrics on the GPU device execution, these metrics can be misleading and overestimate the utilization of the GPU resources. Second, lower-level profiling tools provide access to performance counters and insights on how to optimize GPU kernels. However, these tools cannot capture the efficiency of host/device interactions occurring at a higher level. Finally, when evaluating energy bottlenecks, the mentioned profiling tools cannot provide a detailed breakdown of the energy consumed by modern GPUs during ML training. To tackle these shortcomings, this thesis makes three key contributions organized as a top-down analysis of GPU-accelerated ML workloads.First, we analyze ML frameworks' runtime execution on a CPU-GPU tandem. We propose a new profiling methodology that leverages data from an ML framework's profiler. We use this methodology to provide new insights into the runtime execution of inference, for three ML models. Our results show that GPU kernels' execution must be long enough to hide the runtime overhead of the ML framework, increasing GPU utilization. However, this strive for longer kernel execution leads to the use of bigger batches of data, seemingly pushing the need for more GPU memory.Second, we analyze the utilization of GPU resources when performing ML training. We propose a new profiling methodology combining the use of high-level and low-level profilers to provide new insights into the utilization of the GPU's inner components. Our experiments, on two modern GPUs, suggest that bigger GPU memory helps enhance throughput and utilization from a high level. However, our results also suggest that a plateau has been reached, eliminating the push for bigger batches. Furthermore, we observe that the fastest GPU cores (tensor cores) are idle most of the time, and the tested workloads are now limited by kernels that do not use these cores. Thus, our results suggest that the current GPU paradigm is reaching a saturation point.Finally, we analyze the energy consumption of GPUs during ML training. We propose an energy model and calibration methodology that uses microbenchmarks to provide a breakdown of the GPU energy consumption. We implement and validate this approach with a modern NVIDIA GPU. Our results suggest that data movement is responsible for most of the energy consumption (up to 84% of the dynamic energy consumption of the GPU). This further motivates the push for newer architectures, optimizing memory accesses (e.g., processing in/near memory, vectorized architectures).This thesis provides a comprehensive analysis of the performance and energy bottlenecks of GPU-accelerated ML workloads. We believe our contributions uncover some of the limitations of current GPU architectures and motivate the need for more advanced profiling techniques to design more efficient ML accelerators. We hope that our work will inspire future research in this direction.L'augmentation en complexité des applications d'Intelligence Artificielle (IA) entraîne une demande accrue en puissance de calcul et en énergie pour entraîner et exécuter des modèles d'apprentissage automatique (ML). Les processeurs graphiques (GPU), forts d'architectures améliorées (e.g., ajout de cœurs dédiés à l'IA en 2017), sont devenus le système de prédilection pour de telles tâches. Concevoir des systèmes plus efficients pour l'IA n'est possible qu'avec une connaissance approfondie des limites des systèmes existants, où matériel et logiciel sont étroitement couplés. Mais l'abstraction des plateformes d'IA et la nature fermée des architectures GPU modernes masquent le processus d'exécution, rendant ses performances difficiles à évaluer.L'objectif de cette thèse est caractériser les facteurs limitant la performance et augmentant la consommation énergétique des tâches d'IA exécutées avec des GPUs modernes. Cette thèse adresse trois limitations majeures des outils existants. Premièrement, les outils de caractérisation proposés par les plateformes de développement d'IA sont conçus pour aider les développeurs de modèles ML, mais ne donnent pas d'informations sur la charge additionnelle que représente l'exécution de ces plateformes. Deuxièmement, les outils de caractérisation proposés par les fabricants de GPUs permettent l'accès à des compteurs de performance, mais qui ne permettent pas d'estimer l'efficacité des interactions entre le GPU et l'unité centrale (CPU). Enfin, pour caractériser la consommation énergétique des GPUs lors de l'entraînement d'IA, ces outils ne permettent pas d'obtenir une décomposition détaillée. Pour adresser ces limitations, cette thèse propose trois contributions.Premièrement, nous analysons l'exécution des plateformes d'IA sur un couple CPU-GPU. Nous proposons une nouvelle méthodologie de caractérisation réutilisant les données fournies par des outils existants. Cette méthodologie permet d'extraire de nouvelles informations quant à l'exécution de modèles d'IA. Nous étudions l'exécution de trois modèles d'IA et nos résultats montrent que l'exécution des opérations destinées au GPU doit être suffisamment longue pour masquer le temps d'exécution de la plateforme d'IA, augmentant l'utilisation GPU. Pour autant, cette incitation à utiliser des opérations plus longues conduit à l'utilisation de lots de données plus conséquents, augmentant la demande en mémoire GPU.Deuxièmement, nous analysons l'utilisation des ressources internes au GPU lors de l'entraînement. Nous proposons une nouvelle méthodologie de caractérisation combinant les outils proposés par les fabricants de GPUs et par les plateformes d'IA. Nos résultats suggèrent qu'un plafond de performance a été atteint, annulant les bénéfices à utiliser des lots de données plus larges pour l'entraînement. Nous observons que les cœurs les plus performants du GPU (tensor cores) restent inactifs durant la majorité du temps d'entraînement, limité par les opérations qui n'utilisent pas ces cœurs. Nos résultats suggèrent que les architectures GPU modernes ont atteint un point de saturation.Enfin, nous analysons la consommation énergétique des GPUs lors de l'entraînement. Nous proposons une méthodologie basée sur l'utilisation de microprogrammes afin d'obtenir une décomposition de la consommation énergétique. Nos résultats suggèrent que les transferts de données sont responsables pour la majorité de la consommation énergétique dynamique du GPU (jusqu'à 84%). Ces résultats soutiennent la tendance de recherche pour des architectures cherchant optimiser les transferts de données (e.g., traitement en mémoire ou à proximité, architectures vectorielles).Cette thèse propose une analyse approfondie des limites de performance et de la consommation énergétique des tâches d'IA exécutées à l'aide de GPUs modernes. Nous espérons que ce travail inspirera de futures recherches dans cette direction, pour concevoir des accélérateurs d'IA plus efficients
A Fast and Efficient Graph-Based methodology for Cell-Aware Model Generation
No full textInternational audienceAs modern Integrated Circuits (ICs) feature eversmaller transistors, the prevalence of manufacturing defects within standard cells (intra-cell defects) has increased. Detecting and localizing these defects is crucial to guarantee a fast yield ramp-up and to maintain a low-test escape rate. Unfortunately, traditional fault models such as stuck at and transition fail to adequately represent intra-cell defects. The Cell-Aware (CA) approach was introduced to tackle this problem, but it requires time-consuming analog SPICE simulations for standard cell characterization. To speed-up the CA model generation process, this paper presents a methodology based on graph theory called Transistor Undetectable Defect Eliminator (TrUnDeL). This methodology identifies undetectable defects for each stimulus applied to the inputs of the cell, subsequently excluding them from the analog simulations to perform. TrUnDeL uses rulebased and propagation-based techniques and was trialed on combinational and sequential cells of two libraries from STMicroelectronics (P28 and C28) to identify the undetectable stimulus/defect pairs, so that analog simulations are performed only on the remaining pairs. As a result, the CA model generation process time was reduced by a factor of 3 compared to a standard SPICE-based generation process
Attaques par Canaux Auxiliaires Horizontales en Présence de Bruit
No full textRecently introduced to the field of side channel analysis, neural networks have showed to be a powerful and relevant alternative to template attacks. However, their applicability is limited to profiled attack context, as supervised training is needed in order to build a relevant generalized model. When profiling on an open device is not possible, and vertical attacks cannot be applied, the only left possible approach is horizontal attacks. While several contributions have been made for tackling horizontal attacks on asymmetric cryptography algorithms implementations such as RSA or elliptic curve cryptography, their performance remains low and their applicability hard in real life scenario with the presence of high noise. Still, another neural network family known as unsupervised learning neural networks exists, which would not require an open device access and. It must be known if these networks unsupervised learning paradigm and their associated topology can be applied to the context of side-channel attacks and if such is the case, whether or not they can provide better results than traditional methods. Thus, In this work, several approaches are considered to improve clustering based horizontal side channel attacks efficiency. A novel methodology based on statistical analysis is also introduced for univariate points of interest selection. Additionally, an alternative metric for quantifying points of interest exploitability in a clustering attack is proposed and compared to commonly used metrics. The proposed methods allow providing significant improvement over state of the art attacks performance and giving a better explainability of obtained results.Récemment, l'utilisation de réseaux de neurones dans le cadre des attaques par canaux auxiliaires de type profilées sur systèmes ouverts a démontré son efficacité jusqu'à presque remplacer les techniques précédemment utilisées. Néanmoins, lorsqu'il n'est pas possible d'avoir accès à un système ouvert et lorsque les attaques dites verticales ne sont pas envisageables, la principale option restante est de mettre en oeuvre des attaques horizontales. C'est généralement le cas pour des implémentations d'algorithmes de cryptographie asymétrique (RSA, ECC). Les attaques horizontales existantes s'appuient sur des techniques de classification ou clustering issues du monde des statistiques. Même s'il a été apporté l'efficacité de ces techniques dans certaines circonstances, en pratique le taux de succès d'attaques basés sur ces techniques reste tout de même relativement faible, en particulier dans le cas d'environements avec la présence de hauts niveaux de bruits. Il existe toutefois une autre catégorie de réseaux de neurones dit à apprentissage non-supervisé, pour lesquels l'accès à un système ouvert n'est pas nécessaire. Il s'agit alors de déterminer si ce type de réseau peut être utilisé dans le contexte des attaques par canaux auxiliaire et, le cas échéant, si le gain par rapport aux techniques d'attaques déjà utilisées est suffisant. L'objectif de ces travaux est donc de valider cette idée en identifiant et en proposant une ou plusieurs topologies de réseaux de neurones adaptées aux attaques horizontales par clustering et d'en vérifier l'efficacité sur l'implémentation d'algorithmes cryptographiques asymétrique. De plus, une méthodologie alternative pour la sélection univariée de points d'intérêts basée sur des méthodes statistique est proposée, ainsi qu'une nouvelle métrique pour la quantification de fuite et l'exploitabilité des points sélectionnés. Les résultats obtenus montrent une amélioration des taux de succès obtenus par rapport aux méthodes proposées dans l'état de l'art
Compter les paires de mots qui se chevauchent
No full textComments:version 2: 20 pages, 1 figure, 3 tables, appendix A, B, Cversion 1: 16 pages, 1 figure, 2 tables, appendix A, B, CMSC-class: MCS: 05-06ACM-class: G.2.1License: http://creativecommons.org/licenses/by-nc-sa/4.0/Eine Korrelation ist ein binärer Vektor, der alle möglichen Überlappungspositionen zweier Wörter codiert, wobei eine Überlappung für ein geordnetes Paar von Wörtern (u,v) auftritt, wenn ein Suffix des Wortes u mit einem Präfix des Wortes v übereinstimmt. Da mehrere Paare die gleiche Korrelation haben können, ist es relevant zu zählen, wie viele Wortpaare die gleiche Korrelation teilen, abhängig von der Größe des Alphabets und der Länge der n-Wörter. Wir stellen Rekursionen vor, um die Anzahl dieser Paare - Populationsgröße genannt - für jede beliebige Korrelation zu berechnen; dazu nutzen wir eine Beziehung zwischen den Überlappungen zweier Wörter und die Selbstüberlappung eines Wortes aus. Mit diesem Theorem können wir die Anzahl der Paare berechnen, deren längste Überlappung eine bestimmte Länge hat, und zeigen, dass die erwartete Länge der längsten "Border" zweier Wörter asymptotisch divergiert, was zwei offene Fragen löst, die Gabric 2022 aufgeworfen hat. Schließlich stellen wir auch Grenzwerte für das asymptotische Populationsverhältnis jeglicher Korrelation zur Verfügung. Angesichts der Bedeutung von Wortüberschneidungen in Bereichen wie Wortkombinatorik, Bioinformatik und digitaler Kommunikation können unsere Ergebnisse die Analyse von Algorithmen für die Verarbeitung von Zeichenketten, das Design von Codes oder die Zusammenstellung von Genomen erleichtern.A correlation is a binary vector that encodes all possible positions of overlaps of two words, where an overlap for an ordered pair of words occurs if a suffix of matches a prefix of . As multiple pairs can have the same correlation, it is relevant to count how many pairs of words share the same correlation depending on the alphabet size and word length . We exhibit recurrences to compute the number of such pairs -- which is termed population size -- for any correlation; for this, we exploit a relationship between overlaps of two words and self-overlap of one word. This theorem allows us to compute the number of pairs with a longest overlap of a given length and to show that the expected length of the longest border of two words asymptotically diverges, which solves two open questions raised by Gabric in 2022. Finally, we also provide bounds for the asymptotic of the population ratio of any correlation. Given the importance of word overlaps in areas like word combinatorics, bioinformatics, and digital communication, our results may ease analyses of algorithms for string processing, code design, or genome assembly.Une corrélation est un vecteur binaire qui encode toutes les positions possibles de chevauchement de deux mots. Un chevauchement pour une paire ordonnée de mots (u,v) existe (et est défini) si un suffixe du mot u égale un préfixe du mot v. Comme plusieurs paires de mots peuvent avoir la même corrélation, il est pertinent de compter combien de paires de mots partagent une même corrélation en fonction de la taille de l'alphabet et de la longueur des mots notée n. Nous présentons des récurrences pour calculer le nombre de ces paires - nombre appelé taille de la population - pour n'importe quelle corrélation ; pour cela, nous exploitons une relation entre les chevauchements de deux mots et l'auto-chevauchement d'un mot. Ce théorème nous permet de calculer le nombre de paires dont le plus long chevauchement est d'une longueur donnée, ainsi que de montrer que la longueur moyenne du plus long bord de deux mots diverge asymptotiquement. Ceci résout deux questions ouvertes soulevées par Gabric en 2022. Enfin, nous fournissons également des bornes asymptotiques du ratio de population pour une corrélation quelconque. Étant donnée l'importance des chevauchements de mots dans des domaines tels que la combinatoire des mots, la bioinformatique et la communication digitale, nos résultats peuvent faciliter l'analyse des algorithmes pour le traitement des chaînes de caractères, la conception de codes ou l'assemblage de génomes
FCAvizIR: Exploring Relational Data Set’s Implications Using Metrics and Topics
No full textInternational audienceImplication is a core notion of Formal Concept Analysis and its extensions. It provides information about the regularities present in the data. When one considers a relational data set of real-size, implications are numerous and their formulation, which combines primitive and relational attributes computed using Relational Concept Analysis framework, is complex. For an expert wishing to answer a question based on such a corpus of implications, having a smart exploration strategy is crucial. In this paper, we propose a visual approach, implemented in a web platform named FCAvizIR, for leveraging such corpus. Comprised of three interactive and coordinated views and a toolbox, FCAvizIR has been designed to explore corpora of implication rules following Schneiderman’s famous mantra “overview first, zoom and filter, then details on demand”. It enables metrics filtering, e.g. fixing a minimum and a maximum support value, and the multiple selection of relations and attributes in the premise and in the conclusion to identify the corresponding subset of implications presented as a list and Euler diagrams. An example of exploration is presented using an excerpt of Knomana to analyze plant-based extracts for controlling pests
Application du DEEP LEARNING au traitement de données LIDAR TERRESTRE pour l’évaluation de TRAITS ARCHITECTURAUX et de fonctionnement d’arbres fruitiers
No full textWith the effects of climate change, a growing human population, and the need to ensurefood security, understanding the development of plants is a crucial part of the possible solutions. This study is considered to be highly significant in addressing these pressing concerns. To undertake such a study, it is necessary to explore how genetic variability gives rise to specific sets of architectural traits. Understanding these architectural variations facilitates the regulation, prediction and assurance of fruit production. It will also allow management strategies to be proposed to maintain the health of the tree and optimize its productivity. Fruit trees typically consist of two components: the upper part, including the trunk, branches, and other organs above ground, and the underground part encompassing the entire root system. In both cases, studying the architecture raises various questions concerning tree geometry, the genes involved in tree development and variation, and the successive states of the tree. By addressing these questions, understanding the architecture of fruit trees can contribute to the improvement of varieties and their production. Hence, several techniques have been developed to measure tree organs and model their architecture and shape. Initially, this task required a group of human operators to physically measure these objects directly in the field. However, this approach is time-consuming and demands extensive observation. Over the past few decades, the advent of new sensors such as cameras and LiDAR (Light Detection and Ranging) has facilitated the acquisition of digital representations of trees, opening up new possibilities for study. The objective of this thesis is to obtain architectural metrics that provide an overall perspective of the tree’s geometry, followed by a more precise approximation at the organ level. These metrics were based on the processing of point clouds obtained from terrestrial and aerial LiDAR in an apple orchard including a collection of genotypes. The point clouds were processed by developing two pipelines utilizing various filtering, machine learning, and deep learning algorithms.Face aux effets du changement climatique, à l’augmentation de la population et à la nécessité d’assurer la sécurité alimentaire, la compréhension du développement des plantes est un élément essentiel des solutions. Cette étude vise à répondre à ces préoccupations urgentes. Pour entreprendre une telle étude, il est nécessaire d’explorer comment la variabilité génétique donne lieu à des ensembles spécifiques de caractéristiques architecturales. Dans le cas des arbres fruitiers qui seront le support de cette étude, la compréhension de ces variations architecturales facilite la régulation, la prédiction et l’assurance de la production. Elle permettra également de proposer des stratégies de gestion visant à maintenir la santé de l’arbre et à optimiser sa productivité.Les arbres fruitiers se composent généralement de deux parties : la partie supérieure,comprenant le tronc, les branches et les autres organes aériens, et la partie souterraine comprenant l’ensemble du système racinaire. Dans les deux cas, l’étude de l’architecture soulève diverses questions concernant la géométrie de l’arbre, les gènes impliqués dans son développement et ses variations, ainsi que les états successifs au cours de son ontogénie. En répondant à ces questions, la compréhension de l’architecture des arbres fruitiers peut contribuer à l’amélioration des variétés et de leur production. C’est pourquoi plusieurs techniques ont été développées pour mesurer les organes de l’arbre et modéliser leur architecture, incluant leur topologie et leur forme. Initialement, cette tâche nécessitait un groupe d’opérateurs humains pour mesurer physiquement ces objets directement sur le terrain. Cependant, cette approche prend beaucoup de temps et nécessite des observations approfondies. Au cours des dernières décennies, l’avènement de nouveaux capteurs tels que les caméras et le LiDAR (Light Detection and Ranging) a facilitél’acquisition de représentations numériques des arbres, ouvrant ainsi de nouvelles possibilités d’étude. L’objectif de cette thèse est d’obtenir des descripteurs de l’architecture donnant une charactérisation globale de la géométrie de l’arbre, puis une approximation plus précise au niveau des organes. Ces descripteurs ont été basées sur le traitement de nuages de points obtenus à partir de LiDAR terrestres et aériens dans un verger de pommiers contenant une collection de génotypes. Les nuages de points ont été traités en développant deux pipelines utilisant divers algorithmes de filtrage, d’apprentissage automatique et d’apprentissage profond
End-Effectors Changer Design for Humanoids
No full textInternational audienceAlmost all (not to say all) existing humanoids have not been designed with the ability to change their endeffectors (head, feet and hands) on-the-fly. Inspired by the toolchanging mechanisms in robotics automation and manufacturing, we propose an end-effectors changer mechanism suitable to humanoids. This letter explains why enabling humanoids with such a technology is important and why existing tool-changer mechanisms are not adapted. The proposed changer mechanism is not actuated. Yet, it does not require human intervention to assist the change of end-effectors. We assess our mechanism through a comparative study with existing tool-changers and demonstrations with the HRP-4 humanoid. We claim that our idea could be a new turn in the design of future humanoids and open perspective to modular sizing of robots. The proposed mechanism can possibly apply to animaloids to some extent
Finite Groundings for ASP with Functions: A Journey through Consistency
No full textInternational audienceAnswer set programming (ASP) is a logic programming formalism used in various areas of artificial intelligence like combinatorial problem solving and knowledge representation and reasoning. It is known that enhancing ASP with function symbols makes basic reasoning problems highly undecidable. However, even in simple cases, state of the art reasoners, specifically those relying on a ground-and-solve approach, fail to produce a result. Therefore, we reconsider consistency as a basic reasoning problem for ASP. We show reductions that give an intuition for the high level of undecidability. These insights allow for a more fine-grained analysis where we characterize ASP programs as "frugal" and "non-proliferous". For such programs, we are not only able to semi-decide consistency but we also propose a grounding procedure that yields finite groundings on more ASP programs with the concept of "forbidden" facts