Dans cette thèse, nous décrivons la conception et l'implémentation d'une plate-forme logicielle de spéculation de threads, ou fils d'exécution, appelée VMAD, pour "Virtual Machine for Advanced Dynamic analysis and transformation", et dont la fonction principale est d'être capable de paralléliser de manière spéculative un nid de boucles séquentiel de différentes façons, en ré-ordonnançant ses itérations. La transformation à appliquer est sélectionnée au cours de l'exécution avec pour objectifs de minimiser le nombre de retours arrières et de maximiser la performance. Nous effectuons des transformations de code en appliquant le modèle polyédrique que nous avons adapté à la parallélisation spéculative au cours de l'exécution. Pour cela, nous construisons au préalable un patron de code qui est "patché" par notre "runtime", ou support d'exécution logiciel, selon des informations de profilage collectées sur des échantillons du temps d'exécution. L'adaptabilité est assurée en considérant des tranches de code de tailles différentes, qui sont exécutées successivement, chacune étant parallélisée différemment, ou exécutée en séquentiel, selon le comportement des accès à la mémoire observé. Nous montrons, sur plusieurs programmes que notre plate-forme offre de bonnes performances, pour des codes qui n'auraient pas pu être traités efficacement par les systèmes spéculatifs de threads proposés précédemment. / In this thesis, we present a Thread-Level Speculation (TLS) framework whose main feature is to speculatively parallelize a sequential loop nest in various ways, to maximize performance. We perform code transformations by applying the polyhedral model that we adapted for speculative and runtime code parallelization. For this purpose, we designed a parallel code pattern which is patched by our runtime system according to the profiling information collected on some execution samples. We show on several benchmarks that our framework yields good performance on codes which could not be handled efficiently by previously proposed TLS systems.

Os modos de interação de silsesquioxano poliédrico oligomérico (POSS) de gaiolas fechadas com distintos grupos funcionais foram avaliados na nanoestruturação de polipropileno isotático (iPP) via processamento reativo. Analisaram-se POSS com grupos substituintes isobutila, alila e vinila em concentrações de 0,5, 1, 2 e 5%m misturados a iPP fundido utilizando peróxido de dicumila (DCP) como iniciador. Na caracterização dos nanocompósitos foram utilizadas diversas técnicas. A morfologia foi avaliada através de cromatografia por exclusão de tamanho, espectroscopia de infravermelho com transformada de Fourier, microscopia de transmissão e difração de raios X. O comportamento viscoelástico dos materiais no estado fundido foi medido por reologia oscilatória e no estado sólido por análises dinâmico-mecânicas. As transições térmicas foram levantadas tanto por análises dinâmico-mecânicas como por calorimetria diferencial de varredura. Modificações morfológicas e viscoelásticas importantes foram observadas para os nanocompósitos em dependência do tipo e teor de POSS empregado. A adição do Octaisobutil-POSS (OI) sugere ação estabilizante radicalar e lubrificante para este POSS. Os efeitos da incorporação do Alilisobutil-POSS (AL) indicam que este atuou como agente plastificante em função da concentração. Com Octavinil-POSS (OV) os nanocompósitos parecem adquirir estrutura ramificada ou interligada em dependência da concentração. A ativação radicalar promovida pelo DCP mostrou-se fundamental na enxertia de alguns POSS. Assim, a forma e intensidade das interações entre nanocargas e matriz foram definidas pelos grupos funcionais e concentração dos POSS. Alterações observadas na morfologia, propriedades térmicas e viscoelásticas são resultantes dessas formas e graus de interação. Deste modo, foi possível propor mecanismos de interação e arranjos morfológicos entre iPP, DCP e POSS pela avaliação do conjunto de resultados obtidos. / Submitted by Ana Guimarães Pereira (agpereir@ucs.br) on 2015-10-06T16:44:04Z No. of bitstreams: 1 Dissertacao Sergio Graniero Echeverrigaray.pdf: 3289598 bytes, checksum: f804be75d287c3fd55eeb0690f47dfab (MD5) / Made available in DSpace on 2015-10-06T16:44:04Z (GMT). No. of bitstreams: 1 Dissertacao Sergio Graniero Echeverrigaray.pdf: 3289598 bytes, checksum: f804be75d287c3fd55eeb0690f47dfab (MD5) / The interaction modes of polyhedral oligomeric silsesquioxane (POSS) of closed cages with distinct functional groups were evaluated on isotactic polypropylene (iPP) nanostructuration via reactive processing. POSS were analyzed with isobutyl, allyl and vinyl substituent groups in concentrations of 0.5, 1, 2 and 5m% mixed with melting iPP using dicumil peroxide (DCP) as initializer. Several techniques were used to characterize the nanocomposites. The morphology was evaluated through size exclusion chromatography, Fourier transformed infrared spectroscopy, transmission electron microscopy and X-ray diffraction. The samples viscoelastic behavior in melting state was measured by oscillatory rheometry and in solid state by dynamic mechanical analysis. The thermal transitions were obtained through dynamic mechanical analysis and differential scanning calorimetry. Important morphology and viscoelastic modifications were observed in nanocomposites by dependency on the type and content of POSS used. The addition of OctaIsobutyl-POSS (OI) suggests lubricant and radicalar stabilizing action for this POSS. The AllylIsobutyl-POSS (AL) incorporation effects indicate that this one acted as plasticizing agent in function of concentration. With OctaVinyl-POSS (OV), the nanocomposites seem to acquire ramified or interlinked structure in dependency on concentration. The radicalar activation promoted by DCP was decisive in the grafting efficiency for some POSS. Therefore, the mode and the interaction intensity between nanoparticles and polymeric matrix were defined by functional groups and POSS concentration. Changes observed in morphology, thermal and viscoelastic properties as in solid state as in melting state are results of these modes and interaction degrees. It was possible to propose interaction mechanisms and morphology arrangements among iPP, DCP and POSS by evaluation of the obtained results as a whole.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / The concept of treewidth was introduced by Robertson and Seymour. Treewidth may be defined as the size of the largest vertex set in a tree decomposition. Recent results show that several NP-Complete problems can be solved in polynomial time, or linear, when restricted to graphs with small treewidth. In our bibliographic research, we focus attention on the calculation of lower bounds for the treewidth and we described, in our dissertation, some of the principal results already available in the literature. We realize that linear-integer formulations for determining the treewidth are very limited in the literature and there are no studies available on the polyhedra associated with them. The Elimination Order Formulation (EOF) has been proposed by Koster and Bodlaender. It is based on orderly disposal of vertices and the relationship between the treewidth of a graph and its chordalizations. As a result of our study, we present a simplification of EOF formulation, we show that the polyhedron associated with this simplification is affine isomorphic to the EOF formulation. We determine the dimension of the polyhedron associated with the simplification, we briefly present a set of very simple facets and we introduce, analyse and demonstrate be a facet, some more complex inequalities. / O conceito de largura em Ãrvore (âtreewidthâ) foi introduzido por Robertson e Seymour. A largura em Ãrvore de um grafo G à o mÃnimo k tal que G pode ser decomposto em uma DecomposiÃÃo em Ãrvore (DEA) com cada subconjunto de vÃrtice com no mÃximo k+1 vÃrtices. Resultados recentes demonstram que vÃrios problemas NP-Completos podem ser resolvidos em tempo polinomial, ou ainda linear, quando restritos a grafos com largura em Ãrvore pequena. Em nossa pesquisa bibliogrÃfica, focamos a atenÃÃo no cÃlculo de limites inferiores para a largura em Ãrvore e descrevemos, em nossa dissertaÃÃo, alguns dos resultados jà disponÃveis na literatura. NÃs percebemos que formulaÃÃes lineares-inteiras para a determinaÃÃo da largura em Ãrvore sÃo limitadas na literatura e nÃo hà estudos disponÃveis sobre os poliedros associados a elas. A formulaÃÃo por ordem de eliminaÃÃo (EOF) foi proposta por Koster e Bodlaender. Ela à baseada na eliminaÃÃo ordenada de vÃrtices e na relaÃÃo entre a largura em Ãrvore de um grafo e suas cordalizaÃÃes. Como resultado de nosso estudo, apresentamos uma simplificaÃÃo da formulaÃÃo EOF, demonstramos que o poliedro associado a simplificaÃÃo à afim-isomÃrfico ao da formulaÃÃo EOF, verificamos a dimensÃo do poliedro associado à simplificaÃÃo, apresentamos brevemente um rol de facetas muito simples desse poliedro e, em seguinte, introduzimos, analisamos e demonstramos ser faceta algumas desigualdades mais complexas.

Os modos de interação de silsesquioxano poliédrico oligomérico (POSS) de gaiolas fechadas com distintos grupos funcionais foram avaliados na nanoestruturação de polipropileno isotático (iPP) via processamento reativo. Analisaram-se POSS com grupos substituintes isobutila, alila e vinila em concentrações de 0,5, 1, 2 e 5%m misturados a iPP fundido utilizando peróxido de dicumila (DCP) como iniciador. Na caracterização dos nanocompósitos foram utilizadas diversas técnicas. A morfologia foi avaliada através de cromatografia por exclusão de tamanho, espectroscopia de infravermelho com transformada de Fourier, microscopia de transmissão e difração de raios X. O comportamento viscoelástico dos materiais no estado fundido foi medido por reologia oscilatória e no estado sólido por análises dinâmico-mecânicas. As transições térmicas foram levantadas tanto por análises dinâmico-mecânicas como por calorimetria diferencial de varredura. Modificações morfológicas e viscoelásticas importantes foram observadas para os nanocompósitos em dependência do tipo e teor de POSS empregado. A adição do Octaisobutil-POSS (OI) sugere ação estabilizante radicalar e lubrificante para este POSS. Os efeitos da incorporação do Alilisobutil-POSS (AL) indicam que este atuou como agente plastificante em função da concentração. Com Octavinil-POSS (OV) os nanocompósitos parecem adquirir estrutura ramificada ou interligada em dependência da concentração. A ativação radicalar promovida pelo DCP mostrou-se fundamental na enxertia de alguns POSS. Assim, a forma e intensidade das interações entre nanocargas e matriz foram definidas pelos grupos funcionais e concentração dos POSS. Alterações observadas na morfologia, propriedades térmicas e viscoelásticas são resultantes dessas formas e graus de interação. Deste modo, foi possível propor mecanismos de interação e arranjos morfológicos entre iPP, DCP e POSS pela avaliação do conjunto de resultados obtidos. / The interaction modes of polyhedral oligomeric silsesquioxane (POSS) of closed cages with distinct functional groups were evaluated on isotactic polypropylene (iPP) nanostructuration via reactive processing. POSS were analyzed with isobutyl, allyl and vinyl substituent groups in concentrations of 0.5, 1, 2 and 5m% mixed with melting iPP using dicumil peroxide (DCP) as initializer. Several techniques were used to characterize the nanocomposites. The morphology was evaluated through size exclusion chromatography, Fourier transformed infrared spectroscopy, transmission electron microscopy and X-ray diffraction. The samples viscoelastic behavior in melting state was measured by oscillatory rheometry and in solid state by dynamic mechanical analysis. The thermal transitions were obtained through dynamic mechanical analysis and differential scanning calorimetry. Important morphology and viscoelastic modifications were observed in nanocomposites by dependency on the type and content of POSS used. The addition of OctaIsobutyl-POSS (OI) suggests lubricant and radicalar stabilizing action for this POSS. The AllylIsobutyl-POSS (AL) incorporation effects indicate that this one acted as plasticizing agent in function of concentration. With OctaVinyl-POSS (OV), the nanocomposites seem to acquire ramified or interlinked structure in dependency on concentration. The radicalar activation promoted by DCP was decisive in the grafting efficiency for some POSS. Therefore, the mode and the interaction intensity between nanoparticles and polymeric matrix were defined by functional groups and POSS concentration. Changes observed in morphology, thermal and viscoelastic properties as in solid state as in melting state are results of these modes and interaction degrees. It was possible to propose interaction mechanisms and morphology arrangements among iPP, DCP and POSS by evaluation of the obtained results as a whole.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Cette thèse étudie, au niveau continu et au niveau discret sur des maillages polyédriques, les équations de transport tridimensionnelles scalaire et vectorielle. Ces équations sont constituées d'un terme diffusif, d'un terme advectif et d'un terme réactif. Dans le cadre des systèmes de Friedrichs, l'analyse mathématique est effectuée dans les espaces du graphe associés aux espaces de Lebesgue. Les conditions de positivité usuelles sur le tenseur de Friedrichs sont étendues au niveau continu et au niveau discret afin de prendre en compte les cas d'intérêt pratique où ce tenseur prend des valeurs nulles ou raisonnablement négatives. Un nouveau schéma convergeant à l'ordre 3/2 est proposé pour le problème d'advection-réaction scalaire en considérant des degrés de liberté scalaires associés aux sommets du maillage. Deux nouveaux schémas considérant également des degrés de libertés aux sommets sont proposés pour le problème de transport scalaire en traitant de manière robuste les différents régimes dominants. Le premier schéma converge à l'ordre 1/2 si les effets advectifs sont dominants et à l'ordre 1 si les effets diffusifs sont dominants. Le second schéma améliore la précision de ce schéma en convergeant à l'ordre 3/2 lorsque les effets advectifs sont dominants. Enfin, un nouveau schéma convergeant à l'ordre 1/2 est obtenu pour le problème d'advection-réaction vectoriel en considérant un seul et unique degré de liberté scalaire sur chaque arête du maillage. La précision et les performances de tous ces schémas sont examinées sur plusieurs cas tests utilisant des maillages polyédriques tridimensionnels / This thesis analyzes, at the continuous and at the discrete level on polyhedral meshes, the scalar and the vector transport problems in three-dimensional domains. These problems are composed of a diffusive term, an advective term, and a reactive term. In the context of Friedrichs systems, the continuous problems are analyzed in Lebesgue graph spaces. The classical positivity assumption on the Friedrichs tensor is generalized so as to consider the case of practical interest where this tensor takes null or slightly negative values. A new scheme converging at the order 3/2 is devised for the scalar advection-reaction problem using scalar degrees of freedom attached to mesh vertices. Two new schemes considering as well scalar degrees of freedom attached to mesh vertices are devised for the scalar transport problem and are robust with respect to the dominant regime. The first scheme converges at the order 1/2 when advection effects are dominant and at the order 1 when diffusion effects are dominant. The second scheme improves the accuracy by converging at the order 3/2 when advection effects are dominant. Finally, a new scheme converging at the order 1/2 is devised for the vector advection-reaction problem considering only one scalar degree of freedom per mesh edge. The accuracy and the efficiency of all these schemes are assessed on various test cases using three-dimensional polyhedral meshes

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées. / Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations.

It is a well known fact that scientific programs spend most of their running time in executing loops operating on arrays. The polyhedral model is a mathematical framework which was designed to optimize this process. Its use in automatic paralyzation of nested loops goes back to the work of Kuck (1978), who showed that the domain of nested loop with affine lower and upper bounds can be described in terms of a polyhedron, and the seminal work of Karp, Miller and Winograd (1967) on scheduling systems of uniform recurrence equations. For a long period of time Graphite (it is part of the GNU Compiler Collection) was relying on CLooG library to produce SSA intermediate representation from the polyhedral model. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. That is why the following goal was chosen: Creation of SSA generator based on Integer Set Library. / Как известно, большая часть времени исполнения программ, связанных с научными расчетами, тратится на выполнение циклов и взаимодействие с массивами. С целью оптимизации этого процесса был разработан математический фреймворк — полиэдральная модель. Первые её применения можно встретить в работах Дэвида Кука и Ричарда Карпа от 1978 и 1967 соответственно. С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Такими примерами служат библиотеки CLooG и ISL. В отличие от библиотеки CLooG, специализированной для генерации кода из поэлидарльной модели, библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева. В рамках магистерской работы была поставлена следующая цель: Cоздание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

La physique actuelle cherche, à côté des expériences, à vérifier et déduire les lois de la nature en simulant les modèles physiques sur d'énormes ordinateurs. Cette thèse explore comment accélérer ces simulations en améliorant les programmes qui les font tourner. L'application de référence est la chromodynamique quantique sur réseaux (LQCD pour "Lattice Quantum Chromodynamics"), une branche de la théorie quantique des champs, tournant sur le plus récent des supercalculateurs d'IBM, le Blue Gene/Q.Dans un premier temps, on améliore le code source de tmLQCD, un programme de LQCD, dont l'opération clef pour la performance est un stencil à 8 points en dimension 4. On étudie deux stratégies d'optimisation différentes: la première se donne comme priorité d'améliorer la localité spatiale et temporelle; la seconde utilise le préchargement matériel de flux de données. Sur le Blue Gene/Q, la première stratégie permet d'atteindre 20% de la performance crête théorique. La seconde, avec jusqu'à 54% de la performance crête est bien meilleure mais utilise 4 fois plus de mémoire car elle stocke les résultats dans l'ordre où les utilise le stencil suivant, ce qui requiert de dupliquer des données. Les autres techniques exploitées sont la programmation directe du système de communication (appelé MUSPI chez IBM), un mécanisme allégé de gestion des threads, le préchargement explicite de certaines données (à l'aide de l'instruction dcbt) et la vectorisation manuelle (en utilisant les instructions SIMD de largeur 4; appelé QPX par IBM). Le préchargement de liste et la mémoire transactionnelle - deux nouveaux mécanismes du Blue Gene/Q - n'améliorent pas les performances.Dans un second temps, on présente la réalisation d'une extension appelé Molly au compilateur LLVM, pour optimiser automatiquement le programme, et plus précisément la distribution des données et des calculs entre les nœuds d'un cluster tel que le Blue Gene/Q. Molly représente les tableaux par des polyèdres entiers et utilise l'extension existante Polly qui représente les boucles et les instructions par des polyèdres. Partant de la spécification de la distribution des données et de l'emplacement des calculs, Molly ajoute le code qui gère les flots de données entre les nœuds de calcul. Molly peut aussi permuter l'ordre des données en mémoire. La tâche principale de Molly est d'agréger les données dans des ensembles qui sont envoyés dans le même tampon au même destinataire, pour éviter l'overhead des transferts trop petits. Nous présentons un algorithme qui minimise le nombre de transferts pour des boucles non-paramétrées, basé sur les antichaînes du flot des données. De plus, nous implémentons une heuristique qui tient compte de la manière dont le programmeur a écrit son code. Les primitives de communication asynchrone sont insérées juste après que les données soient disponibles - respectivement juste avant qu'elles soient utilisées. Une bibliothèque runtime implémente ces primitives en utilisant MPI. Molly gère la distribution pour tout code représentable dans le modèle polyédrique, mais fonctionne mieux pour du code à stencil tel LQCD. Compilé avec Molly, le code LQCD atteint 2,5% de la performance crête. L'écart de performance est surtout dû au fait que les autres optimisations ne sont pas faites, par exemple la vectorisation. Les versions futures de Molly pourraient aussi gérer efficacement les codes non à stencil et exploiter les autres optimisations qui ont rendu le code LQCD optimisé à la main si rapide. / Motivated by modern day physics which in addition to experiments also tries to verify and deduce laws of nature by simulating the state-of-the-art physical models using oversized computers, this thesis explores means of accelerating such simulations by improving the simulation programs they run. The primary focus is Lattice Quantum Chromodynamics (QCD), a branch of quantum field theory, running on IBM newest supercomputer, the Blue Gene/Q.In a first approach, the source code of tmLQCD, a Lattice QCD program, is improved to run faster on the Blue Gene machine. Its most performance-relevant operation is a 8-point stencil in 4 dimensional space. Two different optimization strategies are perused: One with the priority of improving spatial and temporal locality, and a second making use of the hardware's data stream prefetcher. On Blue Gene/Q the first strategy reaches up to 20% of the peak theoretical floating point operation performance of that machine. The second strategy with up to 54% of peak is much faster at the cost of using 4 times more memory by storing the data in the order they will be used in the next stencil operation, duplicating data where necessary.Other techniques exploited are direct programming of the messaging hardware (called MUSPI by IBM), a low-overhead work distribution mechanism for threads, explicit data prefetching of data (using dcbt instruction) and manual vectorization (using QPX; width-4 SIMD instructions). Hardware-based list prefetching and transactional memory - both distinct and novel features of the Blue Gene/Q system -- did not improve the program's performance.The second approach is the newly-written LLVM compiler extension called Molly which optimizes the program itself, specifically the distribution of data and work between the nodes of a cluster machine such as Blue Gene/Q. Molly represents arrays using integer polyhedra and uses another already existing compiler extension Polly which represents statements and loops using polyhedra. When Molly knows how data is distributed among the nodes and where statements are executed, it adds code that manages the data flow between the nodes. Molly can also permute the order of data in memory. Molly's main task is to cluster data into sets that are sent to the same target into the same buffer because single transfers involve a massive overhead. We present an algorithm that minimizes the number of transfers for unparametrized loops using anti-chains of data flows. In addition, we implement a heuristic that takes into account how the programmer wrote the code. Asynchronous communication primitives are inserted right after the data is available respectively just before it is used. A runtime library implements these primitives using MPI.Molly manages to distribute any code that is representable by the polyhedral model, but does so best for stencils codes such as Lattice QCD. Compiled using Molly, the Lattice QCD stencil reaches 2.5% of the theoretical peak performance. The performance gap is mostly because all the other optimizations are missing, such as vectorization. Future versions of Molly may also effectively handle non-stencil codes and use make use of all the optimizations that make the manually optimized Lattice QCD stencil so fast.