Texte remanié de : Ph. D : Mathématiques : University of Chicago : 1999. / Notes bibliogr.

Cette thèse montre comment le calcul formel permet la manipulation d'une grande classe de suites et fonctions solutions d'opérateurs linéaires, la classe des fonctions holonomes. Celle-ci contient de nombreuses fonctions spéciales, en une ou plusieurs variables, et de nom- breuses suites de la combinatoire. Un cadre théorique est tout d'abord introduit pour algorith- miser les propriétés de clôture de la classe holonome, pour y permettre un test à zéro et pour unifier les calculs différentiels sur les fonctions et les calculs de récurrences sur les suites. Ces méthodes s'appuient sur des calculs par une extension de la théorie des bases de Gröbner dans un cadre de polynômes non commutatifs, les polynômes de Ore. Deux types d'algorithmes de sommation et d'intégration symboliques définies et indéfinies sont ensuite développés, dont la justification théorique fait appel à la théorie des D-modules holonomes. Les premiers ont recours à une élimination polynomiale non commutative par bases de Gröbner ; les seconds à des algo- rithmes de résolution de systèmes fonctionnels linéaires en leurs solutions fractions rationnelles. Bien plus que la recherche de formes closes, l'objectif est de pouvoir continuer à calculer avec la représentation implicite des objets holonomes même en l'absence de formes explicites. Ce type de calculs permet en particulier la preuve automatique d'identités sommatoires et intégrales. Une implantation de ces algorithmes dans le système de calcul formel Maple a permis de donner la première preuve automatique d'identités jusqu'à présent inaccessibles par le calcul formel.

Architectures reconfigurables dynamiquement offrent théoriquement excellent compromis entre performance et flexibilité. Pratiquement, ces architectures sont basées sur un ou plusieurs processeurs et plusieurs cellules reconfigurables. Une cellule reconfigurable peut charger, exécuter et décharger des accélérateurs matériels. Cette propriété permet la virtualisation des tâches matérielles. Dans ce contexte, une application peut prendre avantage de la flexibilité du logiciel et la performance du matériel. Dans les architectures reconfigurables actuels, les tâches matérielles sont limitées à une coopérative multi-tâches , depuis le temps de reconfiguration et l'heure de contexte stockage sont coûteux . Bien que le temps de reconfiguration est dépendante de l’architecture, le temps requis pour stocker ou restaurer le contexte dépend fortement des applications s'exécutant sur des tâches matériels. La réduction de ce temps des changements de contexte est obligatoire d'offrir à la tâche matérielle d'un multi- tâches préemptif, tout comme les tâches de logiciels. Plusieurs méthodes existent pour effectuer les opérations contexte commutateur matériel dans un contexte cellulaire homogène : chaîne de relecture dédiée sur tissus reconfigurables, des points de contrôle, de numérisation de la chaîne sur le contexte réel. Mais, rien n'a été proposé dans un contexte de tissu hétérogène (par exemple une accélération matérielle nuage fournir sur différents types de carte FPGA) .L'objectif de cette thèse est de proposer de nouvelles méthodes et algorithmes pour permettre le matériel des changements de contexte, même entre des cibles matérielles hétérogènes. Au cours de la thèse, l'étudiant devra :- Réaliser une bibliographie sur les méthodes du matériel du groupe de préemption existants dans le contexte cellulaire homogène.- Proposer des algorithmes qui permettent une solution légère et générique changement de contexte pour les tâches matérielles .- Valider ces algorithmes par leur intégration dans un flux de production d' accélérateur matériel . Ainsi, le flux prolongée peut générer, en plus de la tâche matérielle d'une application, le support matériel dédié pour des changements de contexte.- Proposer une stratégie de génération (multi- cible supplémentaire, ...) adapté pour cibles hétérogènes. La stratégie doit préserver les points de synchronisation entre les objectifs- Prototype de preuve de concepts sur la stratégie sur un nuage de FPGA. / Dynamically reconfigurable architectures offer theoretically excellent trade-off between performance and flexibility. Practically, these architectures are based on one or several processors and several reconfigurable cells. A reconfigurable cell can load, execute and unload hardware accelerators. This property enables virtualization of hardware tasks. In this context, an application can take benefit from both software flexibility and hardware performance. In current reconfigurable architectures, hardware tasks are limited to cooperative multi-tasking, since reconfiguration time and context-storing time are expensive. While reconfiguration time is architecture-dependent, the time required to store or restore the context strongly depends on applications running on hardware tasks. Reducing this context-switch time is mandatory to offer to hardware task a preemptive multi-tasking, just like software tasks. Several methods exist to perform the hardware context-switch operations in an homogeneous cell context: dedicated readback chain on reconfigurable fabrics, checkpoints, scan-chain on live context. But, nothing has been proposed in an heterogeneous fabric context (e.g. a cloud providing hardware acceleration on various kind of FPGA board).The goal of this thesis is to propose new methodologies and algorithms to enable hardware context-switch even between heterogeneous hardware targets. During the thesis, the student will have to:- Realize a bibliography on the existing hardware task preemption methods in homogeneous cell context.- Propose algorithms that enable a lightweight and generic context switch solution for hardware tasks.- Validate these algorithms by their integration in a hardware accelerator generation flow. Thus, the extended flow can generate in addition of the hardware task of an application, the dedicated hardware support for context-switch.- Propose an generation strategy (incremental, multi-target,...) suitable for heterogeneous targets. The strategy has to preserve synchronization points between targets- Prototype proof-of-concepts on the strategy on an FPGA cloud.

Depuis plusieurs décennies, afin de réduire la consommation énergétique des processeurs, les constructeurs fabriquent des ordinateurs de plus en plus parallèles.Dans le même temps, l'écart de fréquence entre les processeurs et la mémoire a significativement augmenté.Pour compenser cet écart, les processeurs modernes embarquent une hiérarchie de caches complexe.Développer un programme efficace sur de telles machines est une tâche complexe.Par conséquent, l'analyse de performance est devenue une étape majeure lors du développement d'applications requérant des performances.La plupart des outils d'analyse de performances se concentrent sur le point de vue du processeur.Ces outils voient la mémoire comme une entité monolithique et sont donc incapable de comprendre comment elle est accédée.Cependant, la mémoire est une ressource critique et les schémas d'accès à cette dernière peuvent impacter les performances de manière significative.Quelques outils permettant l'analyse de performances mémoire existent, cependant ils sont basé sur un échantillon age à large grain.Par conséquent, ces outils se concentrent sur une petite partie de l’Exécution et manquent le comportement global de l'application.De plus, l'échantillonnage à large granularité ne permet pas de collecter des schémas d'accès.Dans cette thèse, nous proposons deux outils différences pour analyser le comportement mémoire d'une application.Le premier outil est conçu spécifiquement pour pour les machines NUMA (Not Uniform Memory Accesses) et fournit plusieurs visualisations du schéma global de partage de chaque structure de données entre les flux d’ExécutionLe deuxième outil collecte des traces mémoires a grain fin avec information temporelles.Nous proposons de visualiser ces traces soit à l'aide d'un outil générique de gestion de traces soit en utilisant une approche programmatique basé sur R.De plus nous évaluons ces deux outils en les comparant a des outils existant de trace mémoire en terme de performances, précision et de complétude. / Since a few decades, to reduce energy consumption, processor vendors builds more and more parallel computers.At the same time, the gap between processors and memory frequency increased significantly.To mitigate this gap, processors embed a complex hierarchical caches architectureWriting efficient code for such computers is a complex task.Therefore, performance analysis has became an important step of the development of applications seeking for performances.Most existing performance analysis tools focuses on the point of view of the processor.Theses tools see the main memory as a monolithic entity and thus are not able to understand how it is accessed.However, memory is a common bottleneck in High Performances Computing, and the pattern of memory accesses can impact significantly the performances.There are a few tools to analyze memory performances, however theses tools are based on a coarse grain sampling.Consequently, they focus on a small part of the execution missing the global memory behavior.Furthermore, these coarse grain sampling are not able to collect memory accesses patterns.In this thesis we propose two different tools to analyze the memory behavior of an application.The first tool is designed specifically for Not Uniform Memory Accesses machines and provides some visualizations of the global sharing pattern inside each data structure between the threads.The second one collects fine grain memory traces with temporal information.We can visualize theses traces either with a generic trace management framework or with a programmatic exploration using R.Furthermore we evaluate both of these tools, comparing them with state of the art memory analysis tools in terms of performances, precision and completeness.

Le premier but de cette thèse est d’étudier les séquences de chevauchements dans les prismes d’accrétion et les chaînes plissées grâce au calcul à la rupture. La méthode, issue du génie civil, est adaptée ici à la géologie structurale dans l’objectif de détecter les modes de rupture au cours du plissement. Cubas et al. (2008) ont appliqué l’approche externe, de façon analytique, sur des séquences de chevauchements, prédisant ainsi la position des failles, l’évolution de la séquence et la borne supérieure à la force tectonique. L’approche complémentaire, l’approche interne, donne les distributions de contraintes à chaque pas de raccourcissement ainsi que la borne inférieure à la force tectonique. Ce problème d’optimisation est basé sur la discrétisation de la structure, dont les inconnues sont les contraintes nodales. La validation de cette méthode sur un bloc rectangulaire pouvant glisser sur un niveau de décollement (Hafner, 1951) permet d’identifier deux modes de rupture : activation totale du décollement sans rupture dans le matériau ou pas d’activation du décollement avec rupture dans le matériau. L’application sur un pli de rampe met en évidence les systèmes de failles conjuguées classiques : rampe - rétro-chevauchement, et les zones en extension au sommet de la couche qui étaient encore peu connues. Une modélisation par éléments finis de l’initiation d’un pli de rampe donne les mêmes contraintes que celles obtenues par optimisation, pour un coût de temps calcul plus important. Le deuxième objectif de cette thèse est d’étudier les mécanismes de ruine en 3D dans les prismes d’accrétion. La méthode proposée est basée sur l’approche externe numérique, le champ de vitesse virtuel étant construit sur la discrétisation de la structure. Une validation en 2D montre que ce schéma numérique permet de retrouver la criticalité du prisme au sens de Dalhen (1984). En 3D, la pente topographique d’un prisme triangulaire est choisi pour varier latéralement, d’un côté sous-critique et de l’autre super-critique. La déformation est localisée du côté sous-critique et diffuse du côté super-critique. L’influence de la friction sur le mur de poussée et sur les murs latéraux du prisme est également étudiée. Suivant la valeur de l’angle de friction sur le mur de poussée, il existe deux modes distincts de rupture : une rampe ou un système rampe - rétro-chevauchement. L’angle de friction sur le mur latéral du prisme entraˆine une déformation verticale sur 1.5 fois l’épaisseur du prisme. Le troisième but de cette thèse est d’étudier les effets 3D en boite de sable, en faisant varier la géométrie de la boite et celle du prisme. Une boite étroite et une épaisseur de sable importante implique une déformation contrôlée entièrement par les frottements sur les vitres latérales. L’évolution de cette déformation est observable sur l’enregistrement des forces de chaque côté de la boite. La géométrie de la boite et du système de compression influe de façon qualitative sur la position du mode de ruine dans la boite pour une même géométrie de prisme. / The first objective of this thesis is to study sequences of thrusting in accretionary wedges and in fold-and-thrust belts by application of limit analysis. The method, inherited from civil engineering, is adapted here for structural geology problems with the objective to determine the dominant failure mode responsible for folding. Cubas et al. (2008) applied the external approach, analytically, to sequences of thrusting, predicting the position and the life span of a give thrust, and of course the least upper bound on the tectonic force. The complementary approach, the internal approach, provides the stress distribution at each step of the shortening of the structure as well as the best lower bound on the tectonic force. This optimization problems relies on a spatial discretization of the domain and the basic unknowns are the nodal stresses. The validation of the method is conducted with a rectangular block sliding over the décollement (Hafner, 1951) and provides two modes of failure : a complete activation of the décollement with no bulk failure or no activation of this décollement and bulk failure. The application to the fault-bend fold reveals the classical conjugate set of ramps and back thrusts and the regions of extension within the hanging wall, which were not recognized so far. A finite-element modeling of the initiation of the slip over the ramp provides the same distribution as the one obtained by optimization although for a larger computer time. The second objective of this thesis is to study the 3D geometry of the failure modes in accretionary wedges. The proposed method is numerical and based on the external approach, the virtual velocity field being interpolated over the discretized domain. The 2D validation consists in capturing the stability transition defined by Dahlen (1984). The 3D wedge geometry includes a lateral variation in the topographic slope such that the right and left cross section are sub-critical and super-critical.The deformation is localized in the sub-critical region and more diffuse as one moves towards the super-critical regions. The influence of the back wall and of the d´ecollement friction is also studied. Two modes of failure could be selected depending on the friction angle on the back wall : a single ramp or a system ramp and back thrust. The friction on the lateral walls implies a vertical stretching of the bulk material over a width which is 1.5 times the wedge thickness. The third objective of this thesis is to study 3D effects in analogue experiments done in the laboratory by varying the geometry of the experimental set up and of the wedge. A narrow set up and a thick wedge at its toe implies a deformation which is controlled by the lateral wall friction. The evolution of the deformation is also analysed by monitoring the forces at the two ends to the experimental set up. The geometry of the set up and of the compressive device influences qualitatively the position of the failure mode within the wedge for the same wedge geometry.

Québec Université Laval, Bibliothèque 2016

Les modèles géométriques de calcul permettent d’effectuer des calculs à l’aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d’illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d’abord à travers l’étude de fractales que les machines à signaux sont capables d’une utilisation massive et parallèle de l’espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base les modules munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l’application de cette méthode et l’utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l’efficacité et le pouvoir de calcul parallèle des machines a signaux. / Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, through a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components —called modules— supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines.

Cette thèse de théorie de la démonstration étudie les interactions entre le λ-calcul différentiel d'Ehrhard et Regnier d'un côté, et certaines émanations calculatoires de la logique classique (le λμ-calcul de Parigot et le λ-barre-μ-calcul de Herbelin) de l'autre. L'étude est initiée et guidée par la décomposition de ces calculs dans des extensions de la logique linéaire de Girard.<br /><br />Dans une première partie, on définit un cadre commun pour ces extensions, dans le formalisme des réseaux d'interaction de Lafont, et on y rappelle des résultats de la littérature ou du folklore. On donne en particulier la traduction du λμ-calcul et du λ-barre-μ-calcul dans les réseaux polarisés de Laurent et celle du fragment finitaire du λ-calcul différentiel dans les réseaux différentiels d'Ehrhard et Regnier.<br /><br />Dans la deuxième partie, on introduit les réseaux différentiels polarisés (RDP), comme l'extension par une polarisation à la Laurent des réseaux différentiels. La pertinence des règles de réduction nouvelles est soulignée par l'étude d'un modèle dénotationnel commun aux réseaux différentiels et aux réseaux polarisés.<br /><br />Enfin, on présente trois calculs de termes, chacun pouvant être considéré comme une lecture en arrière de tout ou partie des interactions définies par les RDP : un λμ-calcul différentiel, qui correspond à la réunion des réseaux différentiels et des réseaux polarisés ; un λ-barre-μ-calcul avec produit de convolution sur les piles, qui fait intervenir la structure de bigèbre des types polarisés introduite dans les RDP, mais pas la dérivée ; enfin, un λ-barre-μ-calcul différentiel qui développe toute l'expressivité des RDP.

Cette thèse s'inscrit comme une étape vers la maîtrise de la résistance au choc des structures en béton, en développant la connaissance du comportement dynamique du matériau pour mieux calculer les ouvrages vis-à-vis des chargements accidentels. Une première partie récapitule les mécanismes physiques mis en évidence grâce aux essais de traction directe à des vitesses échelonnées du régime quasi-statique au domaine atteint lors des chocs durs (technique des barres d'Hopkinson), et propose plusieurs expressions de l'évolution de la résistance avec la vitesse, en fonction des paramètres caractéristiques du matériau. On a pu en déduire une optimisation du béton par rapport aux sollicitations dynamiques rapides. Une deuxième partie décrit l'essai de dalles au tube à choc, mis au point pour valider sur une structure modèle les résultats obtenus à l'échelle du matériau. Les données recueillies sur 24 dalles constituées de différents bétons, armés ou non, sont présentées en détails. Leur analyse permet de tester plusieurs méthodes de calcul approchées, et de définir un cahier des charges incontournable pour des modèles de calcul en dynamique plus sophistiqués, qui restent à développer.

Ce travail porte sur l'analyse de la fiabilité de structures marines de type Jacket, de comportement élastique-parfaitement plastique, vis-à-vis de chargement de houle linéaire stochastique. Les fonctions d'état de sécurité ou de ruine du système mécanique, calculées à l'aide d'une méthode d'analyse de contraintes pas-à-pas, prennent en compte les efforts combinés de flexion et de traction-compression par le flambement (écoulement bi-dimensionnel), dans les éléments de la structure. Les incertitudes des résistances des éléments de la structure sont prises en compte par des lois normales ou log-normales, définies à partir de données statistiques, rapportées par le comité LRFD (sur des facteurs de résistance et de chargement), de la Société Américaine de Génie civil. L'incertitude du chargement de houle est prise en compte par un modèle de houle linéaire stochastique, gaussien stationnaire ergodique. L'approche de la probabilité de ruine globale du système mécanique se fait par deux méthodes: la méthode dite de Premier Ordre, basée sur l'approximation des hyperplans équivalents des intersections ou des unions des régions de ruine du système, et la méthode dite hybride, basée sur la simulation Monte-Carlo. Enfin, deux exemples d'application d'un portique et d'une structure marine installée en eau moyennement profonde, mettent en évidence les avantages de l'utilisation du modèle d'efforts combinés de flexion et de traction-compression, y compris le flambement, proposé dans ce travail. Les modèles proposés dans ce travail, d'application aux structures marines, mais de portée beaucoup plus grande, permettent d'étudier la variation de la probabilité de ruine globale d'un système mécanique, en fonction des critères adoptés dans sa conception. Ils permettent également d'établir des critères pour définir les niveaux de sécurité désirables.