Ce manuscrit présente les travaux menés pour proposer un flot de conception permettant d'implanter des processeurs RISP dans un circuit reprogrammable (FPGA). Après une description des différentes solutions envisageables pour réaliser des prototypes dans le domaine du traitement d'image, ce document décrit une méthode qui consiste à générer des modèles matériels de processeurs destinés au traitement d'images, avec des opérateurs taillés sur une application donnée. Un ensemble d'expérimentations utilisant des algorithmes courants permet d'évaluer les performances du flot de conception proposé. Le prototypage rapide d'un système biométrique sans contact, basé sur la reconnaissance de paumes a été aussi réalisé sur la plateforme de test.

Les processeurs graphiques (GPU) actuels offrent une importante puissance de calcul disponible à faible coût. Ce fait a conduit à détourner leur emploi pour réaliser du calcul non graphique, donnant naissance au domaine du calcul généraliste sur processeur graphique (GPGPU). Cette thèse considère d'une part des techniques logicielles pour tirer parti de l'ensemble des opérateurs arithmétiques spécifiques aux GPU dans le cadre du calcul scientifique, et d'autre part des adaptations matérielles aux GPU afin d'exécuter plus efficacement les applications généralistes. En particulier, nous identifions la régularité parallèle comme une opportunité d'optimisation des architectures parallèles, et exposons son potentiel par la simulation d'une architecture GPU existante. Nous considérons ensuite deux alternatives permettant d'exploiter cette régularité. D'une part, nous mettons au point un mécanisme matériel dynamique afin d'améliorer l'efficacité énergétique des unités de calcul. D'autre part, nous présentons une analyse statique opérée à la compilation permettant de simplifier le matériel dédié au contrôle dans les GPU.

Depuis plusieurs années, le marché des circuits intégrés numériques requiert des systèmes de plus en plus complexes dans un temps toujours plus réduit. Afin de répondre à ses deux exigences, les industriels de la conception font appel à des fournisseurs externes proposant des circuits fonctionnant sur des signaux d'horloge dédiés. Lorsque ces derniers communiquent entre eux, les horloges d'émission et de réception ne sont pas les mêmes, on parle de « Clock Domain Crossing » (CDC).Les CDC correspondent à des communications asynchrones et peuvent provoquer des dysfonctionnements critiques. Par ailleurs, ces problèmes étant intermittents et complexes à analyser, ils ne peuvent pas être exhaustivement vérifiés avec des méthodes telles que l’analyse de timing ou la simulation fonctionnelle. Avec l'augmentation du nombre de CDC dans les circuits, les industriels de la conception assistée par ordinateur (EDA) ont proposé des solutions logicielles spécialisées dans la vérification statique des CDC. Cependant, les circuits développés étant en constante évolution, les outils ne sont pas en mesure de s’adapter. Pour pallier ces problèmes, la vérification industrielle des CDC est basée sur la spécification de contraintes et d'exclusions par l'utilisateur. Ces actions, qui se substituent aux outils, peuvent masquer des bugs. De plus, l’effort humain requis par cette approche n’est pas compatible avec le temps alloué au développement de circuits industriels. Nous avons donc cherché à automatiser la vérification en proposant des solutions basées sur des propriétés formelles. Les travaux ont consisté à analyser les différentes techniques de conception et de vérification des CDC à travers l’évaluation des principaux outils du marché. A partir des résultats obtenus, nous avons formalisé les problèmes pratiques et proposé des modèles permettant d’obtenir des résultats exhaustifs automatiquement. Les essais ont été réalisés sur un sous-système à base de processeurs (CPUSS) développé chez STMicroelectronics. L'adoption de nos modèles permet une vérification complète des CPUSS de manière automatique ce qui est essentiel dans un environnement industriel compétitif. En effet, le nombre d’informations devant être spécifiées par l’utilisateur a été réduit de moitié pour chacun des outils évalués. Par ailleurs, ces travaux ont montré que l’axe de développement des outils CDC avec l’ajout de fonctionnalités telles que les flots hiérarchiques ou l’injection de fautes n’améliore pas la qualité de résultats. Une collaboration ayant été mise en place avec les principaux fournisseurs outils, certaines solutions seront probablement intégrées aux outils dans les années à venir. / For several years now, the digital IC market has been requiring both more complex systems and reduced production times. In this context, the semiconductor chip maker companies call on external IP providers offering components working on dedicated clock signals. When these IPs communicate between them, the source and destination clocks are not the same, we talk about "Clock Domain Crossing" (CDC).CDC correspond to asynchronous communications and can cause critical failures. Furthermore, due to the complexity and the random nature of CDC issues, they can not be exhaustively checked with methods such as timing analysis or functional simulation. With the increase of CDC in the digital designs, EDA tools providers have developed software solutions dedicated to CDC static verification.Whereas, the designs are subject to continuous change, the verification tools are not able to be up to date. To resolve these practical issues, the CDC industrial verification is based on the specification of constraints and exclusions by the user. This manual flow, which replaces the tools, can mask bugs. Moreover, the human effort required by this approach is incompatible with the time allowed to industrial designs development.Our goal has been to automate the verification submitting solutions based on formal properties.The work consisted in the analysis of the different CDC design and verification approaches through the evaluation of main CDC checker tools. From the results obtained, we have formalized the practical problems and proposed models to obtain automatically exhaustive results. The tests have been performed on a processor-based subsystem (CPUSS) developed at STMicroelectronics.Adopting our models enables a complete checking of CPUSS in an automatic way, which is essential within a competitive industrial environment. Actually, the amount of information to be specified by the user has been reduced by half for each one of the evaluated tools. Otherwise, this work has shown that the development axis of the CDC tools despite the addition of functionalities such as hierarchical flows or fault injection, doesn’t improve the quality of results (QoR). Since a collaboration has been established with the main tool providers some solutions would probably be included into the tools over the coming years.

Les systèmes embarqués sont de plus en plus complexes et requièrent des besoins en puissance de calcul toujours plus importants. Ils doivent être capables de s'adapter à l'évolution rapide de leurs applications qui requièrent un haut niveau de performance (ordre du TOPS: Téra-opérations par seconde) et de parallélisme. Par ailleurs, la complexité des parties irrégulières étant de plus en plus importantes, des solutions de calcul performantes et adaptées doivent être mises en œuvre afin de prendre en compte leur dynamisme. Une prise en compte efficace du dynamisme réduit le déséquilibre de charge entre les ressources de calcul et améliore grandement les performances globales.Pour répondre aux besoins de ces applications de calcul intensif massivement parallèle et dynamique, nous proposons dans cette thèse l’architecture AHDAM qui signifie « Asymmetric Homogeneous with Dynamic Allocator Manycore architecture ». Cette architecture a été conçue afin de masquer efficacement la latence d’accès à la mémoire extérieure dont de nombreux accès sont nécessaires lors de la manipulation de grands volumes de données. Pour cela, des processeurs multitâches ont été utilisés. Par ailleurs, l’architecture AHDAM imbrique plusieurs niveaux de parallélisme afin de tirer partie efficacement des différentes formes de parallélisme des applications, et ainsi atteindre un haut niveau de performance. Enfin, cette architecture utilise un contrôleur centralisé pour équilibrer la charge de calcul entre ses ressources de calcul afin d’augmenter leur taux d’utilisation et supporter les applications fortement dynamiques.L’architecture AHDAM a été évaluée en portant une application de radio logicielle appelée «spectrum radio-sensing ». Avec 136 cœurs cadencés à 500 MHz, l'architecture AHDAM atteint une performance crête de 196 GOPS et répond aux exigences de l'application. / Embedded systems are getting more complex and require more intensive processing capabilities. They must be able to adapt to the rapid evolution of the high-end embedded applications that are characterized by their high computation-intensive workloads (order of TOPS: Tera Operations Per Second), and their high level of parallelism. Moreover, since the dynamism of the applications is becoming more significant, powerful computing solutions should be designed accordingly. By exploiting efficiently the dynamism, the load will be balanced between the computing resources, which will improve greatly the overall performance. To tackle the challenges of these future high-end massively-parallel dynamic embedded applications, we have designed the AHDAM architecture, which stands for “Asymmetric Homogeneous with Dynamic Allocator Manycore architecture". Its architecture permits to process applications with large data sets by efficiently hiding the processors' stall time using multithreaded processors. Besides, it exploits the parallelism of the applications at multiple levels so that they would be accelerated efficiently on dedicated resources, hence improving efficiently the overall performance. AHDAM architecture tackles the dynamism of these applications by dynamically balancing the load between its computing resources using a central controller to increase their utilization rate.The AHDAM architecture has been evaluated using a relevant embedded application from the telecommunication domain called “spectrum radio-sensing”. With 136 cores running at 500 MHz, AHDAM architecture reaches a peak performance of 196 GOPS and meets the computation requirements of the application.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L'omniprésence des ordinateurs et la demande de toujours plus de puissance poussent les architectes processeur à chercher des moyens d'augmenter les performances de ces processeurs. La tendance actuelle est de répliquer sur une même puce plusieurs cœurs d'exécution pour paralléliser l'exécution. Si elle se poursuit, les processeurs deviendront massivement multicoeurs avec plusieurs centaines voire un millier de cœurs disponibles. Cependant, la loi d'Amdahl nous rappelle que l'augmentation de la performance séquentielle sera toujours nécessaire pour améliorer les performances globales. Une voie essentielle pour accroître la performance séquentielle est de perfectionner le traitement des branchements, ceux-ci limitant le parallélisme d'instructions. La prédiction de branchements est la solution la plus étudiée, dont l'intérêt dépend essentiellement de la précision du prédicteur. Au cours des dernières années, cette précision a été continuellement améliorée et a atteint un seuil qu'il semble difficile de dépasser. Une autre solution est d'éliminer les branchements et de les remplacer par une construction reposant sur des instructions prédiquées. L'exécution des instructions prédiquées pose cependant plusieurs problèmes dans les processeurs à exécution dans le désordre, en particulier celui des définitions multiples. Les travaux présentés dans cette thèse explorent ces deux aspects du traitement des branchements. La première partie s'intéresse à la prédiction de branchements. Une solution pour améliorer celle-ci sans augmenter la précision est de réduire le coût d'une mauvaise prédiction. Cela est possible en exploitant la reconvergence de flot de contrôle et l'indépendance de contrôle pour récupérer une partie du travail fait par le processeur sur le mauvais chemin sur les instructions communes aux deux chemins pour éviter de le refaire sur le bon chemin. La deuxième partie s'intéresse aux instructions prédiquées. Nous proposons une solution au problème des définitions multiples qui passe par la prédiction sélective de la valeur des prédicats. Un mécanisme de rejeu sélectif est utilisé pour réduire le coût d'une mauvaise prédiction de prédicat. / Computers are everywhere and the need for always more computation power has pushed the processor architects to find new ways to increase performance. The today's tendency is to replicate execution core on the same die to parallelize the execution. If it goes on, processors will become manycores featuring hundred to a thousand cores. However, Amdahl's law reminds us that increasing the sequential performance will always be vital to increase global performance. A perfect way to increase sequential performance is to improve how branches are executed because they limit instruction level parallelism. The branch prediction is the most studied solution, its interest greatly depending on its accuracy. In the last years, this accuracy has been continuously improved up to reach a hardly exceeding limit. An other solution is to suppress the branches by replacing them with a construct based on predicated instructions. However, the execution of predicated instructions on out-of-order processors comes up with several problems like the multiple definition problem. This study investigates these two aspects of the branch treatment. The first part is about branch prediction. A way to improve it without increasing the accuracy is to reduce the coast of a branch misprediction. This is possible by exploiting control flow reconvergence and control independence. The work done on the wrong path on instructions common to the two paths is saved to be reused on the correct path. The second part is about predicated instructions. We propose a solution to the multiple definition problem by selectively predicting the predicate values. A selective replay mechanism is used to reduce the cost of a predicate misprediction.

Nous assistons à une explosion du nombre d’appareils mobiles équipés de capteurs optiques : smartphones, tablettes, drones... préfigurent un Internet des objets imminent. De nouvelles applications de traitement d’images (filtres, compression, réalité augmentée) exploitent ces capteurs mais doivent répondre à des contraintes fortes de vitesse et d’efficacité énergétique. Les architectures modernes — processeurs manycore, GPUs,... — offrent un potentiel de performance, avec cependant une hausse sensible de la complexité de programmation.L’ambition de cette thèse est de vérifier l’adéquation entre le domaine du traitement d’images et ces architectures modernes : concilier programmabilité, portabilité et performance reste encore aujourd’hui un défi. Le domaine du traitement d’images présente un fort parallélisme intrinsèque, qui peut potentiellement être exploité par les différents niveaux de parallélisme offerts par les architectures actuelles. Nous nous focalisons ici sur le domaine du traitement d’images par morphologie mathématique, et validons notre approche avec l’architecture manycore du processeur MPPA de la société Kalray.Nous prouvons d’abord la faisabilité de chaînes de compilation intégrées, composées de compilateurs, bibliothèques et d’environnements d’exécution, qui à partir de langages de haut niveau tirent parti de différents accélérateurs matériels. Nous nous concentrons plus particulièrement sur les processeurs manycore, suivant les différents modèles de programmation : OpenMP ; langage flot de données ; OpenCL ; passage de messages. Trois chaînes de compilation sur quatre ont été réalisées, et sont accessibles à des applications écrites dans des langages spécifiques au domaine du traitement d’images intégrés à Python ou C. Elles améliorent grandement la portabilité de ces applications, désormais exécutables sur un plus large panel d’architectures cibles.Ces chaînes de compilation nous ont ensuite permis de réaliser des expériences comparatives sur un jeu de sept applications de traitement d’images. Nous montrons que le processeur MPPA est en moyenne plus efficace énergétiquement qu’un ensemble d’accélérateurs matériels concurrents, et ceci particulièrement avec le modèle de programmation flot de données. Nous montrons que la compilation d’un langage spécifique intégré à Python vers un langage spécifique intégré à C permet d’augmenter la portabilité et d’améliorer les performances des applications écrites en Python.Nos chaînes de compilation forment enfin un environnement logiciel complet dédié au développement d’applications de traitement d’images par morphologie mathématique, capable de cibler efficacement différentes architectures matérielles, dont le processeur MPPA, et proposant des interfaces dans des langages de haut niveau. / Many mobile devices now integrate optic sensors; smartphones, tablets, drones... are foreshadowing an impending Internet of Things (IoT). New image processing applications (filters, compression, augmented reality) are taking advantage of these sensors under strong constraints of speed and energy efficiency. Modern architectures, such as manycore processors or GPUs, offer good performance, but are hard to program.This thesis aims at checking the adequacy between the image processing domain and these modern architectures: conciliating programmability, portability and performance is still a challenge today. Typical image processing applications feature strong, inherent parallelism, which can potentially be exploited by the various levels of hardware parallelism inside current architectures. We focus here on image processing based on mathematical morphology, and validate our approach using the manycore architecture of the Kalray MPPA processor.We first prove that integrated compilation chains, composed of compilers, libraries and run-time systems, allow to take advantage of various hardware accelerators from high-level languages. We especially focus on manycore processors, through various programming models: OpenMP, data-flow language, OpenCL, and message passing. Three out of four compilation chains have been developed, and are available to applications written in domain-specific languages (DSL) embedded in C or Python. They greatly improve the portability of applications, which can now be executed on a large panel of target architectures.Then, these compilation chains have allowed us to perform comparative experiments on a set of seven image processing applications. We show that the MPPA processor is on average more energy-efficient than competing hardware accelerators, especially with the data-flow programming model. We show that compiling a DSL embedded in Python to a DSL embedded in C increases both the portability and the performance of Python-written applications.Thus, our compilation chains form a complete software environment dedicated to image processing application development. This environment is able to efficiently target several hardware architectures, among them the MPPA processor, and offers interfaces in high-level languages.

Les primitives de la cryptographie à clé publique reposent sur la difficulté supposée de résoudre certains problèmes mathématiques. Dans ce travail, on s'intéresse à la cryptanalyse du problème du logarithme discret dans les sous-groupes multiplicatifs des corps finis. Les algorithmes de calcul d'index, utilisés dans ce contexte, nécessitent de résoudre de grands systèmes linéaires creux définis sur des corps finis de grande caractéristique. Cette algèbre linéaire représente dans beaucoup de cas le goulot d'étranglement qui empêche de cibler des tailles de corps plus grandes. L'objectif de cette thèse est d'explorer les éléments qui permettent d'accélérer cette algèbre linéaire sur des architectures pensées pour le calcul parallèle. On est amené à exploiter le parallélisme qui intervient dans différents niveaux algorithmiques et arithmétiques et à adapter les algorithmes classiques aux caractéristiques des architectures utilisées et aux spécificités du problème. Dans la première partie du manuscrit, on présente un rappel sur le contexte du logarithme discret et des architectures logicielles et matérielles utilisées. La seconde partie du manuscrit est consacrée à l'accélération de l'algèbre linéaire. Ce travail a donné lieu à deux implémentations de résolution de systèmes linéaires basées sur l'algorithme de Wiedemann par blocs : une implémentation adaptée à un cluster de GPU NVIDIA et une implémentation adaptée à un cluster de CPU multi-cœurs. Ces implémentations ont contribué à la réalisation de records de calcul de logarithme discret dans les corps binaires GF(2^{619}) et GF(2^{809} et dans le corps premier GF(p_{180}) / The security of public-key cryptographic primitives relies on the computational difficulty of solving some mathematical problems. In this work, we are interested in the cryptanalysis of the discrete logarithm problem over the multiplicative subgroups of finite fields. The index calculus algorithms, which are used in this context, require solving large sparse systems of linear equations over finite fields. This linear algebra represents a serious limiting factor when targeting larger fields. The object of this thesis is to explore all the elements that accelerate this linear algebra over parallel architectures. We need to exploit the different levels of parallelism provided by these computations and to adapt the state-of-the-art algorithms to the characteristics of the considered architectures and to the specificities of the problem. In the first part of the manuscript, we present an overview of the discrete logarithm context and an overview of the considered software and hardware architectures. The second part deals with accelerating the linear algebra. We developed two implementations of linear system solvers based on the block Wiedemann algorithm: an NVIDIA-GPU-based implementation and an implementation adapted to a cluster of multi-core CPU. These implementations contributed to solving the discrete logarithm problem in binary fields GF(2^{619}) et GF(2^{809}) and in the prime field GF(p_{180})

Avec l’augmentation du nombre de cœurs, les problèmes de congestion sont commencé avec les interconnexions conventionnelles. Afin de remédier à ces défis, WiNoCoD projet (Wired RF Network-on-Chip Reconfigurable-on-Demand) a été initié par le financement de l’Agence Nationale de Recherche (ANR). Ce travail de thèse contribue à WiNoCoD projet. Une structure de contrôleur de RF est proposé pour l’interconnexion OFDMA de WiNoCoD et plusieurs algorithmes d’allocation de bande passante efficaces (distribués et centralisés) sont développés, concernant les demandes et contraintes très spécifiques de l’environnement sur-puce. Un protocole innovante pour l’arbitrage des sous-porteuses pour des longueurs bimodales de paquets sur-puce, qui ne nécessite aucun signalisation supplémentaire est introduit. Utilisation des ordres de modulation élevés avec plus grande consommation d’énergie est évaluée. / With rapidly increasing number of cores on a single chip, scalability problems have arised due to congestion and latency with conventional interconnects. In order to address these issues, WiNoCoD project (Wired RF Network-on-Chip Reconfigurable-on-Demand) has been initiated by the support of French National Research Agency (ANR). This thesis work contributes to WiNoCoD project. A special RF controller structure has been proposed for the OFDMA based wired RF interconnect of WiNoCoD. Based on this architecture, effective bandwidth allocation algorithms have been presented, concerning very specific requirements and constraints of on-chip environment. An innovative subcarrier allocation protocol for bimodal packet lengths of cache coherency traffic has been presented, which is proven to decrease average latency significantly. In addition to these, effective modulation order selection policies for this interconnect have been introduced, which seeks the optimal delay-power trade-off.

PASC-HLL est une unité centrale d'ordinateur adaptée à l'exécution du langage Pascal. Cette réalisation illustre une méthodologie de conception descendante qui, à partir d'un cahier des charges (but) et en fonction des matériels existants (moyens) permet de concevoir la machine étape par étape depuis le langage Pascal jusqu'à la réalisation matérielle