Cette thèse présente l'étude et l'implantation de deux méthodes pour le placement automatique de circuits intégrés. Un circuit intégré peut être considéré comme un ensemble de blocs et une liste d'interconnexions entre ces blocs. Le probleme du placement consiste a disposer les blocs sur la surface hôte en respectant diverses contraintes et en optimisant des critères comme la surface occupée et la longueur totale de connexions. Les méthodes présentées ici sont toutes les deux guidées par l'optimisation de la connectique. La première fait appel a une technique d'analyse de données, l'analyse d'un tableau de proximités. Dans un premier temps, des proximités sont definies entre les blocs de façon a refléter un agencement ideal en fonction de la connectique. L'utilisation de l'atp permet alors d'obtenir une disposition planaire des blocs respectant au mieux les proximités qui ont été définies. L'analyse effectuée fait le point sur les diverses façons de définir les proximités entre les blocs, ainsi que sur les traitements ultérieurs destines a l'obtention d'un placement réalisable. Les qualités et les limitations de cette approche sont ensuite discutées. La seconde methode est connue sous le nom de placement par bipartitionnements successifs. L'ensemble des blocs du circuit et la surface hôte sont ainsi bipartitionnes récursivement jusqu'à ce que l'emplacement de chaque bloc soit déterminé. A partir des algorithmes existants, des heuristiques ont été mises au point afin de permettre la prise en compte de contraintes supplémentaires comme le traitement des plots d'entrées-sorties ou des blocs pré-fixes. L'expérimentation a permis de valider ces heuristiques et de comparer les résultats du placement a ceux fournis par la première methode

Dans cette thèse, nous nous intéressons à la résolution parallèle de grands systèmes linéaires creux. Nous nous focalisons plus particulièrement sur les solveurs linéaires creux hybrides directs itératifs tels que HIPS, MaPHyS, PDSLIN ou ShyLU, qui sont basés sur une décomposition de domaine et une approche « complément de Schur ». Bien que ces solveurs soient moins coûteux en temps et en mémoire que leurs homologues directs, ils ne sont néanmoins pas exempts de surcoûts. Dans une première partie, nous présentons les différentes méthodes de réduction de la consommation mémoire déjà existantes et en proposons une nouvelle qui n’impacte pas la robustesse numérique du précondionneur construit. Cette technique se base sur une atténuation du pic mémoire par un ordonnancement spécifique des tâches de calcul, d’allocation et de désallocation des blocs, notamment ceux se trouvant dans les parties « couplage » des domaines.Dans une seconde partie, nous nous intéressons à la question de l’équilibrage de la charge que pose la décomposition de domaine pour le calcul parallèle. Ce problème revient à partitionner le graphe d’adjacence de la matrice en autant de parties que de domaines désirés. Nous mettons en évidence le fait que pour avoir un équilibrage correct des temps de calcul lors des phases les plus coûteuses d’un solveur hybride tel que MaPHyS, il faut à la fois équilibrer les domaines en termes de nombre de noeuds et de taille d’interface locale. Jusqu’à aujourd’hui, les partitionneurs de graphes tels que Scotch et MeTiS ne s’intéressaient toutefois qu’au premier critère (la taille des domaines) dans le contexte de la renumérotation des matrices creuses. Nous proposons plusieurs variantes des algorithmes existants afin de prendre également en compte l’équilibrage des interfaces locales. Toutes nos modifications sont implémentées dans le partitionneur Scotch, et nous présentons des résultats sur de grands cas de tests industriels. / In this thesis, we focus on the parallel solving of large sparse linear systems. Our main interestis on direct-iterative hybrid solvers such as HIPS, MaPHyS, PDSLIN or ShyLU, whichrely on domain decomposition and Schur complement approaches. Althrough these solvers arenot as time and space consuming as direct methods, they still suffer from serious overheads. Ina first part, we thus present the existing techniques for reducing the memory consumption, andwe present a new method which does not impact the numerical robustness of the preconditioner.This technique reduces the memory peak by doing a special scheduling of computation, allocation,and freeing tasks in particular in the Schur coupling blocks of the matrix. In a second part,we focus on the load balancing of the domain decomposition in a parallel context. This problemconsists in partitioning the adjacency graph of the matrix in as many domains as desired. Wepoint out that a good load balancing for the most expensive steps of an hybrid solver such asMaPHyS relies on the balancing of both interior nodes and interface nodes of the domains.Through, until now, graph partitioners such as MeTiS or Scotch used to optimize only thefirst criteria (i.e., the balancing of interior nodes) in the context of sparse matrix ordering. Wepropose different variations of the existing algorithms to improve the balancing of interface nodesand interior nodes simultaneously. All our changes are implemented in the Scotch partitioner.We present our results on large collection of matrices coming from real industrial cases.