L’émergence des systèmes embarqués a permis le développement des réseaux de capteurs sans fil dans de nombreux domaines différents. Cependant, la sécurité reste un problème ouvert. La vulnérabilité des nœuds est principalement liée au manque de ressources. En effet, l’unité de traitement ne dispose pas d’assez de puissance et de mémoire pour gérer des mécanismes de sécurité très complexes.La cryptographie est une solution qui est largement utilisée pour sécuriser les réseaux. Par rapport à la cryptographie symétrique, la cryptographie asymétrique nécessite des calculs plus compliqués,mais elle offre une distribution de clés plus sophistiquée et la signature numérique. Dans cette thèse, nous essayons d’optimiser la performance d’ECC (Elliptic Curve Cryptography), un cryptosystème asymétrique qui est connu pour sa robustesse et son utilisation de clé plus courte par rapport à RSA. Nous proposons d’utiliser le parallélisme pour accélérer le calcul de la multiplication scalaire, qui est reconnue comme l’opération la plus coûteuse sur les courbes elliptiques. Les résultats de tests ont montré que notre solution offre un gain intéressant malgré une augmentation de la consommation d’énergie.La deuxième partie de la contribution concerne l’application de la tolérance aux pannes dans notre architecture de parallélisation. Nous utilisons les nœuds redondants pour la détection des pannes et la restauration du calcul. Ainsi, en utilisant l’ECC et la tolérance aux pannes, nous proposons une solution de sécurité efficace et sûre pour les systèmes embarqués. / The emergence of embedded systems has enabled the development of wireless sensor networks indifferent domains. However, the security remains an open problem. The vulnerability of sensor nodesis mainly due to the lack of resources. In fact, the processing unit doesn’t have enough power ormemory to handle complex security mechanisms.Cryptography is a widely used solution to secure networks. Compared with symmetric cryptography,the asymmetric cryptography requires more complicated computations, but it offers moresophisticated key distribution schemes and digital signature.In this thesis, we try to optimize the performance of ECC. An asymmetric cryptosystem which isknown for its robustness and the use of shorter keys than RSA. We propose to use parallelismtechniques to accelerate the computation of scalar multiplications, which is recognized as the mostcomputationally expensive operation on elliptic curves. The test results have shown that our solutionprovides a significant gain despite an increase in energy consumption.The 2nd part of our contribution is the application of fault tolerance in our parallelism architecture.We use redundant nodes for fault detection and computation recovery. Thus, by using ECC and faulttolerance, we propose an efficient and reliable security solution for embedded systems.

Aujourd'hui, philosophes et hommes de sciences se trouvent d'accord pour affirmer que le mécanisme n'a plus cours. Or, il hante toujours les esprits. Donc, il est toujours important d'essayer de comprendre son projet. En menant une étude actuelle du mécanisme dans laquelle on estime que l'idée du mécanisme était donnée dès le départ, on peut se demander si le mécanisme est à la fois une théorie scientifique au sens fort du terme et une philosophie authentique ou bien s'il est l'une sans être l'autre ou encore s'il n'est ni l'une ni l'autre. D'un côté, il apparaît que le mécanisme classique est une théorie scientifique au sens strict, celle de la mécanique, mais, étendu aux systèmes ouverts, il est une théorie scientifique au sens distendu - sens entretenu par l'effet de parallélismes idéologiques - ; et de l'autre, il s'avère que le mécanisme est une philosophie sans un contenu original sans doute, mais très spécifique. Qu'on ne voie pas de contradiction entre l'affirmation suivant laquelle le mécanisme est une théorie scientifique et celle d'après laquelle le mécanisme est une philosophie. Avec le mécanisme, on est comme dans un clair-obscur où on a l'impression que les extrêmes se touchent. La philosophie mécaniciste, quant à elle, où serait-elle ? Dans ce clair-obscur et ailleurs ! / Philosophers and scientists these days agree to the view that mechanism has become a thing of the past. Yet, there remains a lingering doubt about it. That's why it is important to try and assess its scope. By way of investigating mechanism today, taking the notion for granted, one may wonder whether mechanism is both, strictly speaking, a theory and a genuine philosophy. It may also be the one thing and not the other, or neither one thing nor the other. On the one hand, it appears that classic mechanism is a scientific theory in its own right. Yet, once it is extended to open systems, it becomes a laxer form of scientific theory, the meaning of which subsides through a network of ideological parallels. On the other hand, it appears that mechanism is a philosophy of its own, though it does not obviously pioneer any new ground. There is no contradiction in terms between the facts that some may argue that mechanism is a scientific theory, while others may claim that it is a philosophy. With mechanism, one is sailing in troubled waters and may have the feeling opposites meet. As for the mechanist philosophy, where might it lay? Well, somewhere in those troubled waters and elsewhere !

Pour répondre à des impératifs croissants de fiabilité et de sûreté, les procédés mis en œuvre dans le cadre du contrôle non destructif sont en constante évolution. Au vu de la complexité des techniques utilisées, la simulation prend une part importante dans leur développement. Nous présentons des travaux ayant abouti à un outil rapide de simulation du champ émis par un traducteur ultrasonore plan quelconque dans des configurations complexes de contrôle non destructif impliquant des géométries maillées sans arêtes saillantes, des matériaux isotropes ou anistropes, homogènes ou hétérogènes et des trajectoires d'ondes pouvant comporter des rebonds et des transmissions. Les fronts d'ondes ultrasonores sont approximés à l'aide d'interpolateurs polynomiaux locaux à des pinceaux de rayons ultrasonores. Ceux-ci sont obtenus au moyen d'un algorithme de recherche de surface par lancer de pinceaux et subdivisions successives. Ils permettent le calcul des grandeurs utiles à la constitution de la réponse impulsionnelle en chaque point d'un échantillonnage du traducteur respectant le critère de Shannon. De cette façon, nous pouvons calculer une réponse impulsionnelle qui, convoluée au signal d'excitation du traducteur, donne le champ ultrasonore. Les performances des simulations ont été accrues par l'exploitation du parallélisme de tâches et des instructions SIMD dans les parties les plus coûteuses du calcul. Enfin, un outil de calcul progressif continu a été développé pour permettre une visualisation interactive d'images de champ. Il exploite une méthode de reconstruction d'images et ordonnance les calculs de champ de manière à accélérer la convergence des images produites / In order to fulfill increasing reliability and safety requirements, non destructive testing techniques are constantly evolving and so does their complexity. Consequently, simulation is an essential part of their design. We developed a tool for the simulation of the ultrasonic field radiated by any planar probes into non destructive testing configurations involving meshed geometries without prominent edges, isotropic and anisotropic, homogeneous and heterogeneous materials, and wave trajectories that can include reflections and transmissions. We approximate the ultrasonic wavefronts by using polynomial interpolators that are local to ultrasonic ray pencils. They are obtained using a surface research algorithm based on pencil tracing and successive subdivisions. Their interpolators enable the computation of the necessary quantities for the impulse response computation on each point of a sampling of the transducer surface that fulfills the Shannon criterion. By doing so, we can compute a global impulse response which, when convoluted with the excitation signal of the transducer, results in the ultrasonic field. The usage of task parallelism and of SIMD instructions on the most computationally expensive steps yields an important performance boost. Finally, we developed a tool for progressive visualization of field images. It benefits from an image reconstruction technique and schedules field computations in order to accelerate convergence towards the final image

Les méthodes de décomposition de domaine en espace ont prouvé leur utilité dans le cadre des architectures parallèles. Pour les problèmes d’évolution en temps, il est nécessaire d’introduire une dimension supplémentaire de parallélisme dans la direction du temps. Ceci peut alors être couplé avec des méthodes de type optimisé Schwarz waveform relaxation. Nous nous intéressons dans cette thèse aux méthodes directes de décomposition en temps. Nous en étudions particulièrement deux. Dans une première partie nous étudions la méthode de produit tensoriel, introduite par R. E. Lynch, J. R. Rice, et D. H. Thomas in 1963. Nous proposons une méthode d’optimisation des pas de temps, basée sur une étude d’erreur en variable de Fourier en temps. Nous menons cette étude sur les schémas d’Euler et de Newmark pour la discrétisation en temps de l’équation de la chaleur. Nous présentons ensuite des tests numériques établissant la validité de cette approche. Dans la seconde partie, nous étudions les méthodes dites de Bloc, introduites par Amodio et Brugnano en 1997. Nous comparons diverses implémentations de la méthode, basées sur différentes approximations de l’exponentielle de matrice. Nous traitons l’équation de la chaleur et l’équation des ondes, et montrons par une étude numérique bidimensionnelle la puissance de la méthode. / Domain decomposition methods in space applied to Partial Differential Equations (PDEs) expanded considerably thanks to their effectiveness (memory costs, calculation costs, better local conditioned problems) and this related to the development of massively parallel machines. Domain decomposition in space-time brings an extra dimension to this optimization. In this work, we study two different direct time-parallel methods for the resolution of Partial Differential Equations. The first part of this work is devoted to the Tensor-product space-time method introduced by R.E. Lynch, J. R. Rice, and D. H. Thomas in 1963. We analyze it in depth for Euler and Crank-Nicolson schemes in time applied to the heat equation. The method needs all time steps to be different, while accuracy is optimal when they are all equal (in the Euler case). Furthermore, when they are close to each other, the condition number of the linear problems involved becomes very big. We thus give for each scheme an algorithm to compute optimal time steps, and present numerical evidences of the quality of the method. The second part of this work deals with the numerical implementation of the Block method of Amodio and Brugnano presented in 1997 to solve the heat equation with Euler and Crank- Nicolson time schemes and the elasticity equation with Euler and Gear time schemes. Our implementation shows how the method is accurate and scalable.

Le besoin croissant en simulation a conduit à l’élaboration de supercalculateurs complexes et d’un nombre croissant de logiciels hautement parallèles. Ces supercalculateurs requièrent un rendement énergétique et une puissance de calcul de plus en plus importants. Les récentes évolutions matérielles consistent à augmenter le nombre de noeuds de calcul et de coeurs par noeud. Certaines ressources n’évoluent cependant pas à la même vitesse. La multiplication des coeurs de calcul implique une diminution de la mémoire par coeur, plus de trafic de données, un protocole de cohérence plus coûteux et requiert d’avantage de parallélisme. De nombreuses applications et modèles actuels peinent ainsi à s’adapter à ces nouvelles tendances. En particulier, générer du parallélisme massif dans des méthodes d’éléments finis utilisant des maillages non structurés, et ce avec un nombre minimal de synchronisations et des charges de travail équilibrées, s’avèrent particulièrement difficile. Afin d’exploiter efficacement les multiples niveaux de parallélisme des architectures actuelles, différentes approches parallèles doivent être combinées. Cette thèse propose plusieurs contributions destinées à paralléliser les codes et les structures irrégulières de manière efficace. Nous avons développé une approche parallèle hybride par tâches à grain fin combinant les formes de parallélisme distribuée, partagée et vectorielle sur des structures irrégulières. Notre approche a été portée sur plusieurs applications industrielles développées par Dassault Aviation et a permis d’importants gains de performance à la fois sur les multicoeurs classiques ainsi que sur le récent Intel Xeon Phi. / The growing need for numerical simulations results in larger and more complex computing centers and more HPC softwares. Actual HPC system architectures have an increasing requirement for energy efficiency and performance. Recent advances in hardware design result in an increasing number of nodes and an increasing number of cores per node. However, some resources do not scale at the same rate. The increasing number of cores and parallel units implies a lower memory per core, higher requirement for concurrency, higher coherency traffic, and higher cost for coherency protocol. Most of the applications and runtimes currently in use struggle to scale with the present trend. In the context of finite element methods, exposing massive parallelism on unstructured mesh computations with efficient load balancing and minimal synchronizations is challenging. To make efficient use of these architectures, several parallelization strategies have to be combined together to exploit the multiple levels of parallelism. This P.h.D. thesis proposes several contributions aimed at overpassing this limitation by addressing irregular codes and data structures in an efficient way. We developed a hybrid parallelization approach combining the distributed, shared, and vectorial forms of parallelism in a fine grain taskbased approach applied to irregular structures. Our approach has been ported to several industrial applications developed by Dassault Aviation and has led to important speedups using standard multicores and the Intel Xeon Phi manycore.

Les systèmes cyber-physiques mélangent des comportements physiques continus, tel la vitesse d'un véhicule, et des comportement discrets, tel que le régulateur de vitesse d'un véhicule. Ils sont désormais omniprésents dans notre société. Un grand nombre de ces systèmes sont dits critiques, i.e. une mauvaise conception entraînant un comportement non prévu, un bug, peut mettre en danger des êtres humains. Il est nécessaire de développer des méthodes pour garantir le bon fonctionnement de tels systèmes. Les méthodes formelles regroupent des procédés mathématiques pour garantir qu'un système se comporte comme attendu, par exemple que le régulateur de vitesse n'autorise pas de dépasser la vitesse maximale autorisée. De récents travaux ont permis des progrès significatifs dans ce domaine, mais l'approche adoptée est encore monolithique, i.e. que le système est modélisé d'un seul tenant et est ensuite soumis à la preuve. Notre problématique est comment modéliser efficacement des systèmes cyber-physiques dont la complexité réside dans une répétition de morceaux élémentaires. Et une fois que l'on a obtenu une modélisation, comment garantir le bon fonctionnement de tels systèmes. Notre approche consiste à modéliser le système de manière compositionnelle. Plutôt que de vouloir le modéliser d'un seul tenant, il faut le faire morceaux par morceaux, appelés composants. Chaque composant correspond à un sous-système du système final qu'il est simple de modéliser. On obtient le système complet en assemblant les composants ensembles. Ainsi une usine de traitement des eaux est obtenue en assemblant différentes cuves. L'intérêt de cette méthode est qu'elle correspond à l'approche des ingénieurs dans l'industrie : considérer des éléments séparés que l'on compose ensuite. Mais cette approche seule ne résout pas le problème de la preuve de bon fonctionnement du système. Il faut aussi rendre la preuve compositionnelle. Pour cela, on associe à chaque composant des propriétés sur ses entrées et sortie, et on prouve qu'elles sont respectées. Cette preuve peut être effectué par un expert, mais aussi par un ordinateur si les composants sont de tailles raisonnables. Il faut ensuite nous assurer que lors de l'assemblage des composants, les propriétés continuent à être respectées. Ainsi, la charge de la preuve est reportée sur les composants élémentaires, l'assurance du respect des propriétés désirées est conservée lors des étapes de composition. On peut alors obtenir une preuve du bon fonctionnement de systèmes industriels avec un coût de preuve réduit. Notre contribution majeure est de proposer une telle approche compositionnelle à la fois pour modéliser des systèmes cyber-physiques, mais aussi pour prouver qu'ils respectent les propriétés voulues. Ainsi, à chaque étape de la conception, on s'assure que les propriétés sont conservées, si possible à l'aide d'un ordinateur. Le système résultant est correct par construction. De ce résultat, nous avons proposé plusieurs outils pour aider à la conception de systèmes cyber-physiques de manière modulaire. On peut raisonner sur les propriétés temporelles de tels systèmes, par exemple est-ce que le temps de réaction d'un contrôleur est suffisamment court pour garantir le bon fonctionnement. On peut aussi raisonner sur des systèmes où un mode nominal cohabite avec un mode d'urgence. / Cyber-physical systems mix continuous physical behaviors, e.g. the velocity of a vehicle, and discrete behaviors, e.g. the cruise-controller of the vehicle. They are pervasive in our society. Numerous of such systems are safety-critical, i.e. a design error which leads to an unexpected behavior can harm humans. It is mandatory to develop methods to ensure the correct functioning of such systems. Formal methods is a set of mathematical methods that are used to guarantee that a system behaves as expected, e.g. that the cruise-controller does not allow the vehicle to exceed the speed limit. Recent works have allowed significant progress in the domain of the verification of cyber-physical systems, but the approach is still monolithic. The system under consideration is modeled in one block. Our problematic is how to efficiently model cyber-physical systems where the complexity lies in a repetition of elementary blocks. And once this modeling done, how guaranteeing the correct functioning of such systems. Our approach is to model the system in a compositional manner. Rather than modeling it in one block, we model it pieces by pieces, called components. Each component correspond to a subsystem of the final system and are easier to model due to their reasonable size. We obtain the complete system by assembling the different components. A water-plant will thus be obtained by the composition of several water-tanks. The main advantage of this method is that it corresponds to the work-flow in the industry : consider each elements separately and compose them later. But this approach does not solve the problem of the proof of correct functioning of the system. We have to make the proof compositional too. To achieve it, we associate to each component properties on its inputs and outputs, then prove that they are satisfied. This step can be done by a domain expert, but also by a computer program if the component is of a reasonable size. We have then to ensure that the properties are preserved through the composition. Thus, the proof effort is reported to elementary components. It is possible to obtain a proof of the correct functioning of industrial systems with a reduced proof effort. Our main contribution is the development of such approach in Differential Dynamic Logic. We are able to modularly model cyber-physical systems, but also prove their correct functioning. Then, at each stage of the design, we can verify that the desired properties are still guaranteed. The resulting system is correct-by-construction. From this result, we have developed several tools to help for the modular reasoning on cyber-physical systems. We have proposed a methodology to reason on temporal properties, e.g. if the execution period of a controller is small enough to effectively regulate the continuous behavior. We have also showed how we can reason on functioning modes in our framework.

La simulation haute-fidélité des coeurs de réacteurs nucléaires nécessite une évaluation précise du flux neutronique dans le coeur du réacteur. Ce flux est modélisé par l’équation de Boltzmann ou équation du transport neutronique. Dans cette thèse, on s’intéresse à la résolution de cette équation par la méthode des ordonnées discrètes (SN) sur des géométries cartésiennes. Cette méthode fait intervenir un schéma d’itérations à source, incluant un algorithme de balayage sur le domaine spatial qui regroupe l’essentiel des calculs effectués. Compte tenu du très grand volume de calcul requis par la résolution de l’équation de Boltzmann, de nombreux travaux antérieurs ont été consacrés à l’utilisation du calcul parallèle pour la résolution de cette équation. Jusqu’ici, ces algorithmes de résolution parallèles de l’équation du transport neutronique ont été conçus en considérant la machine cible comme une collection de processeurs mono-coeurs indépendants, et ne tirent donc pas explicitement profit de la hiérarchie mémoire et du parallélisme multi-niveaux présents sur les super-calculateurs modernes. Ainsi, la première contribution de cette thèse concerne l’étude et la mise en oeuvre de l’algorithme de balayage sur les super-calculateurs massivement parallèles modernes. Notre approche combine à la fois la vectorisation par des techniques de la programmation générique en C++, et la programmation hybride par l’utilisation d’un support d’exécution à base de tâches: PaRSEC. Nous avons démontré l’intérêt de cette approche grâce à des modèles de performances théoriques, permettant également de prédire le partitionnement optimal. Par ailleurs, dans le cas de la simulation des milieux très diffusifs tels que le coeur d’un REP, la convergence du schéma d’itérations à source est très lente. Afin d’accélérer sa convergence, nous avons implémenté un nouvel algorithme (PDSA), adapté à notre implémentation hybride. La combinaison de ces techniques nous a permis de concevoir une version massivement parallèle du solveur SN Domino. Les performances de la partie Sweep du solveur atteignent 33.9% de la performance crête théorique d’un super-calculateur à 768 cores. De plus, un calcul critique d’un réacteur de type REP 900MW à 26 groupes d’énergie mettant en jeu 1012 DDLs a été résolu en 46 minutes sur 1536 coeurs. / High-fidelity nuclear reactor core simulations require a precise knowledge of the neutron flux inside the reactor core. This flux is modeled by the linear Boltzmann equation also called neutron transport equation. In this thesis, we focus on solving this equation using the discrete ordinates method (SN) on Cartesian mesh. This method involves a source iteration scheme including a sweep over the spatial mesh and gathering the vast majority of computations in the SN method. Due to the large amount of computations performed in the resolution of the Boltzmann equation, numerous research works were focused on the optimization of the time to solution by developing parallel algorithms for solving the transport equation. However, these algorithms were designed by considering a super-computer as a collection of independent cores, and therefore do not explicitly take into account the memory hierarchy and multi-level parallelism available inside modern super-computers. Therefore, we first proposed a strategy for designing an efficient parallel implementation of the sweep operation on modern architectures by combining the use of the SIMD paradigm thanks to C++ generic programming techniques and an emerging task-based runtime system: PaRSEC. We demonstrated the need for such an approach using theoretical performance models predicting optimal partitionings. Then we studied the challenge of converging the source iterations scheme in highly diffusive media such as the PWR cores. We have implemented and studied the convergence of a new acceleration scheme (PDSA) that naturally suits our Hybrid parallel implementation. The combination of all these techniques have enabled us to develop a massively parallel version of the SN Domino solver. It is capable of tackling the challenges posed by the neutron transport simulations and compares favorably with state-of-the-art solvers such as Denovo. The performance of the PaRSEC implementation of the sweep operation reaches 6.1 Tflop/s on 768 cores corresponding to 33.9% of the theoretical peak performance of this set of computational resources. For a typical 26-group PWR calculations involving 1.02×1012 DoFs, the time to solution required by the Domino solver is 46 min using 1536 cores.

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels.

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses.<br />Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion.<br />Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout en améliorant les algorithmes déjà existants en leur associant une phase de sélection des communications les plus utiles.<br />Concernant la phase de d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement Scotch.<br />Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre de l'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition.

Le travail a porté sur le développement d'une méthode de décomposition de domaine pour le calcul de structures électroniques avec les modèles de Hartree-Fock ou DFT (Density Functional Theory). La simulation de ces modèles passe traditionnellement par la résolution d'un problème aux valeurs propres généralisé, dont la complexité cubique est un verrou pour pouvoir traiter un grand nombre d'atomes. La méthode MDD (Multilevel Domain Decomposition), introduite au cours de la thèse de Maxime Barrault (2005), est une alternative à cette étape bloquante. Elle consiste à se ramener à un problème de minimisation sous contraintes où on peut exploiter les propriétés de localisation de la solution. Les résultats acquis au cours de la présente thèse sont :* l'analyse numérique de la méthode : on a montré, sur un problème simplifié présentant les mêmes difficultés mathématiques, un résultat de convergence locale de l'algorithme ; * l'augmentation de la vitesse de calcul et de la précision, pour les répartitions "1D" des sous-domaines, ainsi que la démonstration de la scalabilité jusqu'à $1000$ processeurs; * l'extension de l'algorithme et de l'implémentation aux cas où les sous-domaines sont répartis en "2D/3D".