La thèse veut démontrer que toutes les compositions contenues dans L'Art de la Fugue possèdent entre elles des liaisons strictes et essentielles qui vont au-delà de la simple coprésence et/ou élaboration du même sujet, en créant une unité et une progression de la complexité technique dans son évolution. À travers une analyse détaillée de toutes les fugues sur trois niveaux: rythmique, harmonique et morphologique, notre objectif est d’identifier et de cataloguer tous les éléments spécifiques qui créent cette unité, afin d'arriver à la présentation du système des techniques compositionnelles utilisées par le compositeur. Nous proposons des nouveaux outils analytiques pour la compréhension des problématiques majeures liées à l’œuvre, l’ordonnancement du recueil et sa destination instrumentale. / The thesis aims to demonstrate that all the compositions contained in the “Art of Fugue” are bound together by a pattern of tight and essential connections, which go beyond an unstructured co-existence or a simple elaboration of a common subject: they form one unit and are ordered in a sequence of increasing technical complexity.The author makes a detailed analysis of all Fugues at three levels, Rhythm, Harmony and Morphology; he identifies and classifies all elements that create the unit: he presents the method and suite of techniques employed by the composer; finally, he proposes new analytical tools for the comprehension of the main issues related.

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

Ce travail propose de montrer de quelle manière Clément Marot a conçu son métier d’auteur. À cette fin, il prend d’abord appui sur une reconstruction synthétique et critique de la carrière du poète, des premiers engagements auprès de Nicolas de Neufville ou (peut-être) de la reine Claude, jusqu’au service de François Ier, afin d’en comprendre les contraintes, et la façon dont elles conditionnent l’écriture (I). Suit logiquement l’étude des représentations du métier d’auteur dans l’œuvre, c’est-à-dire du discours par lequel le poète se met en scène en tant qu’auteur ; celle-ci comprend ainsi l’analyse de la signature marotique ainsi que des choix lexicaux et métaphoriques qui caractérisent le regard que le poète pose sur son activité (II). Marot faisant partie des premiers écrivains à s’impliquer fortement dans le processus d’impression, la troisième partie est consacrée à l’enquête bibliographique qui s’intéresse à la totalité des éditions marotiques autorisées : elle en présente les différents acteurs et propose une description matérielle des ouvrages, afin de reconstituer l’histoire de leur fabrication et de déterminer la mesure de la collaboration du poète (III). Les conclusions de l’enquête sont exploitées dans la dernière partie pour mettre en évidence le sens du projet poétique et éditorial des recueils considérés. L’étude de leur ordonnancement en est la clé principale, Marot s’emparant du critère de l’organisation pour se réapproprier une œuvre qui lui échappe en raison même de son succès, et faire finalement de la presse un instrument essentiel pour réaliser ses intentions (IV). / This study offers to show how Clément Marot conceived of his role as an author. For this purpose, it begins with a synthetic and critical narrative of the poet’s career, from the first appointments, under the patronage of Nicolas de Neufville or (maybe) Queen Claude de France, to the service of Francis I, so as to bring to light the constraints of the office and the way they influenced his writing process (I). The study then explores the representations of the author’s work in the text, i.e. the way the poet portrays himself as an author; it includes the analysis of Marot’s signature and of the lexical and metaphorical choices which define the way the poet looks at his own activity (II). Because Marot is one of the first writers to get fully involved in the printing process, the third part is devoted to a bibliographical inquiry dealing with all the authorized editions of Marot’s works: it presents the various actors involved and offers a material description of the books, in order to reconstruct the story of their making and to determine the extent of the poet’s collaboration in the process of their production (III). The findings of the inquiry are used in the last part to highlight the import of Marot’s poetical and editorial project. To this end, the study of the books’ dispositio provides the main key, as Marot uses it to reclaim a work that eludes him because of its very success, managing to turn the printing press into an instrument at the service of his auctorial intentions (IV).

La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème. / The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Les travaux menés dans cette thèse de doctorat s’inscrivent dans le cadre d’un effort pluslarge d’automatisation des systèmes de simulation industriels. Dans l’industrie aéronautique,et plus particulièrement au sein d’Airbus, l’application historique de la simulation est laformation des pilotes. Il existe aussi des utilisations plus récentes dans la conception desystèmes, ainsi que dans l’intégration de ces systèmes. Ces dernières utilisations exigent untrès haut degré de représentativité, là où historiquement le plus important était le ressenti dupilote. Les systèmes sont aujourd’hui divisés en plusieurs sous-systèmes qui sont conçus, implémentéset validés indépendamment, afin de maintenir leur contrôle malgré l’augmentationde leurs complexités et la réduction des temps de mise sur le marché. Airbus maîtrise déjà lasimulation de ces sous-systèmes, ainsi que leurs intégrations en simulation. Cettemaîtriseest empirique, les spécialistes de la simulation reprennent l’ordonnancement d’intégrationsprécédentes, et l’adaptent à une nouvelle intégration. C’est un processus qui peut parfois êtrechronophage, et qui peut introduire des erreurs. Les tendances actuelles de l’industrie sont à la flexibilité des moyens de production, àl’intégration d’outils logistiques permettant le suivi, à l’utilisation d’outils de simulation enproduction, et à l’optimisation des ressources. Les produits sont de plus en plus souvent desitérations d’anciens produits améliorés, et les tests et simulations intégrés à leurs cycles de vie.Travailler de manière empirique dans une industrie qui nécessite de la flexibilité estune contrainte, et il est aujourd’hui important de facilement modifier des simulations. Laproblématique est donc de mettre en place des méthodes et outils permettant a priori degénérer des ordonnancements de simulations représentatifs.Afin de répondre à ce problème, nous avons mis en place une méthode permettant de décrireles composants d’une simulation, la manière dont cette simulation pourra être exécutée,ainsi que des fonctions permettant de générer des ordonnancements. Par la suite, nous avonsimplémenté un outil afin d’automatiser la recherche d’ordonnancement, en se basant sur desheuristiques. Enfin nous avons testé et vérifié notre méthode et outils sur des cas d’étudesacadémiques et industriels. / The work carried out in this Ph.D. thesis is part of a broader effort to automate industrialsimulation systems. In the aeronautics industry, and more especially within Airbus, thehistorical application of simulation is pilot training. There are also more recent uses in thedesign of systems, as well as in the integration of these systems. These latter applicationsrequire a very high degree of representativeness, where historically the most important factorhas been the pilot’s feeling. Systems are now divided into several subsystems that are designed, implemented andvalidated independently, in order tomaintain their control despite the increase in their complexity,and the reduction in time-to-market. Airbus already has expertise in the simulationof these subsystems, as well as their integration into a simulation. This expertise is empirical;simulation specialists use the previous integrations schedulings and adapt it to a newintegration. This is a process that can sometimes be time-consuming and can introduce errors.The current trends in the industry are towards flexible production methods, integrationof logistics tools for tracking, use of simulation tools in production, as well as resourcesoptimization. Products are increasingly iterations of older, improved products, and tests andsimulations are increasingly integrated into their life cycles. Working empirically in an industry that requires flexibility is a constraint, and nowadays itis essential to facilitate the modification of simulations. The problem is, therefore, to set upmethods and tools allowing a priori to generate representative simulation schedules.In order to solve this problem, we have developed a method to describe the elementsof a simulation, as well as how this simulation can be executed, and functions to generateschedules. Subsequently, we implemented a tool to automate the scheduling search, based onheuristics. Finally, we tested and verified our method and tools in academic and industrialcase studies.

Une séparation existe de longue date entre les domaines de la compilation et de l'ordonnancement temps-réel. Si ces deux domaines ont le même objectif - la construction d'implantations correctes - la séparation se justifie historiquement par des différences significatives entre les modèles et les méthodes utilisés. Cependant, avec la complexification des applications et du materiel qui les exécute, les problèmes étudiés dans ces deux domaines se confondent désormais largement. Dans cette thèse, nous nous concentrons sur la génération automatique de code pour des systèmes de contrôle embarqué incluant des contraintes complexes (notamment temps-réel). A ces fins, nous défendons l'idée qu'il est profitable de fournir un effort commun de recherche entre ces deux communautés. En adaptant une technique de compilation au problème d'ordonnancement temps réel d'applications sur des architectures multiprocessurs, nous montrons à la fois les difficultés inhérentes à cet effort commun, mais aussi les possibles avancées qu'il porte. En effet, nous montrons que l'adaptation de techniques d'optimisation à de nouveaux objectifs, dans un contexte différent facilite le développement de systèmes de meilleure qualité. Nous proposons d'utiliser les formalismes et langages synchrones comme base formelle commune dans ce travail d'adaptation. Ceux-cis étendent naturellement les modèles classiques utilisés pour l'ordonnancement temps réel (graphes de tâches dépendentes) et la compilation (SSA et graphes de dépendence de données), et fournissent également des techniques efficaces pour la manipulation de structures de contrôle complexes. Nous avons implanté nos résultats dans le compilateur LoPhT. / There is a long standing separation between the fields of compiler construction and real-time scheduling. While both fields have the same objective - the construction of correct implementations – the separation was historically justified by significant differences in the models and methods that were used. Nevertheless, with the ongoing complexification of applications and of the hardware of the execution platforms, the objects and problems studied in these two fields are now largely overlapping. In this thesis, we focus on the automatic code generation for embedded control systems with complex constraints, including hard real-time requirements. To this purpose, we advocate the need for a reconciled research effort between the communities of compilation and real-time systems. By adapting a technique usually used in compilers (software pipelining) to the system-level problem of multiprocessor scheduling of hard real-time applications, we shed light on the difficulties of this unified research effort, but also show how it can lead to real advances. Indeed we explain how adapting techniques for the optimization of new objectives, in a different context, allows us to develop more easily systems of better quality than what was done until now. In this adaptation process, we propose to use synchronous formalisms and languages as a common formal ground. These can be naturally seen as extensions of classical models coming from both real-time scheduling (dependent task graphs) and compilation (single static assignment and data dependency graphs), but also provide powerful techniques for manipulating complex control structures. We implemented our results in the LoPhT compiler.

Au milieu des années deux mille, le développement de microprocesseurs a atteint un point à partir duquel l'augmentation de la fréquence de fonctionnement et la complexification des micro-architectures devenaient moins efficaces en termes de consommation d'énergie, poussant ainsi la densité d'énergie au delà du raisonnable. Par conséquent, l'industrie a opté pour des architectures multi-cœurs intégrant plusieurs unités de calcul sur une même puce. Les sytèmes hautes performances d'aujourd'hui sont composés de centaines de cœurs et les systèmes futurs intègreront des milliers d'unités de calcul. Afin de fournir une bande passante mémoire suffisante dans ces systèmes, la mémoire vive est distribuée physiquement sur plusieurs contrôleurs mémoire avec un accès non-uniforme à la mémoire (NUMA). Des travaux de recherche récents ont identifié les modèles de programmation à base de tâches dépendantes à granularité fine comme une approche clé pour exploiter la puissance de calcul des architectures généralistes massivement parallèles. Toutefois, peu de recherches ont été conduites sur l'optimisation dynamique des programmes parallèles à base de tâches afin de réduire l'impact négatif sur les performances résultant de la non-uniformité des accès à la mémoire. L'objectif de cette thèse est de déterminer les enjeux et les opportunités concernant l'exploitation efficace de machines many-core NUMA par des applications à base de tâches et de proposer des mécanismes efficaces, portables et entièrement automatiques pour le placement de tâches et de données, améliorant la localité des accès à la mémoire ainsi que les performances. Les décisions de placement sont basées sur l'exploitation des informations sur les dépendances entre tâches disponibles dans les run-times de langages de programmation à base de tâches modernes. Les évaluations expérimentales réalisées reposent sur notre implémentation dans le run-time du langage OpenStream et un ensemble de benchmarks scientifiques hautes performances. Enfin, nous avons développé et implémenté Aftermath, un outil d'analyse et de débogage de performances pour des applications à base de tâches et leurs run-times. / Within the last decade, microprocessor development reached a point at which higher clock rates and more complex micro-architectures became less energy-efficient, such that power consumption and energy density were pushed beyond reasonable limits. As a consequence, the industry has shifted to more energy efficient multi-core designs, integrating multiple processing units (cores) on a single chip. The number of cores is expected to grow exponentially and future systems are expected to integrate thousands of processing units. In order to provide sufficient memory bandwidth in these systems, main memory is physically distributed over multiple memory controllers with non-uniform access to memory (NUMA). Past research has identified programming models based on fine-grained, dependent tasks as a key technique to unleash the parallel processing power of massively parallel general-purpose computing architectures. However, the execution of task-paralel programs on architectures with non-uniform memory access and the dynamic optimizations to mitigate NUMA effects have received only little interest. In this thesis, we explore the main factors on performance and data locality of task-parallel programs and propose a set of transparent, portable and fully automatic on-line mapping mechanisms for tasks to cores and data to memory controllers in order to improve data locality and performance. Placement decisions are based on information about point-to-point data dependences, readily available in the run-time systems of modern task-parallel programming frameworks. The experimental evaluation of these techniques is conducted on our implementation in the run-time of the OpenStream language and a set of high-performance scientific benchmarks. Finally, we designed and implemented Aftermath, a tool for performance analysis and debugging of task-parallel applications and run-times.

Cette thèse vise à établir un système informatique permettant le calcul de structures musicales, leurs représentations/manipulations à un niveau compositionnel, ainsi que leurs diffusions interactives. Elle constitue une étude à la croisée de multiples domaines informatiques : la modélisation des systèmes discrets, l'ordonnancement, la conception logicielle ou encore les interfaces homme-machine. Nous proposons une architecture dans laquelle la modification des programmes peut affecter leurs sorties, y compris durant la phase de restitution, tout en conservant les avantages compositionnels d'une approche temps-différé. Nous introduisons également de nouveaux outils pour planifier leur exécution grâce à la conception de scenarios dynamiques, que nous appelons la meta-composition. Les mécanismes de calcul et de restitution sont entremêlés : la restitution peut être affectée par des calculs qu'elle a elle-même déclenchés. Les différents résultats décrits dans ce manuscrit sont implantés dans le logiciel de composition OpenMusic, qui peut alors modéliser les ¿uvres à la fois comme des structures musicales et comme des programmes en continuelle exécution. / This thesis aims at designing a computer system enabling the computation of musical structures, their presentation/handling on a compositional side, and their interactive rendering. It is a study at the crossroads between several computer science research fields : discrete systems modeling, scheduling, software design and human-computer interfaces. We propose an architecture where program editing can affect their outputs, including during the rendering phase, while preserving the compositional benefits of a deferred-time approach. Compositions are therefore considered as continually running programs, where computation and rendering mechanisms are interleaved. We introduce new tools and interfaces to arrange their execution through time thanks to dynamic temporal scenario scripting, which we call meta-composing. The different results described in this manuscript are implemented in the computer-aided composition environment OpenMusic.

Ce travail s’inscrit dans le domaine de l’ordonnancement à base de programmation par contraintes. Dans ce cadre, la contrainte de ressource la plus fréquemment rencontrée est la cumulative, qui permet de modéliser des processus se déroulant de manière parallèle.Nous étudions dans cette thèse la contrainte cumulative en nous aidant d’outils rarement utilisés en programmation par contraintes (analyse polyédrale, dualité de la programmation linéaire, dualité de la géométrie projective) et proposons deux contributions pour le domaine.Le renforcement cumulatif est un moyen de générer des contraintes cumulatives redondantes plus serrées, de manière analogue à la génération de coupes en programmation linéaire entière. Il s'agit ici de l'un des premiers exemples de contrainte globale redondante.Le Raisonnement Énergétique est une propagation extrêmement puissante pour la contrainte cumulative, avec jusque-là une complexité élevée en O(n^{3}). Nous proposons un algorithme qui calcule cette propagation avec une complexité O(n^{2}log n), ce qui constitue une amélioration significative de cet algorithme connu depuis plus de 25 ans. / This work falls in the scope of constraint-based scheduling. In this framework, the most frequently encountered resource constraint is the cumulative, which enables the modeling of parallel processes.In this thesis, we study the cumulative constraint with the help of tools rarely used in constraint programming (polyhedral analysis, linear programming duality, projective geometry duality) and propose two contributions for the domain.Cumulative strengthening is a means of generating tighter redundant cumulative constraints, analogous to the generation of cuts in integer linear programming. This is one of the first examples of a redundant global constraint.Energy Reasoning is an extremely powerful propagation for cumulative constraint, with hitherto a high complexity of O(n^{3}). We propose an algorithm that computes this propagation with a O(n^{2}log n) complexity, which is a significant improvement of this algorithm known for more than 25 years.

La demande des systèmes de communication sans fil pour des débits élevés continue d'augmenter, et il n'y a pas de signes que cette tendance va se ralentir. Trois des techniques les plus importantes qui ont émergé pour répondre à de telles demandes sont l'OFDMA, le relais coopératif et le MIMO. Afin d'utiliser pleinement les capacités des systèmes appliquant de telles techniques, il est essentiel de développer des algorithmes efficaces d'ordonnancement et, plus généralement, des algorithmes efficaces d'allocation de ressources. Les études classiques sur ce sujet examinent des systèmes où les demandes de données des utilisateurs ne sont pas prises en considération et/ou un CSI parfait et complet est supposée être disponible pour le mécanisme d'ordonnancement. Cependant, dans la pratique, différentes limitations peuvent entraîner l'absence d'une connaissance parfaite et/ou complète du CSI, telles que les ressources limitées pour le feedback, le co^ut de sondage et le retard dans le processus de feedback.Par conséquent, dans cette thèse nous examinons les problèmes d'ordonnancement et de feedback sous des considérations réalistes concernant la connaissance du CSI. L'analyse est effectuée au niveau des paquets et considère la dynamique des files d'attente avec des processus d'arrivée arbitraires, et où la mesure de performance principale que nous adoptons est la stabilité des files d'attente. La première partie de la thèse considère un système MIMO multipoint à multipoint utilisant le mode TDD, tout en supposant un backhaul à capacité limitée et en tenant compte du coût du feedback. En ce qui concerne la technique de gestion de l'interférence, nous appliquons l'alignement d'interférence (IA) si plus d'une paire sont actives et SVD si une seule paire est active. La deuxième partie de la thèse considère un système OFDMA avec plusieurs utilisateurs et canaux, où un feedback retardé et limité est pris en compte. Deux scénarios sont étudiés, à savoir le système sans relais et le système avec relais. Pour ce dernier, nous considérons une imperfection supplémentaire supposant que les utilisateurs ont une connaissance incomplète des coefficients du fading entre la station de base et le relais. / Demand of wireless communication systems for high throughputs continues to increase, and there are no signs this trend is slowing down. Three of the most prominent techniques that have emerged to meet such demands are OFDMA, cooperative relaying and MIMO. To fully utilize the capabilities of systems applying such techniques, it is essential to develop eficient scheduling algorithms and, more generally, eficient resource allocation algorithms. Classical studies on this subject investigate in much detail settings where the data requests of the users are not taken into consideration or where the perfect and full CSI is assumed to be available for the scheduling mechanism. In practice, however, diferent limitations may result in not having perfect or full CSI knowledge, such as limited feedback resources, probing cost and delay in the feedback process. Accordingly, in this thesis we examine the problems of scheduling and feedback allocations under realistic considerations concerning the CSI knowledge. Analysis is performed at the packet level and considers the queueing dynamics in the systems with arbitrary arrival processes, where the main performance metric we adopt is the stability of the queues. The first part of the thesis considers a multi-point to multi-point MIMO system with TDD mode under limited backhaul capacity and taking into account the feedback probing cost. Regarding the interference management technique, we apply interference alignment (IA) if more than one pair are active and SVD if only one pair is active. The second part of the thesis considers a multiuser multichannel OFDMA-like system where delayed and limited feedback is accounted for. Two scenarios are investigated, namely the system without relaying and the system with relaying. For the latter one, an additional imperfection we account for is that the users have incomplete knowledge of the fading coeficients between the base-station and the relay.