Tesis sobre el tema "Matrice mémoire"

La plupart des protocoles de stockage quantique de l'information reposent sur l'enregistrement d'un signal lumineux dans une superposition d'états de longue durée de vie. L'élément clé pour réaliser un tel enregistrement est un système atomique à 3 niveaux en Lambda, où deux sous-niveaux fondamentaux sont couplés optiquement à un même niveau supérieur. L'excitation optique est alors stockée dans une superposition des deux sous-niveaux fondamentaux. Les cristaux dopés aux ions de terre rare sont des candidats prometteurs pour ces applications, car ils présentent des durées de vie des cohérences optiques et hyperfines particulièrement longues. Cette thèse est consacrée à l'étude de l'ion thulium, un ion de terre rare non-Kramers, comme alternative aux ions Pr et Eu qui ont longtemps été considérés comme étant les seuls candidats possibles pour la réalisation d'une mémoire quantique. Grâce à son spin nucléaire 1/2, le thulium présente une structure de sous-niveaux Zeeman nucléaires particulièrement simple, dont l'espacement peut être aisément contrôlé à l'aide d'un champ magnétique externe. De plus, la longueur d'onde d'absorption du thulium à 793 nm est accessible aux lasers à semi-conducteurs qui peuvent être facilement stabilisés en dessous du kHz. Au cours de cette thèse, nous avons construit un système à 3 niveaux en Lambda dans le Tm:YAG. Nous avons également mis en oeuvre des processus cohérents permettant de manipuler optiquement un état de superposition de spin nucléaire, comme les échos Raman et le STIRAP. L'ensemble des résultats obtenus montrent que le thulium est un bon candidat pour la démonstration de certains protocoles de mémoire quantique.

L'objet de cette thèse est l'étude asymptotique du modèle de Hopfield dont le but est de simuler le phénomène neuronal de mémoire associative. Après une brève introduction au calcul neuronal et une description générale de la modélisation mathématique de la mémoire associative, nous définissons le modèle étudié dans le cadre d'une dynamique d'évolution déterministe, respectivement séquentielle (modèle de Hopfield) ou parallèle (modèle de Little). Nous étudions alors la stabilité asymptotique de $p$ images originales, au sens presque sûr pour l'espace de probabilité associé aux variables aléatoires modélisant ces images, ainsi que l'attraction de certaines configurations, en une seule étape de la dynamique, si $p$ est de l'ordre $N/\log N$ ($N$ la taille du réseau). La fonction énergie ayant notamment pour minima locaux les images originales et tous les autres points fixes de l'application associée à la dynamique, il est intéressant d'en connaître les fluctuations sur l'espace des configurations. Après avoir rappelé les résultats de Newman, relatifs à l'existence de barrières énergétiques, nous montrons que asymptotiquement et presque sûrement, sous certaines hypothèses sur $p$, les images combinées, combinaisons d'un nombre fine ou de toutes les images combinées, ne peuvent être des minima plus profonds que les images originales elles-mêmes. En ces points, nous calculons la limite presque sûre du hamiltonien normalisé. Au chapitre suivant, nous décrivons la dynamique stochastique de Glauber qui nous conduit à définir les mesures de Gibbs pour la limite thermodynamique de ce systèmes. Nous étudions alors, dans un dernier chapitre, le comportement asymptotique de l'énergie libre: pour toute température, cette variable aléatoire converge presque sûrement vers une constante, si $p/N$ converge vers 0, et vérifie la propriété d'être auto-moyennée, si $p$ est inférieur au proportionnel à $N$. En conclusion, nous terminons en évoquant quelques problèmes ouverts et des extensions possibles du modèle de Hopfield.

La mémoire à changement de phase (PCM) s’inscrit dans la stratégie de développement de mémoires non-volatiles embarquées sur les nœuds technologiques avancés (sub 28nm). En effet, la mémoire Flash-NOR devient de plus en plus onéreuse à intégrer dans les technologies avec des diélectriques à forte permittivité et des grilles métalliques. Cette thèse a donc pour objectif principal de réaliser des véhicules de tests afin d’étudier un point mémoire novateur PCM + OTS et de proposer des solutions afin de combler ses lacunes et ses limites suivant les applications envisagées. L’étude a pour support deux technologies différentes le HCMOS9A et le P28FDSOI. La première sert de support pour le développement d’un véhicule de validation technologique du point mémoire OTS+PCM. La deuxième est, quant à elle, utilisée pour démontrer la surface obtenu avec un dimensionnement agressif du point mémoire. Enfin, un circuit de lecture optimisé pour ce point mémoire a été réalisé permettant la compensation des courants de fuites ainsi que la régulation des tensions de polarisations de la matrice au cours de la lecture
Phase change memory (PCM) is part of the strategy to develop non-volatiles memories embedded in advanced technology nodes (sub 28nm). Indeed, Flash-NOR memory is becoming more and more expensive to integrate in technologies with high permittivity dielectrics and metallic gates. The main objective of this thesis is therefore to realize tests vehicles in order to study an innovative PCM + OTS memory point and to propose solutions to fill its gaps and limitations according to the envisaged applications. The study is based on two different technologies: HCMOS9A and P28FDSOI. The first one is used as support for the development of a technological validation vehicle of the OTS+PCM memory point. The second one is used to demonstrate the surface obtained with an aggressive sizing of the memory point. Finally, an optimized readout circuit for this memory point has been realized allowing the compensation of leakage currents as well as the regulation of the bias voltages of the matrix during the reading

La modélisation, l'élaboration et la caractérisation de nouvelles brasures composites sans plomb à propriétés adaptatives est encouragée par les menaces d'interdiction du plomb dans l'industrie électronique ainsi que par la demande incessante de fiabilité accrue. Dans ce contexte, des joints de brasure composite à matrice Sn-3,8Ag-0,7Cu et renfort particulaire en alliage à mémoire de forme NiTi sont développés. Une caractérisation microstructurale et mécanique de la matrice sans plomb est effectuée. Les évolutions de la chimie et de la microstructure de la surface des particules de NiTi au cours des différentes étapes du procédé de dépôt d'un agent mouillant sur leur surface sont étudiées. Finalement la tenue à la fatigue thermomécanique de ces nouveaux matériaux est évaluée et met en évidence l'influence du renfort en alliage à mémoire de forme.

Les calculs d'écoulements stationnaires peuvent être considérés comme efficace si l?état stationnaire est atteint pour un temps CPU réduit mais aussi si la place mémoire utilisée reste faible; cette dernière exigence devient primordiale pour les applications industrielles où le nombre de points de calcul est très important. Ceci vaut également pour les écoulements instationnaires, désormais classiquement résolus via une approche pas-de-temps dual pour laquelle les états physiques successifs sont vus comme des états stationnaires vis-à-vis d'un temps fictif. Le besoin crucial de méthodes implicites à faible encombrement mémoire a conduit au développement de traitements sans matrice. Pour les applications qui intéressent le CEA, à savoir la simulation d'écoulements réactifs multi-espèces à l'intérieur d'une enceinte de réacteur nucléaire à eau pressurisée, les méthodes doivent être assez versatiles pour traiter la gamme d'écoulements allant du quasi-incompressible au fortement compressible. Le préconditionnement bas-Mach des équations de Navier-Stokes permet d'appliquer en régime incompressible les schémas initialement conçus pour la simulation des écoulements compressibles. Le présent travail montre comment obtenir un traitement implicite sans matrice pour tout régime d'écoulement lorsque la phase implicite contient une matrice de préconditionnement; l'efficacité intrinsèque du schéma implicite sans matrice couplé à une technique de relaxation de type Jacobi par point (PJ) ou Symmetric Gauss-Seidel (SGS) est étudiée grâce à une analyse de Von Neumann; puis des comparaisons avec des méthodes implicites blocs standards sont effectuées. La méthode implicite sans matrice est finalement implémentée au sein du code non-structuré CAST3M et elle est appliquée à la modélisation d'un Té de mélange à faible nombre de Mach. Le schéma implicite sans matrice constitue une alternative compétitive pour la simulation des écoulements compressibles et faiblement compressibles en maillages non-structurés.

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices
creuses.

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.

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.

Concernant la phase 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.

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.

Les grandes matrices de covariance constituent certainement l’un des modèles les plus utiles pour les applications en statistiques en grande dimension, en communication numérique, en biologie mathématique, en finance, etc. Les travaux de Marcenko et Pastur (1967) ont permis de décrire le comportement asymptotique de la mesure spectrale de telles matrices formées à partir de N copies indépendantes de n observations d’une suite de variables aléatoires iid et sa convergence vers une distribution de probabilité déterministe lorsque N et n convergent vers l’infini à la même vitesse. Plus récemment, Merlevède et Peligrad (2016) ont démontré que dans le cas de grandes matrices de covariance issues de copies indépendantes d’observations d’un processus strictement stationnaire centré, de carré intégrable et satisfaisant des conditions faibles de régularité, presque sûrement, la distribution spectrale empirique convergeait étroitement vers une distribution non aléatoire ne dépendant que de la densité spectrale du processus sous-jacent. En particulier, si la densité spectrale est continue et bornée (ce qui est le cas des processus linéaires dont les coefficients sont absolument sommables), alors la distribution spectrale limite a un support compact. Par contre si le processus stationnaire exhibe de la longue mémoire (en particulier si les covariances ne sont pas absolument sommables), le support de la loi limite n'est plus compact et des études plus fines du comportement des valeurs propres sont alors nécessaires. Ainsi, cette thèse porte essentiellement sur l’étude des asymptotiques et des fluctuations des plus grandes valeurs propres de grandes matrices de covariance associées à des processus stationnaires à longue mémoire. Dans le cas où le processus stationnaire sous-jacent est Gaussien, l’étude peut être simplifiée via un modèle linéaire dont la matrice de covariance de population sous-jacente est une matrice de Toeplitz hermitienne. On montrera ainsi que dans le cas de processus stationnaires gaussiens à longue mémoire, les fluctuations des plus grandes valeurs propres de la grande matrice de covariance empirique convenablement renormalisées sont gaussiennes. Ce comportement indique une différence significative par rapport aux grandes matrices de covariance empirique issues de processus à courte mémoire, pour lesquelles les fluctuations de la plus grande valeur propre convenablement renormalisée suivent asymptotiquement la loi de Tracy-Widom. Pour démontrer notre résultat de fluctuations gaussiennes, en plus des techniques usuelles de matrices aléatoires, une étude fine du comportement des valeurs propres et vecteurs propres de la matrice de Toeplitz sous-jacente est nécessaire. On montre en particulier que dans le cas de la longue mémoire, les m plus grandes valeurs propres de la matrice de Toeplitz convergent vers l’infini et satisfont une propriété de type « trou spectral multiple ». Par ailleurs, on démontre une propriété de délocalisation de leurs vecteurs propres associés. Dans cette thèse, on s’intéresse également à l’universalité de nos résultats dans le cas du modèle simplifié ainsi qu’au cas de grandes matrices de covariance lorsque les matrices de Toeplitz sont remplacées par des matrices diagonales par blocs
Large covariance matrices play a fundamental role in the multivariate analysis and high-dimensional statistics. Since the pioneer’s works of Marcenko and Pastur (1967), the asymptotic behavior of the spectral measure of such matrices associated with N independent copies of n observations of a sequence of iid random variables is known: almost surely, it converges in distribution to a deterministic law when N and n tend to infinity at the same rate. More recently, Merlevède and Peligrad (2016) have proved that in the case of large covariance matrices associated with independent copies of observations of a strictly stationary centered process which is square integrable and satisfies some weak regularity assumptions, almost surely, the empirical spectral distribution converges weakly to a nonrandom distribution depending only on the spectral density of the underlying process. In particular, if the spectral density is continuous and bounded (which is the case for linear processes with absolutely summable coefficients), the limiting spectral distribution has a compact support. However, if the underlying stationary process exhibits long memory, the support of the limiting distribution is not compact anymore and studying the limiting behavior of the eigenvalues and eigenvectors of the associated large covariance matrices can give more information on the underlying process. This thesis is in this direction and aims at studying the asymptotics and the fluctuations of the largest eigenvalues of large covariance matrices associated with stationary processes exhibiting long memory. In the case where the underlying stationary process is Gaussian, the study can be simplified by a linear model whose underlying population covariance matrix is a Hermitian Toeplitz matrix. In the case of stationary Gaussian processes exhibiting long memory, we then show that the fluctuations of the largest eigenvalues suitably renormalized are Gaussian. This limiting behavior shows a difference compared to the one when large covariance matrices associated with short memory processes are considered. Indeed in this last case, the fluctuations of the largest eigenvalues suitably renormalized follow asymptotically the Tracy-Widom law. To prove our results on Gaussian fluctuations, additionally to usual techniques developed in random matrices analysis, a deep study of the eigenvalues and eigenvectors behavior of the underlying Toeplitz matrix is necessary. In particular, we show that in the case of long memory, the largest eigenvalues of the Toeplitz matrix converge to infinity and satisfy a property of “multiple spectral gaps”. Moreover, we prove a delocalization property of their associated eigenvectors. In this thesis, we are also interested in the universality of our results in the case of the simplified model and also in the case of large covariance matrices when the Toeplitz matrices are replaced by bloc diagonal matrices

Les algorithmes de la multiplication rapide de matrices (FMM) pour multiplier deux matrices n x n réduisent le nombre asymptotique d'opérations de O (n³) de la méthode traditionnelle à O (n²,xx), donc la parallélisation des algorithmes de FMM donne des résultats remarquables par rapport aux algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle. Dans cette parallélisation, l'application des algorithmes de FMM au niveau inter-processeur nécessite une conception plus fine de celle-ci mais conduit à des algorithmes plus efficaces. Pour utiliser des algorithmes de FMM au niveau inter-processeur, le point le plus important est de déterminer les sous-matrices après avoir appliqué r fois les formules de FMM et puis de trouver la matrice résultat à partir des produits de ces sous-matrices. Avec une valeur définie de r, nous pouvons manuellement résoudre ce problème comme dans les travaux précédents avec r=1,2, mais la solution pour le cas général n'est pas encore trouvée. Dans cette thèse, en combinant notre solution générale pour ce problème avec un bon modèle de stockage des sous-matrices, et avec les algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) nous avons une voie générale de parallélisation adaptative des algorithmes de FMM sur machines à mémoire distribuée. L'analyse de complexité prouve que nos algorithmes sont plus rapides que les algorithmes parallèles basés sur la méthode traditionnelle quand la taille de matrice est grande et notre travail est pertinent pour exploiter de meilleurs algorithmes quand le niveau de récursivité est assez grand. Les résultats expérimentaux sur Fujitsu Siemens Computers/hpcLine confirment le résultat théorique en montrant que nos algorithmes sont plus rapides que l'algorithme de Cannon de 1,2 à 2,4 fois pour les matrices de taille 8196 x 8196
Fast matrix multiplication (FMM) algorithms to multiply two n x n matrices reduce the asymptotic operation count from O (n³) of the traditional method to O (n². Xx), thus the parallelization of FMM algorithms always gives remarkable results in comparison to the parallel matrix multiplication algorithms based on traditional method. Within this parallelization, the application of FMM algorithms at the inter-processor level requires us to solve more difficult problems in designing but it forms the most effective algorithms. To use FMM algorithms at the inter-processor level, the most significant point is to determine the submatrices after having recursively executed r times the FMM formulas and then to find the result matrix from the products of these sub matrices. With a definite value of r, we can manually solve this problem like in the previous works with r=1,2, but the solution for the general case has not been found. In this PhD work, by combining our general solution for this problem with a good storage map of submatrices to processor, and with the parallel matrix multiplication algorithms based on traditional method (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) we have a general scalable parallelization of FMM algorithms on distributed memory computers. Complexity analyses show that our algorithms should be faster than the parallel algorithms based on traditional method when the matrix size is large and our work is relevant to exploit better algorithms when the recursion level is large enough. Experimental results on Fujitsu Siemens Computers/hpcLine confirm the theoretical result by showing that our algorithms perform better than Cannon's Algorithm from 1. 2 to 2. 4 times for matrices of size 8196 x 8196

Les méthodes directes de résolution de systèmes linéaires creux sont connues pour leurs besoins mémoire importants qui peuvent constituer une barrière au traitement de problèmes de grandes taille. De ce fait, les travaux effectués durant cette thèse ont porté d'une part sur l'étude du comportement mémoire d'un algorithme de factorisation de matrices creuses, en l'occurrence la méthode multifrontale, et d'autre part sur l'optimisation et la minimisation de la mémoire nécessaire au bon déroulement de la factorisation aussi bien dans un cadre séquentiel que parallèle. Ainsi, des algorithmes optimaux pour la minimisation de la mémoire ont été proposés pour le cas séquentiel. Pour le cas parallèle, nous avons introduit dans un premier temps des stratégies d'ordonnancement visant une amélioration du comportement mémoire de la méthode. Puis, nous les avons étendues pour avoir un objectif de performance tout en gardant un bon comportement mémoire. Enfin, dans le cas où l'ensemble des données à traiter a encore une taille plus importante que celle de la mémoire, il est nécessaire de concevoir des approches de factorisation out-of-core. Pour être efficaces, ces méthodes nécessitent d'une part de recouvrir les opérations d'entrées/sorties par des calculs, et d'autre part de réutiliser des données déjà présentes en mémoire pour réduire le volume d'entrées/sorties. Ainsi, une partie des travaux présentés dans cette thèse ont porté sur la conception de techniques out-of-core implicites adaptées au schéma des accès de la méthode multifrontale et reposant sur une modification de la politique de pagination du système d'exploitation à l'aide d'un outil bas-niveau (MMUM&MMUSSEL)
Direct methods for solving sparse linear systems are known for their large memory requirements that can represent the limiting factor to solve large systems. The work done during this thesis concerns the study and the optimization of the memory behaviour of a sparse direct method, the multifrontal method, for both the sequential and the parallel cases. Thus, optimal memory minimization algorithms have been proposed for the sequential case. Concerning the parallel case, we have introduced new scheduling strategies aiming at improving the memory behaviour of the method. After that, we extended these approaches to have a good performance while keeping a good memory behaviour. In addition, in the case where the data to be treated cannot fit into memory, out-of-core factorization schemes have to be designed. To be efficient, such approaches require to overlap I/O operations with computations and to reuse the data sets already in memory to reduce the amount of I/O operations. Therefore, another part of the work presented in this thesis concerns the design and the study of implicit out-of-core techniques well-adapted to the memory access pattern of the multifrontal method. These techniques are based on a modification of the standard paging policies of the operating system using a low-level tool (MMUM&MMUSSEL)

Le marché de l’électronique flexible devrait atteindre un chiffre d’affaire de plus de 10 milliards de dollars à l’horizon 2020. La réalisation de circuits dotés de flexibilité mécanique accompagnera l’essor de nouvelles applications liées à l’internet des objets ou à l’électronique grande surface. Après la logique, la mémoire est un organe fondamental de tout système électronique. Dans cette thèse, nous nous sommes intéressés au développement de mémoires non-volatiles de type CBRAM (Conductive Bridge Random Acces Memory) pour les applications électroniques flexibles. Ces mémoires possèdent une structure MEM (Métal-Électrolyte-Métal) et font partie des mémoires non volatiles émergentes de type ReRAM (Resistive RAM). L’effet mémoire est basé sur une commutation de résistance due à des phénomènes d’oxydo-réduction et de migration ionique aboutissant à la formation/dissolution d’un filament conducteur dans l’électrolyte solide. La possibilité d’utiliser des verres de chalcogénures ou encore des polymères comme électrolytes solide offre à ces mémoires un avenir prometteur pour les applications flexibles. Après avoir passé en revue les différents matériaux exploités pour la réalisation de CBRAM, nous exposerons des travaux concernant la fabrication et la caractérisation de mémoires basées sur des électrolytes de GeS$_x$ et de Ge$_X$Sb$_Y$Te$_Z$ sur substrats de silicium. Les caractéristiques I-V obtenues (phénomènes de set et reset) sont ensuite confrontées à des simulations réalisées à l’aide d’un modèle électro-thermique qui considère le courant ionique comme facteur limitant. La dernière partie de ce travail est quant à elle dédiée au développement de mémoires flexibles
Flexible electronics market revenue is expected to exceed $10B by 2020. Duento their mechanical flexibility, flexible circuits will enable numerous developmentsnin various fields from internet-of-things applications to large area electronics. Besides logic devices, memory is the second fundamental component of any electronic system. During this thesis, we aimed at developing nonvolatile memories referred as CBRAM (Conductive-Bridge Random Access Memories) for flexible electronics applications. These devices consist in a simple Metal-Electrolyte-Metal structure. The memory effect relies on resistance switching due to the formation/dissolution of a metallic conductive filament within a solid electrolyte. The use of chalcogenide glasses or polymers layers as solid-electrolytes offers many opportunities for future for flexible applications. In a first part, memory devices based on of GeS$_x$ and de Ge$_X$Sb$_Y$Te$_Z$ solid electrolytes on silicon substrates we fabricated and electrically tested. Experimental results were then confronted to an electro-thermal model, based on ionic current, developed during this thesis. The final chapter of this manuscript is devoted to the development of flexible memories

Le marché de l’électronique flexible devrait atteindre un chiffre d’affaire de plus de 10 milliards de dollars à l’horizon 2020. La réalisation de circuits dotés de flexibilité mécanique accompagnera l’essor de nouvelles applications liées à l’internet des objets ou à l’électronique grande surface. Après la logique, la mémoire est un organe fondamental de tout système électronique. Dans cette thèse, nous nous sommes intéressés au développement de mémoires non-volatiles de type CBRAM (Conductive Bridge Random Acces Memory) pour les applications électroniques flexibles. Ces mémoires possèdent une structure MEM (Métal-Électrolyte-Métal) et font partie des mémoires non volatiles émergentes de type ReRAM (Resistive RAM). L’effet mémoire est basé sur une commutation de résistance due à des phénomènes d’oxydo-réduction et de migration ionique aboutissant à la formation/dissolution d’un filament conducteur dans l’électrolyte solide. La possibilité d’utiliser des verres de chalcogénures ou encore des polymères comme électrolytes solide offre à ces mémoires un avenir prometteur pour les applications flexibles. Après avoir passé en revue les différents matériaux exploités pour la réalisation de CBRAM, nous exposerons des travaux concernant la fabrication et la caractérisation de mémoires basées sur des électrolytes de GeS(x) et de Ge(x)Sb(y)Te(z) sur substrats de silicium. Les caractéristiques I-V obtenues (phénomènes de set et reset) sont ensuite confrontées à des simulations réalisées à l’aide d’un modèle électro-thermique qui considère le courant ionique comme facteur limitant. La dernière partie de ce travail est quant à elle dédiée au développement de mémoires flexibles
Flexible electronics market revenue is expected to exceed 10B dollars by 2020. Duento their mechanical flexibility, flexible circuits will enable numerous developmentsnin various fields from internet-of-things applications to large area electronics. Besides logic devices, memory is the second fundamental component of any electronic system. During this thesis, we aimed at developing nonvolatile memories referred as CBRAM (Conductive-Bridge Random Access Memories) for flexible electronics applications. These devices consist in a simple Metal-Electrolyte-Metal structure. The memory effect relies on resistance switching due to the formation/dissolution of a metallic conductive filament within a solid electrolyte. The use of chalcogenide glasses or polymers layers as solid-electrolytes offers many opportunities for future for flexible applications. In a first part, memory devices based on of GeS(X) and de Ge(X)Sb(Y)Te(Z) solid electrolytes on silicon substrates we fabricated and electrically tested. Experimental results were then confronted to an electro-thermal model, based on ionic current, developed during this thesis. The final chapter of this manuscript is devoted to the development of flexible memories

La factorisation d'une matrice creuse est une approche robuste pour la résolution de systèmes linéaires creux de grande taille. Néanmoins, une telle factorisation est connue pour être coûteuse aussi bien en temps de calcul qu'en occupation mémoire. Quand l'espace mémoire nécessaire au traitement d'une matrice est plus grand que la quantité de mémoire disponible sur la plate-forme utilisée, des approches dites hors-mémoire (out-of-core) doivent être employées : les disques étendent la mémoire centrale pour fournir une capacité de stockage suffisante. Dans cette thèse, nous nous intéressons à la fois aux aspects théoriques et pratiques de telles factorisations hors-mémoire. Les environnements logiciel MUMPS et SuperLU sont utilisés pour illustrer nos discussions sur des matrices issues du monde industriel et académique. Tout d'abord, nous proposons et étudions dans un cadre séquentiel différents modèles hors-mémoire qui ont pour but de limiter le surcoût dû aux transferts de données entre la mémoire et les disques. Pour ce faire, nous revisitons les algorithmes qui ordonnancent les opérations de la factorisation et proposons de nouveaux schémas de gestion mémoire s'accommodant aux contraintes hors-mémoire. Ensuite, nous nous focalisons sur une méthode de factorisation particulière, la méthode multifrontale, que nous poussons aussi loin que possible dans un contexte parallèle hors-mémoire. Suivant une démarche pragmatique, nous montrons que les techniques hors-mémoire permettent de résoudre efficacement des systèmes linéaires creux de grande taille. Quand seuls les facteurs sont stockés sur disque, une attention particulière doit être portée aux données temporaires, qui restent en mémoire centrale. Pour faire décroître efficacement l'occupation mémoire associée à ces données temporaires avec le nombre de processeurs, nous repensons l'ordonnancement de la factorisation parallèle hors-mémoire dans son ensemble.

Cette thèse présente des études préliminaires visant à réaliser des mémoires quantiques dans des ions de terre rare en matrice cristalline. Les mémoires quantiques sont un élément essentiel de tout processus de traitement quantique de l'information. Si les photons sont les meilleurs vecteurs pour le transport d'information, les systèmes matériels représentent les meilleurs objets quantiques pour réaliser des opérations de stockage et de traitement de l'information. Les transitions Raman sont un processus intéressant pour réaliser le couplage lumière-matière car elles sont insensibles à la décohérence par émission spontanée. Les ions de terre rare ont été choisis car ils présentent des durées de vies de cohérence relativement longues. Dans ce manuscrit, après une présentation détaillée des différents ions de terre rare et des différentes matrices cristallines, on justifie le choix de travailler sur l'ion Thulium inséré dans un cristal de YAG. On discute ensuite de la façon de créer un système à trois niveaux efficace dans ce matériau à l'aide d'un champ magnétique. On présente les résultats expérimentaux de spectroscopie de l'ion Thulium en champ magnétique qui permettent de mesurer les facteurs gyromagnétiques du Thulium. On détaille la procédure de préparation du système à trois niveaux de façon à éliminer l'effet de l'élargissement inhomogène des transitions. On décrit enfin une première opération de manipulation cohérente d'un ensemble macroscopique d'ions Thulium, en utilisant un laser ultra-stable construit au laboratoire: l'opération de transfert adiabatique de population entre deux niveaux du système, par excitation cohérente "Sécante Hyperbolique Complexe".

Cette thèse présente des études préliminaires visant à réaliser des mémoires quantiques dans des ions de terre rare en matrice cristalline. Si les photons sont les meilleurs vecteurs pour le transport d'information, les systèmes matériels représentent les meilleurs objets quantiques pour réaliser des opérations de stockage et de traitement de l'information. Les transitions Raman sont un processus intéressant pour réaliser le couplage lumière-matière car elles sont insensibles à la décohérence par émission spontanée. Les ions de terre rare ont été choisis car ils présentent des durées de vies de cohérence relativement longues. Après une présentation détaillée des différents ions de terre rare et des différentes matrices cristallines, on justifie le choix de travailler sur l'ion Thulium:YAG pour lequel un laser stabilisé a été réalisé. On discute de la façon de créer un système à trois niveaux efficace dans ce matériau à l'aide d'un champ magnétique, en utilisant l'effet couplé de l'interaction hyperfine et de l'effet Zeeman électronique. On présente les résultats expérimentaux de spectroscopie de l'ion Thulium en champ magnétique et on mesure les facteurs gyromagnétiques de ce système, en bon accord avec les valeurs théoriques. On détaille la procédure de préparation du système à trois niveaux de façon à éliminer l'effet de l'élargissement inhomogène des transitions. On décrit enfin une première opération de manipulation cohérente d'un ensemble macroscopique d'ions Thulium: le transfert adiabatique de population entre deux niveaux du système, par excitation cohérente "Sécante Hyperbolique Complexe". Des taux de transfert de l'ordre de 95% ont été atteints
This thesis relates to preliminary studies aiming to achieve quantum memories in rare earth ions doped inorganic crystals. If photons are the best vectors for information transport, materials systems represent the best quantum objects to achieve inforrmation storage and manipulation. As they are insensitive to decoherence by spontaneous emission, Raman transitions are an interesting process to realize the light-matter coupling. Rare earth ions have been chosen because they exhibit relatively long coherence lifetime. After a detailed presentation of the different rare earth ions and the different crystals, we justify the choice of working on Thulium:YAG ions, for which we built a stabilised laser. We discuss on the possibility to create an efficient three-level system in this material with the help of an external magnetic field, using the coupled effect of hyperfine interaction and electronic Zeeman interaction. We present the experimentals results of spectroscopy of Thulium ion in a magnetic field and we measure the system gyromagnetic factors, which present a good agreement with the theoretical values. We present the three-level system preparation procedure, aiming to eliminate the transitions inhomogeneous broadening. We describe a first coherent manipulation process of a thulium ions macroscopic ensemble: the population adiabatic transfer between two levels of the system, using the "Complex Hyperbolic Secant" excitation procedure. Transfer rates of about 95% have been achieved

Ce mémoire est consacre a l'étude des propriétés optiques de molécules organiques encagées dans des matrices solides synthétisées par procede sol-gel. Nous montrons que de tels matériaux peuvent avoir des applications dans les domaines des lasers solides accordables et de l'optique non linéaire. Le procède sol-gel permet de transformer par polymérisation inorganique une solution réactionnelle appelée sol, en un gel solide poreux, appele xerogel. Le sol initial peut être dope avec des molécules organiques qui seront, après gélification, encagées dans les pores de la matrice solide hote. Ce procède étant très riche en possibilités de synthèse, nous avons pu étudier des xerogels de natures très diverses. Nous avons pu constater qu'une même molécule organique présente des comportements très différents suivant le type de matrice hote qu'elle dope. La nature des interactions entre les matrices solides hotes et les molécules organiques dopantes (rhodamines et triphénylméthanes) et leurs conséquences sur les propriétés de ces dernières ont été étudiées. Nous avons pu mettre en évidence deux paramètres de synthèse extrêmement importants quant a leurs conséquences sur le comportement des molécules encagées: d'une part la proportion d'eau présente dans le sol, et d'autre part, la nature de l'environnement initial du ou des atomes (ex: sio#2). C'est grâce a de nombreuses mesures d'optique linéaire et a leur interprétation que nous avons pu mieux comprendre la structure physico-chimique des xerogels dopes dont certains aspects ont, de surcroît, pu être modélises. Nous avons interprète en termes de viscosité apparente des résultats d'analyses temporelles de saturation d'absorption dans des xerogels dopes avec du vert de malachite. En ce qui concerne les applications, les travaux que nous avons effectues indiquent qu'il est possible de choisir le type de la matrice solide afin d'y retrouver les propriétés connues des molécules organiques en phase liquide. Des lasers solides accordables ont ainsi pu être développes. A l'inverse, il est également possible, en choisissant d'autres types de matrice, de synthétiser des matériaux aux propriétés originales. Nous avons ainsi réalise des xerogels dopes que nous avons dénommes optogels (optically active xerogels). Ces optogels constituent des mémoires optiques dont le comportement a été interprète en termes d'effet Kerr a mémoire

Ce mémoire est consacre a l'étude des propriétés optiques de molécules organiques encagées dans des matrices solides synthétisées par procede sol-gel. Nous montrons que de tels matériaux peuvent avoir des applications dans les domaines des lasers solides accordables et de l'optique non linéaire. Le procède sol-gel permet de transformer par polymérisation inorganique une solution réactionnelle appelée sol, en un gel solide poreux, appele xerogel. Le sol initial peut être dope avec des molécules organiques qui seront, après gélification, encagées dans les pores de la matrice solide hote. Ce procède étant très riche en possibilités de synthèse, nous avons pu étudier des xerogels de natures très diverses. Nous avons pu constater qu'une même molécule organique présente des comportements très différents suivant le type de matrice hote qu'elle dope. La nature des interactions entre les matrices solides hotes et les molécules organiques dopantes (rhodamines et triphénylméthanes) et leurs conséquences sur les propriétés de ces dernières ont été étudiées. Nous avons pu mettre en évidence deux paramètres de synthèse extrêmement importants quant a leurs conséquences sur le comportement des molécules encagées: d'une part la proportion d'eau présente dans le sol, et d'autre part, la nature de l'environnement initial du ou des atomes (ex: sio#2). C'est grâce a de nombreuses mesures d'optique linéaire et a leur interprétation que nous avons pu mieux comprendre la structure physico-chimique des xerogels dopes dont certains aspects ont, de surcroît, pu être modélises. Nous avons interprète en termes de viscosité apparente des résultats d'analyses temporelles de saturation d'absorption dans des xerogels dopes avec du vert de malachite. En ce qui concerne les applications, les travaux que nous avons effectues indiquent qu'il est possible de choisir le type de la matrice solide afin d'y retrouver les propriétés connues des molécules organiques en phase liquide. Des lasers solides accordables ont ainsi pu être développes. A l'inverse, il est également possible, en choisissant d'autres types de matrice, de synthétiser des matériaux aux propriétés originales. Nous avons ainsi réalise des xerogels dopes que nous avons dénommes optogels (optically active xerogels). Ces optogels constituent des mémoires optiques dont le comportement a été interprète en termes d'effet Kerr a mémoire

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille par des méthodes directes de factorisation. Dans ce contexte, la taille de la matrice des facteurs constitue un des facteurs limitants principaux pour l'utilisation de méthodes directes de résolution. Nous supposons donc que la matrice des facteurs est de trop grande taille pour être rangée dans la mémoire principale du multiprocesseur et qu'elle a donc été écrite sur les disques locaux (hors-mémoire : OOC) d'une machine multiprocesseurs durant l'étape de factorisation. Nous nous intéressons à l'étude et au développement de techniques efficaces pour la phase de résolution après une factorization multifrontale creuse. La phase de résolution, souvent négligée dans les travaux sur les méthodes directes de résolution directe creuse, constitue alors un point critique de la performance de nombreuses applications scientifiques, souvent même plus critique que l'étape de factorisation. Cette thèse se compose de deux parties. Dans la première partie nous nous proposons des algorithmes pour améliorer la performance de la résolution hors-mémoire. Dans la deuxième partie nous pousuivons ce travail en montrant comment exploiter la nature creuse des seconds membres pour réduire le volume de données accédées en mémoire. Dans la première partie de cette thèse nous introduisons deux approches de lecture des données sur le disque dur. Nous montrons ensuite que dans un environnement parallèle le séquencement des tâches peut fortement influencer la performance. Nous prouvons qu'un ordonnancement contraint des tâches peut être introduit; qu'il n'introduit pas d'interblocage entre processus et qu'il permet d'améliorer les performances. Nous conduisons nos expériences sur des problèmes industriels de grande taille (plus de 8 Millions d'inconnues) et utilisons une version hors-mémoire d'un code multifrontal creux appelé MUMPS (solveur multifrontal parallèle). Dans la deuxième partie de ce travail nous nous intéressons au cas de seconds membres creux multiples. Ce problème apparaît dans des applications en electromagnétisme et en assimilation de données et résulte du besoin de calculer l'espace propre d'une matrice fortement déficiente, du calcul d'éléments de l'inverse de la matrice associée aux équations normales pour les moindres carrés linéaires ou encore du traitement de matrices fortement réductibles en programmation linéaire. Nous décrivons un algorithme efficace de réduction du volume d'Entrées/Sorties sur le disque lors d'une résolution hors-mémoire. Plus généralement nous montrons comment le caractère creux des seconds -membres peut être exploité pour réduire le nombre d'opérations et le nombre d'accès à la mémoire lors de l'étape de résolution. Le travail présenté dans cette thèse a été partiellement financé par le projet SOLSTICE de l'ANR (ANR-06-CIS6-010)
We consider the solution of very large systems of linear equations with direct multifrontal methods. In this context the size of the factors is an important limitation for the use of sparse direct solvers. We will thus assume that the factors have been written on the local disks of our target multiprocessor machine during parallel factorization. Our main focus is the study and the design of efficient approaches for the forward and backward substitution phases after a sparse multifrontal factorization. These phases involve sparse triangular solution and have often been neglected in previous works on sparse direct factorization. In many applications, however, the time for the solution can be the main bottleneck for the performance. This thesis consists of two parts. The focus of the first part is on optimizing the out-of-core performance of the solution phase. The focus of the second part is to further improve the performance by exploiting the sparsity of the right-hand side vectors. In the first part, we describe and compare two approaches to access data from the hard disk. We then show that in a parallel environment the task scheduling can strongly influence the performance. We prove that a constraint ordering of the tasks is possible; it does not introduce any deadlock and it improves the performance. Experiments on large real test problems (more than 8 million unknowns) using an out-of-core version of a sparse multifrontal code called MUMPS (MUltifrontal Massively Parallel Solver) are used to analyse the behaviour of our algorithms. In the second part, we are interested in applications with sparse multiple right-hand sides, particularly those with single nonzero entries. The motivating applications arise in electromagnetism and data assimilation. In such applications, we need either to compute the null space of a highly rank deficient matrix or to compute entries in the inverse of a matrix associated with the normal equations of linear least-squares problems. We cast both of these problems as linear systems with multiple right-hand side vectors, each containing a single nonzero entry. We describe, implement and comment on efficient algorithms to reduce the input-output cost during an outof- core execution. We show how the sparsity of the right-hand side can be exploited to limit both the number of operations and the amount of data accessed. The work presented in this thesis has been partially supported by SOLSTICE ANR project (ANR-06-CIS6-010)

Nous nous intéressons au développement d'un nouvel algorithme pour estimer la norme d'une matrice de manière incrémentale, à l'implantation d'un modèle de référence des Basic Linear Algebra Subprograms for sparse matrices (Sparse BLAS), et à la réalisation d'un nouveau gestionnaire de tâches pour MUMPS, un solveur multifrontal pour des architectures à mémoire distribuée. Notre méthode pour estimer la norme d'une matrice s'applique aux matrices denses et creuses. Elle peut s'avérer utile dans le cadre des factorisations QR, Cholesky, ou LU. Le standard Sparse BLAS définit des interfaces génériques. Nous avons été amenés à répondre aux questions concernant la représentation et la gestion des données. Le séquencement de tâches devient un enjeu important dès que nous travaillons sur un grand nombre de processeurs. Grâce à notre nouvelle approche, nous pouvons améliorer le passage a l'échelle du solveur MUMPS.

Le but de ce memoire est d'étudier les voies possibles pour minimiser le sur-coût des communications consécutif à la parallélisation d'algorithmes numériques sur machines parallèles à mémoire distribuée. La première voie explorée consiste à optimiser les schémas de communication des données et résultats mis en oeuvre dans les versions parallèles de noyaux de calcul. Nous proposons notamment de nouveaux algorithmes pour réaliser une transposition de matrices carrées allouées par blocs, sur différentes topologies de réseaux d'interconnexion. Nous avons également étudié le problème de l'échange total. Ce schéma de communication se retrouve fréquemment dans les versions parallèles d'algorithmes numériques (comme dans l'algorithme du gradient conjugué). Nous proposons des algorithmes efficaces d'échange total pour des topologies toriques. La deuxième voie qui a été explorée consiste à recouvrir les communications par du calcul. Nous avons étudié quelques principes algorithmiques de base permettant de masquer au mieux les communications. Ceux-ci sont basés, notamment, sur des techniques d'enchainement de phases de calcul et de communication, ainsi que sur le re-ordonnancement local de tâches afin d'optimiser le recouvrement. Ces techniques sont illustrées sur des algorithmes parallèles de calcul de transformée de Fourier. Les différentes implantations de ces algorithmes sur de nombreuses machines parallèles à mémoire distribuée (T3D de Cray, SP2 d'IBM, iPSC-860 et Paragon d'Intel) montrent le gain en temps d'exécution apporté par ces méthodes.

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses. 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. 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. Concernant la phase 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. 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.

Les grilles de calcul offrent une alternative intéressante pour les applications de calcul matriciel, grandes consommatrices de ressources de calcul et de mémoire. Néanmoins, les modèles de calcul de type 'task farming' inhérents à la plupart de ces systèmes rendent difficile une programmation efficace car la granularité de ces applications les rend inadaptées Dans cette thèse, nous proposons un modèle de programmation sur grilles de calcul non-dédiées basé sur la gestion de la localité des données; du réseau de communication jusqu'aux mémoires locales des noeuds de calcul, pour des applications matricielles basées sur des distributions par blocs. La technique de programmation out-of-core est introduite comme réponse aux problèmes de restriction mémoire sur les noeuds de calcul. Cette technique tend à minimiser l'impact des entrées/sorties nécessaires au calcul lorsque la taille des tâches excède la taille mémoire allouable. D'un autre côté, des techniques de placement persistant proposant l'anticipation de migration et le clouage des données permettent d'optimiser les besoins en communications et d'atteindre un bon niveau de performances par rapport aux implémentations classiques Les évaluations de performances ont été réalisées sur deux noyaux de l'algèbre matriciel sur de larges plateformes de calcul déployées sur trois sites géographiquement distribués, en France et au Japan, et sur la plateforme expérimentale Grid'5000

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l'utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d'entrées de l'inverse d'une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d'abord plusieurs schémas de stockage qui permettent de réduire significativement l'espace mémoire utilisé lors de la résolution, dans le cadre d'exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d'accès aux facteurs stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d'opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d'abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les techniques de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d'algorithmes de répartition et d'ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l'utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d'inconnues) et sur des machines massivement parallèles (jusqu'à quelques milliers de coeurs). Elles ont permis d'améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur).

Les réseaux de transport en commun sont des systèmes critiques pour le bon fonctionnement des villes. Ces systèmes doivent être planifiées et organisés avec rigueur en s'appuyant sur un dispositif de collecte et d'analyse des données.L'ambition de cette thèse est de s'interroger sur la pertinence de ce dispositif et sur l'apport des nouvelles sources de données passives. Quatre axes de recherches sont explorés : la mesure de la fraude, l'estimation de la demande sous forme de matrices origine-destination, l'étude de la variabilité des comportements de déplacements et la prédiction moyen-terme de la fréquentation. Ces travaux montrent que les données passives offrent des opportunités intéressantes pour améliorer la planification des réseaux de transport en commun
Public transit networks are critical systems for the proper functioning of cities.These systems must be rigorously planned and organized based on data collection and data analysis. The ambition of this thesis is to question the relevance of this mechanism and the contribution of new passive data sources. Four research axes are explored : the measurement of fare evasion, the estimation of demand in the form of origin-destination matrices, the study of the variability of travel behavior and the prediction of medium-term ridership. This work shows that passive data offer interesting opportunities to improve the planning of public transit networks

L'administration d'un système de stockage de données consiste à fournir à chaque application un espace de stockage ayant une qualité de service appropriée aux besoins de cette application : qualité exprimée en terme de capacité de stockage, de fiabilité et disponibilité du stockage, et de performances en temps d'accès et en débit (bande passante). Cette thèse se propose de faire l'étude de l'administration automatique d'un système de stockage hétérogène dédié au service d'objets multimédias. Après avoir étudié et effectué la classification des différentes politiques de placement conçus pour exploiter ce type de système de stockage, nous proposons un nouveau placement, l'EFLEX (Entrelacement FLEXible) qui permet d'exploiter conjointement la bande passante et la capacité de stockage du système. .
The data administration of storage system consists in providing to each application a storage space having a quality of service appropriate to the needs for this application: quality expressed in term of storage capacity, reliability and availability of storage, and of performances in access time and throughput (bandwidth). This thesis proposes to make the study of the automatic administration of a heterogeneous storage system dedicated to the service of multimedia objects. After having studied and having carried out the classification of the various policies of placement designed to exploit this type of storage system, we propose a new data placement, the EFLEX (Entrelacement FLEXible - that is "flexible interleaving") that makes it possible to jointly exploit the bandwidth and the storage capacity of the system. .

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses.
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.
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.
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.
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.