Arithm´ etique des ordinateurs Arnaud Tisserand Ar´ enaire INRIA LIP ´ Ecole do

Arithm´ etique des ordinateurs Arnaud Tisserand Ar´ enaire INRIA LIP ´ Ecole doctorale de math´ ematiques et d’informatique fondamentale de Lyon 12 avril 2005 Plan de l’expos´ e – Introduction — Arithm´ etique flottante A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 2/76 Partie 1 Introduction A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 3/76 L’arithm´ etique chez les Babyloniens Utilisation d’un syst` eme de position (le premier de l’histoire) en base 60 avec les chiffres suivants (et la base auxiliaire 10) : 1 2 3 4 5 6 7 8 9 10 Exemple de codage : = 33 × 60 + 24 = 2004 Syst` eme de position en base β sur n chiffres (pour des entiers naturels) : x = xn−1xn−2 · · · x1x0 = n−1 X i=0 xi βi A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 4/76 Oh, la belle table de multiplication. . . Illustration de la table de multi- plication par 25 trouv´ ee ` a Suse et dat´ ee du IIe mill´ enaire av. J.-C (conserv´ ee au Mus´ ee du Louvre). Remarque : seuls les produits par (1), 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40, 50 sont n´ ecessaires sur les 59 possibles. A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 5/76 Le boulier chinois : position de repos (0) x5 x1 10 1 100 1 000 10 000 100 000 1 000 000 10 000 000 100 000 000 1 000 000 000 • Les colonnes repr´ esentent les unit´ es, les dizaines, les centaines, les mil- liers,. . . de la droite vers la gauche • Les boules sont activ´ ees lorsqu’elles sont au plus proche de la barre du milieu, et d´ esactiv´ ees sinon (0 est donc repr´ esent´ e ci-dessus) • Les boules situ´ ees au dessus de la barre horizontale du milieu sont multipli´ ees par 5 (celles de dessous par 1). A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 6/76 Le boulier chinois : ´ ecriture de 2647 2 6 7 4 La premi` ere illustration connue d’un boulier chinois dans un livre date de 1175. Il existe des dispositifs proches (tablettes avec des rainures sur lesquelles on d´ eplace des petits cailloux) depuis bien plus longtemps. Il existe des concours de rapidit´ e de calcul sur des bouliers. Le japonais Yoshio Kogima a effectu´ e correctement 50 divisions, avec des op´ erandes de 5 ` a 7 chiffres, en 1 min 18 s et 4 centi` emes sur un boulier japonais (soroban) ! A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 7/76 Le boulier chinois : 2647+1362 2 6 7 4 +1 +1 +3 +1 +3 +6 +1 +3 +6 +2 4 0 0 9 état de départ état 1 état 3 état 5 état 2 état 4 A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 8/76 Arithm´ etique des ordinateurs ´ Etude et conception de “moyens” pour effectuer les calculs de base en machine. • unit´ es de calcul mat´ erielles : ▶additionneur/soustracteur, multiplieur, diviseur, . . . ▶unit´ es flottantes ▶op´ erateurs sp´ ecifiques (ex : filtres pour traitement du signal) • support logiciel pour les calculs de base : ▶biblioth` eques math´ ematiques de base (libm) ▶biblioth` eques de fonctions ´ el´ ementaires (sin, cos, exp, log, . . .) ▶biblioth` eques multi-pr´ ecision ▶biblioth` eques d’arithm´ etique d’intervalle • validation de la qualit´ e num´ erique : ▶test et/ou preuve de la pr´ ecision de calculs ▶preuve du bon comportement des op´ erations (d´ epassements, . . . ) A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 9/76 Arithm´ etique des ordinateurs (suite) Les trois aspects fondamentaux de l’arithm´ etique des ordinateurs : • Syst` emes de repr´ esentation des nombres : entier, virgule fixe, virgule flottante, redondant, grande base, syst` eme logarithmique, syst` eme modulaire, corps finis. . . • Algorithmes de calcul : addition–soustraction, multiplication, division, PGCD, racine carr´ ee, fonc- tions ´ el´ ementaires (sin, cos, exp, log . . .), op´ erateurs composites (ex : 1/ p (x2 + y2)), op´ erateurs sp´ ecifiques (FIR, DCT, crypto), algorithmes num´ eriques, preuves de programmes. . . • Maˆ ıtriser les implantations : cibles logicielles et mat´ erielles, support arithm´ etique dans les langages de programmation, validation, test, optimisation des performances (vitesse, m´ emoire, surface de circuit, temps r´ eel, consommation d’´ energie). . . A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 10/76 Arithm´ etique des ordinateurs (suite) Liens avec : • architecture des ordinateurs • micro-´ electronique • outils CAO de circuits • algorithmes num´ eriques • calcul formel • optimisation globale • th´ eorie des nombres • preuves formelles • . . . A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 11/76 Arithm´ etique des ordinateurs (suite) Exemples de sujets de recherche dans l’´ equipe/projet Ar´ enaire : • biblioth` eque de fonctions ´ el´ ementaires avec arrondi correct • biblioth` eque d’arithm´ etique d’intervalle en multi-pr´ ecision • biblioth` eque pour le support flottant dans les processeurs entiers • op´ erateurs de cryptographie pour circuits FPGA • unit´ es flottantes et logarithmiques pour circuits FPGA • op´ erateurs arithm´ etiques mat´ eriels ` a basse consommation d’´ energie • arithm´ etique corps finis pour biblioth` eque d’alg` ebre lin´ eaire • preuves automatiques d’op´ erations arithm´ etiques A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 12/76 Syst` eme logarithmique Un nombre est repr´ esent´ e par son signe et le logarithme de sa valeur absolue ´ ecrit en virgule fixe (le nombre 0 doit ˆ etre repr´ esent´ e par un codage sp´ ecial). Les op´ erations dans ce syst` eme s’effectuent en utilisant : log2(a × b) = log2 a + log2 b log2(a ÷ b) = log2 a −log2 b log2(a ± b) = log2 a + log2(1 ± 2log2 b−log2 a) log2(aq) = q × log2 a o` u les fonctions log2(1 + 2x) et log2(1 −2x) sont tabul´ ees ou approch´ ees. Applications en traitement du signal et en contrˆ ole num´ erique. Il y avait mˆ eme un projet europ´ een pour concevoir un processeur avec des unit´ es de calcul 32 bits en syst` eme logarithmique. A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 13/76 Besoins dans les processeurs/architectures ´ evolu´ es • Op´ erateurs arithm´ etiques capables de fonctionner ` a de hautes fr´ equences • Op´ erateurs arithm´ etiques ` a basse consommation d’´ energie pour les appli- cations embarqu´ ees et les appareils portables • Prendre en compte les nouvelles contraintes technologiques • Ajout de nouvelles fonctionnalit´ es de calcul, exemple : FMA (fused multiply and add), op´ erateurs de cryptographie, unit´ es graphiques • Sujets de recherche actuels sur les op´ erateurs arithm´ etiques mat´ eriels : ▶nouvelles fonctionnalit´ es ▶basse consommation d’´ energie ▶op´ erateurs reconfigurables ▶op´ erateurs pour la cryptographie/signature ▶. . . A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 14/76 Suite de J.-M. Muller      u0 = 2 u1 = −4 un+1 = 111 −1130 un + 3000 unun−1 −100 −50 0 50 100 0 5 10 15 20 u(n) n n un programme C n un programme C 0 2.000000000000000 9 2.913589954376221 1 -4.000000000000000 10 -111.709793090820312 2 18.500000000000000 11 111.898239135742188 3 9.378377914428711 12 100.661544799804688 4 7.801147460937500 13 100.040603637695312 5 7.154346466064453 14 100.002494812011719 6 6.805830478668213 15 100.000152587890625 7 6.578579425811768 16 100.000007629394531 8 6.235515594482422 17 100.000000000000000 Et pourtant, (un) converge th´ eoriquement vers 6 ! A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 15/76 Exemple de Shampine et Watts (1/2) On cherche la solution de l’´ equation diff´ erentielle suivante :  f ′(x) = 10(f(x) −x2) f(0) = 0.02 R´ esolution num´ erique par la m´ ethode de Runge-Kutta d’ordre 4 (et 100000 points) sur un PentiumIV : valeur f(x) prg. C (float) prg. C (double) exacte f(1) 1.07524 1.22 1.22 f(2) 1018.31 4.42 4.42 f(3) -1.4026e+07 9.66711 9.62 f(4) 4.97446e+11 -250.367 16.82 f(5) -1.91225e+14 1.45778e+07 26.02 f(6) -7.33462e+19 -1.22707e+11 37.22 A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 16/76 Exemple de Shampine et Watts (2/2) La solution de  f ′(x) = 10(f(x) −x2) f(0) = 0.02 est f(x) = 1 50 + 1 5x + x2 Celle de  f ′(x) = 10(f(x) −x2) f(0) = c est f(x) = 1 50 + 1 5x + x2 + (c −1 50)e10x La solution d´ epend donc tr` es fortement des conditions initiales. A. Tisserand – INRIA LIP Ar´ enaire – Arithm´ etique des ordinateurs 17/76 Maple : BUG # 1542 Bug pr´ esent sur la version “Maple 6.01, IBM uploads/Litterature/ arithmetiques-des-ordinateurs-plan-d-x27-expose.pdf

• Détails
• Publié le Jui 12, 2022
• Catégorie Literature / Litté...
• Langue French
• Taille du fichier 0.8282MB