# Fonctionnement d'un ordinateur/La performance d'un ordinateur

Dans ce chapitre, nous allons définir ce qui fait qu'un ordinateur est plus rapide qu'un autre. En clair, nous allons étudier la performance d'un ordinateur. C'est loin d'être une chose triviale : de nombreux paramètres font qu'un ordinateur sera plus rapide qu'un autre. De plus, la performance ne signifie pas la même chose selon le composant dont on parle. La performance d'un processeur n'est ainsi pas comparable à la performance d'une mémoire ou d'un périphérique.

## La performance du processeur

Concevoir un processeur n'est pas une chose facile et en concevoir un qui soit rapide l'est encore moins, surtout de nos jours. Pour comprendre ce qui fait la rapidité d'un processeur, nous allons devoir déterminer ce qui fait qu'un programme lancé sur notre processeur va prendre plus ou moins de temps pour s’exécuter.

### Le temps d’exécution d'une instruction : CPI et fréquence

Le temps que met un programme pour s’exécuter est le produit :
* du nombre moyen d'instructions exécutées par le programme ;
* de la durée moyenne d'une instruction, en seconde.
    $T=N\times T_{\text{instruction}}$, avec N le nombre moyen d'instruction du programme et $T_{\text{instruction}}$ la durée moyenne d'une instruction.
Le nombre moyen d'instructions exécuté par un programme s'appelle l'Instruction path length, ou encore longueur du chemin d'instruction en français. Si on utilise le nombre moyen d’instructions, c'est car il n'est pas forcément le même d'une exécution à l'autre. Par exemple, certaines sections de code ne sont exécutées que si une condition bien spécifique est remplie, d'autres sont répétées en boucle, etc. Tout cela deviendra plus clair quand nous aborderons les instructions et les structures de contrôle, dans un chapitre dédié.
Le temps d’exécution d'une instruction peut s'exprimer en secondes, mais on peut aussi l'exprimer en nombre de cycles d'horloge. Par exemple, sur les processeurs modernes, une addition va prendre un cycle d'horloge, une multiplication entre 1 et 2 cycles, etc. Cela dépend du processeur, de l'opération, et d'autres paramètres assez compliqués. Mais on peut calculer un nombre moyen de cycle d'horloge par opération : le CPI (Cycle Per Instruction). Le temps d’exécution moyen d'une instruction dépend alors :
* du nombre moyen de cycles d'horloge nécessaires pour exécuter une instruction, qu'on notera CPI (ce qui est l'abréviation de Cycle Per Instruction) ;
* et de la durée d'un cycle d'horloge, notée P (P pour période).
    $T_{\text{instruction}}=CPI\times P$
Quand on sait que la durée d'un cycle d'horloge n'est autre que l'inverse de la fréquence on peut reformuler en :
    $T_{\text{instruction}}={\frac {CPI}{f}}$, avec f la fréquence.

### La puissance de calcul : IPC et fréquence

On peut rendre compte de la puissance du processeur par une seconde approche. Au lieu de faire intervenir le temps mis pour exécuter une instruction, on peut utiliser la puissance de calcul, à savoir le nombre de calculs que l'ordinateur peut faire par seconde. En toute rigueur, cette puissance de calcul se mesure en nombre d'instructions par secondes, une unité qui porte le nom de IPS. En pratique, la puissance de calcul se mesure en MIPS : Million Instructions Per Second, (million de calculs par seconde en français). Plus un processeur a un MIPS élevé, plus il sera rapide : un processeur avec un faible MIPS mettra plus de temps à faire une même quantité de calcul qu'un processeur avec un fort MIPS. Le MIPS est surtout utilisé comme estimation de la puissance de calcul sur des nombres entiers. Mais il existe cependant une mesure annexe, utilisée pour la puissance de calcul sur les nombres flottants : le FLOPS, à savoir le nombre d'opérations flottantes par seconde.
Par définition, le nombre d'instruction par secondes se calcule en prenant le nombre d'instruction exécutée, et en divisant par le temps d’exécution, ce qui donne :
    $IPS={\frac {N}{T}}={\frac {1}{T_{\text{instruction}}}}$, avec $T_{\text{instruction}}$ le temps moyen d’exécution d'une instruction.
Sachant que l'on a vu plus haut que $T_{\text{instruction}}=CPI\times P={\frac {CPI}{f}}$, on peut faire le remplacement :
    $IPS={\frac {1}{CPI\times P}}={\frac {f}{CPI}}$
Pour simplifier les calculs, on peut remarquer que l'inverse du CPI n'est autre que le nombre de calculs qui sont effectués par cycle d'horloge. Celui-ci porte le doux nom d'IPC (Instruction Per Cycle). Celui-ci a plus de sens sur les processeurs actuels, qui peuvent effectuer plusieurs calculs en même temps, dans des circuits différents (des unités de calcul différentes, pour être précis). Sur ces ordinateurs, l'IPC est supérieur à 1. En remplaçant l'inverse du CPI par l'IPC, on a alors :
    $IPS=IPC\times f$
L'équation nous dit quelque chose d'assez intuitif : plus la fréquence du processeur est élevée, plus il est puissant. Cependant, des processeurs de même fréquence ont souvent des IPC différents, ce qui fait que la relation entre fréquence et puissance de calcul dépend fortement du processeur. On ne peut donc pas comparer deux processeurs sur la seule base de leur fréquence. Et si la fréquence est généralement une information qui est mentionnée lors de l'achat d'un processeur, l'IPC ne l'est pas. La raison vient du fait que la mesure de l'IPC n'est pas normalisée car l'IPC varie énormément suivant les opérations, le programme, diverses optimisations matérielles, etc.
On vient de voir que le temps d’exécution d'un programme est décrit par la formule suivante :
    $T=N\times {\frac {CPI}{f}}={\frac {N}{IPC\times f}}$, avec f la fréquence.
Les équations précédentes nous disent qu'il existe trois moyens pour accélérer un programme :
* diminuer le nombre d'instructions à exécuter ;
* diminuer le CPI (nombre de cycles par instruction) ou augmenter l'IPC ;
* augmenter la fréquence.
Diminuer le nombre d'instructions à exécuter dépend surtout du programmeur ou des compilateurs, et la conception du processeur n'a actuellement que peu d'impact à l'heure actuelle. Les deux autres solutions sont fortement impactées par la loi de Moore, et nous en parlerons au chapitre suivant.

## La performance d'une mémoire

Toutes les mémoires ne sont pas faites de la même façon et les différences entre mémoires sont nombreuses. Dans cette partie, on va passer en revue les différences les plus importantes. La rapidité d'une mémoire se mesure grâce à deux paramètres : le temps de latence et son débit binaire.
* Le temps de latence correspond au temps qu'il faut pour effectuer une lecture ou une écriture : plus il est bas, plus la mémoire est rapide.
* Le débit mémoire correspond à la quantité d'informations qui peut être récupéré ou enregistré en une seconde dans la mémoire : plus il est élevé, plus la mémoire est rapide

### Le temps d’accès d'une mémoire

La vitesse d'une mémoire correspond au temps qu'il faut pour récupérer une information dans la mémoire, ou pour y effectuer un enregistrement. Lors d'une lecture/écriture, il faut attendre un certain temps que la mémoire finisse de lire ou d'écrire la donnée : ce délai est appelé le temps d'accès, ou aussi temps de latence. Plus celui-ci est bas, plus la mémoire est rapide. Il se mesure en secondes, millisecondes, microsecondes pour les mémoires les plus rapides. Généralement, le temps de latence dépend de temps de latences plus élémentaires, qui sont appelés les timings mémoires.
Cependant, tous les accès à la mémoire ne sont pas égaux en termes de temps d'accès. Généralement, lire une donnée ne prend pas le même temps que l'écrire. Dit autrement, le temps d'accès en lecture est souvent inférieur au temps d'accès en écriture. Il faut dire qu'il est beaucoup plus fréquent de lire dans une mémoire qu'y écrire, et les fabricants préfèrent donc réduire le temps d'accès en lecture.
Voici les temps d'accès moyens en lecture de chaque type de mémoire :
* Registres : 1 nanoseconde (10$^{-9}$)
* Caches : 10 - 100 nanosecondes (10$^{-9}$)
* Mémoire RAM : 1 microseconde (10$^{-6}$)
* Mémoires de masse : 1 milliseconde (10$^{-3}$)

### Le débit d'une mémoire

Enfin, toutes les mémoires n'ont pas le même débit binaire. Le débit binaire d'une mémoire est la quantité de données qu'on peut lire ou écrire par seconde. Il se mesure en octets par seconde ou en bits par seconde. Évidemment, plus ce débit est élevé, plus la mémoire sera rapide.
Il ne faut pas confondre le débit et le temps d'accès. Pour faire une analogie avec les réseaux, le débit binaire peut être vu comme la bande passante, alors que le temps d'accès serait similaire au ping. Il est parfaitement possible d'avoir un ping élevé avec une connexion qui télécharge très vite, et inversement. Pour la mémoire, c'est similaire. D'ailleurs, le débit binaire est parfois improprement appelé bande passante.

### Le temps de balayage

Le temps de balayage d'une mémoire est le temps mis pour parcourir/accéder à toute la mémoire. Concrètement, il est défini en divisant la capacité de la mémoire par son débit binaire. Le résultat s'exprime en secondes. Le temps de balayage est en soi une mesure peu utilisée, sauf dans quelques applications spécifiques. C'est le temps nécessaire pour lire ou réécrire tout le contenu de la mémoire. On peut le voir comme une mesure du compromis réalisé entre la capacité de la mémoire et sa rapidité : une mémoire aura un temps de balayage d'autant plus important qu'elle est lente à capacité identique, ou qu'elle a une grande capacité à débit identique. Généralement un temps de balayage faible signifie que la mémoire est rapide par rapport à sa capacité.
Comme dit plus haut, le temps d'accès est différent pour les lectures et les écritures, et il en est de même pour le débit binaire. En conséquence, le temps de balayage n'est pas le même si le balayage se fait en lecture ou en écriture. On doit donc distinguer le temps de balayage en lecture qui est le temps mis pour lire la totalité de la mémoire, et le temps de balayage en écriture qui est le temps mis pour écrire une donnée dans toute la mémoire. Généralement, on balaye une mémoire en lecture quand on veut recherche une donnée bien précise dedans. Par contre, le balayage en écriture correspond surtout aux cas où on veut réinitialiser la mémoire, la remplir tout son contenu avec des zéros afin de la remettre au même état qu'à son démarrage.
Un exemple de balayage en écriture est celui d'une réinitialisation de la mémoire, à savoir remplacer le contenu de chaque case mémoire par un 0. Le temps nécessaire pour réinitialiser la mémoire n'est autre que le temps de balayage en écriture. En soi, les opérations de réinitialisation de la mémoire sont plutôt rares. Certains vieux ordinateurs effaçaient la mémoire à l'allumage, et encore pas systématiquement, mais ce n'est plus le cas de nos jours. Un cas plus familier est celui du formatage complet du disque dur. Si vous voulez formater un disque dur ou une clé USB ou tout autre support de stockage, le système d'exploitation va vous donner deux choix : le formatage rapide et le formatage complet. Le formatage rapide n'efface pas les fichiers sur le disque dur, mais utilise des stratagèmes pour que le système d'exploitation ne puisse plus savoir où ils sont sur le support de stockage. Les fichiers peuvent d'ailleurs être récupérés avec des logiciels spécialisés trouvables assez facilement. Par contre, le formatage complet efface la totalité du disque dur et effectue bel et bien une réinitialisation. Le temps mis pour formater le disque dur n'est autre que le temps de balayage en écriture.
Un autre cas de réinitialisation de la mémoire est celui de l'effacement du framebuffer sur les très vielles cartes graphiques. Sur les vielles cartes graphiques, la mémoire vidéo ne servait qu'à stocker des images calculées par le processeur. Le processeur calculait l'image à afficher et l'écrivait dans la mémoire vidéo, appelée framebuffer. Puis, l'image était envoyée à l'écran quand celui-ci était libre, la carte graphique gérant l'affichage. L'écran affichait généralement 60 images par secondes, et le processeur devait calculer une image en moins de 1/60ème de seconde. Mais si le processeur mettait plus de temps, l'image dans le framebuffer était un mélange de l'ancienne image et des parties de la nouvelle image déjà calculées par le processeur. L'écran affichait donc une image bizarre durant 1/60ème de seconde, ce qui donnait des légers bugs graphiques très brefs, mais visibles. Pour éviter cela, le framebuffer était effacé entre chaque image calculée par le processeur. Au lieu d'afficher un bug graphique, l'écran affichait alors une image blanche en cas de lenteur du processeur. Cette solution était possible, car les mémoires de l'époque avaient un temps de balayage en écriture assez faible. De nos jours, cette solution n'est plus utilisée, car la mémoire vidéo stocke d'autres données que l'image à afficher à l'écran, et ces données ne doivent pas être effacées.
Le temps de balayage en lecture est surtout pertinent dans les cas où on recherche une donnée précise dans la mémoire. L'exemple le plus frappant est celui des antivirus, qui recherchent si une certaine suite de donnée est présente en mémoire RAM. Les antivirus scannent régulièrement la RAM à la recherche du code binaire de virus, et doivent donc balayer la RAM et appliquer des algorithmes assez complexes sur les données lues. Bref, le temps de balayage donne le temps nécessaire pour scanner la RAM, si on oublie le temps de calcul. Tous les exemples précédents demandent de scanner la RAM à la recherche d'une donnée précise, et le temps de balayage donne une borne inférieure à ce temps de recherche. Cet exemple n'est peut-être pas très réaliste, mais il deviendra plus clair dans le chapitre sur les mémoires associatives, un type de mémoire particulier conçu justement pour réduire le temps de balayage en lecture au strict minimum.
Enfin, on peut aussi citer le cas où l'on souhaite vérifier le contenu de la mémoire, pour vérifier si tous les bytes fonctionnent bien. Il arrive que les mémoires RAM aient des pannes : certains bytes tombent en panne après quelques années d'utilisation, et deviennent inaccessibles. Lorsque cela arrive, tout se passe bien tant que les bytes défectueux ne sont pas lus ou écrits. Mais quand cela arrive, les lectures renvoient des données incorrectes. Les conséquences peuvent être très variables, mais cela cause généralement des bugs assez importants, voire des écrans ou de beaux plantages. De nombreux cas d'instabilité système sont liés à ces bytes défectueux. Il est possible de vérifier l'intégrité de la mémoire avec des logiciels spécialisés, qui vérifient chaque byte de la mémoire un par un. Les systèmes d'exploitation modernes incorporent un logiciel de ce genre, comme Windows qui en a un d'intégré. Le BIOS ou l'UEFI de votre ordinateur a de bonnes chances d'intégrer un logiciel de ce genre. Ces logiciels de diagnostic mémoire balayent la mémoire byte par byte, case mémoire par case mémoire, et effectuent divers traitements dessus. Dans le cas le plus simple, ils écrivent une donnée dans chaque byte, avant de le lire : si la donnée lue et écrite ne sont pas la même, le byte est défectueux. Mais d'autres traitements sont possibles. Toujours est-il que ces utilitaires balayent la mémoire, généralement plusieurs fois. Le temps de balayage donne alors une idée du temps que mettront ces logiciels de diagnostic pour s’exécuter.

## La performance d'un bus

La performance d'un bus est quelque chose de complexe à décrire. Mais le critère principal est le débit binaire. Le débit binaire est la quantité de données que le bus peut transmettre d'un composant à un autre, par seconde. Il se mesure en octets par seconde ou en bits par seconde. Les bus haute performance sont capables de transmettre un grand nombre de données par seconde, alors que ceux de basse performance ne peuvent échanger qu'un petit nombre de données sur le bus.
Le débit binaire d'un bus est influencé par deux autres paramètres : sa largeur et sa fréquence. La fréquence du bus est assez simple à comprendre : le bus est cadencé par une horloge, qui a une certaine fréquence. A chaque cycle, il transfère plusieurs bits à la fois. Le nombre de bits transmis en même temps est appelé la largeur du bus. Par exemple, un bus d'une largeur de 16 bits peut transférer deux octets par cycle d'horloge. La largeur du bus correspond au nombre de fils utilisés pour transférer les données. Si un bus peut transférer 8 bits par cycle, cela signifie que ce bus dispose de 8 fils, un par bit, chaque fil peut transmettre un bit par cycle. Le débit binaire est le produit de la largeur du bus par sa fréquence.

## Les limites de la performance des applications : le roofline model

Plus haut, nous avons parlé des performances du processeur et de la mémoire de manière isolée. Dans les faits, les programmes qui s'exécutent sur un processeur utilisent les deux, et à des degrés divers. Il y a un continuum entre des programmes qui accèdent beaucoup à la mémoire et font peu de calculs, et les programmes opposé qui font beaucoup de calculs mais accèdent peu à la RAM. Un programme très gourmand en calculs profitera d'un processeur rapide, même si la mémoire RAM est lente. Et inversement, un programme qui accède beaucoup à la mémoire a besoin d'une mémoire RAM rapide, même si le processeur ne suit pas.
    Dans le même genre, les personnes afficionados de jeux vidéos ont sans doute entendu parler du bottleneck CPU/GPU pour désigner les jeux vidéo dont le framerate est limité soit le CPU ou par la carte graphique. La performance est alors la responsabilité partagée du processeur et de la carte graphique, mais l'un des deux sera le facteur limitant.
Pour quantifier ce genre de compromis, Samuel Williams, Andrew Waterman, et David Patterson, ont inventé le roffline model, initialement été décrit dans cet article scientifique :
* Roofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures.
Nous allons décrire ce modèle dans ce chapitre. Il est souvent vu dans les chapitres sur les architectures parallèles dans les rares cours d'architecture des ordinateur qui en font mention, mais il s'agit bel et bien d'un modèle qui marche sur les architectures à un seul cœur/processeur.

### Le modèle de base

Le modèle introduit le concept d'intensité calculatoire. Il s'agit du nombre d'opérations réalisées pour un octet lu/écrit depuis la mémoire RAM. Elle varie suivant le programme considéré, tous les programmes n'ont pas la même intensité calculatoire. En clair, il s'agit du nombre d’opérations réalisé par un programme, divisé par le débit binaire mémoire. Le débit binaire utilisé est celui de la mémoire RAM, pas des caches, car la mémoire est supposée partagée.
A forte intensité calculatoire, on fait beaucoup de calculs comparé aux accès mémoires. On demande donc plus au processeur qu'à la mémoire. A basse intensité calculatoire, on accède beaucoup à la mémoire et on fait peu d'opérations. La mémoire est donc le facteur limitant. Globalement, au-delà d'une certaine intensité calculatoire, c'est le processeur qui sera limitant (et inversement, ce sera la mémoire). Il existe un point d'équilibre où la mémoire et la performance des CPU sont tous deux des facteurs limitants, le système est parfaitement équilibré.
Le roofline donne la performance totale, qui est limitée par le débit de la mémoire, par la performance maximale des CPUs parallèles exprimée en MIPS/FLOPS, et par l'intensité calculatoire. Le modèle est un simple diagramme en deux dimensions, avec l'intensité calculatoire en abscisse, et la performance en ordonnée. Plus l'intensité calculatoire augmente, plus les performances augmentent, à débit binaire égal. La mémoire est alors le facteur limitant, et on fait alors plus de calcul à débit binaire égal. Mais au-delà d'une intensité calculatoire bien précise, le débit binaire n'est plus le facteur limitant, mais c'est le processeur qui limite les performances. On a atteint un plateau dépendant des CPUs.

### Les calculs qui permettent d'obtenir la courbe du modèle

Pour obtenir la courbe, rien de plus simple. Le modèle part du principe qu'il y a une puissance de calcul maximale indépassable, exprimée en FLOPS ou en MIPS. Il s'agit de la limite maximale obtenable en ne tenant compte que du processeur, pas du débit de la mémoire. Elle correspond à la portion plate de la courbe. Notons la puissance de calcul maximale permise par le CPU $\pi$.
Maintenant, la performance est aussi limitée par le débit binaire de la mémoire. Si l'on a un débit binaire de $D$, alors la performance maximale se calcule en multipliant ce débit binaire par l'intensité calculatoire. Ce dernier est un nombre de calculs par octet lu/écrit, on multiplie par le nombre total d'octets lus/écrits : on a bien une puissance de calcul. En notant $P_{RAM}$ le résultat, on a :
    $P_{RAM}=\beta \times I$, avec I l'intensité calculatoire et $\beta$ le débit binaire.
La puissance réelle dépend des deux limites. Elle ne peut pas dépasser la performance max permise par le CPU, pas plus qu'elle ne peut dépasser celle permise par le débit de la RAM. En clair, la performance maximale possible est la plus petite valeur entre les deux :
    $P=\min {\begin{cases}\pi \\\beta \times I\end{cases}}$

### Les limites du modèle

Il faut préciser que le modèle donne une limite maximale pour la performance. Dans les faits, les applications ne l'atteindront pas. Elle auront une performance inférieure à la limite maximale, pour une intensité arithmétique donnée. La performance réelle sera parfois très proche, parfois très éloignée de la performance maximale.
Les raisons à cela sont multiples. La première est tout simplement que le processeur n'utilise pas son plein potentiel, sans que ce soit lié à la mémoire ou aux caches. Par exemple, il n'arrive pas à alimenter ses circuits de calculs pour des raisons diverses et variées. Le plafond est alors plus bas qu'il n'y parait et quelques optimisations logicielles permettent de faire remonter le plafond effectif.
Il est aussi possible que le programme considéré n'utilise pas bien le débit binaire de la mémoire, une partie est gâchée par des accès mémoire inutiles. Diverses optimisations logicielles ou matérielles permettent alors de se rapprocher du maximum théorique dans la portion limitée par la mémoire. Sans ces optimisations, la courbe a une pente décalée vers la droite, car le programme fait moins d'accès mémoire pour une intensité arithmétique inchangée.
Notons que le débit binaire considéré dans le modèle est celui de la mémoire RAM. L'usage de mémoires caches change la donne d'une manière assez originale. Une mauvaise utilisation des caches fait que l'intensité arithmétique stagnera à un niveau maximal. En clair, cela se traduit par des barrières verticales sur le diagramme, que le programme ne pourra pas dépasser. Le programme restera à gauche, dans la partie limitée par la barrière. Et celle-ci est systématiquement dans la portion gauche de la courbe, celle limitée par la mémoire.
Pour résumer, le modèle peut aider les programmeurs à savoir quoi optimiser, s'ils savent faire des mesures adéquates sur un grand nombre de hardware différents. Mais il nous dit plusieurs choses importantes : un programme peut être limité soit par le CPU, soit par le débit binaire de la mémoire, soit par une mauvaise utilisation des caches. Par un programme ne se comportera de la même manière qu'un autre, les compromis seront différents du fait d'intensité arithmétiques différentes. Et suivant la machine, un même programme se comportera très différemment. Il y a donc une grande variabilité des performances d'un programme et d'une machine à l'autre.
De plus, les programmeurs doivent faire face à des compromis lorsqu'ils optimisent. Par exemple, optimiser l'intensité arithmétique en améliorant l'utilisation des mémoires caches ou en réduisant les accès mémoire a du sens, mais seulement si la performance est limitée par la mémoire. Mais une telle optimisation ne servira à rien si le facteur limitant est la performance du processeur. Dans le passé, c'était surtout la performance des mémoire et du processeur qui étaient limitante. Mais de nos jours, le problème tient surtout dans les caches et la bonne utilisation de la hiérarchie mémoire, du moins pour une majorité de programmes. Les situations sont assez variables, mais les grandes lignes du hardware actuel sont là : les processeurs sont des monstres de puissance théorique, les mémoires RAM ont un débit absolument énorme, mais on se heurte aux barrières liées aux mémoires caches.