Cette thèse porte sur la résolution séquentielle et parallèle du problème de la satisfiabilité propositionnelle(SAT). Ce problème important sur le plan théorique admet de nombreuses applications qui vont de la vérification formelle de matériels et de logiciels à la cryptographie en passant par la planification et la bioinformatique. Plusieurs contributions sont apportées dans cette thèse. La première concerne l’étude et l’intégration des concepts d’intensification et de diversification dans les solveurs SAT parallèle de type portfolio. Notre seconde contribution exploite l’état courant de la recherche partiellement décrit par les récentes polarités des littéraux « progress saving », pour ajuster et diriger dynamiquement les solveurs associés aux différentes unités de calcul. Dans la troisième contribution, nous proposons des améliorations de la stratégie de réduction de labase des clauses apprises. Deux nouveaux critères, permettant d’identifier les clauses pertinentes pour la suite de la recherche, ont été proposés. Ces critères sont utilisés ensuite comme paramètre supplémentaire de diversification dans les solveurs de type portfolio. Finalement, nous présentons une nouvelle approche de type diviser pour régner où la division s’effectue par ajout de contraintes particulières. / In this thesis, we deal with the sequential and parallel resolution of the problem SAT. Despite of its complexity, the resolution of SAT problem is an excellent and competitive approach for solving thecombinatorial problems such as the formal verification of hardware and software, the cryptography, theplanning and the bioinfomatics. Several contribution are made in this thesis. The first contribution aims to find the compromise of diversification and intensification in the solver of type portfolio. In our second contribution, we propose to dynamically adjust the configuration of a core in a portfolio parallel sat solver when it is determined that another core performs similar work. In the third contribution, we improve the strategy of reduction of the base of learnt clauses, we construct a portfolio strategy of reduction in parallel solver. Finally, we present a new approach named "Virtual Control" which is to distribute the additional constraints to each core in a parallel solver and verify their consistency during search.

L’évolution des supercalculateurs est à la source de défis logiciels et architecturaux. Dans la quête de puissance de calcul, l’interdépendance des éléments du processus de simulation devient de plus en plus impactante et requiert de nouvelles approches. Cette thèse se concentre sur le développement logiciel et particulièrement sur l’observation des programmes parallèles s’exécutant sur des milliers de cœurs. Dans ce but, nous décrivons d’abord le processus de développement de manière globale avant de présenter les outils existants et les travaux associés. Dans un second temps, nous détaillons notre contribution qui consiste d’une part en des outils de débogage et profilage par prise de traces, et d’autre part en leur évolution vers un couplage en ligne qui palie les limitations d’entrées–sorties. Notre contribution couvre également la synchronisation des horloges pour la prise de traces avec la présentation d’un algorithme de synchronisation probabiliste dont nous avons quantifié l’erreur. En outre, nous décrivons un outil de caractérisation machine qui couvre l’aspect MPI. Un tel outil met en évidence la présence de bruit aussi bien sur les communications de type point-à-point que de type collective. Enfin, nous proposons et motivons une alternative à la collecte d’événements par prise de traces tout en préservant la granularité des événements et un impact réduit sur les performances, tant sur le volet utilisation CPU que sur les entrées–sorties / Supercomputers’ evolution is at the source of both hardware and software challenges. In the quest for the highest computing power, the interdependence in-between simulation components is becoming more and more impacting, requiring new approaches. This thesis is focused on the software development aspect and particularly on the observation of parallel software when being run on several thousand cores. This observation aims at providing developers with the necessary feedback when running a program on an execution substrate which has not been modeled yet because of its complexity. In this purpose, we firstly introduce the development process from a global point of view, before describing developer tools and related work. In a second time, we present our contribution which consists in a trace based profiling and debugging tool and its evolution towards an on-line coupling method which as we will show is more scalable as it overcomes IOs limitations. Our contribution also covers our time-stamp synchronisation algorithm for tracing purposes which relies on a probabilistic approach with quantified error. We also present a tool allowing machine characterisation from the MPI aspect and demonstrate the presence of machine noise for both point to point and collectives, justifying the use of an empirical approach. In summary, this work proposes and motivates an alternative approach to trace based event collection while preserving event granularity and a reduced overhead

La modélisation des problèmes multi-domaine est abordée dans un cadre purement Eulérien. Un maillage unique, ne représentant plus la matière, est utilisé. Les différentes frontières et leur évolution sont décrites via des outils numériques tels que la méthode Level Set. Les caractéristiques locales de chaque sous domaines sont déterminées par des lois de mélange.Ce travail est une des premières tentations appliquant une approche Eulérienne pour modéliser de problèmes de grandes déformations. Dans un premier temps, la capacité de l'approche est testée afin de déterminer les développements nécessaires.Le frottement entre les différents objets est géré par un lubrifiant ajouté dans une couche limite. Combinée avec une technique d'identification, une nouvelle loi de mélange quadratique est introduite pour décrire la viscosité du lubrifiant. Des comparaisons ont été effectuées avec Forge® et les résultats sont trouvés satisfaisants. Pour traiter le contact entre les différents objets, un solveur directionnel a été développé. Malgré que les résultats soient intéressants, il reste le sujet de nouvelles améliorations. La scalabilité de l'approche dans un environnement massivement parallèle est testée aussi. Plusieurs recommandations ont été proposées pour s'assurer d'une performance optimale. La technique du maillage unique permet d'obtenir une très bonne scalabilité. L'efficacité du parallélisme ne dépend que de la partition d'un seul maillage (contrairement aux méthodes Lagrangiennes). La méthode proposée présente des capacités indéniables mais reste loin d'être complète. Des pistes d'amélioration sont proposées en conséquence. / Modeling of multi-domain problems is addressed in a Purely Eulerian framework. A single mesh is used all over the domain. The evolution of the different interacting bodies is described using numerical tools such as the Level Set method. The characteristics of the subdomains, considered as heterogeneities in the mesh, are determined using mixture laws.This work is one of the first attempts applying fully Eulerian Approach to Model large deformation problems. Therefore, the capacity of this approach is tested to determine necessary developments. The friction between the different objects is managed by adding a boundary layer implying the presence of a lubricant. Combined with an identification technique, a new quadratic mixture Law is introduced to determine the lubricant viscosity. Comparisons have been performed with Forge® and results were found satisfactory. To treat the contact problem between the different objects, a directional solver was developed. Despite the interesting results, it remains the topic of further improvements. The scalability of the approach in a massively parallel environment is tested as well. Several recommendations were proposed to ensure an optimal performance. The technique of a single mesh guarantees a very good scalability since the efficiency of parallelism depends of the partition of a single mesh (unlike the Lagrangian Methods). The proposed method presents undeniable capacities but remains far from being complete. Ideas for future Improvements are proposed accordingly.

Cette thèse est une contribution à la problématique de la simulation d'événements rares. A partir de l'étude des méthodes de Splitting, un nouveau cadre théorique est développé, indépendant de tout algorithme. Ce cadre, basé sur la définition d'un processus ponctuel associé à toute variable aléatoire réelle, permet de définir des estimateurs de probabilités, quantiles et moments sans aucune hypothèse sur la variable aléatoire. Le caractère artificiel du Splitting (sélection de seuils) disparaît et l'estimateur de la probabilité de dépasser un seuil est en fait un estimateur de la fonction de répartition jusqu'au seuil considéré. De plus, les estimateurs sont basés sur des processus ponctuels indépendants et identiquement distribués et permettent donc l'utilisation de machine de calcul massivement parallèle. Des algorithmes pratiques sont ainsi également proposés.Enfin l'utilisation de métamodèles est parfois nécessaire à cause d'un temps de calcul toujours trop important. Le cas de la modélisation par processus aléatoire est abordé. L'approche par processus ponctuel permet une estimation simplifiée de l'espérance et de la variance conditionnelles de la variable aléaoire résultante et définit un nouveau critère d'enrichissement SUR adapté aux événements rares / This thesis address the issue of extreme event simulation. From a original understanding of the Splitting methods, a new theoretical framework is proposed, regardless of any algorithm. This framework is based on a point process associated with any real-valued random variable and lets defined probability, quantile and moment estimators without any hypothesis on this random variable. The artificial selection of threshold in Splitting vanishes and the estimator of the probability of exceeding a threshold is indeed an estimator of the whole cumulative distribution function until the given threshold. These estimators are based on the simulation of independent and identically distributed replicas of the point process. So they allow for the use of massively parallel computer cluster. Suitable practical algorithms are thus proposed.Finally it can happen that these advanced statistics still require too much samples. In this context the computer code is considered as a random process with known distribution. The point process framework lets handle this additional source of uncertainty and estimate easily the conditional expectation and variance of the resulting random variable. It also defines new SUR enrichment criteria designed for extreme event probability estimation.

L’IRM à ultra haut champ (UHC) donne accès à une résolution spatiale submillimétrique rendant possible la visualisation de structures plus fines qu’en IRM classique. Depuis quelques années, son potentiel s’est développé dans des laboratoires tels que NeuroSpin, au sein du CEA, qui a l’ambition d’étudier l’anatomie et le fonctionnement du cerveau à une échelle mésoscopique. Toutefois, pour des champs magnétiques supérieurs à 3T, le champ radiofréquence (RF) permettant d’exciter les protons de l’eau a une longueur d’onde inférieure à la dimension de la tête humaine, provoquant des phénomènes d’interférences destructives dans le cerveau. Ceux-ci s’accentuent avec l’augmentation du champ statique, engendrant sur les images des inhomogénéités de signal ou de contraste, qui empêchent d’exploiter tout le potentiel de l’imagerie UHC. Pour améliorer la pertinence des diagnostics cliniques, à défaut de pouvoir homogénéiser le champ RF dans tout le cerveau, il est essentiel de réussir à uniformiser l’excitation des spins. Dans ce but, un système de transmission parallèle (pTx) à 8 canaux a été intégré à l’imageur 7T du laboratoire. Il permet d’émettre sur chaque canal des formes d’impulsions RF différentes, à optimiser pour faire interférer le champ RF produit dans le cerveau de manière plus contrôlée que dans le mode classique à un seul canal d’émission. Ces travaux de thèse consistent à mettre au point des impulsions RF utilisant la pTx pour sélectionner des tranches d’excitation uniforme, et à les appliquer à l’angiographie du cerveau humain à 7T. A UHC, la méthode la plus courante pour homogénéiser l’angle de bascule de l’aimantation dans une coupe consiste à générer consécutivement plusieurs impulsions sélectives optimisées, appelées « spokes », à différentes positions du plan transverse à la coupe dans l’espace de Fourier de transmission. Si elle convient pour uniformiser l’excitation dans le plan de coupe, cette méthode est moins performante pour la sélection de larges tranches car les inhomogénéités de champ RF ne sont alors pas prises en compte dans l’épaisseur de tranche. Ainsi, dans un premier temps, deux méthodes originales de conception d’impulsions RF sélectives sont introduites et explorées pour uniformiser l’excitation de larges tranches : celle des « kT-spokes » qui optimise le placement des spokes dans les 3 dimensions de l’espace de Fourier de transmission, et celle des « spokes 3D » qui génère des impulsions RF optimisées point par point dans le temps. Ces techniques ont été validées avec succès sur des fantômes à 7T et ont permis de surpasser l’état de l’art en termes d’homogénéisation de l’angle de bascule pour la sélection de larges tranches. Dans un deuxième temps, ces méthodes ont été appliquées à la séquence d’angiographie 3D en temps de vol afin d’améliorer la visualisation du réseau artériel dans le cerveau humain à 7T. Cependant, lorsque les tranches sélectionnées sont larges, cette séquence est aussi sensible aux effets de saturation du sang qui empêchent d’apprécier la totalité du réseau artériel avec les profils de tranche d’angles de bascule plats habituels. Pour corriger ce phénomène, les impulsions RF à rampes sont proposées dans l’état de l’art, générant des profils d’angle de bascule qui augmentent avec l’épaisseur de la tranche. Les méthodes de conception d’impulsions RF développées ici ont ainsi été adaptées pour générer ce type de profils et permettre de compenser la saturation du sang avec succès dans les acquisitions à 7T. Ces travaux de thèse ont permis d’ouvrir la voie à une nouvelle application à NeuroSpin puisque l’angiographie n’y avait pas encore été explorée malgré le fort potentiel des UHC pour cette modalité. En outre, les méthodes développées au cours de ces travaux permettent l’excitation simultanée de tranches homogènes, constituant ainsi une perspective prometteuse pour accélérer les acquisitions et repousser les limites de résolution spatiale de l’angiographie en temps de vol à 7T. / Ultra-high field (UHF) MRI allows submillimetric spatial resolution in order to depict finer structures compared to conventional MRI. In recent years, the UHF potential has been explored in laboratories such as NeuroSpin, at Commissariat à l’Énergie Atomique et aux Énergies Alternatives (CEA), to study brain anatomy and function at a mesoscopic scale. However, for high magnetic field strengths (> 3 Tesla), the radiofrequency (RF) field required to excite the water protons has a wavelength shorter than the size of the human head, causing destructive interferences in the brain. These increase with the static field strength leading to signal or contrast inhomogeneity artefacts on brain images, hindering the UHF benefits. However, failing to homogenize the RF field produced in the brain does not preclude from homogenizing the spin excitation to improve image quality and perform better clinical diagnosis. For this purpose, NeuroSpin’s 7T scanner has been equipped with an 8-channel parallel transmission system allowing to transmit independent optimized RF shapes on each channel in order to better control RF field interferences than in conventional single transmit channel. This thesis work focuses on RF pulse design strategies using parallel transmission to select slabs uniformly and on their applications to magnetic resonance angiography (MRA) of the human brain at 7T. In the UHF context, the most common method to homogenize the magnetization flip angle in a slice consists in combining several consecutive optimized selective excitations, so-called “spokes” subpulses, in different locations of the plane transverse to the slice in transmit k-space. Even though this method succeeds in homogenizing the in-plane excitation, its performance is not optimal in large slabs because through-slab RF inhomogeneities are not taken into account. In a first step, two original selective pulse design methods are introduced and explored to homogenize large slab selections: the “kT-spoke” method which optimizes the spoke placements in the three dimensions of the transmit k-space, and the “3D spokes” which consist in optimizing the RF subpulses point by point in time. These methods have been successfully validated in phantoms at 7T and surpassed the state of the art performance in terms of flip angle homogeneity in large slab selections. In a second step, these methods are applied to 3D Time-Of-Flight (TOF) MR angiography to improve the visualization of the arterial network in the human brain at 7T. As most MRI sequences, TOF is particularly sensitive to RF field heterogeneities. Moreover, for large uniform slab excitation, blood saturation effects prevent the depiction of the arterial network before slab exit. To correct for these effects, ramp RF pulses are proposed in the state-of-the-art, generating ascending flip angle profiles through the slab. The RF pulse design methods developed hereby were adapted to generate these profiles, successfully compensating blood saturation in 7T acquisitions. This work paves the way to a new clinical application at NeuroSpin, where MR angiography had not been explored yet, despite the high benefit of UHF for this modality. In addition, the methods developed hereby were also adapted for simultaneous multi-slice excitations. This allows promising perspectives to accelerate acquisitions and push further away the limits of TOF angiography in terms of spatial resolution.

Ces travaux, initiés par le CNES (Centre National d’Etudes Spatiales) dans le cadre du programme de recherche ATAC (Aérodynamique Tuyères et Arrières-Corps), sont principalement consacrés au développement et à la validation de modèles numériques et physiques, pour la prédiction des charges latérales dans les moteurs-fusées. En effet, les systèmes propulsifs mettent en jeu des phénomènes physiques très complexes : mélange turbulent, compressibilité forte (interaction choc/turbulence, couplage de modes vorticité/entropie/acoustique), structures cohérentes et organisations tourbillonnaires dans le cas tridimensionnel, décollements massifs et instabilités à grande échelle. L’analyse de ces phénomènes nécessite le recourt à des modélisations de plus en plus fines basées sur des simulations numériques avancées. Pour faire face au coût prohibitif des simulations directes (ou simulations LES résolues) des couches limites, un nouveau modèle de paroi a été développé, en se basant sur les propriétés d’auto similarité des couches limites compressibles en tuyères supersoniques, et en utilisant des lois de renormalisation dérivées à partir d’une base de données tabulée. Ce modèle permet de prendre en compte la dynamique de l’écoulement tout en réduisant considérablement le nombre de points de calcul et le pas de temps requis pour les simulations LES. Les résultats de calcul mettent en évidence de nombreuses interactions complexes au sein de l’écoulement. En particulier, les interactions amont/aval (supersonique/subsonique),influençant fortement le décollement et la structure de chocs, à l’origine de l’apparition de pics énergétiques associés à des perturbations acoustiques conduisent à l’apparition,par rétroaction, de phénomènes d’instabilités convectives, couplées à des modes globaux dissymétriques en dynamique absolue. Ces phénomènes auto-entretenus sont synonymes d’efforts latéraux et sont représentatifs des expériences menées en laboratoire et sur bancs d’essai moteurs-fusées. En terme d’optimisation des calculs massivement parallèles, une méthode originale, appelée « Drop-Procs », a été développée dans le cadre des frontières immergées. Cette méthode, adaptée aux architectures de calculs intensifs Tier-0, permet une réduction notable du temps CPU (Central Processing Unit), allant jusqu’à 50%, et rendant ainsi ce type de simulations plus accessible à l’échelle industrielle. / This work, initiated by the CNES (Centre National d’Etudes Spatiales) in the ATAC research program (Aérodynamique Tuyères et Arrières-Corps), is devoted to the development and the validation of numerical and physical models for the prediction of side-loads in rocket engines. Indeed, propulsion systems involve complex physical phenomena : turbulent mixing, high compressibility (interaction shock / turbulence, coupling modes vorticity / entropy / acoustic), coherent structure, three-dimensional vortex organizations, massive detachment and large scale instabilities. The analysis of these phenomena requires the uses of advanced numerical simulations. To deal with the high cost of large-eddy simulations boundary layers, a new wall model, based on renormalization laws and a database, was developed. This model allows to take into account the dynamics of the flow while significantly reducing the number of calculation points and the time step required for LES simulations. Results show many complex interactions with in the flow. In particular, the upstream / downstream interactions (supersonic / subsonic), strongly influence the separation and the shock structure, causing the occurrence of energy peaks associated with acoustic disturbances and leading to the appearance of convective instability, coupled with global asymmetric modes. These self-sustained phenomena are synonymous of side-loads and are representative of laboratory experiments and rocket engine test benches. In terms of optimization of massively parallel computing, a new method, called "Drop-Procs", was developed as part of the immersed boundaries. This method is suitable for compute-intensive architectures Tier-0 and allows a significant reduction in CPU time (Central Processing Unit) consumption, up to 50%, making this type of simulation accessible for industrials.

La vision par ordinateur est primordiale pour la compréhension et l’analyse d’une scène routière afin de construire des systèmes d’aide à la conduite (ADAS) plus intelligents. Cependant, l’implémentation de ces systèmes dans un réel environnement automobile et loin d’être simple. En effet, ces applications nécessitent une haute performance de calcul en plus d’une précision algorithmique. Pour répondre à ces exigences, de nouvelles architectures hétérogènes sont apparues. Elles sont composées de plusieurs unités de traitement avec différentes technologies de calcul parallèle: GPU, accélérateurs dédiés, etc. Pour mieux exploiter les performances de ces architectures, différents langages sont nécessaires en fonction du modèle d’exécution parallèle. Dans cette thèse, nous étudions diverses méthodologies de programmation parallèle. Nous utilisons une étude de cas complexe basée sur la stéréo-vision. Nous présentons les caractéristiques et les limites de chaque approche. Nous évaluons ensuite les outils employés principalement en terme de performances de calcul et de difficulté de programmation. Le retour de ce travail de recherche est crucial pour le développement de futurs algorithmes de traitement d’images en adéquation avec les architectures parallèles avec un meilleur compromis entre les performances de calcul, la précision algorithmique et la difficulté de programmation. / Computer Vision (CV) is crucial for understanding and analyzing the driving scene to build more intelligent Advanced Driver Assistance Systems (ADAS). However, implementing CV-based ADAS in a real automotive environment is not straightforward. Indeed, CV algorithms combine the challenges of high computing performance and algorithm accuracy. To respond to these requirements, new heterogeneous circuits are developed. They consist of several processing units with different parallel computing technologies as GPU, dedicated accelerators, etc. To better exploit the performances of such architectures, different languages are required depending on the underlying parallel execution model. In this work, we investigate various parallel programming methodologies based on a complex case study of stereo vision. We introduce the relevant features and limitations of each approach. We evaluate the employed programming tools mainly in terms of computation performances and programming productivity. The feedback of this research is crucial for the development of future CV algorithms in adequacy with parallel architectures with a best compromise between computing performance, algorithm accuracy and programming efforts.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.