Sommaire

1. Notions fondamentales

Je pense qu'il y a un marché mondial pour environ 5 ordinateurs
Thomas WATSON, président d'IBM, 1943.

1.1. Préambule

1.1.1. La révolution informatique

En 2010, l'ordinateur n'a que 65 années d'existence derrière lui. L'âge de la retraite me direz vous ? Eh bien, non. L'ordinateur a encore de beaux jours devant lui et de nombreux progrès et améliorations à venir qui le rendront plus performant et peut être, un jour, pourrons nous le qualifier d'"intelligent", ce qui n'est actuellement pas le cas.

Les ordinateurs ont bouleversé nos modes de vie les rendant plus stressants (vitesse de calcul, réponse rapide) mais ont également permis de simplifier nombre de traitements réalisés manuellement par le passé (statistiques).

Il semble difficile de comparer les premiers calculateurs à nos ordinateurs actuels, cependant nous ne pouvons que nous étonner des progrès réalisés en un temps record.

 Caractéristiques   ENIAC   Ordinateur de bureau   facteur 
 Année   1945   2010   +65 ans 
 poids   50 tonnes   20 kg   / 2500 
 consommation électrique   25 kW   500 à 1000 W   / 25-50 
 capacité mémoire   < 1 ko   Go   x 1.000.000 
 performances (instructions / s)   quelques centaines   100 millions   x 1.000.000 
évolution du matériel

Aujourd'hui (Juin 2016) le super ordinateur le plus puissant (voir le site top500.org) Sunway TaihuLight (Chine) est capable d'atteindre 93 Petaflops ($10^{15}$) avec 10,649,600 coeurs. La prochaine barrière à atteindre étant celle de l'Exaflops ($10^{18}$).

On notera néanmoins qu'il s'agit de la puissance cumulée de tous les processeurs utilisés (voir le lien Présence PC: 17 ans d'évolution des supercalculateurs)

Intel travaille actuellement sur le Teraflop Chip : ASCI Red fut le premier système à atteindre le TeraFlop en 1996. Il était composé de 10.000 Intel Pentium Pro tournant à 200 Mhz et consommait 500.000 W (ainsi que 500.000 W de plus pour le système de climatisation refroidissant l'ensemble des machines). Avec le TeraFlop chip, Intel serait capable de créer un microprocesseur de même puissance (1,01 TeraFlop) dissipant seulement 62 W (cf Knighs Corner, Knights Landing).

Exemple : 2010 le TERA 100 du CEA construit par BULL pour la simulation d'armes nucléaires

Actuellement (2016) ATOS/BULL est l'un des trois ou quatre acteurs mondiaux à savoir concevoir et fabriquer aujourd'hui des supercalculateurs, et le seul européen selon Thierry Breton (PDG d'ATOS/BULL, ancien ministre de l'économie). BULL a conçu le SEQUANA une brique de super-calculateur qui consomme 10 fois moins d'énergie que les machines actuelles, occupe 5$m^2$ au sol et pèse 9 tonnes. Cette brique comprend par exemple dans sa version X1210 24 lames x 3 noeuds soit 72 noeuds capables d'accueillir chacun un Intel Xeon Knights Landing (72 coeurs Atom avec 4 threads + AVX 512), soit un total de 72 x 72 = 5184 coeurs, 6 TeraFlops en simple précision et 3 en double précision.

1.1.2. Besoins en puissance de calcul

Top500 : les calculateurs les plus puissants, dont le K computer avec 10,5 PFlops en 2012.

Les super-calculateurs sont utilisés par les très grandes entreprises et instituts de recherches, pour effectuer rapidement des simulations informatiques qui peuvent éventuellement générer des volumes de données gigantesques.

Les agences de prévisions météorologiques, les centres d'études aérospatiales, les organismes de recherches géologiques et sismologiques figurent parmi les principaux utilisateurs de ces imposantes machines.

Les super-calculateurs remplissent des salles immenses et exigent des batteries de climatiseurs tant ils dégagent de chaleur. Il est a noté que leur consommation électrique est également très importante.

Mars 2007 - Des scientifiques de l'université de CHICAGO en Astrophysique thermonucléaire ont réussi très récemment à modéliser une supernova ... chose qu'il était pourtant pensé impossible à réaliser vu la complexité des calculs. Ainsi, pour pouvoir observer 3 secondes de l'explosion, il a fallu des heures de programmation, et surtout 700 processeurs travaillant sans relâche pendant 58 000 heures pour obtenir ces 3 secondes.

Octobre 2007 - Le groupe d'électronique, d'équipements de télécommunications et d'informatique japonais NEC a annoncé le lancement d'un super-calculateur dont les performances sont à ce jour inégalées, selon son concepteur. Cet ordinateur baptisé SX-9 est présenté comme le super-ordinateur vectoriel le plus puissant du moment, avec une puissance crête de calcul de 839 Teraflops, grâce à des unités centrales de calcul (CPU) chacune capable d'atteindre un niveau de 102 Gigaflops, ce qui est une première, selon NEC.

NEC dit avoir mis en oeuvre dans ce nouveau modèle divers procédés qui permettent de diminuer la surchauffe et d'améliorer la ventilation de sorte que leur encombrement et leur consommation d'électricité s'en trouve réduite.

Le groupe nippon revendique actuellement plus de 1000 supercalculateurs portant sa marque "SX" en service dans le monde.

Cracker un mot de passe

Les progrès réalisés au niveau des CPU ont eu des incidences sur les GPU. Cracker un mot de passe codé en MD5 devient un jeu d'enfant en utilisant une carte graphique.

1.1.3. Pourquoi un cours d'architecture des ordinateurs ?

Dans le cursus d'un étudiant en informatique, un cours d'architecture est fondamental car il permet d'apporter les connaissances liées au matériel. Si on considère que l'essentiel de notre travail d'informaticien touche au logiciel (software), c'est à dire la production d'algorithmes, on oublie souvent que le matériel (hardware) joue un rôle important vis à vis des performances, de la compatibilité et de la portabilité des logiciels.

Dans ce cours, on abordera certains aspects matériels, mais on se focalisera plus particulièrement sur l'apprentissage de l'assembleur, c'est à dire, pour faire court, le langage exécuté par le processeur.

Un autre aspect important est que le domaine de l'architecture des ordinateurs est intimement liée à celui de l'industrie des semi-conducteurs qui est un marché de plusieurs milliards de dollars et qui concerne des sociétés comme Intel, AMD, IBM, Samsung, Texas Instruments, ...

 Rang 2010   Rang 2009   Sociétés   Chiffre
d'affaire 2010 		  Part de
marché 2010 		  Croissance
2010-2009 
 1   1   Intel   41,988   14%   25,6% 
 2   2   Samsung Electronics   28,097   9,4%   58,3% 
 3   3   Toshiba   12,360   4,1%   28,7% 
 4   4   Texas Instruments   11,878   4%   29,9% 
 5   5   STMicroelectronics   10,346   3,5%   22,3% 
 6   11   Renesas Electronics   10,204   3,4%   124,7% 
 7   7   Hynix Semiconductor   9,884   3,3%   63,8% 
 8   13   Micron Technology   8,224   2,7%   97,2% 
 9   6   Qualcomm   7,204   2,4%   12,4% 
 10   12   Broadcom   6,604   2,2%   53% 
    Autres   152,574   51%   22,2% 
    Total   299,363   100%   30,9% 
Résultats 2010 des dix premiers fabricants de semi-conducteurs, Gartner, avril 2011

On note que les principales entreprises sont américaines, japonaises et sud coréennes. En Europe, les deux grands noms de l'industrie des semi-conducteurs sont STMicroelectronics et Infineon.

1.1.4. A quoi cela me sert-il de savoir programmer en assembleur ?

Dans la grande majorité des cas, savoir programmer en assembleur ne sert strictement à rien :

Quels sont les inconvénients de la programmation en assembleur ?

Donc finalement, programmer en assembleur cela ne sert à rien ?

Non car :

Pour résumer

Un système informatique se compose :

Un informaticien se doit de comprendre le fonctionnement du système dans sa globalité car les caractéristiques du matériel influent sur les performances des programmes. Toute personne prétendant être un informaticien sans savoir coder n'est pas un informaticien, c'est un théoricien.

Une bonne connaissance du fonctionnement interne de l'ordinateur permet de comprendre pourquoi certains algorithmes se révèlent efficaces et pourquoi d'autres sont mal adaptés, par rapport à une architecture donnée, et comment en améliorer le fonctionnement.

En effet les traitements informatiques possèdent, au regard de ceux qui les utilisent, une exigence de qualité (robustesse et performance) et l'informatique s'attache à résoudre des problèmes complexes par leur structure ou par le volume de données à gérer. L'informaticien doit donc être capable de trouver le traitement (algorithme) le plus adapté aux données à analyser et savoir coder correctement cet algorithme dans un langage donné (exemple : liste, ajout en fin de liste récursif).

1.2. Le métier d'informaticien

1.2.1. Qu'est ce qu'un ordinateur ?

Définition : Ordinateur

Un ordinateur est une machine électronique conçue pour effectuer des calculs et traiter des informations de manière automatique.

Le terme ordinateur a été inventé par Jacques Perret, professeur de philologie latine à la Sorbonne, à la demande d'IBM France en 1955. IBM cherchait en effet à cette époque un nom pour son nouveau calculateur, qui fut alors baptisé : ordinateur IBM 650.

Un ordinateur est composé de plusieurs parties appelées :

La distinction entre composant et périphérique repose sur le fait qu'un périphérique se trouve éloigné de la carte mère alors qu'un composant est en contact direct avec celle-ci. Cependant le terme composant peut être utilisé pour englober les périphériques.

Pour certains, le terme périphériques fait plutôt référence à tout ce qui est externe au boitier : clavier, souris, moniteur, imprimante... ce qui se trouve à la périphérie.

1.2.2. Qu'est ce que l'informatique ?

Définition : Informatique*

Science de la recherche et du traitement de l'information effectué par un ordinateur. Elle comprend l'ensemble des activités consistant à collecter, organiser et traiter de manière automatique les données par un ordinateur.

Le terme informatique a été créé en mars 1962 par Philippe Dreyfus (Directeur du centre national de calcul électronique de la société Bull dans les années 1950, un des pionniers de l'informatique en France) à partir des mots information et automatique.

En anglais on trouve parfois le terme informatics, mais plus généralement on emploie le terme Computer Science, voire Computer Engineering.

On notera la différence établie entre computer, c'est à dire la tâche première pour laquelle les ordinateurs furent utilisés, et le mot informatique, c'est à dire, leur utilisation au quotidien : le traitement automatique de l'information.

1.2.3. Qu'est ce qu'un informaticien ?

Définition : Informaticien

Un informaticien est un scientifique qui met en place des procédures de traitement automatique de l'information grâce à un ordinateur tout en exploitant au mieux les capacités de la machine.

1.2.3.a  En quoi consiste son travail ?

Le travail de l'informaticien consiste, partant d'énoncés en langage naturel (la langue de la vie courante), à traduire ces énoncés en une série d'opérations clairement définies que l'on appelle algorithme. Ces algorithmes sont ensuite traduits en instructions directement compréhensibles par le microprocesseur de la machine.

Définition : Algorithme

Un algorithme est une succession finie d'actions clairement identifiées exécutées dans un ordre précis.

Le mot algorithme est dérivé du nom du mathématicien persan Al Khwarizmi (vers l'an 820), qui introduisit en Occident la numération décimale (rapportée d'Inde) et enseigna les règles élémentaires des calculs qui en découlaient.

Les exemples qui suivent sont liés à l'aspect algorithmique du métier d'informaticien.

1.2.3.b  Exemple 1

travail de l'informaticien

Le processus de programmation passe par différentes phases :

1.2.3.c  Exemple 2 : crible d'Ératosthène

Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné $N$. On compare deux méthodes :

  1. // ==================================================================
  2. // Author: Jean-Michel RICHER
  3. // email: jean-michel.richer@univ-angers.fr
  4. // find prime numbers in interval [1..100,000,000]
  5. // using:
  6. // - method 1 : function is_prime for each number
  7. // - method 2 : improved version of method_1
  8. //      * i = i + 2
  9. // - method 3 : sieve of Eratosthenes (Crible d'Ératosthène)
  10. //
  11. // compile with
  12. //    g++ -o crible.exe crible.cpp -std=c++11 -lm -O2
  13. //
  14. // ==================================================================
  15. // Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz
  16. // n = 5761455
  17. // method 1: 2m0.530s => 120 s | -98% x67.37
  18. // method 2: 1m0.589s => 60s   | -97% x33.68
  19. // method 3: 1.781s
  20. // ==================================================================
  21.  
  22. #include <iostream>
  23. #include <vector>
  24. #include <cmath>
  25. #include <cstdlib>
  26. #include <algorithm>
  27. using namespace std;
  28.  
  29. const int SIZE = 100000000;
  30.  
  31. bool *tab;
  32.  
  33.  
  34. bool is_prime_1(int n) {
  35.     if (n <= 1) return false;
  36.     if (n == 2) return true;
  37.     int limit = static_cast<int>(floor(sqrt(n)));
  38.     for (int k = 2; k <= limit; ++k) {
  39.         if ((n % k) == 0) return false;
  40.     }
  41.     return true;
  42. }
  43.  
  44. /**
  45.  * check if each number is prime using function
  46.  * is_prime_1()
  47.  */
  48. void method_1() {
  49.    
  50.     tab[0] = false;
  51.     tab[1] = false;
  52.     int i = 2;
  53.     while (i < SIZE) {
  54.         tab[i] = is_prime_1(i);
  55.         ++i;
  56.     }
  57. }
  58.  
  59. /**
  60.  * is_prime_2() is an improvement of is_prime_1
  61.  */
  62.  
  63. bool is_prime_2(int n) {
  64.     if (n <= 1) return false;
  65.     if (n <= 3) return true;
  66.     // check if even number
  67.     if ((n % 2) == 0) return false;
  68.    
  69.     int limit = static_cast<int>(floor(sqrt(n)));
  70.    
  71.     // don't test even numbers because already done
  72.     // with ((n % 2)==0)
  73.     for (int k = 3; k <= limit; k += 2) {
  74.         if ((n % k) == 0) return false;
  75.     }
  76.     return true;
  77. }
  78.  
  79. /**
  80.  * check if each number is prime using function
  81.  * is_prime_2()
  82.  */
  83. void method_2() {
  84.     tab[2] = true;
  85.    
  86.     int i = 3;
  87.     while (i < SIZE) {
  88.         if (is_prime_2(i)) {
  89.             tab[i] = true;
  90.             // !!! work only if 2 is already in v
  91.             // and start with i=3
  92.             ++i;
  93.         }
  94.         ++i;
  95.     }
  96. }
  97.  
  98. /**
  99.  * cribble
  100.  */
  101. void method_3() {
  102.  
  103.     tab[0] = false;
  104.     tab[1] = false;
  105.    
  106.     int i = 2;
  107.     while (i < SIZE) {
  108.         if (tab[i]) {
  109.             for (int j = 2*i; j < SIZE; j+=i) {
  110.                 tab[j] = false;
  111.             }
  112.         }
  113.         ++i;
  114.     }
  115. }
  116.  
  117. /**
  118.  * main function
  119.  */
  120. int main(int argc, char *argv[]) {
  121.    
  122.     tab = new bool[ SIZE ];
  123.    
  124.     // default method
  125.     int method = 1;
  126.    
  127.     if (argc > 1) {
  128.         method = atoi(argv[1]);
  129.         if ((method < 1) || (method > 3)) {
  130.             method = 1;
  131.         }
  132.     }
  133.    
  134.     switch(method) {
  135.         case 1:
  136.             method_1();
  137.             break;
  138.         case 2:
  139.             fill(&tab[0], &tab[SIZE], false);
  140.             method_2();
  141.             break;
  142.         case 3:
  143.             fill(&tab[0], &tab[SIZE], true);
  144.             method_3();
  145.             break;             
  146.     }
  147.        
  148.     int n = 0;
  149.     for (int i=0; i<SIZE; ++i) {
  150.         if (tab[i]) {
  151.             //cout << i << " ";
  152.             ++n;
  153.         }
  154.     }
  155.     cout << endl << "n=" << n << endl;
  156.    
  157.     return EXIT_SUCCESS;
  158. }
  159.  
  160.  

Voici quelques résultats :

 méthode   résultat   amélioration   facteur 
 méthode 1   2m0.530s   -   - 
 méthode 2   1m0.589s   50%   x2 
 méthode 3   1.781s   98%   x67.37 
Crible d'Eratosthène, temps en secondes pour 100 millions de nombres sur Intel Core i5-4570 @ 3.20GHz

1.2.3.d  Exemple 3 : impôts

 if you are single and
if the taxable income is over 		  but not over   the tax is   of the amount over 
 0   21,450   15%   0 
 21,450   51,900   3,217 + 28%   21,450 
 51,900      11,743 + 31%   51,900 
Federal Tax Income
 if you are married and
if the taxable income is over 		  but not over   the tax is   of the amount over 
 0   35,800   15%   0 
 35,800   86,500   5,370 + 28%   35,800 
 86,500      19,566 + 31%   86,500 
Federal Tax Income

Voici une première solution :

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. const double SINGLE_LEVEL1 = 21450.0;
  7. const double SINGLE_LEVEL2 = 51900.0;
  8.  
  9. const double SINGLE_TAX1 =  3217.0;
  10. const double SINGLE_TAX2 = 11743.0;
  11.  
  12. const double MARRIED_LEVEL1 = 35800.0;
  13. const double MARRIED_LEVEL2 = 86500.0;
  14.  
  15. const double MARRIED_TAX1 =  5370.0;
  16. const double MARRIED_TAX2 = 19566.0;
  17.  
  18. const double RATE1 = 0.15;
  19. const double RATE2 = 0.28;
  20. const double RATE3 = 0.31;
  21.  
  22. double tax_amount(double income, bool married) {
  23.     double tax;
  24.    
  25.     if (!married) {
  26.         // single
  27.         if (income <= SINGLE_LEVEL1) {
  28.             tax = income * RATE1;
  29.         } else if (income <= SINGLE_LEVEL2) {
  30.             tax = SINGLE_TAX1 + RATE2 * (income - SINGLE_LEVEL1);
  31.         } else {
  32.             tax = SINGLE_TAX2 + RATE3 * (income - SINGLE_LEVEL2);
  33.         }
  34.     } else {
  35.         // married
  36.         if (income <= MARRIED_LEVEL1) {
  37.             tax = income * RATE1;
  38.         } else if (income <= MARRIED_LEVEL2) {
  39.             tax = MARRIED_TAX1 + RATE2 * (income - MARRIED_LEVEL1);
  40.         } else {
  41.             tax = MARRIED_TAX2 + RATE3 * (income - MARRIED_LEVEL2);
  42.         }
  43.     }
  44.     return tax;
  45. }
  46.  
  47. void report(double income, bool married) {
  48.     double tax = tax_amount(income, married);
  49.     double percent = round((tax / income) * 10000.0) / 100.0;
  50.    
  51.     cout << "Tax for ";
  52.     if (!married) {
  53.         cout << "single";
  54.     } else {
  55.         cout << "married";
  56.     }
  57.     cout << " with income of " << income;
  58.     cout << " = " << tax << " (" << percent << "%" << ")" << endl;
  59. }
  60.  
  61. int main() {
  62.     report(12000.0, false);
  63.     report(38000.0, false);
  64.     report(77000.0, false);
  65.     report(12000.0, true);
  66.     report(38000.0, true);
  67.     report(77000.0, true); 
  68.     return EXIT_SUCCESS;
  69. }
  70.  

problème : que faire si on ajoute plus de tranches d'imposition ? par exemple une tranche à 21% entre RATE1 et RATE2 ?

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <vector>
  5. #include <map>
  6. using namespace std;
  7.  
  8. class TaxProperties {
  9. public:
  10.     vector<double> ceiling;
  11.     vector<double> mintax;
  12.     vector<double> rates;
  13. };
  14.  
  15. map<string, TaxProperties> taxator;
  16.  
  17.  
  18. double tax_amount(double income, bool married) {
  19.     double tax = 0.0;
  20.     TaxProperties *prop;
  21.    
  22.     if (!married) {
  23.         prop = &taxator["single"];
  24.     } else {   
  25.         prop = &taxator["married"];
  26.     }
  27.    
  28.     size_t slice = 0;
  29.     while (slice < (*prop).ceiling.size()) {
  30.         if (income > (*prop).ceiling[slice+1]) ++slice;        
  31.         else break;
  32.     }
  33.        
  34.     tax = (*prop).mintax[slice] + (income - (*prop).ceiling[slice]) * (*prop).rates[slice];
  35.      
  36.     return tax;
  37. }
  38.  
  39. void report(double income, bool married) {
  40.     double tax = tax_amount(income, married);
  41.     double percent = round((tax / income) * 10000.0) / 100.0;
  42.    
  43.     cout << "Tax for ";
  44.     if (!married) {
  45.         cout << "single";
  46.     } else {
  47.         cout << "married";
  48.     }
  49.     cout << " with income of " << income;
  50.     cout << " = " << tax << " (" << percent << "%" << ")" << endl;
  51. }
  52.  
  53. int main() {
  54.     taxator["single"].ceiling = { 0, 21450.0, 51900.0, 10e20};
  55.     taxator["single"].mintax  = { 0, 3217.0, 11743.0 };
  56.     taxator["single"].rates   = { 0.15, 0.28, 0.31 };
  57.    
  58.     taxator["married"].ceiling = { 0, 35800.0, 86500.0, 10e20};
  59.     taxator["married"].mintax  = { 0, 5370.0, 19566.0 };
  60.     taxator["married"].rates   = { 0.15, 0.28, 0.31 };
  61.    
  62.     report(12000.0, false);
  63.     report(38000.0, false);
  64.     report(77000.0, false);
  65.     report(12000.0, true);
  66.     report(38000.0, true);
  67.     report(77000.0, true);
  68.     return EXIT_SUCCESS;
  69. }
  70.  

1.2.3.e  Exemple 4 : informatique vs mathématiques

On désire répondre à la question suivante : calculer la somme des nombres entiers multiple de 3 dans l'intervalle [1..1000].

1.2.4. Quelles doivent être ses qualités ?

Il doit :

ces qualités concourent à le rendre apte à programmer, c'est à dire traduire des traitements humains en opérations compréhensibles par une machine. Un informaticien doit donc être (au minimum) capable :

Remarque : on emploie également comme synonyme du verbe coder, les verbes implanter ou implémenter (tiré de l'anglais).

1.3. Exemples liés au matériel

La suite d'exemples de cette section a pour but de montrer que la programmation assembleur et la connaissance du matériel peuvent influencer le temps d'exécution de nombreux algorithmes.

1.3.1. Produit de matrices

Une matrice est un tableau à deux dimensions de nombres ou de fonctions :

matrix

Soient deux matrices A(n × p) et B(q × m) . Le produit de A par B n'est possible que si p = q. Le résultat est une matrice C(n x m) dont les coefficients ci,j sont définis par la formule suivante :

Ci,j =   Σk= 1, 2.., p=q Aik . Bkj

On peut traduire les formules de calcul mathématiques du produit de deux matrices carrées (800 x 800) en langage C, par : 
#define N 800

double A[N][N], B[N][N], C[N][N];

for (i = 0; i < N; ++i) {
  for (j = 0; j < N; ++j) {
    double s=0;
    for (k = 0; k < N; ++k) s += A[i][k] * B[k][j];
    C[i][j] = s;
  }
}

Si on exécute cet algorithme pour différentes valeurs de N, on s'aperçoit que celui-ci possède un comportement anormal pour des valeurs de N bien précises. Sur un Pentium 4 Prescott 2800 Mhz, on recense les temps d'exécution suivants sous Linux Ubuntu 6.06. Le programme est compilé en utilisant gcc 4.0.

 N   temps 
 800   5 
 1000   11 
 1200   23 
 1240   24 
 1280   127 
 1320   26 
temps d'exécution du produit matriciel

Cette "anomalie" peut être expliquée, comme nous le verrons plus avant dans ce cours, mais nécessite de posséder des connaissances en architecture des ordinateurs afin de comprendre ce genre de phénomène et de pouvoir y remédier.

1.3.2. POPCNT 8s vs 23s

Une même fonction (popcount) s'exécute en 8s ou en 23s en fonction des options de compilation utilisées !! (cf chapitre 3).

Ce phénomène apparaît sur Pentium-M 760, Core 2 Duo E6420, mais pas sur Pentium 4, Core 2 Duo E6750, Athlon 64, Sempron. Qu'elle en est la cause et comment y rémédier ?

1.3.3. GASAT

GASAT (Genetic Algorithm for SAT) est un logiciel écrit par F. Lardeux qui permet de résoudre le problème de SATisfiabilité d'un ensemble de clauses du calcul propositionnel.

Améliorations :

1.3.4. Maximum de Parcimonie (Bioinformatique)

La fonction la plus utilisée est la fonction de calcul d'une séquence hypothétique et du nombre de changements de la séquence hypothétique par rapport aux séquences initiales. Le code de la fonction est le suivant :

int fitch(char *x, char *y, char *z, int size) {
    int changes=0;
  
    for (int i = 0; i < size; ++i) {
        // compute intersection
        z[i] = x[i] & y[i];
        
        // if empty, take union and increase number of changes
        if (z[i] == 0) {
           z[i] = x[i] | y[i];
           ++changes;
        }
    }
    return changes;
}

Cette fonction peut être améliorée grâce aux instructions SSE (vectorisation du code) pas par le compilateur, mais par le programmeur et permet suivant les architectures d'atteindre un gain de 70 à 95 %.

 méthode   temps (s)   gain   commentaire 
 C basique   43.090   -    
 C optimisé 1   39.770   7%   suppression du if (z[i] == 0) 
 C optimisé 2   29.310   32%   autre suppression plus efficace 
 assembleur 1   25.360   41%   traduction de C optimisé 1 version 1 
 assembleur 2   21.750   51%   traduction de C optimisé 1 version 2 
 assembleur 3   21.420   51%   traduction de C optimisé 1 version 3 
 SSE   2.230   95%   version SSE 
temps d'exécution sur Core i7 2600 k

Remarque : la vectorisation utilise les 16 octets des registres SSE, on obtient un gain supérieur au calcul théorique puisque 43,09/2.23 = 19,32 > 16

Autre données sur Core i5 4570 Haswell doté des instructions AVX2 (Advanced Vector Extensions):

On notera que:

1.3.5. Elimination des doublons

Considérons un ensemble d'enregistrements stockés sous forme d'un tableau de $N$ enregistrements de $P$ champs. Le premier champ contient un identifiant d'enregistrement qui varie de 1 à $N$.

On désire supprimer les doublons, c'est à dire les enregistrements qui ont un identifiant différent mais dont les autres champs sont identiques. Quelle méthode utiliseriez vous ?

La méthode la plus simple (méthode 1) est la suivante :

  1. typedef unsigned int u32;
  2. u32 N = 7000000; // 7 millions
  3. u32 P = 10;
  4.  
  5. /**
  6.  * Compare two records given their address
  7.  */
  8. bool is_equal(u32 *a, u32 *b) {
  9.     for (u32 k = 1; k < P; ++k) {
  10.         if (a[k] != b[k]) return false;
  11.     }
  12.     return true;
  13. }
  14.  
  15. // create data
  16. u32 *data = new u32 [ N * P ];
  17.  
  18. // create array that tells which record is a duplicate
  19. bool *remove = new bool [ N ];
  20. fill(&remove[0], &remove[N], false);
  21.  
  22. // fill data ...
  23.  
  24. // find duplicates
  25. for (u32 i = 0; i < N-1; ++i) {
  26.     for (u32 j = i+1; j < N; ++j) {
  27.         if (is_equal(&data[i * P], &data[j * P])) {
  28.             remove[j] = true;
  29.         }
  30.     }
  31. }
  32.  
  33.  
  34.  

mais elle possède une complexité en $O(N^2/2)$.

Un autre méthode (méthode 2) consiste :

Voici une liste de résultats pour différentes architectures :

    Ryzen 1700x   Ryzen 1700x   i7 4790   i7 4790   i5 7400   i5 7400 
 N   méthode 1   méthode 2   méthode 1   méthode 2   méthode 1   méthode 2 
 10.000   0.08   0.00   0.08   0.00   0.10   0.00 
 20.000   0.35   0.01   0.34   0.00   0.36   0.00 
 50.000   2.15   0.02   2.09   0.01   2.26   0.01 
 100.000   8.59   0.03   8.47   0.02   9.06   0.02 
 200.000   36.93   0.07   36.81   0.06   39.39   0.06 
 300.000   93.73   0.10   96.09   0.09   98.68   0.09 
 500.000   313.14   0.26   281.87   0.17   277.46   0.18 
 1.000.000   1285.11   0.42   1152.68   0.40   1134.19   0.40 
Temps d'exécution en secondes sur Ryzen 7 1700X, i7-4790, i5-7400 pour 11 champs (10 + checksum)

1.3.6. Compression vidéo x264

cf. l'article de hardware.fr : Impact des compilateurs sur les architectures CPU x86/x64

 méthode   indice de performance 
 Core i7 AVX   38 
 Core i7 AVX assembleur   139 
Indice de performance sur Core i7 2600 k

1.3.7. Pile et variables locales

On considère le programme suivant :

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int variables[200];
} Contrainte;

#define MAX_CONTRAINTES 10400

int main() {

	Contrainte tabc[MAX_CONTRAINTES];
	
	fprintf(stderr, "coucou");
	return 0;
}

Lorsque l'on fixe MAX_CONTRAINTES à 10400, le programme s'exécute et affiche le message "coucou". Par contre si on passe MAX_CONTRAINTES à 10500, le programme produit un "Segmentation Fault" et le message n'est pas affiché. Pourquoi ?

En fait le problème est lié à la pile : on réserve en effet ici le tableau tabc au noveau de la pile d'appel des sous-programmes.

Under Unix-like systems, programs may throw a Segmentation Fault error. This can be due to stack overflow, especially from recursive function calls or huge data sets.

Pour connaître la taille de la pile, il faut utiliser la commande ulimit 

ulimit -a
stack size              (kbytes, -s) 8192
(voir man bash, puis /ulimit)

Soit une taille de 8192 ko donc 8 Mo.

Or dans le cas présent :

1.3.8. Bug du Boeing 787

Voir le site developpez.com dont sont extraites les paragraphes suivants pour plus de détails.

En 2015, il a été découvert qu’un bogue informatique pouvait empêcher les pilotes de garder le contrôle du Boeing 787, possiblement en plein vol, a informé la Federal Aviation Administration (FAA) dans une directive destinée à toutes les compagnies aériennes utilisant cet avion.

Le bogue qui n’est rien d’autre qu’un problème classique de débordement d’entier, est situé au niveau du contrôle des générateurs de l’avion. Le bogue rapporté par Boeing à la FAA est déclenché lorsque ces derniers sont laissés allumés durant 248 jours (8 mois). Le 787 a quatre de ces unités de contrôle des générateurs, qui allumées simultanément, peuvent s’arrêter en même temps et causer une interruption totale du système électrique.

La note de la FAA n’avait pas donné plus de détails sur ce bogue, mais il s’agirait d’un problème de débordement d’entier 32-bits déclenché après 231 centisecondes (248,55 jours)problème de traduction, c'est 2^31 de fonctionnement continu. 2^31 étant le nombre de secondes dans 248 jours multipliés par 100 (un compteur en centièmes de seconde).

Note: 248.55 jours = 248.55*24*360000 = 2_147_472_000 et 2^31 = 2_147_483_648 !? En fait c'est 248.5513 (= 2^31 / 24 / 3600)

Pour implémenter un tel compteur, deux options peuvent être suivies, soit augmenter le nombre de bits utilisés, ce qui empêche le débordement, ou bien travailler avec l’arithmétique multiprécision. Certains commentateurs ont suggéré qu’il y a ici un besoin de passer à une architecture 64 bits puisqu’elle permet d’utiliser plus de registres (généraux et XMM), un meilleur support pour PIC (position-independent code), et en général une meilleure performance des instructions syscall/sysret du système. Et dans ce cas, la période nécessaire pour le redémarrage de l'avion passerait de 248 jours à 3 milliards d'années !

1.4. Représentation de l'information

Le fonctionnement des ordinateurs se fonde sur un modèle logique ou binaire, c'est à dire, un modèle à 2 états distincts qui sont le 1 ou le 0, le vrai ou le faux, l'ouvert ou le fermé.

1 ≡ vrai ≡ fermé
0 ≡ faux ≡ ouvert

Ce modèle binaire (ou base 2) est utilisé pour représenter l'information de différentes façons en fonction des données à représenter.

1.4.1. Représentation des entiers naturels

Pour représenter un nombre entier naturel dans une base b, il faut disposer de b chiffres disctincts allant de 0 à b-1. Tout nombre N s'exprime alors sous la forme :

N = Σi = 0, .., k   ai × bi

où chaque ai est un chiffre.

Ainsi en base 10, on a :


De la même manière, en base 2 :

Dans la notation binaire :


20 = 1 28 = 256
21 = 2 29 = 512
22 = 4 210 = 1024
23 = 8 211 = 2048
24 = 16 212 = 4096
25 = 32 213 = 8192
26 = 64 214 = 16384
27 = 128 215 = 32768
 
216 = 65536 231 = 2.147.483.648
224 = 16.777.216 232 = 4.294.967.296
Table des puissances de 2

1.4.1.a  Unités


Remarque : c'est l'octet qui est utilisé comme unité de référence pour mesurer la capacité des mémoires.

 Puissance de 2   Unité   Symbole 
 210   kilo octet   ko 
 220   mega octet   Mo 
 230   giga octet   Go 
 240   tera octet   To 
 250   peta octet   Po 
 260   exa octet   Eo 
 270   zetta octet   Zo 
unités couramment utilisées

Pour représenter les données on utilisera 1, 2, 4 ou 8 octets consécutifs pour les nombres entiers et réels.

1.4.1.b  Comment convertir un nombre de la base 10 vers la base $b$ ?

α) Méthode 1 : divisions successives

Il suffit tout simplement de réaliser des divisions successives du nombre par b. Par exemple, pour convertir 13 (base 10) en base 2, il suffit de réaliser les divisions successives de 13 par 2. On part ensuite du dernier résultat obtenu et on remonte le long des restes des divisions. Ainsi :

$13 = 13\_d = 1101\_b$





β) Méthode 2 : intervalles de puissances de 2

On cherche dans quel intervalle de puissances de 2 le nombre à convertir se trouve. Par exemple pour convertir 1970 :

$2^{10}$ < 1970 < $2^{11}$, donc 1970 contient au moins $2^{10} = 1024$, donc on retranche 1024: $1970-1024= 946$

$2^{9}$ < 946 < $2^{10}$, donc 946 contient au moins $2^{9} = 512$, donc on retranche 512: $946-512= 434$

On réitère le processus jusqu'à obtenir : $111\_1011\_0010\_b$

1.4.1.c  Addition de nombres binaires

Pour additionner deux nombres binaires on procède comme en base 10.

X + Y = reste retenue
0 + 0 = 0 0
0 + 1 = 1 0
1 + 0 = 1 0
1 + 1 = 0 1
1 + (1 + 1) = 1 1

par exemple :

  1 1 1 1   (retenues)
    1 1 0 1 (= 1310)
+ 1 1 1 1 (= 1510)
  1 1 1 0 0 (= 2810)

1.4.1.d  Octal et hexadécimal

En informatique les bases 8 (octal) et 16 (hexadécimal) sont souvent utilisées. La base 16 est très pratique car elle permet de représenter les nombres binaires par quartet et permet de représenter un octet grâce à deux chiffres.

En base 16, on utilise 16 chiffres

On passe aisément de la lase 2 à la base 16 en regroupant les bits par quartet :

base 2 0 0 1 1 1 1 1 0 0 1 0 1
base 16 3 E 5


Enfin, on utilise parfois pour distinguer les nombres écrits dans une base donnée, une notation héritée du passé (notamment des premiers assembleurs) :

1.4.2. Représentation des entiers relatifs

Plusieurs représentations existent mais on utilisera la notation binaire en complément à 2 qui permet de réaliser des opérations arithmétiques sans problème.

Dans cette notation, les nombres positifs utilisent le même procédé de réprésentation que la notation binaire de la section précédente.

Pour obtenir le codage binaire d'un nombre négatif on procède en commençant par fixer la taille de l'espace de codage en nombre de bits : par exemple 8, 16 ou 32 bits. Prenons 8 bits das le cas présent. Ensuite :

  1. on prend la valeur absolue du nombre que l'on code sur 8 bits
  2. on complémente chacun des bits (i.e. on remplace les 0 par des 1 et inversement)
  3. on ajoute 1 au résultat final

Par exemple, pour représenter -8 :

| -8 | = 8 =   0 0 0 0 1 0 0 0
Complément   1 1 1 1 0 1 1 1
(+1)   1 1 1 1 1 0 0 0

Autres représentations sur 8 bits :

-1 =   1 1 1 1 1 1 1 1
-2 =   1 1 1 1 1 1 1 0
-127 =   1 0 0 0 0 0 0 1
-128 =   1 0 0 0 0 0 0 0

On remarque que tous les nombres négatifs ont leur bit de poids fort à 1, alors que les nombres positifs ont leur bit de poids fort à 0.

Dans la notation binaire en complément à 2 sur n bits, on peut coder les nombres entre :

-(2n-1)   à   +(2n-1 - 1)

avec n bits : valeur min valeur max
avec 8 bits : -128 +127
avec 16 bits : -32768 +32767
avec 32 bits : -2.147.483.648 +2.147.483.647

1.4.3. Représentation des nombres réels (norme IEEE 754)

La norme IEEE 754 (Standard for Binary Floating-Point Arithmetic) définit 4 représentations de nombres réels (appelés flottants en informatique) :

Les nombres sont décomposés en :




N = (-1)signe × 2(exposant décalé - 127) × (1,mantisse tronquée2)


Représentation Simple
précision		 Double
précision
taille (bits) 32 64
signe 1 1
Exposant 8 11
Mantisse 23 52
Echelle 10+/- 38 10+/- 308
Caractéristiques des représentations IEEE 754

Exemples de représentations :

Valeur Signe Exposant Mantisse Hexadécimal
12,5 0 100.0001.0 100.1000.0000.0000.0000.0000 41.48.00.00
-0,5 1 011.1111.0 000.0000.0000.0000.0000.0000 BF.00.00.00
0.0 0 000.0000.0 000.0000.0000.0000.0000.0000 00.00.00.00


1.4.3.a  Exemple de conversion

On désire convertir 12,510 en notation IEEE 754 :

Finalement, on obtient :

  S exposant déc. mantisse tronquée
  0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
hexadécimal   4 1 4 8 0 0 0 0

Liens :


1.4.3.b  Problèmes liés à la représentation IEEE 754

La représentation IEEE 754 peut poser des problèmes de représentation pour certains nombres après réalisation de calculs. Soit le programme suivant : 

#include <stdio.h>

float v1 = 1.2;
float v2 = 1.3;
float v3 = 1.3001;

int main() {
  float w1 = v1-v2;
  float w2 = v2-v3;

  printf("w1 = %g\n", w1);
  printf("w2 = %g\n", w2);
  return 0;
}

Le résultat en sortie est :

w1 = -0.0999999 (au lieu de 0.1)
w2 = -0.000100017 (au lieu de 0.0001)

En outre, pour comparer deux nombres flottants on utilisera pas l'opérateur d'égalité (=) mais on vérifiera que la valeur absolue de leur différence est inférieure ou égale à un ε donné:

float v1, v2;
if (fabs(v1-v2) < 1E-6) printf("v1 = v2");

1.4.4. Caractères (ASCII, Unicode)

Le codage des caractères a été normalisé dès 1968 avec la norme ASCII (American Standard Code for Information Interchange)

suivant les langages, les chaînes de caractères sont codées différemment :

1.4.4.a  Codage ASCII

Le code ASCII est décomposé en deux tables de 128 caractères :

(Remarque : les tables ci-dessus sont issues du site lookuptables).

Les caractères 0 à 31 sont des caractères non imprimables et correspondent à des codes de contrôle :

Remarque : sous Windows, la fin de ligne est représentée par CR suivi de LF, alors que sous Linux seul LF est utilisé. C'est pourquoi lorsque l'on ouvre sous Linux un fichier texte édité sous Windows on voit apparaître des caractères '^M' qui correspondent à CR.

Voici un petit script qui permet de supprimer les CR sous unix :

#!/bin/sh
# script qui elimine les CR dans les fichiers texte
# on passe en parametre de ce fichier une liste de fichiers qui seront
# traites separement
for i in \$*
do
  echo \$i
  tr -d '\015' <\$i >tmp.txt
  mv tmp.txt \$i
done

1.4.4.b  Codage Unicode

Le standard Unicode est un mécanisme universel de codage de caractères. Les 256 caractères du code ASCII ne sont malheureusement pas suffisants pour coder des langues comme l'arabe, l'hindi, le chinois, le japonais, ... La version 4.1.0 d'Unicode de 2005 permet de coder 245.000 caractères. Les caractères Unicode utilisent 16 ou 32 bits pour stockage.

voir le site suivant pour plus d'informations : unicode.org et le tuteur Unicode.

Remarque : En Java les chaînes de caractères sont codées en utilisant le format UNICODE.

1.4.5. Espace mémoire occupé par les types de base en langage C

 type / octets   32 bits   64 bits 
 char   1   1 
 short int   2   2 
 int   4   4 
 long int   4   8 
 long long int   8   8 
 float   4   4 
 double   8   8 
 void *   4   8 
Espace mémoire occupé par les types de base en C

Compétences à acquérir

il faut être capable de :



Exercices d'entraînement

Exercice 1 : donner la valeur décimale des nombres suivants :

Exercice 2 : convertir les nombres entiers positifs suivants en base 2, 8 et 16 :

Exercice 3 : convertir les nombres entiers négatifs suivants en notation binaire en complément à 2 en utilisant une représentation sur 8 bits :

Exercice 4 : réaliser les additions en binaire en codant les nombres suivants en binaire :

Exercice 5 : convertir les nombres réels suivants en notation IEEE 754 sur 32 bits :

Exercices de programmation

Exercice 6 : écrire un programme en langage C qui prend en paramètre un nombre réel et donne sa représentation binaire au format IEEE 754.

Exercice 7 : écrire un programme en langage C qui permet de convertir un nombre entier naturel exprimé en décimal en sa représentation en base 2, 8 et 16.

Exercice 8 : écrire un programme en langage C qui permet de convertir un nombre entier naturel exprimé en base 2, 8 ou 16 en sa représentation décimale.