Search

International audience

International audience; We give a number of theoretical and practical methods related to the computation of L-functions, both in the local case (counting points on varieties over finite fields, involving in particular a detailed study of Gauss and Jacobi sums), and in the global case (for instance Dirichlet L-functions, involving in particular the study of inverse Mellin transforms); we also give a number of little-known but very useful numerical methods, usually but not always related to the computation of L-functions.

In this course, we introduce the main notions relative to the classical theory of modular forms. A complete treatise in a similar style can be found in the author’s book joint with Stromberg (Cohen and Stromberg, Modular Forms: A Classical Approach, Graduate Studies in Math. 179, American Math. Soc. (2017) [1]).

International audience; We begin by explaining how to compute Fourier expansions at all cusps of any modular form of integral or half-integral weight thanks to a theorem of Borisov-Gunnells and explicit expansions of Eisenstein series at all cusps. Using this, we then give a number of methods for computing arbitrary Petersson products. All this is available in the current release of the Pari/GP package.

International audience

We present a preliminary investigation of macroscopic polarimetric imaging of uterine cervix. Orthogonal state contrast (OSC) images of healthy and anomalous cervices have been taken in vivo at 550 nm. Four ex vivo cervix samples have been studied in full Muller polarimetry, at 550 nm and 700 nm, and characterized in detail by standard pathology. One sample was totally healthy, another one carried CIN lesions at very early stage (CIN1) in its visible exocervical region, while for the other two samples more advanced (CIN3) lesions were present, together with visible glandular epithelium (ectropion). Significant birefringence has been observed in the healthy regions of all six samples, both in vivo and ex vivo. Standard treatments of the Mueller images of the ex vivo samples allowed to quantify both retardation and depolarization. Retardation reached 60° in healthy regions, and disappeared in the anomalous regions of the other three ex vivo samples. The depolarization power was largest in healthy regions, and lower in CINs and ectropion. Possible origins of the observed effects are briefly discussed.

International audience; Motor actions and action verbs activate similar cortical brain regions. A functional interference can be taken as evidence that there is a parallel treatment of these two types of information and would argue for the biological grounding of language in action. A novel approach examining the relationship between language and grip force is presented. With eyes closed and arm extended, subjects listened to words relating (verbs) or not relating (nouns) to a manual action while holding a cylinder with an integrated force sensor. There was a change in grip force when subjects heard verbs that related to manual action. Grip force increased from about 100 ms following the verb presentation, peaked at 380 ms and fell abruptly after 400 ms, signalling a possible inhibition of the motor simulation evoked by these words. These observations reveal the intimate relationship that exists between language and grasp and show that it is possible to elucidate online new aspects of sensorimotor interaction.

International audience; In this expository paper, we show how to use in practice 3-descent with a 3-isogeny to find an estimate for the rank of an elliptic curve having a rational 3-torsion subgroup, and we also give a geometric interpretation of these computations.

International audience; In this study, we examined the influence of child gender and sociocultural (SCL) factors in languageproduction. Subjects were French Parisian children in nine age groups (24, 27, 30, 33, 36, 39, 42, 45and 48 months). A total of 316 language samples were recorded during a 20-min standardized playsession. Measures of grammatical and lexical development included Mean Length of Utterance(MLU) and word type and token—specifically, grammatical words such as determiners, prepositionsand pronouns as well as verbs. ANOVAs revealed strong influences of SCL, with children from highSCL families showing more complex lexical productions and a higher rate of development. Theseobservations suggest that amount of exposure to language accounts for this differential rate ofacquisition. Analyses also revealed a general effect of gender, showing a small advantage in languageproduction for girls over boys until 36 months of age.

International audience; The SOC framework does not take into account the fact that the oral modality consists of purely transient data, which is not the case for the other modalities. This, however, has important consequences on the nature of oral and written language, on language consciousness, on child language development and on the history of linguistics.

Floating-Point (FP) units in processors are generally limited to supporting a subset of formats defined by the IEEE 754 standard, along with a few target-specific ones (X86 with an 80-bit FP format, and PowerPC performing 128-bit FP arithmetic). As a result, high-efficiency languages and optimizing compilers for high-performance computing are also limited by the FP types supported by these units. However, the pursuit of efficiency and stability on applications has led researchers to investigate a finer control of exponent and fraction bits for finding the right balance between accurate results and execution time and/or energy consumed. For example, numerical computations often involve iterative solvers where the residual error is a function of the input data, or where dynamically adaptive precision can accelerate convergence. Numerical analysts have to resort to explicit conversions and multi-versioning, resulting in code bloat and making the intent of the program even less clear. Little attention in languages and compilers has been given to formats that disrupt the traditional FP arithmetics with runtime capabilities and allow the exploration of multiple configurations, a paradigm recently referred to as variable precision computing. This thesis proposes to overcome the limiting language and compiler support for traditional FP formats with novel FP arithmetic with runtime capabilities, showing the intersection between compiler technology and variable precision arithmetic. We present an extension of the C type system that can represent generic FP operations and formats, supporting both static precision and dynamically variable precision. We design and implement a compilation flow bridging the abstraction gap between this type system and low-level FP instructions or software libraries. The effectiveness of our solution is demonstrated through an LLVM-based implementation, leveraging aggressive optimizations in LLVM including the Polly loop nest optimizer. We provide support for two backend code generators: one for the ISA of a variable precision FP arithmetic coprocessor, and one for the MPFR multi-precision floating-point library. We demonstrate the productivity benefits of our intuitive programming model and its ability to leverage an existing compiler framework. Experiments on two high-performance benchmark suites yield strong speedups for both our software and hardware targets. We also show interesting insights on the use of variable precision computing in linear algebra kernels., Les unités de calcul à virgule flottante (FP) prennent en charge un sous-ensemble de formats définis par la norme IEEE 754, ainsi que quelques formats qui leur sont spécifiques (le format de 80 bits sur de l’architecture x86, et le format 128 bit propriétaire des PowerPC). De fait, les langages et les compilateurs optimisants utilisés en calcul intensif sont limités par les formats supportés sur les machines cibles. Cependant, la recherche de l’efficacité et de la stabilité des applications a conduit les numériciens à explorer d’autres tailles pour les exposants et les parties fractionnaires afin de trouver un bon équilibre entre la précision des résultats, le temps d’exécution et l’énergie consommée. C’est le cas pour les calculs numériques qui font appel à des solveurs itératifs dont l’erreur résiduelle est une fonction des données d’entrée, ou ceux pour lesquels une précision adaptable dynamiquement peut accélérer la convergence. Les numériciens doivent recourir à des conversions explicites et prévoir plusieurs versions du code, ce qui entraîne un accroissement de la taille de ce dernier au détriment de sa lisibilité Peu d’attention a été accordée au support d’autre formats flottants dans les langages et à leur compilation, ainsi qu’à leurs conséquences sur le processus d’analyse numérique. Le calcul en précision variable est un paradigme récent qui propose de faire varier les formats à l’exécution et d’en analyser les effets. Les travaux que nous présentons visent à surmonter les limites actuelles des langages et de leur compilation en y ajoutant le support aux formats à précision variable, et en abordant certains des problèmes que ces formats font apparaître à la jonction de la compilation et de l’arithmétique à précision variable. Pour cela nous proposons une extension du système de types du langage C permettant de représenter de manière générique les formats flottants et leurs opérations, aussi bien en précision statique que dynamique. Nous avons mis en œuvre un flot de compilation qui implémente ce système de type jusqu’à la génération de code vers des jeux d’instructions ou des bibliothèques supportant de tels formats. Notre solution basée sur LLVM a démontré son efficacité en tirant parti des puissantes optimisations de LLVM, notamment l’optimisation de nids de boucles par Polly. Nous proposons un support pour deux générateurs de code : un premier pour le jeu d’instruction d’un coprocesseur arithmétique à précision variable, et un deuxième ciblant la bibliothèque MPFR de virgule flottante en multi précision. Ce support démontre les avantages de productivité de notre modèle de programmation intuitif et sa capacité à tirer parti d’une chaîne de compilation existante. Les expérimentations réalisées sur deux suites de référence en calcul à haute performance ont permis d’obtenir de fortes accélérations aussi bien pour nos cibles logicielles que matérielles. Nous présentons également des résultats intéressants sur l’utilisation de la précision variable pour des noyaux d’algèbre linéaire.

The security of embedded systems containing sensitive data has become a main concern. These widely deployed devices are subject to physcial attacks, requiring protections both in hardware and software. The race for higher productivity and shorter time to market in the deployment of secure systems pushes for automatic solutions. This thesis studies the integration of software countermeasures against fault attacks in development tools, with a special focus on the compiler. The goal is to enable the automatic application, at compilation time, of a wide range of countermeasures. We propose two protection schemes against these attacks which can be automatically deployed: one scheme dedicated to loop control flow and the second dedicated to the protection of the call graph. These schemes, integrated in the LLVM compiler framework, allow to focus security application on sensitive areas of the targeted code, thus limitating the overhead. Faults that can be exploited are different from a device to another, we thus also provide an ISA-level characterization of fault effects on a superscalar processor representative of mobile phones. This work highlights the need of studying fault effects on more complex platforms, leading to the design of new protection schemes and automating their compilation-time application., La sécurité des systèmes embarqués contenant des données sensibles est un enjeu crucial. La disponibilité de ces objets en fait une cible privilégiée pour les attaques physiques, nécessitant l'ajout de protections matérielles et logicielles. La recherche de réduction des coûts de développement pousse les industriels à opter pour du déploiement automatique de protections. L'objet de la thèse consiste à étudier l'intégration de contre-mesures logicielles contre les attaques par faute dans les outils de développement, en particulier dans le compilateur, afin d'automatiser l'application de contre-mesures variées. Pour cela, nous proposons deux schémas de protection génériques et automatiquement déployables contre ces attaques : un dédié à la sécurisation des boucles et le deuxième à la sécurisation du graphe d'appel. Ces schémas spécifiques, intégrés dans un même compilateur (LLVM) permettent la sécurisation de parties sensibles et choisies du code limitant ainsi leur surcoût en performances. Les fautes exploitables variant d'un composant à l'autre, nous proposons également une caractérisation des effets des fautes au niveau du jeu d'instructions sur une plateforme intégrant un processeur superscalaire typique des téléphones mobiles. Ces travaux montrent la nécessité d'étudier les injections de faute sur des plateformes complexes, de concevoir de nouveaux schémas de protection adaptés, et de continuer à intégrer dans un même compilateur plus de schémas de sécurisation.

With the rising complexity of the underlying computer hardware, the analysis of the timing behavior of real-time software is becoming more and more complex and imprecise. Time-predictable computer architectures thus have been proposed to provide hardware support for timing analysis. The goal is to deliver tighter worst-case execution time (WCET) estimates while keeping the analysis overhead minimal. These estimates are typically provided by standalone WCET analysis tools. The emergence of time-predictable architectures is, however, quite recent. While several designs have been introduced, efforts are still needed to assess their effectiveness in actually enhancing the worst-case performance. For many time-predictable hardware, timing analysis is either non-existing or lacking proper support. Consequently, time-predictable architectures are barely supported in existing WCET analysis tools. The general contribution of this thesis is to help filling this gap and turning some opportunities into concrete advantages. For this, we take interest in the Patmos processor. The already existing support around Patmos allows for an effective exploration of techniques to enhance the worst-case performance. Main contributions include: (1) Handling of predicated execution in timing analysis, (2) Comparison of the precision of stack cache occupancy analyses, (3) Analysis of preemption costs for the stack cache, (4) Preemption mechanisms for the stack cache, and (5) Prefetching-like technique for the stack cache. In addition, we present our WCET analysis tool Odyssey, which implements timing analyses for Patmos.; En raison de la complexité croissante des architectures matérielles, l'analyse temporelle du logiciel temps-réel devient de plus en plus complexe et imprécise. Les architectures prédictibles des ordinateurs ont donc été proposées afin d'assurer un support matériel dédié à analyse temporelle. The but est de fournir des estimations plus précises de pire-temps d'exécution de programmes (WCET), tout en gardant le coût et la compexité de l'analyse minimal. Ces estimations proviennent typiquement d'outils dédiés à l'analyse WCET. L'émergence de ces architectures spécialisées est, toutefois, assez récent. Bien que plusieurs designs d'architectures ont été proposés, des efforts sont encore nécessaires pour évaluer leurs capacités à améliorer les performances pire cas. Pour plusieurs composants matériels prédictibles, l'analyse temporelle est manquante ou partiellement supportée. En conséquence, les architectures prédictibles sont à peine supportées dans les outils d’analyse WCET existants. Dans cette thèse, nous nous intéressons au processeur prédictible Patmos. Le support existant autour de la plateforme permet une exploration effective des techniques d'optimisation pour les performances pire cas. Les principales contributions comprennent: (1) Une gestion des prédicats dans le flux d'anayse WCET, (2) Une comparaison de la précision des analyses d'occupancy pour le stack cache, (3) Une analyse des coûts de préemption pour le stack cache, (4) Des mécanismes de préemption pour le stack cache, et (5) Des techniques de prefetching pour le stack cache. En outre, nous présentons Odyssey -- notre outil d'analyse WCET pour le processeur Patmos.

With the rising complexity of the underlying computer hardware, the analysis of the timing behavior of real-time software is becoming more and more complex and imprecise. Time-predictable computer architectures thus have been proposed to provide hardware support for timing analysis. The goal is to deliver tighter worst-case execution time (WCET) estimates while keeping the analysis overhead minimal. These estimates are typically provided by standalone WCET analysis tools. The emergence of time-predictable architectures is, however, quite recent. While several designs have been introduced, efforts are still needed to assess their effectiveness in actually enhancing the worst-case performance. For many time-predictable hardware, timing analysis is either non-existing or lacking proper support. Consequently, time-predictable architectures are barely supported in existing WCET analysis tools. The general contribution of this thesis is to help filling this gap and turning some opportunities into concrete advantages. For this, we take interest in the Patmos processor. The already existing support around Patmos allows for an effective exploration of techniques to enhance the worst-case performance. Main contributions include: (1) Handling of predicated execution in timing analysis, (2) Comparison of the precision of stack cache occupancy analyses, (3) Analysis of preemption costs for the stack cache, (4) Preemption mechanisms for the stack cache, and (5) Prefetching-like technique for the stack cache. In addition, we present our WCET analysis tool Odyssey, which implements timing analyses for Patmos., En raison de la complexité croissante des architectures matérielles, l'analyse temporelle du logiciel temps-réel devient de plus en plus complexe et imprécise. Les architectures prédictibles des ordinateurs ont donc été proposées afin d'assurer un support matériel dédié à analyse temporelle. The but est de fournir des estimations plus précises de pire-temps d'exécution de programmes (WCET), tout en gardant le coût et la compexité de l'analyse minimal. Ces estimations proviennent typiquement d'outils dédiés à l'analyse WCET. L'émergence de ces architectures spécialisées est, toutefois, assez récent. Bien que plusieurs designs d'architectures ont été proposés, des efforts sont encore nécessaires pour évaluer leurs capacités à améliorer les performances pire cas. Pour plusieurs composants matériels prédictibles, l'analyse temporelle est manquante ou partiellement supportée. En conséquence, les architectures prédictibles sont à peine supportées dans les outils d’analyse WCET existants. Dans cette thèse, nous nous intéressons au processeur prédictible Patmos. Le support existant autour de la plateforme permet une exploration effective des techniques d'optimisation pour les performances pire cas. Les principales contributions comprennent: (1) Une gestion des prédicats dans le flux d'anayse WCET, (2) Une comparaison de la précision des analyses d'occupancy pour le stack cache, (3) Une analyse des coûts de préemption pour le stack cache, (4) Des mécanismes de préemption pour le stack cache, et (5) Des techniques de prefetching pour le stack cache. En outre, nous présentons Odyssey -- notre outil d'analyse WCET pour le processeur Patmos.

Compilers looking for an efficient implementation of a function must find which optimizations are the most beneficial. This is a complex problem, especially in the early steps of the compilation process. Each decision may impact the transformations available in subsequent steps. We propose to represent the compilation process as the progressive refinement of a partially specified implementation. All potential decisions are exposed upfront and commute. This allows for making the most discriminative decisions first and for building a performance model aware of which optimizations may be applied in subsequent steps. We apply this approach to the generation of efficient GPU code for linear algebra and yield performance competitive with hand-tuned libraries.; Les compilateurs cherchant à améliorer l’efficacité des programmes doivent déterminer quelles optimisations seront les plus bénéfiques. Ce problème est complexe, surtout lors des premières étapes de la compilation où chaque décision influence les choix disponibles aux étapes suivantes. Nous proposons de représenter la compilation comme le raffinement progressif d’une implémentation partiellement spécifiée. Les décisions possibles sont toutes connues dès le départ et commutent. Cela permet de prendre les décisions les plus importantes en premier et de construire un modèle de performance capable d'anticiper les potentielles optimisations. Nous appliquons cette approche pour générer du code d'algèbre linéaire ciblant des GPU et obtenons des performances comparables aux bibliothèques optimisées à la main.

Nowadays, optimizing compilers are increasingly challenged by the diversity of programming languages and heterogeneity of architectures. The polyhedral model is a powerful mathematical framework for programs to exploit automatic parallelization and locality optimization, playing an important role in the field of optimizing compilers. A long standing limitation of the model has been its restriction to static control affine programs, resulting in an emergent demand for the support of non-affine extensions. This is particularly acute in the context of heterogeneous architectures where a variety of computation kernels need to be analyzed and transformed to match the constraints of hardware accelerators and to manage data transfers across memory spaces. We explore multiple non-affine extensions of the polyhedral model, in the context of a welldefined intermediate language combining affine and syntactic elements. On the one hand, we explain how transformations and code generation for loops with non-affine, data-dependent and dynamic loop bounds are integrated into a polyhedral framework, extending the applicable domain of polyhedral compilation in the realm of non-affine applications. On the other hand, we describe the integration of overlapped tiling for stencil computations into a general polyhedral framework, automating non-affine transformations in polyhedral compilation. We evaluate our techniques on both CPU and GPU architectures, validating the effectiveness of the optimizations by conducting an in-depth performance comparison with state-of-the-art frameworks and manually-written libraries., De nos jours, l'optimisation des compilateurs est de plus en plus mise à l'épreuve par la diversité des langages de programmation et l'hétérogénéité des architectures. Le modèle polyédrique est un puissant cadre mathématique permettant aux programmes d’exploiter la parallélisation automatique et l’optimisation de la localité, jouant un rôle important dans le domaine de l’optimisation des compilateurs. Une limite de longue date du modèle réside dans sa restriction aux programmes affines à contrôle statique, ce qui a entraîné une demande émergente de prise en charge d'extensions non affines. Cela est particulièrement aigu dans le contexte d'architectures hétérogènes où une variété de noyaux de calcul doivent être analysés et transformés pour répondre aux contraintes des accélérateurs matériels et pour gérer les transferts de données à travers des espaces mémoire. Nous explorons plusieurs extensions non affines du modèle polyhédral, dans le contexte d'un langage intermédiaire bien défini combinant des éléments affines et syntaxiques. D'un côté, nous expliquons comment les transformations et la génération de code pour des boucles avec des limites de boucle dynamiques non dépendantes des données et dynamiques sont intégrées dans un cadre polyédrique, élargissant ainsi le domaine applicable de la compilation polyédrique dans le domaine des applications non affines. D'autre part, nous décrivons l'intégration du pavage en recouvrement pour les calculs de pochoir dans un cadre polyhédral général, en automatisant les transformations non affines dans la compilation polyhédrique. Nous évaluons nos techniques sur des architectures de CPU et de GPU, en validant l'efficacité des optimisations en effectuant une comparaison approfondie des performances avec des frameworks et des librairies écrites à la pointe de la technologie.

In this thesis, we are interested in Kahn process networks, a simple yet expressive model of concurrency, and its parallel implementation on modern shared-memory architectures. Kahn process networks expose concurrency to the programmer through an arrangement of sequential processes and single-producer single-consumer channels.The focus is on the implementation aspects. Of particular importance to our study are two parameters: lock freedom and relaxed memory. The development of fast and efficient lock-free algorithms ties into concerns of controlled resource consumption (important in embedded systems) and reliable performance on current and future platforms with unfair or skewed scheduling such as virtual machines and GPUs. Our work with relaxed memory models complements this more theoretical approach by offering a window into realistic shared-memory architectures.We present a new lock-free algorithm for a Kahn process network interpreter. It is disjoint-access parallel: we allow multiple threads to work on the same shared Kahn process network, fully utilizing the parallelism exhibited by independent processes. It is non-blocking in that it guarantees global progress in bounded memory, even in the presence of (possibly infinite) delays affecting the executing threads. To our knowledge, it is the first lock-free system of this size, and integrates various well-known non-blocking techniques and concepts (e.g., safe memory reclamation, multi-word updates, assistance) with ideas and optimizations specific to the Kahn network setting. We also discuss a blocking variant of this algorithm, targetted at high-performance computing, with en-couraging experimental results., La thèse porte sur les réseaux de Kahn, un modèle de concurrence simple et expressif proposé par Gilles Kahn dans les années 70, et leur implémentation sur des architectures modernes, multi-cœurs et à mémoire partagée. Dans un réseau de Kahn, le programmeur décrit un programme parallèle comme un ensemble de processus et de canaux communi- cants, chaque canal reliant exactement un processus producteur à un consommateur.Nous nous concentrons ici sur les aspects algorithmiques et les choix de conception liés à l’implémentation, avec en vue deux paramètres clefs : les garanties non bloquantes (lock freedom) et la mémoire relâchée. Le développement d’algorithmes non bloquants efficaces s’inscrit dans une optique de gestion des ressources (importante pour les systèmes embarqués) et de garantie de performance sur les plateformes à ordonnancement irrégulier, telles que les machines virtuelles ou les processeurs graphiques programmables. Un travail complémentaire sur les modèles de mémoire relâchée vient compléter cette ap- proche théorique par un prolongement plus pratique dans le monde des architectures à mémoire partagée contemporaines.Nous présentons un nouvel algorithme non bloquant pour l’interprétation de réseaux de Kahn. Celui-ci est parallèle sur les accès disjoints : il permet à plusieurs processeurs (ou plusieurs threads) de travailler simultanément sur un même réseau de Kahn partagé, tout en exploitant le parallélisme inhérent aux processus indépendants. Il offre dans le même temps des garanties de progrès global non bloquant, c’est-à-dire en mémoire bornée et en présence de retards sur les processeurs. L’ensemble forme, à notre connaissance, le premier système complètement non bloquant de cette envergure. Il met en œuvre une pa- lette cohérente de concepts et de techniques classiques de programmation non bloquante (recyclage de la mémoire, mises à jour complexes avec assistance, etc.), et incorpore des idées et optimisations spécifiques aux réseaux de Kahn. Nous discutons également d’une variante bloquante destinée au calcul haute performance, avec des résultats expérimentaux encourageants.

Since the 60s to the present, the evolution of supercomputers faced three revolutions : (i) the arrival of the transistors to replace triodes, (ii) the appearance of the vector calculations, and (iii) the clusters. These currently consist of standards processors that have benefited of increased computing power via an increase in the frequency, the proliferation of cores on the chip and expansion of computing units (SIMD instruction set). A recent example involving a large number of cores and vector units wide (512-bit) is the co-proceseur Intel Xeon Phi. To maximize computing performance on these chips by better exploiting these SIMD instructions, it is necessary to reorganize the body of the loop nests taking into account irregular aspects (control flow and data flow). To this end, this thesis proposes to extend the transformation named Deep Jam to extract the regularity of an irregular code and facilitate vectorization. This thesis presents our extension and application of a multi-material hydrodynamic mini-application, HydroMM. Thus, these studies show that it is possible to achieve a significant performance gain on uneven codes., L’évolution des supercalculateurs, de leur origine dans les années 60 jusqu’à nos jours, a fait face à 3 révolutions : (i) l’arrivée des transistors pour remplacer les triodes, (ii) l’apparition des calculs vectoriels, et (iii) l’organisation en grappe (clusters). Ces derniers se composent actuellement de processeurs standards qui ont profité de l’accroissement de leur puissance de calcul via une augmentation de la fréquence, la multiplication des cœurs sur la puce et l’élargissement des unités de calcul (jeu d’instructions SIMD). Un exemple récent comportant un grand nombre de cœurs et des unités vectorielles larges (512 bits) est le co-proceseur Intel Xeon Phi. Pour maximiser les performances de calcul sur ces puces en exploitant aux mieux ces instructions SIMD, il est nécessaire de réorganiser le corps des nids de boucles en tenant compte des aspects irréguliers (flot de contrôle et flot de données). Dans ce but, cette thèse propose d’étendre la transformation nommée Deep Jam pour extraire de la régularité d’un code irrégulier et ainsi faciliter la vectorisation. Ce document présente notre extension et son application sur une mini-application d’hydrodynamique multi-matériaux HydroMM. Ces travaux montrent ainsi qu’il est possible d’obtenir un gain de performances significatif sur des codes irréguliers.

This thesis addresses the design and implementationof a programming language for real-time streaming applications,such as video decoding. The model of Kahnprocess networks is a natural fit for this area and hasbeen used extensively. In this model, a program consistsin a set of parallel processes communicating via singlereader, single writer queues. The strength of the modellies in its determinism.Synchronous functional languages such as Lustre arededicated to critical embedded systems. A Lustre programdefines a synchronous Kahn process network, thatis, which can be executed using finite queues and withoutdeadlocks. This is enforced by a dedicated type system,the clock calculus, which establishes a global timescale throughout a program. The global time scale isused to define clocks: per-queue boolean sequences indicating,for each time step, whether a process producesor consumes a token in the queue. This information isused both for enforcing synchrony and for generatingfinite-state software or hardware.We propose and study integer clocks, a generalizationof boolean clocks featuring arbitrarily big natural numbers.Integer clocks model the production or consumptionof several values from the same queue in the courseof a time step. We then rely on integer clocks to definethe local time scale construction, which may hide timesteps performed by a sub-program from the surroundingcontext.These principles are integrated into a clock calculus fora higher-order functional language. We study its properties,proving among other results that well-typed programsdo not deadlock. We adjust the clock-directedcode generation scheme of Lustre to generate finite-statedigital synchronous circuits from typed programs. Thetyping information controls certain trade-offs betweentime and space in the generated circuits., Cette thèse traite de la conception et implémentationd’un langage de programmation pour les systèmes detraitement de flux en temps réel, comme l’encodagevidéo. Le modèle des réseaux de Kahn est bien adaptéà ce domaine et y est couramment utilisé. Dans cemodèle, un programme consiste en un ensemble deprocessus parallèles communicant à travers des filesmono-producteur, mono-consommateur. La force dumodèle réside en son déterminisme.Les langages synchrones fonctionnels comme Lustresont dédiés aux systèmes embarqués critiques. Un programmeLustre définit un réseau de Kahn synchronequi peut être exécuté avec des files bornées et sans blocage.Cette propriété est garantie par un système detypes dédié, le calcul d’horloge, qui établit une échellede temps globale à un programme. Cette échelle detemps globale est utilisée pour définir les horloges, sé-quences booléennes indiquant pour chaque file, et àchaque pas de temps, si un processus produit ou consommeune donnée. Cette information sert non seulementà assurer la synchronie mais également à générerdu logiciel ou matériel à état fini.Nous proposons et étudions les horloges entières, unegénéralisation des horloges booléennes autorisant desentiers naturels arbitrairement grands. Les horlogesentières décrivent la production ou consommation deplusieurs valeurs depuis une même file au cours d’uninstant. Nous les utilisons pour définir la constructiond’échelle de temps locale, qui peut masquer despas de temps cachés par un sous-programme au contexteenglobant.Ces principes sont intégrés à un calcul d’horloge pourun langage fonctionnel d’ordre supérieur. Nous étudionsses propriétés et prouvons en particulier que lesprogrammes bien typés ne bloquent pas. Nous compilonsles programmes typés vers des circuits numériquessynchrones en adaptant le schéma de générationde code dirigé par les horloges de Lustre. L’informationde typage contrôle certains compromis entre temps etespace dans les circuits générés.

Multi-core processors are now in widespread use in almost all areas of computing: desktops, laptops and accelerators such as GPGPUs (General Purpose Graphics Processing Units). To harness the power of multi-core processors and complex memory hierarchies, the need for powerful compiler optimizations and especially loop nest transformations is now in high demand. The polyhedral optimization framework is showing promising results in addressing such a problem. It's an algebraic program representation and a set of analyses, transformations and code generation algorithms that enable a compiler to reason about advanced loop nest transformations addressing most of the parallelism and locality-enhancing challenges.In this thesis we address some of the limitations of the polyhedral framework. We address three problems and propose practical solutions to these three problems.The first problem is related to the ability to apply tiling on code that has false dependences (loop nest tiling is an optimization that changes the order of execution of statements in a loop nest in order to enhance data locality; false dependences are induced by the reuse of a single memory location to store multiple values during the life of the program). To preserve the validity of loop nest transformations and parallelization, data-dependences need to be analyzed. Memory dependences come in two varieties: true dependences (a.k.a. flow dependences) and false dependences (a.k.a. output and anti dependences). While true dependences must be satisfied in order to preserve the correct order of computations. False dependences reduce the degrees of freedom for loop transformations. In particular, loop tiling is severely limited in the presence of these dependences. While array expansion, a transformation that transforms scalars into arrays and arrays into higher dimensional arrays, removes all false dependences, the overhead of this transformation on memory and the detrimental impact on register-level reuse can be catastrophic. We propose and evaluate a compilation technique to safely ignore a large number of false dependences in order to enable loop nest tiling in the polyhedral model. It is based on the precise characterization of interferences between live range intervals, and it does not incur any scalar or array expansion.The second problem is related to the long compilation time that one may experience when using polyhedral tools to optimize a program. Particularly, the long execution time of the Pluto affine scheduling algorithm. The Pluto affine scheduling algorithm is the algorithm that is responsible for changing the schedule (order of execution) of statements in order to optimize the code (maximize parallelism and data locality). Reducing the execution time of this affine scheduling algorithm enhances the overall compilation time. We introduce and evaluate a technique called offline statement clustering. It is a practical technique designed to reduce the execution time of the Pluto affine scheduling algorithm without much loss in optimization opportunities. Using this technique, the statements of the program are clustered into macro-statements, the Pluto affine scheduling algorithm is then used to schedule the macro-statements instead of scheduling the original statements of the program. Since the number of macro-statements is less than the number of statements in the original program, scheduling the macro-statements is in general faster than scheduling the original statements of the program. We present the statement clustering algorithm, we show how offline statement clustering integrates transparently with the work-flow of a state-of-the-art polyhedral compiler and present two heuristics for choosing how statements should be clustered together. We show experimentally that statement clustering can reduce the scheduling time by a factor of 8x (in median) without a significant loss in optimization opportunities...; Les processeurs multi-coeurs sont maintenant largement utilisés presque partout en informatique: ordinateurs de bureau, ordinateurs portables et accélérateurs tels que les GPGPU (General Purpose Graphics Processing Units). La difficulté de la programmation des systèmes parallèles est considérée comme un problème majeur qui va empêcher l'exploitation de leurs capacités dans le futur. Pour exploiter la puissance des processeurs multi-coeurs et les hiérarchies complexes de mémoire, il y a une grande nécessité pour utiliser des outils de parallélisation et d'optimisation automatique de code. L'optimisation polyédrique est un axe de recherche qui a comme but de résoudre ces problèmes. C'est est une représentation algébrique du programme et un ensemble d'analyses, de transformations et d'algorithmes de génération de code qui permettent à un compilateur de raisonner sur des transformations avancées de nids de boucle. Dans cette thèse, nous abordons certaines des limites du modèle polyédrique. Nous nous intéréssons particulièrement à trois problèmes et nous proposons des solutions pratiques à ces trois problèmes. Le premier problème est lié à la capacité d'appliquer l'optimisation de tuilage sur un code qui contient des fausses dépendances. Nous proposons une téchnique qui permet d'ignorer certaines fausses dépendences et donc qui permet d'appliquer l'optimisation de tuilage qui n'est pas possible sinon. Le second problème est lié au temps de compilation qui peut être trés long pour certains programmes. Nous proposons une téchnique qui transforme la représentation originale du programme à une nouvelle representation dans laquelle il y a moins d'instructions. L'optimisation de cette nouvelle représentation du programme est moins couteuse en terme de temps de compilation en comparaison avec l'optimisation de la représentation originale du programme. Le troisième problème est lié à deux limites: la première limite concerne la possibilité d'utiliser la compilation polyédrique sur des programmes qui ne resepectent pas les restrictions classiques du modèle polyédrique (un programme peut être représenté de façon précise dans le modèle polyédrique s'il ne contient pas des conditionnelles non-affines, des bornes de boucles non-affines et des accés non-affines). La seconde limite est liée à l'aptitude des outils à générer un code performant dans les performances se rapprochent des performances du code écrit à la main. Pour éviter ces deux limites, nous proposons un language de programmation que l'on appelle PENCIL, c'est un sous-ensemble de GNU C99 avec des règles de programmation spécifiques et quelques extensions. L'utilisation de ce sous-ensemble et l'utilisation de ces extensions permettent aux compilateurs de mieux exploiter le parallélisme et de mieux optimiser le code.

Multi-core processors are now in widespread use in almost all areas of computing: desktops, laptops and accelerators such as GPGPUs (General Purpose Graphics Processing Units). To harness the power of multi-core processors and complex memory hierarchies, the need for powerful compiler optimizations and especially loop nest transformations is now in high demand. The polyhedral optimization framework is showing promising results in addressing such a problem. It's an algebraic program representation and a set of analyses, transformations and code generation algorithms that enable a compiler to reason about advanced loop nest transformations addressing most of the parallelism and locality-enhancing challenges.In this thesis we address some of the limitations of the polyhedral framework. We address three problems and propose practical solutions to these three problems.The first problem is related to the ability to apply tiling on code that has false dependences (loop nest tiling is an optimization that changes the order of execution of statements in a loop nest in order to enhance data locality; false dependences are induced by the reuse of a single memory location to store multiple values during the life of the program). To preserve the validity of loop nest transformations and parallelization, data-dependences need to be analyzed. Memory dependences come in two varieties: true dependences (a.k.a. flow dependences) and false dependences (a.k.a. output and anti dependences). While true dependences must be satisfied in order to preserve the correct order of computations. False dependences reduce the degrees of freedom for loop transformations. In particular, loop tiling is severely limited in the presence of these dependences. While array expansion, a transformation that transforms scalars into arrays and arrays into higher dimensional arrays, removes all false dependences, the overhead of this transformation on memory and the detrimental impact on register-level reuse can be catastrophic. We propose and evaluate a compilation technique to safely ignore a large number of false dependences in order to enable loop nest tiling in the polyhedral model. It is based on the precise characterization of interferences between live range intervals, and it does not incur any scalar or array expansion.The second problem is related to the long compilation time that one may experience when using polyhedral tools to optimize a program. Particularly, the long execution time of the Pluto affine scheduling algorithm. The Pluto affine scheduling algorithm is the algorithm that is responsible for changing the schedule (order of execution) of statements in order to optimize the code (maximize parallelism and data locality). Reducing the execution time of this affine scheduling algorithm enhances the overall compilation time. We introduce and evaluate a technique called offline statement clustering. It is a practical technique designed to reduce the execution time of the Pluto affine scheduling algorithm without much loss in optimization opportunities. Using this technique, the statements of the program are clustered into macro-statements, the Pluto affine scheduling algorithm is then used to schedule the macro-statements instead of scheduling the original statements of the program. Since the number of macro-statements is less than the number of statements in the original program, scheduling the macro-statements is in general faster than scheduling the original statements of the program. We present the statement clustering algorithm, we show how offline statement clustering integrates transparently with the work-flow of a state-of-the-art polyhedral compiler and present two heuristics for choosing how statements should be clustered together. We show experimentally that statement clustering can reduce the scheduling time by a factor of 8x (in median) without a significant loss in optimization opportunities..., Les processeurs multi-coeurs sont maintenant largement utilisés presque partout en informatique: ordinateurs de bureau, ordinateurs portables et accélérateurs tels que les GPGPU (General Purpose Graphics Processing Units). La difficulté de la programmation des systèmes parallèles est considérée comme un problème majeur qui va empêcher l'exploitation de leurs capacités dans le futur. Pour exploiter la puissance des processeurs multi-coeurs et les hiérarchies complexes de mémoire, il y a une grande nécessité pour utiliser des outils de parallélisation et d'optimisation automatique de code. L'optimisation polyédrique est un axe de recherche qui a comme but de résoudre ces problèmes. C'est est une représentation algébrique du programme et un ensemble d'analyses, de transformations et d'algorithmes de génération de code qui permettent à un compilateur de raisonner sur des transformations avancées de nids de boucle. Dans cette thèse, nous abordons certaines des limites du modèle polyédrique. Nous nous intéréssons particulièrement à trois problèmes et nous proposons des solutions pratiques à ces trois problèmes. Le premier problème est lié à la capacité d'appliquer l'optimisation de tuilage sur un code qui contient des fausses dépendances. Nous proposons une téchnique qui permet d'ignorer certaines fausses dépendences et donc qui permet d'appliquer l'optimisation de tuilage qui n'est pas possible sinon. Le second problème est lié au temps de compilation qui peut être trés long pour certains programmes. Nous proposons une téchnique qui transforme la représentation originale du programme à une nouvelle representation dans laquelle il y a moins d'instructions. L'optimisation de cette nouvelle représentation du programme est moins couteuse en terme de temps de compilation en comparaison avec l'optimisation de la représentation originale du programme. Le troisième problème est lié à deux limites: la première limite concerne la possibilité d'utiliser la compilation polyédrique sur des programmes qui ne resepectent pas les restrictions classiques du modèle polyédrique (un programme peut être représenté de façon précise dans le modèle polyédrique s'il ne contient pas des conditionnelles non-affines, des bornes de boucles non-affines et des accés non-affines). La seconde limite est liée à l'aptitude des outils à générer un code performant dans les performances se rapprochent des performances du code écrit à la main. Pour éviter ces deux limites, nous proposons un language de programmation que l'on appelle PENCIL, c'est un sous-ensemble de GNU C99 avec des règles de programmation spécifiques et quelques extensions. L'utilisation de ce sous-ensemble et l'utilisation de ces extensions permettent aux compilateurs de mieux exploiter le parallélisme et de mieux optimiser le code.

Despite decades of research on high-level loop optimizations and theirsuccessful integration in production C/C++/FORTRAN com- pilers, most compilerinternal loop transformation systems only partially address the challengesposed by the increased complexity and diversity of today’s hardware. Especiallywhen exploiting domain specific knowledge to obtain optimal code for complextargets such as accelerators or many-cores processors, many existing loopoptimization frameworks have difficulties exploiting this hardware. As aresult, new domain specific optimization schemes are developed independentlywithout taking advantage of existing loop optimization technology. This resultsboth in missed optimization opportunities as well as low portability of theseoptimization schemes to different compilers. One area where we see the need forbetter optimizations are iterative stencil computations, an importantcomputational problem that is regularly optimized by specialized, domainspecific compilers, but where generating efficient code is difficult.In this work we present new domain specific optimization strategies that enablethe generation of high-performance GPU code for stencil computations. Differentto how most existing domain specific compilers are implemented, we decouple thehigh-level optimization strategy from the low-level optimization andspecialization necessary to yield optimal performance. As high-leveloptimization scheme we present a new formulation of split tiling, a tilingtechnique that ensures reuse along the time dimension as well as balancedcoarse grained parallelism without the need for redundant computations. Usingsplit tiling we show how to integrate a domain specific optimization into ageneral purpose C-to-CUDA translator, an approach that allows us to reuseexisting non-domain specific optimizations. We then evolve split tiling into ahybrid hexagonal/parallelogram tiling scheme that allows us to generate codethat even better addresses GPU specific concerns. To conclude our work ontiling schemes we investigate the relation between diamond and hexagonaltiling. Starting with a detailed analysis of diamond tiling including therequirements it poses on tile sizes and wavefront coefficients, we provide aunified formulation of hexagonal and diamond tiling which enables us to performhexagonal tiling for two dimensional problems (one time, one space) in thecontext of a general purpose optimizer such as Pluto. Finally, we use thisformulation to evaluate hexagonal and diamond tiling in terms ofcompute-to-communication and compute-to-synchronization ratios.In the second part of this work, we discuss our contributions to importantinfrastructure components, our building blocks, that enviable us to decoupleour high-level optimizations from both the necessary code generationoptimizations as well as the compiler infrastructure we apply the optimizationto. We start with presenting a new polyhedral extractor that obtains apolyhedral representation from a piece of C code, widening the supported C codeto exploit the full generality of Presburger arithmetic and taking special careof modeling language semantics even in the presence of defined integerwrapping. As a next step, we present a new polyhedral AST generation approach,which extends AST generation beyond classical control flow generation byallowing the generation of user provided mappings. Providing a fine-grainedoption mechanism, we give the user fine grained control about AST generatordecisions and add extensive support for specialization e.g., with a newgeneralized form of polyhedral unrolling. To facilitate the implementation ofpolyhedral transformations, we present a new schedule representation, scheduletrees, which proposes to make the inherent tree structure of schedules explicitto simplify the work with complex polyhedral schedules.The last part of this work takes a look at our contributions to low-levelcompilers.; Malgré des décennies de recherche sur l’optimisation de boucle auxhaut niveau et leur intégration réussie dans les compilateurs C/C++et FORTRAN, la plupart des systèmes de transformation de bouclene traitent que partiellement les défis posé par la complexité croissanteet la diversité du matériel d’aujourd’hui. L’exploitation de laconnaissance dédiée a un domaine d’application pour obtenir le codeoptimal pour cibles complexes, tels que des accélérateurs ou des microprocessorsmulti-coeur, pose des problèmes pour les formalismeset outils d’optimisation de boucle existants. En conséquence, de nouveauxschémas d’optimisation qui exploitent la connaissance dédiéea un domaine sont développées indépendamment sans profiter dela technologie d’optimisation de boucle existante. Cela conduit à despossiblités d’optimisation raté et ainsi qu’à une faible portabilité deces schémas d’optimisation entre des compilateurs différents. Un domainepour lequel on voit la nécessité d’améliorer les optimisationsest le calcul de pochoir itératifs, un probléme de calcul important quiest réguliérement optimisé par les compilateurs dédiées, mais pourlequel générer code efficace est difficile.Dans ce travail, nous présentons des nouvelles stratégies pour l’optimisationdédiée qui permettent la génération de code GPU haute performancepour des calculs de pochoir. À la différence de la façon dontla plupart des compilateurs existants sont mis en oeuvre, nous découplonsla stratégie d’optimisation de haut niveau de l’optimisationde bas niveau et la spécialisation nécessaire pour obtenir la performanceoptimale. Comme schéma d’optimisation de haut niveau, nousprésentons une nouvelle formulation de “split tiling”, une techniquequi permet la réutilisation de données dans la dimension du tempsainsi que le parallélisme équilibré à gros grain sans la nécessité derecourir à des calculs redondants. Avec le “split tiling”, nous montronscomment intégrer une optimisation dédiée dans un traducteurgénérique source-à-source, C vers CUDA, une approche qui nouspermet de réutiliser des optimisations existants non-dédiées. Nousprésentons ensuite notre technique appelée “hybrid hexagonal / parallelogramtiling", un schéma qui nous permet de générer du codeque cible directement les préoccupations spécifiques aux GPUs. Pourconclure notre travail sur le "loop tiling", nous étudions la rapport entre“diamond tiling” et “hexagonal tiling”. À partir d’une analyse de“diamond tiling” détailée, qui comprend les exigences qu’elle posesur la taille de tuile et les coefficients de front d’onde, nous fournissonsune formulation unifiée de l’“hexagonal tiling” et du “diamondtiling” qui nous permet de réaliser un “hexagonal tiling” pourvdes problèmes avec deux dimensions (un temps, un espace) dans lecadre d’un usage dans un optimiseur générique, comme “Pluto”. Enfin,nous utilisons cette formulation pour évaluer l’“hexagonal tiling”et le “diamond tiling” en terme de rapport de calcul-à-communicationet calcul-à-synchronisation.Dans la deuxième partie de ce travail, nous discutons nos contributionsaux composants de l’infrastructure les plus important, nos“building blocks”, qui nous permettent de découpler notre optimisationde haut niveau tant des optimisations nécessaires dàns la générationde code que de l’infrastructure de compilation générique. Nouscommençons par présenter le nouveau “polyhedral extractor” (pet),qui obtient une représentation polyédrique d’un morceau de code C.pet utilise l’arithmétique de Presburger en sa généralité pour élargirle fragment de code C supporté et porter une attention particulièreà la modélisation de la sémantique des langages même en présencede dépassement de capacité des entiers.

It was conjectured in the late 60's by J.-P. Serre and proved in the early 70's by P.Deligne that to each newform f = q +Σn ⩾2 anqn 2 Sk(N; "), k ⩾2, and each primel of the number field Kf = Q(an; n ⩾ 2), is attached an l-adic Galois representationPf;l : Gal(Q=Q) ! GL2(ZKf;l ), which is unrami fied outside ℓN and such the characteristicpolynomial of the Frobenius element at p ∤ ℓN is X2 apX +"(p)pk1. Reducing modulo land semi-simplifying, one gets a mod l Galois representation Pf;l : Gal(Q=Q) ! GL2(Fl),which is unrami filed outside ℓN and such that the characteristic polynomial of the Frobeniuselement at p ℓN is X2 apX +"(p)pk1 mod l. In particular, its trace is ap mod l, whichgives a quick way to compute ap mod l for huge p.The goal of this thesis is to study and implement an algorithm based on this idea(originally due to J.-M. Couveignes and B. Edixhoven) which computes the coefficients apmodulo l by computing the mod l Galois representation first, relying on the fact that ifk < ℓ, this representation shows up in the ℓ-torsion of the jacobian of the modular curveX1(ℓN).Thanks to several improvements, such as the use of K. Khuri-Makdisi's methods tocompute in the modular Jacobian J1(ℓN) or the construction of an arithmetically well-behaved function alph 2 Q(J1(ℓN)), this algorithm performs very well, as illustrated bytables of coefficients. This thesis ends by the presentation of a method to formally provethat the output of the algorithm is correct.; J.-P. Serre a conjecturé à la fin des années 60 et P. Deligne a prouvé au début des années 70 que pour toute newform f = q + ∑ n⩾2 a n q n 2 S k (N; "), k ⩾ 2, et tout premier l du corps de nombres Kf = Q(a n ; n ⩾ 2), il existe une représentation galoisienne l-adique pf;l : Gal(Q=Q) ! GL2 (ZKf;l) qui est non-ramifiée en dehors de ℓN et telle que le polynôme caractéristique du Frobenius en p ∤ ℓN est X2 a pX + "(p)p k 1 .Après réduction modulo l et semi-simplification, on obtient une représentation galoisienne pf;l : Gal(Q=Q) ! GL2 (Fl) modulo l, non-ramifiée en dehors de ℓN et telle que lepolynôme caractéristique du Frobenius en p ∤ ℓN est X 2 a pX + "(p)p k 1mod l, d'où un moyen de calcul rapide de ap mod l pour p gigantesque.L'objet de cette thèse est l'étude et l'implémentation d'un algorithme reposant sur cette idée (initialement due à J.-M. Couveignes and B. Edixhoven), qui calcule les coefficients ap modulo l en calculant d'abord cette représentation modulo l, en s'appuyant sur le fait que pour k < ℓ, cette représentation est réalisée dans la ℓ-torsion de la jacobienne de la courbe modulaire X1 (ℓN ).Grâce à plusieurs améliorations, telles que l'utilisation des méthodes de K. KhuriMakdisi pour calculer dans la jacobienne modulaire J1(ℓN ) ou la construction d'une fonction a 2 Q (J1(ℓN )) au bon comportement arithmétique, cet algorithme est très efficace, ainsi qu'illustré par des tables de coefficients. Cette thèse se conclut par la présentation d'une méthode permettant de prouver formellement que les résultats de ces calculs sont corrects.

Despite decades of research on high-level loop optimizations and theirsuccessful integration in production C/C++/FORTRAN com- pilers, most compilerinternal loop transformation systems only partially address the challengesposed by the increased complexity and diversity of today’s hardware. Especiallywhen exploiting domain specific knowledge to obtain optimal code for complextargets such as accelerators or many-cores processors, many existing loopoptimization frameworks have difficulties exploiting this hardware. As aresult, new domain specific optimization schemes are developed independentlywithout taking advantage of existing loop optimization technology. This resultsboth in missed optimization opportunities as well as low portability of theseoptimization schemes to different compilers. One area where we see the need forbetter optimizations are iterative stencil computations, an importantcomputational problem that is regularly optimized by specialized, domainspecific compilers, but where generating efficient code is difficult.In this work we present new domain specific optimization strategies that enablethe generation of high-performance GPU code for stencil computations. Differentto how most existing domain specific compilers are implemented, we decouple thehigh-level optimization strategy from the low-level optimization andspecialization necessary to yield optimal performance. As high-leveloptimization scheme we present a new formulation of split tiling, a tilingtechnique that ensures reuse along the time dimension as well as balancedcoarse grained parallelism without the need for redundant computations. Usingsplit tiling we show how to integrate a domain specific optimization into ageneral purpose C-to-CUDA translator, an approach that allows us to reuseexisting non-domain specific optimizations. We then evolve split tiling into ahybrid hexagonal/parallelogram tiling scheme that allows us to generate codethat even better addresses GPU specific concerns. To conclude our work ontiling schemes we investigate the relation between diamond and hexagonaltiling. Starting with a detailed analysis of diamond tiling including therequirements it poses on tile sizes and wavefront coefficients, we provide aunified formulation of hexagonal and diamond tiling which enables us to performhexagonal tiling for two dimensional problems (one time, one space) in thecontext of a general purpose optimizer such as Pluto. Finally, we use thisformulation to evaluate hexagonal and diamond tiling in terms ofcompute-to-communication and compute-to-synchronization ratios.In the second part of this work, we discuss our contributions to importantinfrastructure components, our building blocks, that enviable us to decoupleour high-level optimizations from both the necessary code generationoptimizations as well as the compiler infrastructure we apply the optimizationto. We start with presenting a new polyhedral extractor that obtains apolyhedral representation from a piece of C code, widening the supported C codeto exploit the full generality of Presburger arithmetic and taking special careof modeling language semantics even in the presence of defined integerwrapping. As a next step, we present a new polyhedral AST generation approach,which extends AST generation beyond classical control flow generation byallowing the generation of user provided mappings. Providing a fine-grainedoption mechanism, we give the user fine grained control about AST generatordecisions and add extensive support for specialization e.g., with a newgeneralized form of polyhedral unrolling. To facilitate the implementation ofpolyhedral transformations, we present a new schedule representation, scheduletrees, which proposes to make the inherent tree structure of schedules explicitto simplify the work with complex polyhedral schedules.The last part of this work takes a look at our contributions to low-levelcompilers., Malgré des décennies de recherche sur l’optimisation de boucle auxhaut niveau et leur intégration réussie dans les compilateurs C/C++et FORTRAN, la plupart des systèmes de transformation de bouclene traitent que partiellement les défis posé par la complexité croissanteet la diversité du matériel d’aujourd’hui. L’exploitation de laconnaissance dédiée a un domaine d’application pour obtenir le codeoptimal pour cibles complexes, tels que des accélérateurs ou des microprocessorsmulti-coeur, pose des problèmes pour les formalismeset outils d’optimisation de boucle existants. En conséquence, de nouveauxschémas d’optimisation qui exploitent la connaissance dédiéea un domaine sont développées indépendamment sans profiter dela technologie d’optimisation de boucle existante. Cela conduit à despossiblités d’optimisation raté et ainsi qu’à une faible portabilité deces schémas d’optimisation entre des compilateurs différents. Un domainepour lequel on voit la nécessité d’améliorer les optimisationsest le calcul de pochoir itératifs, un probléme de calcul important quiest réguliérement optimisé par les compilateurs dédiées, mais pourlequel générer code efficace est difficile.Dans ce travail, nous présentons des nouvelles stratégies pour l’optimisationdédiée qui permettent la génération de code GPU haute performancepour des calculs de pochoir. À la différence de la façon dontla plupart des compilateurs existants sont mis en oeuvre, nous découplonsla stratégie d’optimisation de haut niveau de l’optimisationde bas niveau et la spécialisation nécessaire pour obtenir la performanceoptimale. Comme schéma d’optimisation de haut niveau, nousprésentons une nouvelle formulation de “split tiling”, une techniquequi permet la réutilisation de données dans la dimension du tempsainsi que le parallélisme équilibré à gros grain sans la nécessité derecourir à des calculs redondants. Avec le “split tiling”, nous montronscomment intégrer une optimisation dédiée dans un traducteurgénérique source-à-source, C vers CUDA, une approche qui nouspermet de réutiliser des optimisations existants non-dédiées. Nousprésentons ensuite notre technique appelée “hybrid hexagonal / parallelogramtiling", un schéma qui nous permet de générer du codeque cible directement les préoccupations spécifiques aux GPUs. Pourconclure notre travail sur le "loop tiling", nous étudions la rapport entre“diamond tiling” et “hexagonal tiling”. À partir d’une analyse de“diamond tiling” détailée, qui comprend les exigences qu’elle posesur la taille de tuile et les coefficients de front d’onde, nous fournissonsune formulation unifiée de l’“hexagonal tiling” et du “diamondtiling” qui nous permet de réaliser un “hexagonal tiling” pourvdes problèmes avec deux dimensions (un temps, un espace) dans lecadre d’un usage dans un optimiseur générique, comme “Pluto”. Enfin,nous utilisons cette formulation pour évaluer l’“hexagonal tiling”et le “diamond tiling” en terme de rapport de calcul-à-communicationet calcul-à-synchronisation.Dans la deuxième partie de ce travail, nous discutons nos contributionsaux composants de l’infrastructure les plus important, nos“building blocks”, qui nous permettent de découpler notre optimisationde haut niveau tant des optimisations nécessaires dàns la générationde code que de l’infrastructure de compilation générique. Nouscommençons par présenter le nouveau “polyhedral extractor” (pet),qui obtient une représentation polyédrique d’un morceau de code C.pet utilise l’arithmétique de Presburger en sa généralité pour élargirle fragment de code C supporté et porter une attention particulièreà la modélisation de la sémantique des langages même en présencede dépassement de capacité des entiers.

Across the wide range of multiprocessor architectures, all seem to share one common problem: they are hard to program. It is a general belief that parallelism is a software problem, and that perhaps we need more sophisticated compilation techniques to partition the application into concurrent threads. Many experts also make the point that the underlining architecture plays an equally important architecture before one may expect significant progress in the programmability of multiprocessors. Our approach favors a convergence of these viewpoints. The convergence of dataflow and von Neumann architecture promises latency tolerance, the exploitation of a high degree of parallelism, and light thread switching cost. Multithreaded dataflow architectures require a high degree of parallelism to tolerate latency. On the other hand, it is error-prone for programmers to partition the program into large number of fine grain threads. To reconcile these facts, we aim to advance the state of the art in automatic thread partitioning, in combination with programming language support for coarse-grain, functionally deterministic concurrency. This thesis presents a general thread partitioning algorithm for transforming sequential code into a parallel data-flow program targeting a multithreaded dataflow architecture. Our algorithm operates on the program dependence graph and on the static single assignment form, extracting task, pipeline, and data parallelism from arbitrary control flow, and coarsening its granularity using a generalized form of typed fusion. We design a new intermediate representation to ease code generation for an explicit token match dataflow execution model. We also implement a GCC-based prototype. We also evaluate coarse-grain dataflow extensions of OpenMP in the context of a large-scale 1024-core, simulated multithreaded dataflow architecture. These extension and simulated architecture allow the exploration of innovative memory models for dataflow computing. We evaluate these tools and models on realistic applications., Quelque-soit le multiprocesseur et son architecture, la facilité de leur programmation demeure une difficulté majeure. Une croyance bien installée est que l’exploitation correcte et efficace du parallélisme dans une application est une question pour les concepteurs d’outils de développement logiciel. Selon cette vision, nous avons besoin de techniques de compilation plus sophistiqués pour partitionner une application en threads simultanés. Mais de nombreux experts revendiquent que l'architecture joue un rôle tout aussi important: il faut opérer un changement fondamental dans l'architecture de processeurs avant que l’on puisse espérer des progrès importants au niveau de leur programmabilité. Notre approche favorise la convergence de ces points de vue. La convergence entre le calcul parallèle “en flot de données” avec l'architecture de von Neumann est porteuse de nombreuses promesses. En particulier en termes de tolérance à la latence, en termes d’exploitation d'un haut degré de parallélisme, le tout pour un très faible coût de changement de contexte entre threads. Les architectures à flot de données multithread exigent un haut degré de parallélisme pour tolérer la latence. D'autre part, le partitionnement d’un programme en un grand nombre de threads à grain fin est une source d'erreurs commune pour les développeurs. Pour reconcilier ces faits, nous nous efforçons de faire progresser l'état de l'art dans le partitionnement automatique de threads, conjointement avec le support du langage de programmation pour l’exploitation de parallélisme à plus gros grain, tout en préservant un concurrence déterministe. Cette thèse présente un algorithme général de partitionnement de threads, pour transformer du code séquentiel en un programme exprimant du parallélisme en flot de données. Notre algorithme fonctionne sur le Program Dependence Graph (PDG) et la forme en assignation unique statique (Static Single Assignment, SSA), pour extraire du parallélisme de tâche, pipeline, et de données, en présence de flot de contrôle arbitraire. Nous avons conçu une nouvelle représentation intermédiaire pour faciliter la génération de code, et son exécution parallèle en flot de données. Nous avons également mis en œuvre ces algorithmes dans un prototype fondé sur GCC, et contribué au développement d’une plateforme de simulation permettant d’explorer la parallélisation en flot de données à grande échelle. Ces extensions et l'architecture simulée permettent l'exploration de modèles innovants de mémoire pour le parallélisme en flot de données. Ces outils et modèles ont également été évalués sur des applications réalistes.

The goal of this thesis is to design algorithms that run with better complexity when compiling or parallelizing loop programs. The framework within which our algorithms operate is the polyhedral model of compilation which has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations of the above framework remain one important weakness. We address it by introducing sub-polyhedral compilation by using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra, namely polyhedrawith restricted constraints of the type ax_{i}+bx_{j}\le c (\pm x_{i}\pm x_{j}\le c). A major focus of our sub-polyhedral compilation is the introduction of sub-polyhedral scheduling, where we propose a technique for scheduling using (U)TVPI polyhedra. As part of this, we introduce algorithms that can be used to construct under-aproximations of the systems of constraints resulting from affine scheduling problems. This technique relies on simple polynomial time algorithms to under approximate a general polyhedron into (U)TVPI polyhedra. The above under-approximation algorithms are generic enough that they can be used for many kinds of loop parallelization scheduling problems, reducing each of their complexities to asymptotically polynomial time. We also introduce sub-polyhedral code-generation where we propose algorithms to use the improved complexities of (U)TVPI sub-polyhedra in polyhedral code generation. In this problem, we show that the exponentialities associated with the widely used polyhedral code generators could be reduced to polynomial time using the improved complexities of (U)TVPI sub-polyhedra. The above presented sub-polyhedral scheduling techniques are evaluated in an experimental framework. For this, we modify the state-of-the-art PLuTo compiler which can parallelize for multi-core architectures using permutation and tiling transformations. We show that using our scheduling technique, the above under-approximations yield polyhedra that are non-empty for 10 out of 16 benchmarks from the Polybench (2.0) kernels. Solving the under-approximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.; Notre étude de la compilation sous-polyédrique est dominée par l’introduction de la notion l’ordonnancement affine sous-polyédrique, pour laquelle nous proposons une technique utilisant des sous-polyèdres (U)TVPI. Dans ce cadre, nous introduisons des algorithmes capables de construire des sous-approximations de systèmes de contraintes résultant de problèmes d’ordonnancement affine. Cette technique repose sur des algorithmes polynomiaux simples pour approcher un polyèdre quelconque par un polyèdre (U)TVPI. Nos algorithmes sont suffisamment génériques pour s’appliquer à de nombreux problèmes d’ordonnancement, de parallélisation, et d’optimisation de boucles, réduisant leur complexité temporelle à des fonctions polynomiales. Nous introduisons également une méthode pour la génération de code utilisant des algorithmes sous-polyédriques, tirant parti de la faible complexité des sous-polyèdres (U)TVPI. Dans ce cadre, nous montrons comment réduire la complexité associée aux générateurs de code les plus populaires, ramenant la complexité de plusieurs facteurs exponentiels à des fonctions polynomiales. Nombre de ces techniques sont évaluées expérimentalement. Pour cela, nous avons réalisé une version modifiée du compilateur PLuTo, capable de paralléliser et d’optimiser des nids de boucles pour des architectures multi-cœurs à l’aide de transformations affines, et notamment de partitionnement (tiling). Nous montrons qu’une majorité des noyaux de calcul de la suite Polybench (2.0) peut être manipulée à l’aide de notre technique d’ordonnancement, en préservant la faisabilité des polyèdres lors des sous-approximations. L’utilisation des systèmes approchés par des sous-polyèdres conduit à des gains asymptotiques en complexité, qui se traduit par des réductions significatives en temps de compilation, par rapport à un solveur de programmation linéaire de référence. Nous vérifions également que le code généré par notre prototype de parallélisation sous-polyédrique est compétitif par rapport à la performance du code généré par Pluto.

As transistors size and power limitations stroke computer industry, hardware parallelism arose as the solution, bringing old forgotten problems back into equation to solve the existing limitations of current parallel technologies. Compilers regain focus by being the most relevant puzzle piece in the quest for the expected computer performance improvements predicted by Moores law no longer possible without parallelism. Parallel research is mainly focused in either the language or architectural aspects, not really giving the needed attention to compiler problems, being the reason for the weak compiler support by many parallel languages or architectures, not allowing to exploit performance to the best. This thesis addresses these problems by presenting: Erbium, a low level streaming data-flow language supporting multiple producer and consumer task communication; a very efficient runtime implementation for x86 architectures also addressing other types of architectures; a compiler integration of the language as an intermediate representation in GCC; a study of the language primitives dependencies, allowing compilers to further optimise the Erbium code not only through specific parallel optimisations but also through traditional compiler optimisations, such as partial redundancy elimination and dead code elimination.; Frappée par les rendements décroissants de la performance séquentielle et les limitations thermiques, l’industrie des microprocesseurs s’est tournée résolument vers les multiprocesseurs sur puce. Ce mouvement a ramené des problèmes anciens et difficiles sous les feux de l’actualité du développement logiciel. Les compilateurs sont l’une des pièces maitresses du puzzle permettant de poursuivre la traduction de la loi de Moore en gains de performances effectifs, gains inaccessibles sans exploiter le parallélisme de threads. Pourtant, la recherche sur les systèmes parallèles s’est concentrée sur les aspects langage et architecture, et le potentiel reste énorme en termes de compilation de programmes parallèles, d’optimisation et d’adaptation de programmes parallèles pour exploiter efficacement le matériel. Cette thèse relève ces défis en présentant Erbium, un langage de bas niveau fondé sur le traitement de flots de données, et mettant en œuvre des communications multi-producteur multi-consommateur ; un exécutif parallèle très efficace pour les architectures x86 et des variantes pour d’autres types d’architectures ; un schéma d’intégration du langage dans un compilateur illustré en tant que représentation intermédiaire dans GCC ; une étude des primitives du langage et de leurs dépendances permettant aux compilateurs d’optimiser des programmes Erbium à l’aide de transformations spécifiques aux programmes parallèles, et également à travers des formes généralisées d’optimisations classiques, telles que l’élimination de redondances partielles et l’élimination de code mort.

As transistors size and power limitations stroke computer industry, hardware parallelism arose as the solution, bringing old forgotten problems back into equation to solve the existing limitations of current parallel technologies. Compilers regain focus by being the most relevant puzzle piece in the quest for the expected computer performance improvements predicted by Moores law no longer possible without parallelism. Parallel research is mainly focused in either the language or architectural aspects, not really giving the needed attention to compiler problems, being the reason for the weak compiler support by many parallel languages or architectures, not allowing to exploit performance to the best. This thesis addresses these problems by presenting: Erbium, a low level streaming data-flow language supporting multiple producer and consumer task communication; a very efficient runtime implementation for x86 architectures also addressing other types of architectures; a compiler integration of the language as an intermediate representation in GCC; a study of the language primitives dependencies, allowing compilers to further optimise the Erbium code not only through specific parallel optimisations but also through traditional compiler optimisations, such as partial redundancy elimination and dead code elimination.; Frappée par les rendements décroissants de la performance séquentielle et les limitations thermiques, l’industrie des microprocesseurs s’est tournée résolument vers les multiprocesseurs sur puce. Ce mouvement a ramené des problèmes anciens et difficiles sous les feux de l’actualité du développement logiciel. Les compilateurs sont l’une des pièces maitresses du puzzle permettant de poursuivre la traduction de la loi de Moore en gains de performances effectifs, gains inaccessibles sans exploiter le parallélisme de threads. Pourtant, la recherche sur les systèmes parallèles s’est concentrée sur les aspects langage et architecture, et le potentiel reste énorme en termes de compilation de programmes parallèles, d’optimisation et d’adaptation de programmes parallèles pour exploiter efficacement le matériel. Cette thèse relève ces défis en présentant Erbium, un langage de bas niveau fondé sur le traitement de flots de données, et mettant en œuvre des communications multi-producteur multi-consommateur ; un exécutif parallèle très efficace pour les architectures x86 et des variantes pour d’autres types d’architectures ; un schéma d’intégration du langage dans un compilateur illustré en tant que représentation intermédiaire dans GCC ; une étude des primitives du langage et de leurs dépendances permettant aux compilateurs d’optimiser des programmes Erbium à l’aide de transformations spécifiques aux programmes parallèles, et également à travers des formes généralisées d’optimisations classiques, telles que l’élimination de redondances partielles et l’élimination de code mort.

Despite the benefit of the memory hierarchy, it is still essential, in order to reduce accesses to higher levels of memory, to have an efficient usage of registers and local memories (also called scratchpad memories) present in most embedded processors, graphical processors (GPUs) and network processors. During the compilation, from a source language to an executable code, there are two optimizations that are of utmost importance: the register allocation and the local memory allocation. In this thesis's report we are interested in decoupled approaches, solving separately the allocation and assignment problems, that helps to improve the quality of the register and local memory allocations. In the first part of this thesis we are interested in two aspects of the register allocation problem: the improvements of the just-in-time (JIT) register allocation and the spill minimization problem. We introduce the split register allocation which leverages the decoupled approach to improve register allocation in the context of JIT compilation. We experimentally validate the effectiveness of split register allocation and its portability with respect to register count variations, relying on annotations whose impact on the bytecode size is negligible. We introduce a new decoupled approach, called iterated-optimal allocation, which focus on the spill minimization problem. The iterated-optimal allocation algorithm achieves results close to optimal while offering pseudo-polynomial guarantees for SSA programs and fast allocations on general programs. In the second part of this thesis, we study how a decoupled local memory allocation can be proposed in light of recent progresses in register allocation. We first validate our intuition for decoupled approach to local memory allocation. Then, we study the local memory allocation in a more theoretical way setting the junction between local memory allocation for linearized programs and weighted interval graph coloring. We design and analyze a new variant of the ship-building problem called the submarine-building problem. We show that this problem is NP-complete on interval graphs, while it is solvable in linear time for proper interval graphs, equivalent to unit interval graphs. The submarine-building problem is the first problem that is known to be NP-complete on interval graphs, while it is solvable in linear time for unit interval graphs. In the third part of this thesis, we propose a heuristic-based solution, the clustering allocator, which decouples the local memory allocation problem and aims to minimize the allocation cost. The clustering allocator while devised for local memory allocation, it appears to be a very good solution to the register allocation problem. After many years of separation, this new algorithm seems to be a bridge to reconcile the local memory allocation and the register allocation problems., Malgré la hiérarchie mémoire utilisée dans les ordinateurs modernes, il convient toujours d'optimiser l'utilisation des registres du processeur et des mémoires locales gérées de manières logicielles (mémoires locales) présentes dans beaucoup de systèmes embarqués, de processeurs graphiques (GPUs) et de multiprocesseurs. Lors de la compilation, d'un code source vers un langage machine, deux optimisations de la mémoire revêtent une importance capitale : l'allocation de registres et l'allocation de mémoires locales. Dans ce manuscrit de thèse nous nous intéressons à des approches découplées, qui traitent séparément les problèmes d'allocation et d'assignation, permettant d'améliorer les allocations de registres et de mémoires locales. Dans la première partie de la thèse, nous nous penchons sur le problème de l'allocation de registres. Tout d'abord, nous proposons dans le contexte des compilateurs-juste-à-temps, une allocation de registres fractionnées (split register allocation). Avec cette approche l'allocation de registres est effectuée en deux étapes: une faite durant la phase de compilation statique et l'autre pendant la phase de compilation dynamique. Ce qui permet de réduire le temps d'exécution des programmes avec un impact négligeable sur le temps de compilation. Ensuite Nous introduisons une allocation de registres incrémentale qui permet de résoudre d'une manière quasi-optimale le problème d'allocation. Cette méthode est pseudo-polynomiale alors que le problème d'allocation est NP-complet même à l'intérieur d'un « basic block ». Dans la deuxième partie de la thèse nous nous intéressons au problème de l'allocation de mémoires locales. Au vu des dernières avancées dans le domaine de l'allocation de registres, nous étudions dans quelle mesure le problème d'allocation pourrait être séparé de celui de l'assignation dans le contexte des mémoires locales. Dans un premier temps nous validons expérimentalement que les problèmes d'allocation et d'assignation peuvent être résolus séparément. Ensuite, nous procédons à une étude plus théorique d'une approche découplée de l'allocation de mémoires locales. Cela permet d'introduire de nouveaux résultats sur le « submarine-building problem », une variante du « ship-building problem », que nous avons défini. L'un de ces résultats met en évidence pour la première fois une différence de complexité (P vs. NP-complet) entre les graphes d'intervalles et les graphes d'intervalles unitaires. Dans la troisième partie de la thèse nous proposons une nouvelle heuristique, appelée « clustering allocator » fondée sur la construction de sous-graphes stables d'un graphe d'interférence, permettant de découpler aussi bien le problème d'allocation pour les registres que pour les mémoires locales. Cette nouvelle heuristique se veut le pont qui permettra de réconcilier les problèmes d'allocations de registres et de mémoires locales.

In order to take the performance advantages of the current multicore and heterogeneous architectures the compilers are required to perform more and more complex program transformations. The search space of the possible program optimizations is huge and unstructured. Selecting the best transformation and predicting the potential performance benefits of that transformation is the major problem in today's optimizing compilers. The promising approach to handling the program optimizations is to focus on the automatic loop optimizations expressed in the polyhedral model. The current approaches for optimizing programs in the polyhedral model broadly fall into two classes. The first class of the methods is based on the linear optimization of the analytical cost function. The second class is based on the exhaustive iterative search. While the first approach is fast, it can easily miss the optimal solution. The iterative approach is more precise, but its running time might be prohibitively expensive. In this thesis we present a novel search-based approach to program transformations in the polyhedral model. The new method combines the benefits - effectiveness and precision - of the current approaches, while it tries to minimize their drawbacks. Our approach is based on enumerating the evaluations of the precise, nonlinear performance predicting cost-function. The current practice is to use the polyhedral model in the context of source-to-source compilers. We have implemented our techniques in a GCC framework that is based on the low level three address code representation. We show that the chosen level of abstraction for the intermediate representation poses scalability challenges, and we show the ways to overcome those problems. On the other hand, it is shown that the low level IR abstraction opens new degrees of freedom that are beneficial for the search-based transformation strategies and for the polyhedral compilation in general., Une pression accrue s'exerce sur les compilateurs pour mettre en œuvre des transformations de programmes de plus en plus complexes délivrant le potentiel de performance des processeurs multicœurs et des accélérateurs hétérogènes. L'espace de recherche des optimisations de programmes possibles est gigantesque est manque de structure. La recherche de la meilleure transformation, qui inclut la prédiction des gains estimés de performance offerts par cette transformation, constitue le problème le plus difficiles pour les compilateurs optimisants modernes. Nous avons choisi de nous concentrer sur les transformations de boucles et sur leur automatisation, exprimées dans le modèle polyédrique. Les méthodes d'optimisation de programmes dans le modèle polyédrique se répartissent grossièrement en deux classes. La première repose sur l'optimisation linéaire d'une fonction de analytique de coût. La deuxième classe de méthodes met en œuvre une recherche itérative. La première approche est rapide, mais elle est facilement mise en défaut en ce qui concerne la découverte de la solution optimale. L'approche itérative est plus précise, mais le temps de compilation peut devenir prohibitif. Cette thèse contribue une approche nouvelle de la recherche itérative de transformations de programmes dans le modèle polyédrique. La nouvelle méthode proposée possède la précision et la capacité effective à extraire des transformations profitables des méthodes itératives, tout en en minimisant les faiblesses. Notre approche repose sur l'évaluation systématique d'une fonction de coût et de prédiction de performances non-linéaire. Par ailleurs, la parallélisation automatique dans le modèle polyédrique est actuellement dominée par des outils de compilation source-à-source. Nous avons choisi au contraire d'implémenter nos techniques dans la plateforme GCC, en opérant sur une représentation de code de bas niveau, à trois adresses. Nous montrons que le niveau d'abstraction de la représentation intermédiaire choisie engendre des difficultés de passage à l'échelle, et nous montrons comment les surmonter. À l'inverse, nous montrons qu'une représentation intermédiaire de bas niveau ouvre de nouveaux degrés de liberté, bénéficiant à notre stratégie itérative de recherche de transformations, et à la compilation polyédrique de manière générale.

Applications based on streams, ordered sequences of data values, are important targets of program optimization because of their high computational requirements and the diversity of their application domains: communication, embedded systems, multimedia, etc. One of the most important and difficult problems in special purpose stream language design and implementation is how to schedule these applications in a fine-grain way to exploit available machine resources In this thesis we propose a framework for fine-grain scheduling of streaming applications and nested loops in general. First, we try to pipeline steady state phases (inner loops), by finding the repeated kernel pattern, and executing actor occurrences in parallel as much as possible. Then we merge the kernel prolog and epilog of pipelined phases to move them out of the outer loop. Merging the kernel prolog and epilog means that we shift acotor occurrences, or instructions, from one phase iteration to another and from one outer loop iteration to another, a multidimensional shifting. Experimental shows that our framwork can imporove perfomance, prallelism extraction without increasing the code size, in streaming applications and nested loops in general., Les applications de flux de données sont des cibles importantes de l’optimisation de programme en raison de leur haute exigence de calcul et la diversité de leurs domaines d’application: communication, systèmes embarqués, multimédia, etc. L’un des problèmes les plus importants et difficiles dans la conception des langages de programmation destinés à ce genre d’applications est comment les ordonnancer à grain fin à fin d’exploiter les ressources disponibles de la machine.Dans cette thèse on propose un "framework" pour l’ordonnancement à grain fin des applications de flux de données et des boucles imbriquées en général. Premièrement on essaye de paralléliser le nombre maximum de boucles en appliquant le pipeline logiciel. Après on merge le prologue et l’épilogue de chaque boucle (phase) parallélisée pour éviter l’augmentation de la taille du code. Ce processus est un pipeline multidimensionnel, quelques occurrences (ou instructions) sont décalées par des iterations de la boucle interne et d’autres occurrences (instructions) par des iterationsde la boucle externe. Les expériences montrent que l’application de cette technique permet l’amélioration des performances, extraction du parallélisme sans augmenter la taille du code, à la fois dans le cas des applications de flux des donnée et des boucles imbriquées en général.

This thesis deals with counting relative cubic extensions. In the first chapter we describe a joint work with Henri Cohen. Let k be a number field. We give an asymptotic formula for the number of isomorphism classes of cubic extensions L/k such that the Galois closure of L/k contains a fixed quadratic extension K_2/k. The main tool is Kummer theory. In the second chapter, we suppose k to be an imaginary quadratic number field (with class number 1) and we describe an algorithm for listing all isomorphism classes of cubic extensions L/k up to a bound X on the norm of the relative discriminant ideal.; Cette thèse traite du comptage d'extensions cubiques relatives. Dans le premier chapitre on traite un travail commun avec Henri Cohen. Soit k un corps de nombres. On donne une formule asymptotique pour le nombre de classes d'isomorphisme d'extensions cubiques L/k telles que la clôture galoisienne de L/k contienne une extension quadratique fixée K_2/k. L'outil principal est la théorie de Kummer. Dans le second chapitre, on suppose k un corps quadratique imaginaire (avec nombre de classes 1) et on décrit un algorithme pour énumerer toutes les classes d'isomorphisme d'extensions cubiques L/k jusqu'à une certaine borne X sur la norme du discriminant relatif.

This chapter is a fully revised and expanded version of a conference paper with the same title, presented at the 10th IEEE International Conference on Fuzzy Systems, Melbourne, Australia, December 2–5, 2001; International audience; The issue of understanding and modeling vagueness has been addressed by many authors, especially in the second half of the twentieth century. In this chapter, we try to provide an organized discussion of different categories of vagueness, pointing out circumstances, where they appear. Together, they lead to a trichotomy of the universe of discourse, which seems to be the common feature of the different forms of vagueness. Basic representational frameworks are proposed for each case. This chapter does not advocate a particular view but identifies the characteristic features of each situation.