La vérification formelle de programme n'apporte pas de garantie complète si l'outil de vérification est incorrect. Et, si un programme est vérifié au niveau source, le compilateur pourrait introduire des bugs. Les compilateurs et vérifieurs actuels sont complexes. Pour simplifier l'analyse et la transformation de code, ils utilisent des représentations intermédiaires (IR) de programme, qui ont de fortes propriétés structurelles et sémantiques. Cette thèse étudie d'un point de vue sémantique et formel les IRs, afin de faciliter la preuve de ces outils. Nous étudions d'abord une IR basée registre du bytecode Java. Nous prouvons un théorème sur sa génération, explicitant ce que la transformation préserve (l'initialisation d'objet, les exceptions) et ce qu'elle modifie et comment (l'ordre d'allocation). Nous implantons l'IR dans Sawja, un outil de développement d'analyses statiques de Java. Nous étudions aussi la forme SSA, une IR au coeur des compilateurs et vérifieurs modernes. Nous implantons et prouvons en Coq un middle-end SSA pour le compilateur C CompCert. Pour la preuve des optimisations, nous prouvons un invariant sémantique de SSA clé pour le raisonnement équationnel. Enfin, nous étudions la sémantique des IRs de Java concurrent. La définition actuelle du Java Memory Model (JMM) autorise les optimisations aggressives des compilateurs et des architectures parallèles. Complexe, elle est formellement cassée. Ciblant les architectures x86, nous proposons un sous-ensemble du JMM intuitif et adapté à la preuve formelle. Nous le caractérisons par ses réordonnancements, et factorisons cette preuve sur les IRs d'un compilateur. / An end-to-end guarantee of software correctness by formal verification must consider two sources of bugs. First, the verification tool must be correct. Second, programs are often verified at the source level, before being compiled. Hence, compilers should also be trustworthy. Verifiers and compilers' complexity is increasing. To simplify code analysis and manipulation, these tools rely on intermediate representations (IR) of programs, that provide structural and semantic properties. This thesis gives a formal, semantic account on IRs, so that they can also be leveraged in the formal proof of such tools. We first study a register-based IR of Java bytecode used in compilers and verifiers. We specify the IR generation by a semantic theorem stating what the transformation preserves, e.g. object initialization or exceptions, but also what it modifies and how, e.g. object allocation. We implement this IR in Sawja, a Java static analysis toolbench. Then, we study the Static Single Assignment (SSA) form, an IR widely used in modern compilers and verifiers. We implement and prove in Coq an SSA middle-end for the CompCert C compiler. For the proof of SSA optimizations, we identify a key semantic property of SSA, allowing for equational reasoning. Finally, we study the semantics of concurrent Java IRs. Due to instruction reorderings performed by the compiler and the hardware, the current definition of the Java Memory Model (JMM) is complex, and unfortunately formally flawed. Targetting x86 architectures, we identify a subset of the JMM that is intuitive and tractable in formal proofs. We characterize the reorderings it allows, and factor out a proof common to the IRs of a compiler.

Le développement des systèmes massivement parallèles de type manycores permet d'obtenir une très grande puissance de calcul à bas coût énergétique. Cependant, l'exploitation des performances de ces architectures dépend de l'efficacité de programmation des applications. Parmi les différents paradigmes de programmation existants, celui à mémoire partagée est caractérisé par une approche intuitive dans laquelle tous les acteurs disposent d'un accès à un espace d'adressage global. Ce modèle repose sur l'efficacité du système à gérer les accès aux données partagées. Le système définit les règles de gestion des synchronisations et de stockage de données qui sont prises en charge par les protocoles de cohérence. Dans le cadre de cette thèse nous avons montré qu'il n'y a pas un unique protocole adapté aux différents contextes d'application et d'exécution. Nous considérons que le choix d'un protocole adapté doit prendre en compte les caractéristiques de l'application ainsi que des objectifs donnés pour une exécution. Nous nous intéressons dans ces travaux de thèse au choix des protocoles de cohérence en vue d'améliorer les performances du système. Nous proposons une plate-forme de compilation pour le choix et le paramétrage d'une combinaison de protocoles de cohérence pour une même application. Cette plate- forme est constituée de plusieurs briques. La principale brique développée dans cette thèse offre un moteur d'optimisation pour la configuration des protocoles de cohérence. Le moteur d'optimisation, inspiré d'une approche évolutionniste multi-objectifs (i.e. Fast Pareto Genetic Algorithm), permet d'instancier les protocoles de cohérence affectés à une application. L'avantage de cette technique est un coût de configuration faible permettant d'adopter une granularité très fine de gestion de la cohérence, qui peut aller jusqu'à associer un protocole par accès. La prise de décision sur les protocoles adaptés à une application est orientée par le mode de performance choisi par l'utilisateur (par exemple, l'économie d'énergie). Le modèle de décision proposé est basé sur la caractérisation des accès aux données partagées selon différentes métriques (par exemple: la fréquence d'accès, les motifs d'accès à la mémoire, etc). Les travaux de thèse traitent également des techniques de gestion de données dans la mémoire sur puce. Nous proposons deux protocoles basés sur le principe de coopération entre les caches répartis du système: Un protocole de glissement des données ainsi qu'un protocole inspiré du modèle physique du masse-ressort. / Manycores architectures consist of hundreds to thousands of embedded cores, distributed memories and a dedicated network on a single chip. In this context, and because of the scale of the processor, providing a shared memory system has to rely on efficient hardware and software mechanisms and data consistency protocols. Numerous works explored consistency mechanisms designed for highly parallel architectures. They lead to the conclusion that there won't exist one protocol that fits to all applications and hardware contexts. In order to deal with consistency issues for this kind of architectures, we propose in this work a multi-protocol compilation toolchain, in which shared data of the application can be managed by different protocols. Protocols are chosen and configured at compile time, following the application behaviour and the targeted architecture specifications. The application behaviour is characterized with a static analysis process that helps to guide the protocols assignment to each data access. The platform offers a protocol library where each protocol is characterized by one or more parameters. The range of possible values of each parameter depends on some constraints mainly related to the targeted platform. The protocols configuration relies on a genetic-based engine that allows to instantiate each protocol with appropriate parameters values according to multiple performance objectives. In order to evaluate the quality of each proposed solution, we use different evaluation models. We first use a traffic analytical model which gives some NoC communication statistics but no timing information. Therefore, we propose two cycle- based evaluation models that provide more accurate performance metrics while taking into account contention effect due to the consistency protocols communications.We also propose a cooperative cache consistency protocol improving the cache miss rate by sliding data to less stressed neighbours. An extension of this protocol is proposed in order to dynamically define the sliding radius assigned to each data migration. This extension is based on the mass-spring physical model. Experimental validation of different contributions uses the sliding based protocols versus a four-state directory-based protocol.

Dans la deuxième moitié du XVe siècle, les Croniques et conquestes de Charlemaine de David Aubert, l’Histoire de Charlemagne de Jean Bagnyon et l’anonyme Cronique associee ont cherché à rassembler et compiler les récits associés à Charlemagne. Composées dans des milieux différents à un moment où tant la réécriture en prose que le personnage de l’empereur étaient en vogue, ces compilations ont recyclé des chansons de geste et des chroniques des siècles précédents pour (re)constituer une histoire cohérente du personnage. Leur résultat est tantôt une biographie princière, tantôt un fragment cyclique qui s’arrête à la mort de l’empereur. La prose donne une forme nouvelle à ces récits inédits par leur organisation et leur extension, mais banals par leur matériau, recyclé de compilation en compilation. Par l’étude du contexte historique, et surtout la comparaison des versions proposées, dans leur récit, leurs articulations et leur présentation, nous souhaitons montrer comment la compilation est le reflet d’une lecture critique et organisée propre aux nouvelles habitudes de la fin du Moyen Âge. Le remaniement oriente sa propre lecture en fonction d’un public familier de la tradition littéraire : les morceaux de bravoure sont réécrits, comme l’épisode de Roncevaux, d’autres sont triés et oubliés en fonction du projet propre à chacune des œuvres. La compilation oscille entre la reconnaissance des textes et la déprise introduite par le nouvel ensemble. Au cœur de notre questionnement se trouve la double dynamique de fixation et de malléabilité de la mémoire, érigée au Moyen Âge comme modalité de l’activité littéraire. Nous proposons en annexe la transcription de la Cronique associee (ms Paris, Arsenal 3324) pour rendre ce texte plus facilement accessible. / In the second half of the fifteenth century, David Aubert’s Croniques et conquestes de Charlemaine, Jean Bagnyon’s Histoire de Charlemagne and the anonymous Cronique associee tried to collect and compile the stories linked to Charlemagne. Composed in various circles, when both rewriting in prose and Charlemagne himself were popular, these compilations recycled epic songs and chronicles written in the previous centuries to piece together a coherent story of this character. What results is either a princely biography or a cyclic fragment that is interrupted when the emperor dies. The prose form revives these stories whose structure and scope were novel but whose material had become trite after being compiled again and again. By studying the historical context, and especially by comparing the composition, narrative structure and presentation of different versions, I wish to show how the compilation reflects a critical and organized reading which epitomizes the new practices of the late Middle Ages. The rewriting process bears its own guidelines, depending on a reading public who is familiar with literary tradition: the purple patches, such as the Roncesvalles episode, are rewritten, while other passages are sorted away or forgotten, in keeping with the objective of each specific work. Through compilation, texts are either recognized or abandoned, blended within the new unit. At the heart of my investigation is the twofold dynamic of the fixation and malleability of memory, fashioned in the Middle Ages as a modality of literary activity. A transcript of the Cronique associee (ms Arsenal 3324) is appended to the dissertation in order to make this text more readily accessible.

OCaml est un langage fonctionnel statiquement typé, qui génère après inférence de types un arbre de syntaxe abstraite dans lequel chacun des noeuds est annoté avec un ensemble d’informations issues de cette inférence. Ces informations, en particulier les types inférés, constituent une preuve de typage de l’expression annotée.Ce manuscrit de thèse s’intéresse à la vérification de ces arbres annotés en les considérant comme des preuves de typages du programme, et décrit un ensemble de règles permettant d’en vérifier la cohérence. La formalisation de ces règles de vérification de preuves de types peut être vue comme une représensation du système de types du langage étudié.Cette thèse présente plusieurs aspects de la vérification d’arbres de syntaxe annotés. Le premier cas étudié est la formalisation d’un dérivé de MiniML où toutes les expressions sont annotées de manière théoriquement parfaite, et montre qu’il est possible d’écrire des règles de vérification de manière algorithmique, rendant directe la preuve de correction vis-à-vis de la spécification. La seconde partie s’intéresse à la formalisation de règles de vérification pour un sous-ensemble du premier langage intermédiaire d’OCaml, le TypedTree, accompagné d’un vérificateur implémentant ces règles. Ces règles constituent alors une représentation du système de types d’OCaml, document jusqu’alors inexistant, au mieux disséminé dans diverses publications. / OCaml is a statically typed programming language that generates typed annotated abstract syntax trees after type inference. Each of their nodes contains information derived from the inference like the inferred type and the environment used to find this information. These annotated trees can then be seen as typing proofs of the program.In this thesis, we introduce a consistency checking of type-annotated trees, considering them as typing proof, and we describe a set of rules that defines the consistency property.Such consistency checking rules can then be seen as a formalized representation of the type system, since consistency ensures the typing invariants of the language.This thesis introduces multiple aspects of checking type-annotated trees. First of all, it considers a simplified and ideal version of MiniML and formalizes a set of rules to check consistency. In this formalism, we consider ideally type-annotated trees, which might not be the case for OCaml typed trees. Such type checking rules are presented in an algorithmic form, reducing as much as possible the gap from formalism to implementation. As such, they ease the correction proof between the implementation of the type checker and the specification of the type system. The second part of this thesis is dedicated to the formalization of a set of rules for a subset of the OCaml annotated trees: the TypedTree. The formalism described in these chapters is implemented as a type checker working on large subset of the language, leaving the formalization of some aspects for a further work. These rules constitute a formalized representation of the OCaml type system in a single document.

La chanson québécoise actuelle paraît réconcilier la chanson dite «à texte» et la chanson populaire, comme ce fut le cas pour la chanson engagée des années 1970. Si le thème de l’engagement soutenait plusieurs œuvres chansonnières de cette décennie, celui de la mélancolie semble pouvoir définir une certaine tendance actuelle. Ce mémoire s’intéresse au thème de la mélancolie dans la chanson québécoise contemporaine et plus précisément dans les albums Tu m’intimides de Mara Tremblay, La forêt des mal-aimés de Pierre Lapointe et À Paradis City de Jean Leloup. À la fois auteurs, compositeurs et interprètes, ces trois artistes s’inscrivent dans le champ populaire de la chanson québécoise en créant des œuvres où le texte et la musique mettent la mélancolie en valeur. Dans cette étude, la mélancolie est étudiée en fonction de trois aspects, soit l’être mélancolique, la temporalité mélancolique et l’espace mélancolique. C’est à travers l’exploration de ces trois aspects que sont analysées les chansons du corpus, surtout à partir des textes, mais en considérant aussi certains éléments musicaux.

Software systems are growing ever larger. Early software systems were singular units developed by small teams of programmers writing in the same programming language. Modern software systems, on the other hand, consist of numerous interoperating components written by different teams and in different programming languages. While this more modular and diversified approach to software development has enabled us to build ever larger and more complex software systems, it has, however, made it harder to ensure the reliability and security of software systems. In this thesis we study and remedy the security flaws that arise when attempting to resolve the difference in abstractions between components written in high-level functional programming languages and components written in imperative low-level programming languages. High-level functional programming languages, treat computation as the evaluation of mathematical functions. Low-level imperative programming languages, on the contrary, provide programmers with features that enable them to directly interact with the underlying hardware. While these features help programmers write more efficient software, they also make it easy to write malware through techniques such as buffer overflows and return oriented programming. Concretely, we develop new run-time approaches for protecting components written in functional programming languages from malicious components written in low-level programming languages by making using of an emerging memory isolation mechanism.This memory isolation mechanism is called the Protected Module Architecture (PMA). Informally, PMA isolates the code and data that reside within a certain area of memory by restricting access to that area based on the location of the program counter. We develop these run-time protection techniques that make use of PMA for three important areas where components written in functional programming languages are threatened by malicious low-level components: foreign function interfaces, abstract machines and compilation. In everyone of these three areas, we formally prove that our run-time protection techniques are indeed secure. In addtion to that we also provide implementations of our ideas through a fully functional compiler and a well-performing abstract machine.

Despite the progress made in developing more advanced compilers for embedded systems, programming of embedded high-performance computing systems based on Digital Signal Processors (DSPs) is still a highly skilled manual task. This is true for single-processor systems, and even more for embedded systems based on multiple DSPs. Compilers often fail to optimise existing DSP codes written in C due to the employed programming style. Parallelisation is hampered by the complex multiple address space memory architecture, which can be found in most commercial multi-DSP configurations. This thesis develops an integrated optimisation and parallelisation strategy that can deal with low-level C codes and produces optimised parallel code for a homogeneous multi-DSP architecture with distributed physical memory and multiple logical address spaces. In a first step, low-level programming idioms are identified and recovered. This enables the application of high-level code and data transformations well-known in the field of scientific computing. Iterative feedback-driven search for “good” transformation sequences is being investigated. A novel approach to parallelisation based on a unified data and loop transformation framework is presented and evaluated. Performance optimisation is achieved through exploitation of data locality on the one hand, and utilisation of DSP-specific architectural features such as Direct Memory Access (DMA) transfers on the other hand. The proposed methodology is evaluated against two benchmark suites (DSPstone & UTDSP) and four different high-performance DSPs, one of which is part of a commercial four processor multi-DSP board also used for evaluation. Experiments confirm the effectiveness of the program recovery techniques as enablers of high-level transformations and automatic parallelisation. Source-to-source transformations of DSP codes yield an average speedup of 2.21 across four different DSP architectures. The parallelisation scheme is – in conjunction with a set of locality optimisations – able to produce linear and even super-linear speedups on a number of relevant DSP kernels and applications.

.

.

Cette thèse consiste en une édition critique de la troisième partie d'un livre de François de Belleforest, intitulé Histoire Universelle du Monde (première édition 1570). Surtout connu pour ses traductions diverses, Belleforest est également l'auteur de nombreux ouvrages traitant d'histoire et de géographie. L'Histoire Universelle du Monde, et plus spécifiquement la « Description de l'Europe » est un écrit particulièrement intéressant car il présage des travaux postérieurs de Belleforest, tout en apportant un éclairage sur l?esprit de son temps et ses opinions personnelles, qu'elles soient politiques ou religieuses. En outre, il permet de faire le point sur les connaissances historiques et géographiques de la Renaissance, sur les sources employées par les savants et sur les mythes fondateurs qui perdurent ou sont au contraire combattus. Enfin, ce texte qui se veut une relation neutre des événements survenus en Europe depuis l'Antiquité jusqu'au seizième siècle et une description objective des nations qui la composent est teintée d'un catholicisme militant et laisse transparaître une forme précoce de nationalisme. La thèse comporte le texte complet, amendé et annoté de la « Description de l'Europe ». Elle comprend également trois bibliographies, un index commenté des écrivains cités comme sources par l'auteur, un glossaire et une introduction. Cette dernière vise à présenter la vie et l'oeuvre de François de Belleforest, à expliquer ses visées lors de la rédaction de l'ouvrage, à éclairer le lecteur sur les particularités du style de l'auteur et les difficultés de la grammaire propre à la Renaissance, et enfin à exposer les choix qui ont présidé à la toilette du texte. / This doctoral thesis is a critical edition of the third part of a François de Belleforest's Histoire Universelle du Monde (first edition 1570). Known primarily because of his translations of various works, Belleforest also authored numerous books on topics related to history and geography. The Histoire Universelle du Monde, and specifically the "Description de l'Europe" provide a particularly interesting piece of writing, as it foretells themes found in Belleforest's later works, throws light on the spirit of the Renaissance and illustrate the author's personal political and religious beliefs. Besides, it summarizes historical and geographical knowledge from the Renaissance era, informs us about the authorities used as references by scholars and identifies founding myths that continue to cause persistent controversy. Although Belleforest's text pretends to be a neutral account of events that occurred in Europe from Antiquity to the sixteenth century and is presented as an objective description of its countries, it is in fact a display of militant Catholicism and nationalism. This thesis includes the full emended and annotated text of the "Description de l'Europe". It also contains three bibliographies, a commentated index of specific authorities quoted by Belleforest, a glossary and an introduction. The latter intends to introduce the life and works of Belleforest, and examines his intentions for having written this book. The reader will become enlightened about the characteristics of Belleforest's writing style, the Renaissance era grammatical difficulties, and the essential rules of language that governed the edits in this thesis.