Nombres, opérations, algorithmes et circuits
Cours de recherche (24h de cours, travail
sur des articles scientifiques)
Cours : Florent de Dinechin (Florent.de.Dinechin)
Ce cours étudie les quatre opérations (et quelques autres) et leur
implémentation comme opérateurs dans les ordinateurs. Au 21ème
siècle, il y a encore chaque année de nombreuses publications sur la
meilleure manière de réaliser une addition, et ce
cours est une introduction aux problématiques mises en jeu.
On s'intéresse d'abord aux descriptions algorithmiques de ces
opérations de base. Mais celles-ci dépendent du système employé pour
représenter les nombres. On verra dans ce cours tout un bestiaire de
systèmes, partant de notre bon vieux système de numération de
position (en base 10, 2 ou 264), passant par des variations où les
chiffres sont signés et où la bijection entre un nombre et sa
représentation disparait, pour finir par des représentations
franchement exotiques comme les systèmes modulaires et les systèmes
à plusieurs bases pour les entiers, et les systèmes logarithmiques
pour les réels.
Mais un bon système est un système qui permet de réaliser de bons
opérateurs. Après avoir passé en revue les métriques qui permettent
d'évaluer la qualité d'un opérateur dans différentes technologies,
nous étudierons quelques compromis d”implémentation en matériel.
Plan indicatif
-
Introduction
- Contexte mathématico-architectural
-
Systèmes de représentation des nombres et les quatre
opérations
- Circuits combinatoires, synchrones et asynchrones
- Les métriques de la technologie VLSI
- Opérateurs rapides sur les entiers
- Évaluation des fonctions élémentaires
- Virgule flottante
- Systèmes logarithmiques
- Systèmes RNS
- Arithmétique série
- Opérateurs pour la cryptographie
Bibliographie
-
Ercegovac et Lang, Digital Arithmetic, Morgan Kaufmann, 2003
- Flynn et Oberman, Advanced Computer Arithmetic Design, John Wiley & sons, 2001
- Parhami, Computer Arithmetic, Oxford University Press, 2000
- Koren, Computer Arithmetic Algorithms, Prentice Hall, 1993/2002
- Muller, Arithmétique des ordinateurs, Masson, 1989