No description available.

The modular design methodology has been widely adopted to harness the complexity of large FPGA-based systems. As a result, a number of commercial and academic tool flows emerged to support modular design including Hierarchical Design Flow and Partial Reconfiguration Flow, OpenPR, HMFlow, PARBIT, REPLICA, GoAhead and QFlow frameworks. As all of these projects have shown, a modular approach raises the abstraction level, provides clear boundaries for incremental design, reduces placement complexity, and improves productivity. At the physical layer, modules can be compiled into rectangular regions, suitable for placement on the FPGA fabric. Creating a design then becomes the process of placing all of the modules on the FPGA, followed by inter-module routing. FPGAs, however, are not homogenous, and the shape of individual modules could greatly impact overall device utilization. Prior work in modular assembly utilize modules with a single shape and aspect ratio in the assembly process. Due to the increasing size and heterogeneity of contemporary FPGAs, the placement flexibility of such a module is becoming increasingly limited. This thesis introduces a process that exploits offline shape generation and exploration, enabling the selection of shapes using criterias such as resource usage efficiency, placement flexibility, and device utilization. Module shapes can be generated with these criterias in mind while still taking advantage of the reduced placement complexity of modular design and assembly / Master of Science

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.

Les systèmes informatiques critiques - tels que les commandes de vol électroniques et le contrôle des centrales nucléaires - doivent répondre à des exigences strictes en termes de sûreté de fonctionnement. Nous nous intéressons ici à l'application de méthodes formelles - ancrées sur de solides bases mathématiques - pour la vérification du comportement des logiciels critiques. Plus particulièrement, nous spécifions formellement nos algorithmes et nous les prouvons corrects, à l'aide de l'assistant à la preuve Coq - un logiciel qui vérifie mécaniquement la correction des preuves effectuées et qui apporte un degré de confiance très élevé. Nous appliquons ici des méthodes formelles à l'estimation du Temps d'Exécution au Pire Cas (plus connu par son abréviation en anglais, WCET) de programmes C. Le WCET est une propriété importante pour la sûreté de fonctionnement des systèmes critiques, mais son estimation exige des analyses sophistiquées. Pour garantir l'absence d'erreurs lors de ces analyses, nous avons formellement vérifié une méthode d'estimation du WCET fondée sur la combinaison de deux techniques principales: une estimation de bornes de boucles et une estimation du WCET via la méthode IPET (Implicit Path Enumeration Technique). L'estimation de bornes de boucles est elle-même décomposée en trois étapes : un découpage de programmes, une analyse de valeurs opérant par interprétation abstraite, et une méthode de calcul de bornes. Chacune de ces étapes est formellement vérifiée dans un chapitre qui lui est dédiée. Le développement a été intégré au compilateur C formellement vérifié CompCert. Nous prouvons que le résultat de l'estimation est correct et nous évaluons ses performances dans des ensembles de benchmarks de référence dans le domaine. Les contributions de cette thèse incluent la formalisation des techniques utilisées pour estimer le WCET, l'outil d'estimation lui-même (obtenu à partir de la formalisation), et l'évaluation expérimentale des résultats. Nous concluons que le développement fondé sur les méthodes formelles permet d'obtenir des résultats intéressants en termes de précision, mais il exige des précautions particulières pour s'assurer que l'effort de preuve reste maîtrisable. Le développement en parallèle des spécifications et des preuves est essentiel à cette fin. Les travaux futurs incluent la formalisation de modèles de coût matériel, ainsi que le développement d'analyses plus sophistiquées pour augmenter la précision du WCET estimé. / Safety-critical systems - such as electronic flight control systems and nuclear reactor controls - must satisfy strict safety requirements. We are interested here in the application of formal methods - built upon solid mathematical bases - to verify the behavior of safety-critical systems. More specifically, we formally specify our algorithms and then prove them correct using the Coq proof assistant - a program capable of mechanically checking the correctness of our proofs, providing a very high degree of confidence. In this thesis, we apply formal methods to obtain safe Worst-Case Execution Time (WCET) estimations for C programs. The WCET is an important property related to the safety of critical systems, but its estimation requires sophisticated techniques. To guarantee the absence of errors during WCET estimation, we have formally verified a WCET estimation technique based on the combination of two main methods: a loop bound estimation and the WCET estimation via the Implicit Path Enumeration Technique (IPET). The loop bound estimation itself is decomposed in three steps: a program slicing, a value analysis based on abstract interpretation, and a loop bound calculation stage. Each stage has a chapter dedicated to its formal verification. The entire development has been integrated into the formally verified C compiler CompCert. We prove that the final estimation is correct and we evaluate its performances on a set of reference benchmarks. The contributions of this thesis include (a) the formalization of the techniques used to estimate the WCET, (b) the estimation tool itself (obtained from the formalization), and (c) the experimental evaluation. We conclude that our formally verified development obtains interesting results in terms of precision, but it requires special precautions to ensure the proof effort remains manageable. The parallel development of specifications and proofs is essential to this end. Future works include the formalization of hardware cost models, as well as the development of more sophisticated analyses to improve the precision of the estimated WCET.

La modélisation géométrique est utilisée dans de nombreux domaines pour la construction d’objets 3D, l’animation ou les simulations. Chaque domaine est soumis à ses propres contraintes et nécessiterait un outil dédié. En pratique, un même outil est utilisé pour plusieurs domaines, en factorisant les caractéristiques communes. Ces modeleurs fournissent un ensemble d'opérations types, que l'utilisateur compose pour construire ses objets. Pour des opérations plus spécifiques, les outils actuels offrent des API.La plate-forme Jerboa propose un outil de génération d'opérations géométriques personnalisées. Elles sont définies graphiquement par des règles de transformations de graphes. Des vérifications automatiques de préservation de la cohérence des objets sont faites lors de l’édition qui peuvent être enrichies par des propriétés métiers. Notre contribution a consisté à étendre le langage par des scripts, pour composer les règles et réaliser des opérations complexes. Nous avons étendu les vérifications automatiques, en particulier pour assurer la cohérence géométrique. Enfin, nous avons modifié le processus d'application des opérations pour augmenter les possibilités de contrôle.Pour valider cette approche, nous avons développé un modeleur dédié à la géologie, pour la représentation du sous-sol, en collaboration avec l'entreprise Géosiris. Nous avons défini un flux d'activité avec Géosiris en suivant des contraintes spécifiques à la géologie. Grâce à la rapidité de développement des opérations dans Jerboa, nous avons pu prototyper et tester rapidement plusieurs algorithmes de reconstruction du sous-sol, pour les appliquer sur des données réelles fournies par l'entreprise. / Geometric modeling is used in various scopes for 3D object construction, animation or simulations. Each domain must cope with its constraints and should have its dedicated tool. In fact, several common characteristics of different domains are factored in a single tool. These modelers contain sets of basic operations that the user composes to build his objects. For more specific operations, current common tools offer API.Jerboa’s platform allows to generate personalized geometrical operations. These are defined by graph transformation rules. During their design, many automated verifications are done for the preserving of object consistency. They also be enriched with additional properties. Our contribution consists in extending the Jerboa language with scripts to compose rules and define complex operations. We also extended automated verifications, in particular to ensure geometric consistaency. Finally, we modified operations application process, in order to increase user control possibilities.To validate this approach, we have implemented a geological dedicated modeler for subsoil modeling, in collaboration with Geosiris Company. We defined a workflow with Geosiris that follows specific geological reconstruction constraints. Thanks to the Jerboa rapid prototyping mecanism, we developped and quickly tested several subsoil reconstruction algorithms, and apply them to real data provided by the company.

LNT est un langage formel de spécification récent, basé sur les algèbres de processus, où plusieurs processus concurrents et asynchrones peuvent interagir par rendez-vous multiple, c'est-à-dire à deux ou plus, avec échange de données. La boite à outils CADP (Construction and Analysis of Distributed Processes) offre plusieurs techniques relatives à l'exploration d'espace d'états, comme le model checking, pour vérifier formellement une spécification LNT. Cette thèse présente une méthode de génération d'implémentation distribuée à partir d'un modèle formel LNT décrivant une composition parallèle de processus. En s'appuyant sur CADP, nous avons mis au point le nouvel outil DLC (Distributed LNT Compiler), capable de générer, à partir d'une spécification LNT, une implémentation distribuée en C qui peut ensuite être déployée sur plusieurs machines distinctes reliées par un réseau. Pour implémenter de manière correcte et efficace les rendez-vous multiples avec échange de données entre processus distants, nous avons élaboré un protocole de synchronisation qui regroupe différentes approches proposées par le passé. Nous avons mis au point une méthode de vérification de ce type de protocole qui, en utilisant LNT et CADP, permet de détecter des boucles infinies ou des interblocages dus au protocole, et de vérifier que le protocole réalise des rendez-vous cohérents par rapport à une spécification donnée. Cette méthode nous a permis d'identifier de possibles interblocages dans un protocole de la littérature, et de vérifier le bon comportement de notre propre protocole. Nous avons aussi développé un mécanisme qui permet, en embarquant au sein d'une implémentation des procédures C librement définies par l'utilisateur, de mettre en place des interactions entre une implémentation générée et d'autres systèmes de son environnement. Enfin, nous avons appliqué DLC au nouvel algorithme de consensus Raft, qui nous sert de cas d'étude, notamment pour mesurer les performances d'une implémentation générée par DLC. / LNT is a recent formal specification language, based on process algebras, where several concurrent asynchronous processes can interact by multiway rendezvous (i.e., involving two or more processes), with data exchange. The CADP (Construction and Analysis of Distributed Processes) toolbox offers several techniques related to state space exploration, like model checking, to formally verify an LNT specification. This thesis introduces a distributed implementation generation method, starting from an LNT formal model of a parallel composition of processes. Taking advantage of CADP, we developed the new DLC (Distributed LNT Compiler) tool, which is able to generate, from an LNT specification, a distributed implementation in C that can be deployed on several distinct machines linked by a network. In order to handle multiway rendezvous with data exchange between distant processes in a correct and efficient manner, we designed a synchronization protocol that gathers different approaches suggested in the past. We set up a verification method for this kind of protocol, which, using LNT and CADP, can detect livelocks or deadlocks due to the protocol, and also check that the protocol leads to valid interactions with respect to a given specification. This method allowed us to identify possible deadlocks in a protocol from the literature, and to verify the good behavior of our own protocol. We also designed a mechanism that enables the final user, by embedding user-defined C procedures into the implementation, to set up interactions between the generated implementation and other systems in the environment. Finally, we used the new consensus algorithm Raft as a case study, in particular to measure the performances of an implementation generated by DLC.

Les architectures parallèles hybrides constituées d'un grand nombre de noeuds de calcul multi-coeurs/GPU connectés en réseau offrent des performances théoriques très élevées, de l'ordre de quelque dizaines de TeraFlops. Mais la programmation efficace de ces machines reste un défi à cause de la complexité de l'architecture et de la multiplication des modèles de programmation utilisés. L'objectif de cette thèse est d'améliorer la programmation des applications scientifiques denses sur les architectures parallèles hybrides selon trois axes: réduction des temps d'exécution, traitement de données de très grande taille et facilité de programmation. Nous avons pour cela proposé un modèle de programmation à base de directives appelé DSTEP pour exprimer à la fois la distribution des données et des calculs. Dans ce modèle, plusieurs types de distribution de données sont exprimables de façon unifiée à l'aide d'une directive "dstep distribute" et une réplication de certains éléments distribués peut être exprimée par un "halo". La directive "dstep gridify" exprime à la fois la distribution des calculs ainsi que leurs contraintes d'ordonnancement. Nous avons ensuite défini un modèle de distribution et montré la correction de la transformation de code du domaine séquentiel au domaine distribué. À partir du modèle de distribution, nous avons dérivé un schéma de compilation pour la transformation de programmes annotés de directives DSTEP en des programmes parallèles hybrides. Nous avons implémenté notre solution sous la forme d'un compilateur intégré à la plateforme de compilation PIPS ainsi qu'une bibliothèque fournissant les fonctionnalités du support d'exécution, notamment les communications. Notre solution a été validée sur des programmes de calcul scientifiques standards tirés des NAS Parallel Benchmarks et des Polybenchs ainsi que sur une application industrielle. / Clusters of multicore/GPU nodes connected with a fast network offer very high therotical peak performances, reaching tens of TeraFlops. Unfortunately, the efficient programing of such architectures remains challenging because of their complexity and the diversity of the existing programming models. The purpose of this thesis is to improve the programmability of dense scientific applications on hybrid architectures in three ways: reducing the execution times, processing larger data sets and reducing the programming effort. We propose DSTEP, a directive-based programming model expressing both data and computation distribution. A large set of distribution types are unified in a "dstep distribute" directive and the replication of some distributed elements can be expressed using a "halo". The "dstep gridify" directive expresses both the computation distribution and the schedule constraints of loop iterations. We define a distribution model and demonstrate the correctness of the code transformation from the sequential domain to the parallel domain. From the distribution model, we derive a generic compilation scheme transforming DSTEP annotated input programs into parallel hybrid ones. We have implemented such a tool as a compiler integrated to the PIPS compilation workbench together with a library offering the runtime functionality, especially the communication. Our solution is validated on scientific programs from the NAS Parallel Benchmarks and the PolyBenchs as well as on an industrial signal procesing application.

La recherche interroge la valorisation des archives du Nederlands Filmmuseum [NFM] à partir du travail de compilation du cinéaste Peter Delpeut. Ce corpus de dix films [1989-1999] se situe à cheval entre deux ambitions qui ne sont pas toujours compatibles, entre une volonté d’archiviste de rendre accessible des films muets [1895-1931] parfois de simples fragments, en restituant leur couleur, en créant une sonorisation et une quête artistique, plus personnel et liée à un cinéaste. Convoquant des sources audiovisuelles mais également écrites et orales, il s’agit d’abord de se demander comment le NFM en vient à produire ces compilations afin de mettre en valeur ses collections, de tracer l’histoire de cette cinémathèque et de suivre la trajectoire de Delpeut, en somme de comprendre la rencontre entre cet homme riche d’une expérience de recherche, de critique et de réalisation et une institution en plein bouleversement de sa philosophie dans les années 1990. Le questionnement s’oriente ensuite sur le processus de fabrication lui-même et de la façon dont fonctionnent ces compilations en vue de montrer comment elles sont prises en tension entre le sensoriel et l’analytique, étant au-delà et en deçà d’une stricte valorisation des films muets du NFM. La dernière partie interroge les usages des compilations, la manière dont elles sont liées à la politique de programmation du NFM, comment elles affectent la dynamique de l’institution et du cinéaste, mais aussi comment elles sortent du cadre de la cinémathèque, évaluant à chaque fois les apports et les limites en terme de transmission d’un patrimoine cinématographique. / The research examines the promotion of film archives from the Netherlands Filmmuseum [NFM] through Peter Delpeut’s compilation work. These ten films [1989-1999] are between two directions that are not always in compatibility, on one side an artistic cinematic search and on the other side the archivist’s will of giving access to silent films [1895-1931] that are in fragments, in colour and with a sound creation. Using audiovisual, written and oral sources, the first interest is to focus on whether how the NFM comes to produce these compilations for promoting its collections, lining out the history of this film archive and following Delpeut’s career, to understand the meeting between a man with great experience as researcher, critic and filmmaker and an institution challenging its philosophy during the 1990’s. The research then examines the process of filmmaking itself and functioning of this compilation work to show that there is a tension between sensorial and analytical terms, over the borderline of a strict promotion of NFM’s silent films. The last part explores the utilisation of these compilations, the way they are related to Museum’s programming politics, how they affect this institution and Delpeut’s dynamics, beyond the film archive, each time evaluating the contributions and limitations for the transmission of silent cinema heritage

Les systèmes temps-réel devenaient omniprésents, et jouent un rôle important dans notre vie quotidienne. Pour les systèmes temps-réel dur, calculer des résultats corrects n’est pas la seule exigence, il doivent de surcroît être produits dans un intervalle de temps borné. Connaître le pire cas de temps d’exécution (WCET - Worst Case Execution Time) est nécessaire, et garantit que le système répond à ses contraintes de temps. Pour obtenir des estimations de WCET précises, des annotations sont nécessaires. Ces annotations sont généralement ajoutées au niveau du code source, tandis que l’analyse de WCET est effectuée au niveau du code binaire. L’optimisation du compilateur est entre ces deux niveaux et a un effet sur la structure du code et annotations. Nous proposons dans cette thèse une infrastructure logicielle de transformation, qui pour chaque optimisation transforme les annotations du code source au code binaire. Cette infrastructure est capable de transformer les annotations sans perte d’information de flot. Nous avons choisi LLVM comme compilateur pour mettre en œuvre notre infrastructure. Et nous avons utilisé les jeux de test Mälardalen, TSVC et gcc-loop pour démontrer l’impact de notre infrastructure sur les optimisations du compilateur et la transformation d’annotations. Les résultats expérimentaux montrent que de nombreuses optimisations peuvent être activées avec notre système. Le nouveau WCET estimé est meilleur (plus faible) que l’original. Nous montrons également que les optimisations du compilateur sont bénéfiques pour les systèmes temps-réel. / Real-time systems have become ubiquitous, and play an important role in our everyday life. For hard real-time systems, computing correct results is not the only requirement. In addition, the worst-case execution times (WCET) are needed, and guarantee that they meet the required timing constraints. For tight WCET estimation, annotations are required. Annotations are usually added at source code level but WCET analysis is performed at binary code level. Compiler optimization is between these two levels and has an effect on the structure of the code and annotations.We propose a transformation framework for each optimization to trace the annotation information from source code level to binary code level. The framework can transform the annotations without loss of flow information. We choose LLVM as the compiler to implement our framework. And we use the Mälardalen, TSVC and gcc-loops benchmarks to demonstrate the impact of our framework on compiler optimizations and annotation transformation. The experimental results show that with our framework, many optimizations can be turned on, and we can still estimate WCET safely. The estimated WCET is better than the original one. We also show that compiler optimizations are beneficial for real-time systems.

L’intérêt des différents langages de la famille des diagrammes de décisionvalués (VDD) est qu’ils admettent des algorithmes en temps polynomialpour des traitements (comme l’optimisation, la cohérence inverse globale,l’inférence) qui ne sont pas polynomiaux (sous l’hypothèse P 6= NP), si ilssont effectués sur le problème dans sa forme originale tel que les réseaux decontraintes ou les réseaux bayésiens.Dans cette thèse, nous nous intéressons au problème de configuration deproduit, et plus spécifiquement, la configuration en ligne avec fonction de valuationassociée (typiquement, un prix). Ici, la présence d’un utilisateur enligne nous impose une réponse rapide à ses requêtes, rapidité rendant impossiblel’utilisation de langages n’admettant pas d’algorithmes en temps polynomialpour ces requêtes. La solution proposée est de compiler hors-ligneces problèmes vers des langages satisfaisant ces requêtes, afin de diminuer letemps de réponse pour l’utilisateur.Une première partie de cette thèse est consacrée à l’étude théorique desVDD, et plus particulièrement les trois langages Algebraic Decision Diagrams,Semi ring Labelled Decision Diagrams et Affine Algebraic Decision Diagrams(ADD, SLDD et AADD). Nous y remanions le cadre de définition des SLDD,proposons des procédures de traductions entre ces langages, et étudions la compacitéthéorique de ces langages. Nous établissons dans une deuxième partie lacarte de compilation de ces langages, dans laquelle nous déterminons la complexitéalgorithmique d’un ensemble de requêtes et transformations correspondantà nos besoins. Nous proposons également un algorithme de compilationà approche ascendante, ainsi que plusieurs heuristiques d’ordonnancement devariables et contraintes visant à minimiser la taille de la représentation aprèscompilation ainsi que le temps de compilation. Enfin la dernière partie estconsacrée à l’étude expérimentale de la compilation et de l’utilisation de formescompilées pour la configuration de produit. Ces expérimentations confirmentl’intérêt de notre approche pour la configuration en ligne de produit.Nous avons implémenté au cours de cette thèse un compilateur (le compilateurSALADD) pleinement fonctionnel, réalisant la compilation de réseauxde contraintes et de réseaux bayésiens, et avons développés un ensemble defonctions adaptées à la configuration de produit. Le bon fonctionnement etles bonnes performances de ce compilateur ont été validés via un protocole devalidation commun à plusieurs solveurs. / The different languages from the valued decision diagrams (VDD) family benefitfrom polynomial-time algorithms for some tasks of interest (such as optimization,global inverse consistency, inference) for which no polynomial-timealgorithm exists (unless P = NP) when the input is a constraint network ora Bayesian network considered at start.In this thesis, we focus on configuration product problems, and more specificallyon-line configuration with an associated valuation function (typically, aprice). In this case, the existence of an on-line user forces us to quickly answerto his requests, making impossible the use of languages that does not admitpolynomial-time algorithm for this requests. Therefore, our solution consistsin an off-line compilation of these problems into languages that admit suchpolynomial-time algorithms, and thus decreasing the latency for the user.The first part of this thesis is dedicated to the theoretical study of VDDs,an more specifically Algebraic Decision Diagrams (ADDs), Semi ring LabelledDecision Diagrams (SLDDs) and Affine Algebraic Decision Diagrams(AADDs). We revisit the SLDD framework, propose translation proceduresbetween these languages and study the succinctness of these languages. In asecond part, we establish a knowledge compilation map of these languages,in which we determine the complexity of requests and transformations correspondingto our needs. We also propose a bottom-up compilation algorithmand several variables and constraints ordering heuristics whose aim is to reducethe size of the compiled form, and the compilation time. The last partis an experimental study of the compilation and the use of the compiled formin product configuration. These experimentations confirm the interest of ourapproach for on-line product configuration.We also implemented a fully functional bottom-up compiler (the SALADDcompiler), which is capable of compiling constraints network and Bayesian networkinto SLDDs. We also developed a set of functions dedicated to productconfiguration. The proper functioning and good performances of this programwas validated by a validation protocol common to several solvers.