Plan

1. Représentation flottante
2. Erreurs dans les calculs flottants
3. Représentation IEEE 754
4. Allocation mémoire
5. Glâneur de cellules

Représentation des nombres (1/2)

• entiers: complément à 2 sur n bits (n = 8, 16, 32, 64)
  -2^n-1 £ x < 2^n-1 (arithmétique modulo 2ⁿ)
  sv
  s=0 Þ nombre positif v
  s=1 Þ nombre négatif v -2^n-1
  2³¹ = 2 147 483 6482⁶³ = 9 223 372 036 854 775 808
  
  
• réels: virgule fixe (par exemple p=|su|=16, q=|v|=16)
  suv
  x = su + v / 2^q et réciproquement suv ¬ ë x × 2^qû
  -2^p-1 £ x £ 2^p-1-1/2^q
  2¹⁵ = 32768
  
  Très utilisé en graphique interactif, car opérations entières.
  
  
• réels: flottant sur 32 ou 64 bits
  

  mantisse m sur 24 ou 53 bits,

  exposant e sur 8 ou 11 bits

  x = m   2^e
  em
  2^-127 × 2^-24 £ |x| < 2¹²⁸ pour le calcul numérique.

Représentation des nombres (2/2)

• entiers: précision arbitraire
  représentation en tableaux, listes, structures dynamiques, ...
  beaucoup de bibliothèques de bignums (GMP, Maple, ocaml)
  les opérations dépendent du nombre de chiffres
  efficacité?
  
  
• réels: exacts
  impossible, puisque l'égalité a = b est indécidable
  seules des approximations sont possibles
  
  
• réels: par intervalles
  

Représentation flottante (1/2)

• Réels en notation scientifique
  
  2.439 × 10⁵, -4.0019 × 10⁷, 2.23 × 10^-4,
  
  ± m × 10 ^e
  
  ± m partie significative (mantisse) 0 £ m < 10
  
  e exposant
  
  
• Avec une base b arbitraire
  ± m × b^e  =  ± d₀.d₁ d₂··· d_p-1 × b^e
  
  vaut
  
  ± (d₀ + d₁ b^-1 d₂ b^-2··· d_p-1 b^-(p-1))× b^e (0 £ d_i < b, 0 £ i < p)
  
  
• b = 10 (exemples), b = 2 (en machine)
  
  p nombre de chiffres significatifs
  e_min £ e £ e_max
  
  
• le nombre de chiffres significatifs est fixe
  
  Þ approximation des nombres réels.
  
  
• 0.1 non représentable si b = 2
  x tel que |x| < b^e_min ou |x| > b^e_max non représentable

Représentation flottante (2/2)

• la représentation flottante n'est pas unique
  0.000214 × 10² = 0.214 × 10^-1
  
  
• la représentation normalisée est 2.14 × 10^-2
  (premier chiffre d₀ non nul)
  
  
• la représentation normalisée de 0 utilise des valeurs réservées de e : 1.0 × b^{e_min -1} (d'autres valeurs de m seront utilisées pour ±¥)
  
  
• b = 2, p = 3, e_min=-1, e_max = 2  Þ  16 représentations normalisées

  m

  1.00 1.01 1.10 1.11

  -1 0 1 2 0.5 1 2 4 0.625 1.25 2.5 5 0.75 1.5 3 6 0.875 1.75 3.5 7 0.125 0.25 0.5 1

  
  
  

Erreur (1/4)

• erreur absolue d'arrondi par rapport au nombre réel exact
  
  b/2 × b^-p × b^e
  
  
• erreur relative (ulp = unit in the last place)
  
  1/2 b^-p £ 1/2 ulp £ b/2 b^-p
  
  La précision e de la machine est définie par
  
  e = b/2 b^-p
  
  
  
• les opérations flottantes produisent des erreurs.
  
  
• l'opération la plus redoutable est la soustraction

Erreur (2/4)

• b=10, p = 3
  

  				réel	flottant
  x		=		2.15 × 1012	2.15 × 1012
  y		=		0.000000000000000125 × 1012	2.15 × 1012
  x-y		=		2.149999999999999875 × 1012	0.00 × 1012
  x'		=		10.10	1.01 × 101
  y'		=		9.93	0.99 × 101
  x'-y'		=		0.17	0.02 × 101
  x''		=		1.000 × 10e	1.00 × 10e
  y''		=		0.999 × 10e	0.99 × 10e
  x''-y''		=		0.001 × 10e	0.01 × 10e

  
  
  
• l'erreur relative vaut (b^-p+1 - b^-p)/ b^-p = b - 1
  
  
• dans une soustraction, l'erreur relative est bornée par b - 1
  
  b = 2  Þ  erreur absolue aussi importante que le résultat!

Erreur (3/4)

• si on ajoute un chiffre de précision pendant la soustraction (une garde), l'erreur relative baisse à 2 e
  
  
• pour calculer la précision e Exécution
  
    double a = 1.0, b = 1.0;
    int i = 0;
    while (((a + 1.0) - a) - 1.0 == 0.0) {
      a = 2*a; ++i;
    }
    System.out.println(i);
    while ((((a + b) - a) - b) != 0.0) ++b;
    System.out.println(b);
  }
  
  
  
• l'ordre dans lequel on fait les opérations est important
  Þ  recettes numériques

Erreur (4/4)

• 4ac « b²  Þ  on change de formules:
  

  -b + b2 -4ac 2a		2c -b - b2 -4ac
  -b - b2 -4ac 2a		2c -b + b2 -4ac

  
  
  
• Règle: un test entre flottants n'a aucun sens si l'erreur de |a - b| n'est pas estimée:
  
  
    if (a > b) ...
    else ...
  
  
  
• bugs célèbres dus au calcul flottant: missile Patriot (1991), plate-forme Sleipner A (1991), FDIV Intel (1994), Ariane 501 (1996), etc.

Représentation IEEE 754

• [1.2ex][.2ex]s[1.2ex][.2ex]k[1.2ex][.2ex]f
  s signe (1 bit)
  e exposant (8 bits) (-126 £ e £ 127 )
  f partie fractionnaire (23 bits) (0 £ m < 2²³)
  
  
• valeurs de 1.1754943508222875 × 10^-38 à 3.402823466385288600000 × 10^-38
  
  
• conventions

  e=k-127		f		m
  -126£ k£ 127		0£ f£ 223		± 1.f × 2e
  128		0		±¥
  128		¹ 0		NaN
  -127		0		± 0
  -127		¹ 0		± 0.f × 2-126   (dénormalisé)

Représentation IEEE 754

• [1.2ex][.2ex]s[1.2ex][.2ex]k[1.2ex][.2ex]f
  s signe (1 bit)
  e exposant (11 bits) (-1022 £ e £ 1023 )
  f partie fractionnaire (52 bits) (0 £ m < 2⁵²)
  
  
• valeurs de 2.22507385855072014 × 10^-308 à 1.79766931348623157 × 10³⁰⁸
  
  
• conventions

  e=k-1023		f		m
  -1022£ k£ 1023		0£ f£ 252		± 1.f × 2e
  1024		0		±¥
  1024		¹ 0		NaN
  -1023		0		± 0
  -1023		¹ 0		± 0.f × 2-1022   (dénormalisé)

Allocation mémoire (1/4)

• les variables (statiques) globales et les variables locales ont une durée de vie n'excédant pas celle du bloc de leur déclaration.
  
  
• les fonctions appellent d'autres fonctions; de nouvelles variables locales sont créées, puis disparaissent.
  
  
• à chaque appel de fonction, un bloc d'activation contenant ses variables locales est créé (stack frame); il est supprimé au retour de la fonction.
  
  
• ces blocs ont une structure de pile.
  
  
• les variables (statiques) globales et les variables locates sont encore appelées variables de la pile.

Allocation mémoire (2/4)

• d'autres données sont créés par new.
  
  
• leur durée de vie peut être aussi longue que le programme.
  
  
• ce sont les données du tas
  
  
• pourtant elles peuvent être inutiles à partir d'un certain moment
  
             new Liste(8, new Liste(2, new Liste(29, null)));
      troisElements.suivant.val = 11;
      troisElements = new Liste (9, troisElements.suivant);
  
  
  
  

Allocation mémoire (3/4)

• le GC, glâneur de cellules (garbage collector) récupère l'espace mémoire des données inutiles dans le tas.
  
  
• le GC est intégré à l'interpréteur de la JVM.
  
  
• il existe de multiples manières de faire le GC.
  
  
• le GC de Java doit être cohérent avec l'existence de plusieurs processus (multi-thread).
  
  
• en général, le GC est appelé quand une allocation de mémoire (new) détecte qu'il n'y a plus de place dans le tas.
  
  
  • ·le GC récupère alors toute la place inutile;
    
    
  • ·l'allocation dans le tas devient possible.
    
    
  • ·Si toujours pas de place, on appelle le système d'exploitation (Linux, Windows) pour augmenter la taille de la JVM.
    
    
  • ·Si impossible, on s'arrête pitoyablement.
  
  
  
• le GC provoque un temps d'arrêt dans l'exécution des programmes. (sauf si le GC -- plus compliqué -- est incrémental)

Allocation mémoire (4/4)

• pas de GC dans les vieux langages de programmation (Algol, Pascal, C, C++)
  
  Þ déallocation manuelle
  
  
• GC Þ déallocation automatique de la mémoire du tas
  
  
• les langages de programmation modernes ont un GC
  (Scheme, ML, Java, Modula-3)
  
  GC Þ programmation grandement simplifiée
  
  
• on peut controler l'allocation dans le tas, puisqu'elle est toujours explicite (new).

Glâneur de cellules (1/2)

Compteurs de références: chaque donnée du tas a un compteur de références.

Glâneur de cellules (2/2)

• le compteur de référence est mis à jour à chaque affectation.
  
  
• Si le compteur d'une cellule devient zéro. On libère la cellule, et on met à jour les compteurs des cellules pointées par la cellule libérée.
  
  
• méthode incrémentale. Pas de blocage. Bien pour le temps-réel.
  
  
• mais ne récupère pas les cycles.
  
  
• coût induit sur toutes les opérations de manipulation des références.

Compteurs de références (1/2)

Compteurs de références (2/2)

Méthodes par traçage (1/2)

On marque les cellules atteignables depuis les racines. Et on libère les cellules non marquées.

Méthodes par traçage (2/2)

• La phase de marquage se fait par une simple exploration en profondeur du graphe d'accès à partir des racines. Son résultat se fait en général dans un tableau de bits, 1 bit par mot-mémoire.
  
  La deuxième phase consiste à balayer séquentiellement le tas en récupérant tous les mots-mémoire non marqués.
  
  
• tourne en peu de mémoire
  
  
• autorise les GC conservatifs (pour C ou C++).
  
  
• problème º fragmentation
  
  
• c₁ N + c₂ T/T - N (où T taille du tas, N mots occupés)

Collecteurs par recopie (1/5)

Collecteurs par recopie (2/5)

• tas divisé en 2 zones égales:
  • ·départ (from-space)
  • ·arrivée (to-space).
  
  On alloue des cellules dans la zone de départ à partir d'un index disponible indiquant l'emplacement suivant le dernier mot alloué.
  
  Quand disponible est au bout de la zone, on recopie les cellules accessibles depuis les racines de la zone départ vers la zone d'arrivée.
  
  
• Les cellules recopiées sont compactées. On permute les rôles des deux zones, l'index disponible se retrouvant derrière le dernier mot recopié.
  Þ pas de fragmentation
  
  
• il faut disposer de la moitié de la mémoire (en fait on alloue de la mémoire virtuelle, mais cela peut entrainer des défauts de page au moment du GC).

Collecteurs par recopie (3/5)

Collecteurs par recopie (4/5)

• il faut mettre à jour les contenus des cellules recopiées pour que les références pointent dans la zone d'arrivée.
  
  
• Dans l'algorithme de [Cheney, 70], la recopie se fait par un parcours en largeur du graphe des cellules accessibles à partir des racines.
  
  
• Quand on recopie une cellule de la zone de départ vers la zone d'arrivée, on laisse un renvoi vers sa nouvelle adresse dans le premier mot de cette cellule dans la zone de départ.
  
  
• Pour le parcours, on utilise une file dont les index de début debut et de fin disponible (en fait le premier mot derrière la file) sont initialement positionnés sur le début de la zone d'arrivée.
  
  
• On recopie d'abord les mots directement pointés par les racines, que l'on range dans la file.
  
  
• Tant que la file n'est pas vide, on recopie les mots pointés par le premier élément de la file.

Collecteurs par recopie (5/5)

• Pour copier une cellule, on regarde d'abord si son premier mot pointe vers la zone d'arrivée. Si c'est le cas, rien à faire.
  
  
• Sinon, on copie la cellule au bout de la file dans la zone d'arrivée. Et on met un pointeur de renvoi dans le 1er mot de son ancienne adresse.
  
  c N/T/2 - N (où T taille du tas, N mots occupés)

Langages de programmation

• GC par générations (2 en Ocaml)
  
  
• GC incrémentaux
  
  
• GC concurrents
  
  
• GC distribués
  
  
• polymorphisme
  
  
• modules paramétrés
  
  
• certification du code généré
  
  
• analyse de flot et interférences, etc.
  
  
• cf. en Majeure 1 (cours Langages de programmation)

This document was translated from L^AT_EX by H^EV^EA.