Ce mémoire est composé de deux grandes parties. Dans la première, nous simulons le fonctionnement d'automates cellulaires par différents modèles de calcul parallèle comme les PRAM, les XPRAM et les machines spatiales. Nous obtenons ainsi différentes preuves de l'universalité de ces modèles. Nous tirons quelques conséquences de ces résultats du point de vue de la calculabilité et de la complexité. Dans la seconde partie, nous considérons les automates cellulaires définis sur des graphes de Cayley finis. Nous rappelons la simulation de Róka qui permet de mimer le fonctionnement d'un tore hexagonal d'automates par un tore d'automates de dimension deux. Nous décrivons ensuite différentes manières de plonger un tore d'automates de dimension deux dans un anneau d'automates. Nous déduisons de ces résultats la simulation de tores de dimension finie par un anneau d'automates et celle d'un tore hexagonal d'automates par un anneau d'automates.

In this thesis we describe techniques for code generation and global optimization for a PRAM-NUMA multicore architecture. We specifically focus on the REPLICA architecture which is a family massively multithreaded very long instruction word (VLIW) chip multiprocessors with chained functional units that has a reconfigurable emulated shared on-chip memory. The on-ship memory system supports two execution modes, PRAM and NUMA, which can be switched between at run-time.PRAM mode is considered the standard execution mode and targets mainly applications with very high thread level parallelism (TLP). In contrast, NUMA mode is optimized for sequential legacy applications and applications with low amount of TLP. Different versions of the REPLICA architecture have different number of cores, hardware threads and functional units. In order to utilize the REPLICA architecture efficiently we have made several contributionsto the development of a compiler for REPLICA target code generation. It supports both code generation for PRAM mode and NUMA mode and can generate code for different versions of the processor pipeline (i.e. for different numbers of functional units). It includes optimization phases to increase the utilization of the available functional units. We have also contributed to quantitative the evaluation of PRAM and NUMA mode. The results show that PRAM mode often suits programs with irregular memory access patterns and control flow best while NUMA mode suites regular programs better. However, for a particular program it is not always obvious which mode, PRAM or NUMA, will show best performance. To tackle this we contributed a case study for generic stencil computations, using machine learning derived cost models in order to automatically select at runtime which mode to execute in. We extended this to also include a sequence of kernels.

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ Consider a communications network which can be represented by a graph G = (V;E), where V is a set of sites (processors), and E is a set of links which are used to connect the sites (processors). In some cases, we also assign weights and/or directions to the edges in E. Associated with this network, there are many problems such as (i) whether the network is k-edge (k-vertex) connected withfixed k; (ii) whether there are k-edge (k-vertex) disjoint paths between u and v for a pair of given vertices u and v after the network is dynamically updated by adding and/or deleting an edge etc; (iii) whether the sites in the network can communicate with each other when some sites and links fail; (iv) identifying the first k edges in the network whose deletion will result in the maximum increase in the routing cost in the resulting network for fixed k; (v) how to augment the network at optimal cost with a given feasible set of weighted edges such that the augmented network is k-edge (k-vertex) connected; (vi) how to route messages through the network efficiently. In this thesis we answer the problems mentioned above by presenting efficient parallel algorithms to solve them. As far as we know, most of the proposed algorithms are the first ones in the parallel setting. ¶ Even though most of the problems concerned in this thesis are related to communications networks, we also study the classic edge-coloring problem. The outstanding difficulty to solve this problem in parallel is that we do not yet know whether or not it is in NC. In this thesis we present an improved parallel algorithm for the problem which needs [bigcircle]([bigtriangleup][superscript 4.5]log [superscript 3] [bigtriangleup] log n + [bigtriangleup][superscript 4] log [superscript 4] n) time using [bigcircle](n[superscript 2][bigtriangleup] + n[bigtriangleup][superscript 3]) processors, where n is the number of vertices and [bigtriangleup] is the maximum vertex degree. Compared with a previously known result on the same model, we improved by an [bigcircle]([bigtriangleup][superscript 1.5]) factor in time. The non-trivial part is to reduce this problem to the edge-coloring update problem. We also generalize this problem to the approximate edge-coloring problem by giving a faster parallel algorithm for the latter case. ¶ Throughout the design and analysis of parallel graph algorithms, we also find a technique called the sparsification technique is very powerful in the design of efficient sequential and parallel algorithms on dense undirected graphs. We believe that this technique may be useful in its own right for guiding the design of efficient sequential and parallel algorithms for problems in other areas as well as in graph theory.

This thesis describes the implementation of a source to source compiler that translates Fork language to REPLICA baseline language. The Fork language is a high-level programming language designed for the PRAM (Parallel Random Access Machine) model. The baseline language is a low-level parallel programming language for the REPLICA architecture which implements the PRAM computing model. To support the Fork language on REPLICA, a compiler that translates Fork to baseline is built.  The Fork to baseline compiler is built in compatibility with the Fork implementation for SB-PRAM. Moreover, the libraries that support Fork's features are built using baseline language.The evaluation result verifies that the features of the Fork language are supported in the implementation. The evaluation also shows the scalability of our implementation and shows that the overhead introduced by Fork-to-baseline translation is small.

La diffraction électronique en mode précession (PED) est une méthode récente d’acquisition de clichésde diffraction permettant de minimiser les interactions dynamiques. L’objectif de cette thèse est dedévelopper une méthodologie d’acquisition et de traitement des clichés de diffraction en modeprécession afin de mesurer les champs de déformation en combinant une résolution spatialenanométrique et une sensibilité inférieure à 10-3 typiquement obtenues par d’autres techniques usuellesde microscopie, telle que l’imagerie haute-résolution. Les mesures ont été réalisées sur un JEOL 2010Aéquipé du module de précession Digistar produit par la société Nanomegas.Un système modèle constitué de multicouches Si/SiGe de concentrations connues en Ge a été utilisépour évaluer les performances de la méthodologie développée dans cette thèse. Les résultats indiquentune sensibilité sur la mesure de contraintes qui atteint, au mieux, 1x10-4 et un accord excellent avec lescontraintes simulées par éléments finis. Cette nouvelle méthode a pu ensuite être appliquée sur despuits quantique d’InGaAs et sur des transistors de type Ω−gate.La dernière partie traite d’un nouvel algorithme permettant d’évaluer de manière robuste et rapide lapolycristallinité des matériaux à partir d’une mesure PED. Nous donnons des exemples d’applicationde cette méthode sur divers dispositifs / Precession electron diffraction (PED) is a recent technique used to minimize acquired diffractionpatterns dynamic effects. The primary intention of this PhD work is to improve PED (PrecessionElectron Diffraction) data analysis and treatment methodologies in order to measure the strain at thenanoscale. The strain measurement is intended to reach a 10-3 strain precision as well as usualmicroscopy techniques like high-resolution imaging. To this end, measurements were made with aJEOL 2010A with a Digistar Nanomegas precession module.The approach developed has been used and tested by measuring the strain in a Si/SiGe multilayeredreference sample with a known Ge Content. Strain measurements reached 1x10-4 sensitivity withexcellent finite element strain simulation agreement. This process has been also applied to measure thestrain in microelectronic InGaAs Quantum Well and an "Ω-gate" experimental transistor devices.The second approach developed has been made to provide a robust means of studying electrontransparent nanomaterial polycrystallinity with precession. Examples of applications of this analysismethod are shown on different devices.

La diffraction électronique en mode précession (PED) est une méthode récente d’acquisition de clichésde diffraction permettant de minimiser les interactions dynamiques. L’objectif de cette thèse est dedévelopper une méthodologie d’acquisition et de traitement des clichés de diffraction en modeprécession afin de mesurer les champs de déformation en combinant une résolution spatialenanométrique et une sensibilité inférieure à 10-3 typiquement obtenues par d’autres techniques usuellesde microscopie, telle que l’imagerie haute-résolution. Les mesures ont été réalisées sur un JEOL 2010Aéquipé du module de précession Digistar produit par la société Nanomegas.Un système modèle constitué de multicouches Si/SiGe de concentrations connues en Ge a été utilisépour évaluer les performances de la méthodologie développée dans cette thèse. Les résultats indiquentune sensibilité sur la mesure de contraintes qui atteint, au mieux, 1x10-4 et un accord excellent avec lescontraintes simulées par éléments finis. Cette nouvelle méthode a pu ensuite être appliquée sur despuits quantique d’InGaAs et sur des transistors de type Ω−gate.La dernière partie traite d’un nouvel algorithme permettant d’évaluer de manière robuste et rapide lapolycristallinité des matériaux à partir d’une mesure PED. Nous donnons des exemples d’applicationde cette méthode sur divers dispositifs / Precession electron diffraction (PED) is a recent technique used to minimize acquired diffractionpatterns dynamic effects. The primary intention of this PhD work is to improve PED (PrecessionElectron Diffraction) data analysis and treatment methodologies in order to measure the strain at thenanoscale. The strain measurement is intended to reach a 10-3 strain precision as well as usualmicroscopy techniques like high-resolution imaging. To this end, measurements were made with aJEOL 2010A with a Digistar Nanomegas precession module.The approach developed has been used and tested by measuring the strain in a Si/SiGe multilayeredreference sample with a known Ge Content. Strain measurements reached 1x10-4 sensitivity withexcellent finite element strain simulation agreement. This process has been also applied to measure thestrain in microelectronic InGaAs Quantum Well and an "Ω-gate" experimental transistor devices.The second approach developed has been made to provide a robust means of studying electrontransparent nanomaterial polycrystallinity with precession. Examples of applications of this analysismethod are shown on different devices.