Opérateurs arithmétiques matériels optimisés

Représentation des nombres

Les notions qui sont données ici sont détaillées et très bien expliquées dans deux ouvrages [13, 14] qui pourront être consultés pour davantage de précisions. La valeur v d’un nombre entier ou réel approché est codée à l’aide d’un ensemble de n bits notés {vn−1, · · · , v0}. Dans ce document, on s’intéresse à des nombres entiers ou virgule fixe (des nombres fractionnaires binaires). De plus, par souci de simplicité d’écriture et de clarté des explications, on ne traitera que la base 2. Néanmoins, le passage à d’autres bases est assez direct, en particulier pour les puissances de 2. Pour lire v, on établit une bijection entre les valeurs booléennes, codées électriquement par chaque fil, et l’ensemble de chiffres {0, 1} pour chacun des vi . Il existe différentes manières d’interpréter la valeur de ces fils pour en déduire la valeur mathématique v. Les formats de représentation présentés ci-dessous permettent de coder des entiers. Si on veut travailler sur des approximations de réels, on introduit un facteur d’échelle ULP(v) (pour Unit in Last Position) par lequel on multiplie l’entier codé pour obtenir v. Ce facteur est une puissance de 2 constante pour une notation donnée, qui indique le poids du bit le plus faible. Par exemple, ULP(v) vaut 1 si on travaille sur des entiers. Si ULP(v) = 2−2 , alors on sait que les valeurs v ont deux bits après la virgule, c’est la partie fractionnaire. On est ainsi capable d’attribuer une valeur entière ou virgule fixe à un vecteur de valeurs logiques codées électriquement. – La notation non signée ou numération simple de position représente une valeur positive v par : v = ULP(v) Xn−1 i=0 vi 2 i , d’où v ∈ 

Types de fonctions 

On peut classer les fonctions en deux catégories [15] que sont les fonctions élémentaires (fonctions habituellement utilisées et qu’on peut construire facilement) et les fonctions spéciales (fonctions régulières usitées en physique qui ne sont pas élémentaires : erf, fonctions elliptiques, fonctions de Jacobi, etc.) qui sont difficilement évaluables. Les fonctions élémentaires sont elles-mêmes subdivisées entre fonctions algébriques (solutions d’une équation algébrique) et fonctions transcendantes (sin, tan, exp, log, etc.). Ces catégories s’entendent pour les fonctions d’une variable (plus couramment utilisées) mais elles s’étendent facilement aux fonctions à plusieurs variables comme √ x + y qui est une fonction algébrique à deux variable

Types d’évaluation

L’évaluation en matériel de fonctions numériques est un point crucial dans de nombreuses applications. L’inverse et la fonction sinus sont souvent utilisées en traitement du signal. Les fonctions transcendantes sont récurrentes en calcul flottant, et des fonctions algébriques comme la racine carrée et la norme euclidienne se retrouvent souvent dans des applications graphiques. Le calcul de ces fonctions dans des opérateurs spécialisés est souvent beaucoup plus efficace qu’avec des structures génériques complètes (additions et multiplications de taille inutilement importante). De nombreuses méthodes existent pour l’évaluation de fonctions en matériel : méthodes à base de tables, algorithmes à récurrence de chiffres, approximations polynomiales ou rationnelles, ou encore des combinaisons de ces méthodes [13, 15]. Les méthodes à base de tables sont souvent utilisées pour des applications avec de petits besoins en précision. Des précisions plus grandes peuvent être obtenues en combinant tables et opérations arithmétiques [20, 21]. Les algorithmes à récurrence de chiffres, ou algorithmes décalage-addition, produisent un chiffre du résultat par itération en partant du chiffre de poids le plus fort, comme la division à la main. Les deux plus fameux algorithmes à récurrence de chiffres sont : les algorithmes de type SRT pour la division, racine carrée et autres fonctions algébriques [13], et l’algorithme CORDIC pour certaines fonctions élémentaires [15]. Ces algorithmes utilisent seulement des additions et décalages (plus éventuellement des petites tables) pour le calcul de chaque itération. Ils donnent lieu à des opérateurs qui sont petits, mais qui ont une forte latence à cause de leur convergence linéaire. Augmenter leur base de travail réduit le nombre d’itérations nécessaires, mais demande des circuits sensiblement plus gros pour le calcul des itérations. Les approximations polynomiales sont largement utilisées pour l’évaluation de fonctions, même en matériel où la taille des multiplieurs utilisés pour leur évaluation est un problème majeur. Ces approximations permettent d’évaluer la plupart des fonctions courantes pour peu qu’elles soient régulières. Les approximations rationnelles permettent une évaluation plus précise, mais elles requièrent une division qui s’ajoute au coût matériel si on la calcule de manière classique (un algorithme comme la Eméthode [17, 16] calcule cette division mais de manière « cachée » sans payer le prix d’une opération supplémentaire) et introduit une latence supplémentaire souvent importante. 

Implantation matérielle

Le but d’une implantation matérielle des fonctions numériques est l’amélioration des performances. Par exemple, l’implantation de fonctions cryptographiques en matériel fait habituellement gagner plusieurs ordres de grandeur en vitesse par rapport aux mêmes fonctions codées en logiciel. En plus d’être rapide, un opérateur doit aussi occuper la plus petite surface possible pour des raisons de coût.  Maintenir une bibliothèque contenant les descriptions en VHDL (Very-high-speedintegrated-circuit Hardware Description Language) d’opérateurs spécialisés est difficile, du fait de la gestion limitée des paramètres génériques dans ce langage. Notre approche est donc, plutôt que de fournir une bibliothèque VHDL, d’écrire des programmes en C ou C++ qui génèrent des descriptions d’opérateurs optimisés. L’utilisation de générateurs permet d’effectuer simplement des calculs plus complexes que ceux qu’on ferait à l’aide de formules VHDL, et d’explorer l’espace des paramètres. On trouve ainsi des solutions bien plus efficaces que ce qu’on peut obtenir à l’aide du VHDL seul. La rigidité du VHDL rend aussi difficile l’écriture de certaines structures, même si elles sont régulières, comme par exemple des arbres. Les implantations matérielles des opérateurs décrits dans cette thèse ont été faites sur des circuits de type FPGA (pour Field-Programmable Gate Array). Bien qu’ils soient moins performants que des circuits numériques spécialisés de type ASIC (pour Application-Specific Integrated Circuits), les FPGA ont un coût de développement bien moindre et leur mise en œuvre pour le prototypage est beaucoup plus facile et rapide. De plus, ils disposent de ressources suffisantes même pour des architectures complexes. Toutes ces raisons en font de bons candidats pour la mise en pratique de nos travaux. Les résultats présentés ici peuvent être facilement adaptés aux circuits ASIC, moyennant quelques modifications pour adapter les opérateurs à la structure particulière des ASIC. Par exemple, l’absence de lignes de fast-carry demanderait l’utilisation d’un algorithme plus efficace que l’addition à propagation de retenue, comme des additionneurs à saut de retenue (carry-skip) [13].