Η υλοποίηση αποδοτικών αριθμητικών κυκλωμάτων αποτελεί ένα ανοικτό πεδίο έρευνας καθώς η συνεχής εξέλιξη της τεχνολογίας απαιτεί την επανεκτίμηση των μεθόδων σχεδίασής τους, ενώ παράλληλα δημιουργεί νέους τομείς εφαρμογής τους. Ο τεράστιος όγκος πληροφορίας και η ανάγκη γρήγορης επεξεργασίας της έχει οδηγήσει στην ανάγκη αύξησης της συχνότητας λειτουργίας των αντίστοιχων κυκλωμάτων. Μεγάλης σημασίας παραμένει επίσης η ανάγκη για τη μείωση της κατανάλωσης ισχύος των συστημάτων αυτών, αλλά και του κόστους τους, που συνδέονται άμεσα με την επιφάνεια ολοκλήρωσής τους. Η ικανοποίηση των παραμέτρων αυτών επιτάσσει σε διάφορες περιπτώσεις την υιοθέτηση αριθμητικών συστημάτων, πέραν του συμβατικού δυαδικού συστήματος. Χαρακτηριστικά παραδείγματα αποτελούν το Αριθμητικό Σύστημα Υπολοίπων (Residue Number System – RNS) όπως επίσης και τα αριθμητικά συστήματα πλεοναζουσών αναπαραστάσεων (redundant number systems). Η διδακτορική αυτή διατριβή ασχολείται με την υλοποίηση αποδοτικών κυκλωμάτων για το Αριθμητικό Σύστημα Υπολοίπων, με την έρευνα να επικεντρώνεται στην υιοθέτηση τόσο πλεοναζουσών όσο και μη-πλεοναζουσών αναπαραστάσεων στα διάφορα κανάλια επεξεργασίας του. Το πρώτο μέρος της διατριβής έχει ως στόχο τη σχεδίαση αποδοτικών κυκλωμάτων υπολοίπων με χρήση μη-πλεοναζουσών αναπαραστάσεων τόσο για τις κύριες-βασικές αριθμητικές πράξεις (πρόσθεση, πολλαπλασιασμός) όσο και για τις δευτερεύουσες-βοηθητικές (αφαίρεση, ύψωση σε δύναμη) πράξεις. Συγκεκριμένα, παρουσιάζονται κυκλώματα αφαίρεσης και πρόσθεσης/αφαίρεσης για κανάλια υπολοίπου της μορφής 2^n+-1, κυκλώματα πολλαπλασιασμού με σταθερά για το σύνολο διαιρετών {2^n-1, 2^n, 2^n+1} καθώς και κυκλώματα Booth πολλαπλασιασμού προγραμματιζόμενης λογικής για τα κανάλια υπολοίπου 2^n+-1. Επιπλέον, παρουσιάζονται κυκλώματα ύψωσης στον κύβο για το κανάλι υπολοίπου 2^n-1. Προτείνεται επίσης μια οικογένεια αριθμητικών κυκλωμάτων (αθροιστές, αφαιρέτες, πολλαπλασιαστές, κυκλώματα ύψωσης στο τετράγωνο) υπολοίπου 2^n+1 για την αναπαράσταση ελάττωσης κατά 1, που ενσωματώνουν τη μετατροπή του αποτελέσματος στην κανονική αναπαράσταση μέσα στην αρχιτεκτονική τους, ενώ παρουσιάζεται και μία ενιαία μεθοδολογία σχεδίασης κυκλωμάτων ανάστροφης μετατροπής για σύνολα διαιρετών με κανάλια της μορφής 2^n+1 που υιοθετούν την αναπαράσταση ελάττωσης κατά 1. Τέλος, διερευνούνται και οι διαιρέτες της μορφής 2^n-2 και προτείνονται για αυτούς αποδοτικές αρχιτεκτονικές κυκλωμάτων πρόσθεσης, πολλαπλασιασμού, ύψωσης στο τετράγωνο και ευθείας μετατροπής. Στο δεύτερο μέρος της διατριβής το ενδιαφέρον εστιάζεται σε μία διαφορετική κατηγορία αναπαραστάσεων, οι οποίες παρέχουν περισσότερους από ένα δυνατούς τρόπους κωδικοποίησης των εντέλων τους. Οι πλεονάζουσες αυτές αναπαραστάσεις παρουσιάζουν συγκεκριμένα χαρακτηριστικά, όπως η δυνατότητα εξισορρόπησης ταχύτητας και επιφάνειας υλοποίησης. Στη διατριβή εξετάζονται τρεις πλεονάζουσες αναπαραστάσεις για το Αριθμητικό Σύστημα Υπολοίπων με κανάλια διαιρετών της μορφής 2^n+-1 και παρουσιάζεται μία γενικευμένη μεθοδολογία διαχείρισης των ψηφίων τους, η οποία εφαρμόζεται στη σχεδίαση κυκλωμάτων μετατροπής. Στο τελευταίο μέρος περιγράφονται δύο εφαρμογές συστημάτων που βασίζονται στο Αριθμητικό Σύστημα Υπολοίπων. Αναλυτικότερα, σχεδιάζεται και υλοποιείται ένα σύστημα ανίχνευσης ακμών σε εικόνα με ένα στάδιο προ-επεξεργασίας για μείωση του θορύβου καθώς και τρία φίλτρα πεπερασμένης κρουστικής απόκρισης. / The implementation of efficient arithmetic circuits has always been an open field for research, since the technology evolves rapidly, demanding the reevaluation of their design methods. At the same time this continuous evolution opens new research areas for these circuits. The need for fast processing of a vast amount of information demands an increase of the operational frequency of the corresponding circuits, while at the same time low power consumption, low cost and therefore low area remain of crucial importance. Meeting these needs in arithmetic circuits usually implies the employment of alternative, non-binary number systems. Such examples are the Residue Number System (RNS) and number systems with redundant representations. The subject of this PhD dissertation is the implementation of efficient arithmetic circuits for the RNS emphasizing both in redundant and not redundant representations. The first part of the dissertation deals with the design of efficient non-redundant arithmetic circuits for main arithmetic operations such as addition and multiplication that are met in every processing system, as well as for auxiliary operations like subtraction, squaring and cubing. Specifically, the circuits presented include subtractors and adders/subtractors for the moduli channels of the 2^n+-1 form, single-constant multipliers for the {2^n-1, 2^n, 2^n+1} moduli set, configurable modulo 2^n +-1 Booth-encoded multipliers as well as modulo 2^n-1 cubing units. Furthermore, a family of diminished-1 modulo 2^n+1 arithmetic circuits (adders, subtractors, multipliers and squarers) is also presented, that produces the respective result directly to weighted (normal) representation, embedding that way the conversion process between these two representations. The design of efficient Residue-to-Binary converters is also considered and a novel generic methodology is proposed for the systematic design of those circuits. The modulo 2^n-2 channel is also investigated and an arithmetic processing framework is proposed including adders, multipliers, squarers and Binary-to-Residue converters. In the second part, we focus on a different category of representations, where operands can be encoded in more than one ways. Such representations offer certain characteristics such as a tradeoff between area and speed. In particular, we consider three redundant representations for the RNS processing channels of the 2^n+-1 form, which are the most common choice. A generic methodology is presented for treating their digits in order to design efficient converters for them. The last part of the dissertation presents two applications that are implemented entirely in the RNS domain. Their architectures rely on the proposed arithmetic circuits. The first application is an image edge detector with a pre-processing noise filtering stage. The second application involves the design of three Finite Impulse Response (FIR) filters.

Avec la diminution du nœud de la technologie CMOS, la puissance statique et dynamique augmente spectaculairement. It est devenu l'un des principaux problèmes en raison de l'augmentation du courant de fuite et de la longue distance entre les mémoires et les circuits logiques. Au cours des dernières décennies, les dispositifs de spintronique, tels que la jonction tunnel magnétique (JTM) écrit par transfert de spin, sont largement étudiés pour résoudre le problème de la puissance statique grâce à leur non-volatilité. L'architecture logic-in-memory (LIM) hybride permet de fabriquer les dispositifs de spintronique au-dessus des circuits CMOS, réduisant le temps de transfert et la puissance dynamique. Cette thèse vise à la conception de circuits logiques et mémoires pour le système de faible puissance, en combinant les technologies JTM et CMOS. En utilisant un modèle compact JTM et le design-kit CMOS de STMicroelectronics, nous étudions les circuits hybrides MTJ/CMOS de 1-bit et multi-bit, y compris les opérations de lecture et d'écriture. Les méthodes d'optimisation sont également introduites pour améliorer la fiabilité, ce qui est extrêmement important pour les circuits logiques où les blocs de correction d'erreur ne peuvent pas être facilement intégrés sans sacrifier leurs performances ou augmenter la surface de circuit. Nous étendons la structure MTJ/CMOS hybride de multi-bit à la conception d’une mémoire MRAM avec les circuits périphériques simples. Basés sur le concept de LIM, les circuits logiques/arithmétiques non-volatiles sont conçus. Les JTMs sont intégrés non seulement comme des éléments de stockage, mais aussi comme des opérandes logiques. Tout d'abord, nous concevons et analysons théoriquement les portes logiques non-volatiles (PLNVs) comprenant NOT, AND, OR et XOR. Ensuite, les additionneurs complets non-volatiles (ACNVs) de 1-bit et 8-bit sont proposés et comparés avec l'additionneur classique basé sur la technologie CMOS. Nous étudions l'effet de la taille de transistor CMOS et des paramètres de JMT sur les performances d’ACNV. De plus, nous optimisons l’ACNV sous deux faces. Premièrement, un circuit de détection (mode de tension) de très haute fiabilité est proposé. Après, nous proposons de remplacer le JTM à deux électrodes par un JTM à trois électrodes (écrit par transfert de spin assisté par l’effet Hall de spin) en raison du temps d'écriture et de la puissance plus petit. Basé sur les PLNVs et ACNVs, d'autres circuits logiques peuvent être construits, par exemple, soustracteur non-volatile. Enfin, une mémoire adressable par contenu non-volatile (MACNV) est proposée. Deux décodeurs magnétiques visent à sélectionner des lignes et à enregistrer la position de recherche dans un état non-volatile. / With the shrinking of CMOS (complementary metal oxide semi-conductor) technology, static and dynamic power increase dramatically and indeed has become one of the main challenges due to the increasing leakage current and long transfer distance between memory and logic chips. In the past decades, spintronics devices, such as spin transfer torque based magnetic tunnel junction (STT-MTJ), are widely investigated to overcome the static power issue thanks to their non-volatility. Hybrid logic-in-memory (LIM) architecture allows spintronics devices to be fabricated over the CMOS circuit plane, thereby reducing the transfer latency and the dynamic power dissipation. This thesis focuses on the design of hybrid MTJ/CMOS logic circuits and memories for low-power computing system.By using a compact MTJ model and the STMicroelectronics design kit for regular CMOS design, we investigate the hybrid MTJ/CMOS circuits for single-bit and multi-bit reading and writing. Optimization methods are also introduced to improve the reliability, which is extremely important for logic circuits where error correction blocks cannot be easily embedded without sacrificing their performances or adding extra area to the circuit. We extend the application of multi-context hybrid MTJ/CMOS structure to the memory design. Magnetic random access memory (MRAM) with simple peripheral circuits is designed.Based on the LIM concept, non-volatile logic/arithmetic circuits are designed to integrate MTJs not only as storage elements but also as logic operands. First, we design and theoretically analyze the non-volatile logic gates (NVLGs) including NOT, AND, OR and XOR. Then, 1-bit and 8-bit non-volatile full-adders (NVFAs), the basic elements for arithmetic operations, are proposed and compared with the traditional CMOS-based full-adder. The effect of CMOS transistor sizing and the MTJ parameters on the performances of NVFA is studied. Furthermore, we optimize the NVFA from two levels. From the structure-level, an ultra-high reliability voltage-mode sensing circuit is used to store the operand of NVFA. From the device-level, we propose 3-terminal MTJ switched by spin-Hall-assisted STT to replace the 2-terminal MTJ because of its smaller writing time and power consumption. Based on the NVLGs and NVFAs, other logic circuits can be built, for instance, non-volatile subtractor.Finally, non-volatile content addressable memory (NVCAM) is proposed. Two magnetic decoders aim at selecting a word line to be read or written and saving the corresponding search location in non-volatile state.

La complexité algorithmique est l'étude des ressources nécessaires — le temps, la mémoire, … — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question « VP = VNP ? », version algébrique de « P = NP ? », nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. / Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.