Academic literature on the topic 'Combinatoire des coeurs'

Malgré sa complexité de résolution, le problème de SATisfaisabilité est une excellente et compétitive approche pour résoudre un large éventail de problèmes. Cela génère une forte demande pour une résolution de SAT haute performance de la part des industriels. Au fil du temps, de nombreuses approches et optimisations différentes ont été développées pour résoudre le problème plus efficacement. Ces innovations ont été faites sans prendre en compte le développement des micro processeurs actuels qui voient le nombre de leur cœurs de calcul augmenter. Cette thèse présente un nouveau type d'algorithme parallèle basé sur une forte collaboration où un processus riche est en charge de l'évaluation de l'arbre de recherche et où des processus pauvres fournissent des informations partielles ou globales, heuristiques ou logiques afin de simplifier la tâche du riche. Pour concrétiser ce solveur et le rendre efficace, nous avons étendu la notion de chemin de guidage à celle d'arbre de guidage. L'arbre de recherche est totalement partagé en mémoire centrale et tous les processeurs peuvent y travailler en même temps. Ce nouveau solveur est appelé MTSS pour Multi-Threaded SAT Solver. De plus, nous avons implémenté une tâche pour les processus riche et pauvres qui leur permet d'exécuter un solveur SAT externe, et cela, avec ou sans échange de lemmes afin de paralléliser tous types de solveurs (dédiés aux formules industrielles ou aléatoires). Ce nouvel environnement facilite la parallélisation des futures implémentations pour SAT. Quelques exemples et expérimentations, avec ou sans échange de lemmes, de parallélisation de solveurs externes sont présentées, mais aussi des résultats sur les performances de MTSS. Il est intéressant de noter que certaines accélérations sont super linéaires.

Les algorithmes Branch and Bound (B&B) sont attractifs pour la résolution exacte de problèmes d'optimisation combinatoire (POC) par exploration d'un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille (exemple : benchmarks de Taillard pour FSP) même en utilisant le calcul sur grilles informatiques [Mezmaz et al., IEEE IPDPS'2007]. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d'aujourd'hui [TOP500 ] est requis pour traiter effi cacement de telles instances. Le dé fi est alors d'exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l'implémentation des ces algorithmes pour la résolution de POC de grande taille sur (larges) plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d'ordonnancement Flow-Shop (FSP) est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l'arbre de recherche est hautement irrégulier (en forme et en taille) et très large (milliards de milliards de noeuds), et que l'opérateur d'évaluation des bornes est exorbitant en temps de calcul (environ 97% du temps de B&B). Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU (GB&B) dans laquelle seul l'opérateur d'évaluation est exécuté sur GPU. L'approche traite deux dé fis: la divergence de threads et l'optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu'à ( 100) sont obtenues sur Nvidia Tesla C2050. L'analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l'objectif de la deuxième contribution est d'étendre l'approche (LL-GB&B) a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d'élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l'arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d'atteindre des accélérations allant jusqu'à ( 160) pour les plus grandes instances. La troisième contribution consiste à étudier l'utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente (RLL-GB&B) et une coopérative (PLL-GB&B). Dans le premier cas, le processus d'exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l'approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l'exploration. L'utilisation combinée du multi-coeur et du GPU a montré que l'utilisation de RLL-GB&B n'est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu'à (36%) par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 (certains sites) ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l'algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l'approche B&B@Grid proposée dans [Mezmaz et al., IEEE IPDPS'2007]. B&B@Grid répartit les unités de travail (sous-espaces de recherche codés par des intervalles) entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L'approche combinée nous a permis de résoudre à l'optimalité et e fficacement les instances (20 20) de Taillard.

Dans cette thèse de doctorat, nous avons, dans un premier temps, étudié la décomposition en composantes irréductibles du lieu des points fixes sous l’action d’un sous-groupe fini Γ de SL2(C) de la variété de carquois de Nakajima du carquois de Jordan. La variété de carquois associé au carquois de Jordan est isomorphe soit au schéma ponctuel de Hilbert dans C2 soit à l’espace de Calogero-Moser. Nous avons décrit ces composantes irréductibles à l’aide de variétés de carquois du carquois de McKay associé au sous-groupe fini Γ. Nous nous sommes ensuite intéressés à la combinatoire découlant de l’ensemble d’indexation de ces composantes irréductibles en utilisant une action du groupe de Weyl affine introduite par Nakajima. De plus, nous avons construit un modèle combinatoire lorsque Γ est de type D, qui est le seul cas original et remarquable. En effet, si Γ est de type A, un tel travail a déjà été fait par Iain Gordon et si Γ est de type E, nous avons montré que les points fixes qui sont aussi des points fixes du tore diagonal maximal de SL2(C) sont les idéaux monomiaux du schéma ponctuel de Hilbert dans C2 indexés par les partitions en escaliers. De manière plus précise, si Γ est de type D, nous avons obtenu un modèle de l’ensemble indexant les composantes irréductibles contenant un point fixe du tore maximal diagonal de SL2(C) en termes de partitions symétriques. Enfin, si n est un entier plus grand que 1, en utilisant la classification des résolutions projectives et symplectiques de la singularité (C2)n/Γn où Γn est le produit en couronne du groupe symétrique Sn des n premiers entiers et de Γ, nous avons obtenu une description de toutes ces résolutions projectives et symplectiques en termes de composantes irréductibles du lieu des Γ-points fixes du schéma ponctuel de Hilbert dans C2.Dans un second temps, nous nous sommes intéressés à la restriction de deux fibrés vectoriels au-dessus d’une composante irréductible du lieu des Γ-points fixes du schéma de Hilbert dans C2 fixée. Le premier fibré est le fibré tautologique dont nous avons exprimé la restriction en termes de fibrés tautologiques de Nakajima sur la variété de carquois du carquois de McKay associée à la composante irréductible fixée. Le second fibré vectoriel est le fibré de Procesi. Ce fibré a été introduit par Marc Haiman dans ces travaux démontrant la conjecture n!. Nous avons étudié les fibres de ce fibré en tant que (Sn × Γ)-module. Dans la première partie du chapitre de cette thèse consacré au fibré de Procesi, nous avons démontré un théorème de réduction qui exprime le (Sn × Γ)-module associé à la fibre de la restriction du fibré de Procesi au-desus d’une composante irréductible C du lieu des Γ-points fixes du schéma de Hilbert de n points dans C2 comme l’induit de la fibre de la restriction du fibré de Procesi au-dessus d’une composante irréductible du lieu des Γ-points fixes du schéma de Hilbert de k points dans C2 où l’entier k ≤ n est explicite et dépend de la composante irréductible C et de Γ. Ce théorème est ensuite démontré avec d’autres outils dans deux cas particuliers pour Γ de type A. Enfin, lorsque Γ est de type D, certaines formules explicites de réduction des fibres de la restriction du fibré de Procesi au lieu des Γ-point fixes ont étéobtenues.Pour finir, si l est un entier plus grand que 1, alors dans le cas où Γ est le sous-groupe cyclique d’ordre l contenu dans le tore maximal diagonal de SL2(C) noté µl, le théorème de réduction restreint l’étude des fibres du fibré de Procesi au-dessus du lieu des µl-points fixes du schéma ponctuel de Hilbert dans C2 à l’étude des fibres au-dessus des points du schéma de Hilbert associés aux idéaux monomiaux paramétrés par les l-cœurs. Les (Sn × µl)-modules que l’on obtient semble être reliés à l’espace de Fock de l’algèbre de Kac-Moody ˆsll(C). Une conjecture dans ce sens est énoncée dans le dernier chapitre
In this doctoral thesis, first of all, we have studied the decomposition into irreducible components of the fixed point locus under the action of Γ a finite subgroup of SL2(C) of the Nakajima quiver variety of Jordan’s quiver. The quiver variety associated with Jordan’s quiver is either isomorphic to the punctual Hilbert scheme in C2 or to the Calogero-Moser space. We have described the irreducible components using quiver varieties of McKay’s quiver associated with the finite subgroup Γ. We were then interested in the combinatorics coming out of the indexing set of these irreducible components using an action of the affine Weyl group introduced by Nakajima. Moreover, we have constructed a combinatorial model when Γ is of type D, which is the only original and remarkable case. Indeed, when Γ is of type A, such work has already been done by Iain Gordon and if Γ is of type E, we have shown that the fixed points that are also fixed under the maximal diagonal torus of SL2(C) are the monomial ideals of the punctual Hilbert scheme in C2 indexed by staircase partitions. To be more precise, when Γ is of type D, we have obtained a model of the indexing set of the irreducible components containing a fixed point of the maximal diagonal torus of SL2(C) in terms of symmetric partitions. Finally, if n is an integer greater than 1, using the classification of the projective, symplectic resolutions of the singularity (C2)n/Γn where Γn is the wreath product of the symmetric group on n letters Sn with Γ, we have obtained a description of all such resolutions in terms of irreducible components of the Γ-fixedpoint locus of the Hilbert scheme of points in C2.Secondly, we were interested in the restriction of two vector bundles over a fixed irreducible component of the Γ-fixed point locus of the punctual Hilbert scheme in C2. The first vector bundle is the tautological vector bundle that we have expressed the restriction in terms of Nakajima’s tautological vector bundle on the quiver variety of McKay’s quiver associated with the fixed irreducible component. The second vector bundle is the Procesi bundle. This vector bundle was introduced by Marc Haiman in his work proving the n! conjecture. We have studied the fibers of this bundle as (Sn × Γ)-module. In the first part of the chapter of this thesis dedicated to the Procesi bundle, we have shown a reduction theorem that expresses the (Sn × Γ)-module associated with the fiber of the restriction of the Procesi bundle over an irreducible component C of the Γ-fixed point locus of Hilbert scheme of n points in C2 as the induced of the fiber of the restriction of the Procesi bundle over an irreducible component of the Γ-fixed point locus of the Hilbert scheme of k points in C2 where k ≤ n is explicit and depends on the irreducible component C and Γ. This theorem is then proven with other tools in two edge cases when Γ is of type A. Finally, when Γ is of type D, some explicit reduction formulas of the restriction of the Procesi bundle to the Γ-fixed point locus have been obtained.To finish, if l is an integer greater than 1, then in the case where Γ is the cyclic group of order l contained in the maximal diagonal torus of SL2(C) denoted by µl, the reduction theorem restricts the study of the fibers of the Procesi bundle over the µl-fixed points of the punctual Hilbert scheme in C2 to the study of the fibers over points in the Hilbert scheme associated with monomial ideals parametrized by the l-cores. The (Sn × Γ)-module that one obtains seems to be related to the Fock space of the Kac-Moody algebra ˆsll(C). A conjecture in this direction has been stated in the last chapter

Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire
This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above

Cette thèse décrit une nouvelle stratégie pour le développement de composés organométalliques bioactifs, reposant sur l'assemblage combinatoire de sous-chimiothèques (A et B) indépendantes mais complémentaires et capables de coordiner un cœur métallique M, pour former des complexes A-M-B ligands potentiels de biomolécules. La coordination des métaux, bien adaptée à la production de diversité moléculaire est couramment utilisée en chimie médicinale, en médecine nucléaire diagnostique et thérapeutique. Parmi les éléments utilisables, le rhénium et le technétium sont des métaux de choix pour le développement notre stratégie d'assemblage en raison de leurs propriétés chimiques et radiochimiques et de l'analogie de structure de leurs complexes. Notre principal objectif à été de valider cette stratégie in vitro sur une protéine modèle, la cyclophiline hCyp-18 bien connue au laboratoire. C'est une peptidyl-prolyl isomérase reconnaissant principalement des ligands peptidiques ou pseudo-peptidiques, via deux sous-sites fonctionnellement indépendants liant d'une part le résidu proline (sous-site S1-S1') et d'autre part l'extrémité p-nitroanilide (sous-site S2'-S3') des peptides modèles. Nous avons donc développé puis validé in vitro une nouvelle stratégie de synthèse de ligands de protéines par assemblage combinatoire autour du cœur oxorhénium. Nous avons aussi sélectionné de nouveaux ligands de hCyp-18 présentant une meilleure affinité que le peptide de référence Suc-AAPF-pNA. A partir des chimiothèques de modules déjà préparées, nous avons également initié la sélection des ligands de hCyp-18 par chimie combinatoire dynamique
This manuscript describes the development of a novel strategy for the synthesis of organometallic compounds usable as protein ligands, pharmacophores and tracers for molecular imaging through combinatorial assembly of independent modules. Each supramolecular entity is composed of two molecules A and B which are able to coordinate a metal core M in a complementary and unambiguous way to give a metal complex A-M-B. Among a wide variety of metal cores utilized in supramolecular chemistry and nuclear medicine, we selected the oxorhenium and oxotechnetium cores which feature similar interesting chemical and radiochemical properties. The main goal of this work was to validate the strategy in vitro using a model protein, the human cyclophilin hCyp-18, a peptidylprolyl isomerase (PPIases) implicated in numerous biological processes and diseases. Moreover, hCyp-18 possesses two functionally independent subsites which have been thoroughly characterized by NMR, X-ray crystallography and structure activity relationship studies. We developed novel metallated cyclophilin ligands through oxorhenium coordination of independent peptide moieties which reconstitute a canonic PPIase substrate, tetrapeptide Suc-AAPF-pNA. Assembly and biochemical screening of two libraries led to the selection of 2 complexes which exhibit affinities improved by one order of magnitude relative to the reference peptide. Moreover, a Cys-pNA oxorhenium coordinate devoid of proline analog displayed an interesting affinity for cyclophilin. We also initiated the evolutionary selection of cyclophilin ligands via a dynamic combinatorial chemistry

Ce mémoire-création se propose d'explorer des voies théâtrales alternatives, qui seraient susceptibles de traiter autrement la réalité, cherchant non seulement à la réfléchir -refléter et questionner -dans tout ce qu'elle a de multiple, mais aussi à la faire advenir concrètement sur scène. Notre volonté première était de «désobéir» aux codes du théâtre représentationnel, et ce, en tentant de mettre en jeu des possibles: les potentialités de l'individu contemporain, un individu complexe, habité d'«autres», mais aussi les éléments imprévisibles de la présentation échappant au contrôle du créateur. Pour ce faire, un long processus d'exploration, en salle de répétition, avec quatre acteurs-performeurs, a permis de dégager deux hypothèses de réponse: le hasard et le bricolage pourraient-ils être les moteurs d'une pluralité scénique qui serait en adéquation avec la pluralité de la réalité -celle d'une société et celle d'un individu -, libérée des dogmes de l'uniformisation actuelle? Par leur ouverture à l'hétérogénéité, mais aussi par leur caractère paradoxal, voire contradictoire, ces deux modalités de composition se sont avérées à la fois riches et surprenantes. La réflexion qui suit tente de cerner les formes et effets de l'utilisation du bricolage et du hasard dans une composition scénique, de même que leurs conséquences sur le rôle et les fonctions du metteur en scène et des acteurs. Par bricolage, nous entendons principalement le collage -superposition d'actions dans un même tableau scénique -et le montage - juxtaposition de différents tableaux de nature hétérogène. Cette modalité est assumée à la fois par le metteur en scène en période d'élaboration de la création et par les acteurs, devenus bricoleurs au présent dans le temps même de la présentation devant public. L'une des hypothèses sous-jacentes à cette recherche reposait sur le fait que l'aspect bricolé d'une création peut donner du jeu aux possibles non seulement durant le processus de création, mais aussi pendant la présentation, influençant le contexte de réception et permettant aux spectateurs de devenir à leur tour bricoleurs de sens. L'utilisation du hasard va également dans cette direction: d'une part, le hasard peut agir comme élément structurant, par l'usage de procédés aléatoires; d'autre part, il peut être intégré à même le jeu des acteurs qui doivent composer avec l'imprévisible. Dans un tel processus, le rôle du metteur en scène est forcément à redéfinir, car à travers l'usage du bricolage et du hasard, celui-ci fait l'épreuve du paradoxe, se tenant sur un fragile point d'équilibre entre contrôle et abandon. Tout au long de ce mémoire, à la fois lors de l'exploration pratique et de la réflexion théorique, ce qui est traqué consiste, en fait, en une définition de ce que nous appellerons le «théâtre performatif». Genre multiple s'il en est, le théâtre performatif correspond pour nous à un champ privilégié de recherche sur les relations multiples entre la scène et le réel. Par son rapport à l'action, par la priorité qu'il accorde à la présence de l'acteur-performeur, par son ancrage dans la réalité, par son aspect événementiel, le théâtre performatif se révèle non seulement une conclusion probante, mais une introduction riche en promesses et en expérimentations futures, pour mettre en jeu les possibles de la matérialité scénique et les possibles des détours imprévus que peut prendre la vie. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Théâtre, Performance, Composition, Hasard, Bricolage, Pluralité, Combinatoire.