Architecture de l’ordinateur(assembleur)

Architecture de l’ordinateur
Emmanuel Lazard Université Paris-Dauphine
mars 2011
Computers are my forte! BRAZIL (Terry Gilliam, 1985)
Ce document a initialement été publié sous forme de livre :
Emmanuel Lazard Architecture de l’ordinateur Collection Synthex Pearson Education France, 2006 ISBN : 2-7440-7176-5
Ce livre étant épuisé et l’éditeur n’envisageant pas de réédition, ce dernier a donné son accord pour que le texte du livre soit en libre diffusion. Ce document lui est quasiment identique à quelques corrections orthographiques et mises à jour près.
Les polices de caractères utilisées dans ce document sont : Gentium, Inconsolata et Gill Sans. Ce polycopié est diffusé sous Licence Creative Commons « Paternité – Pas d’Utilisation Commerciale – Pas de Modification 2.0 ».
Vous êtes libres de reproduire, distribuer et communiquer cette création au public selon les conditions suivantes.
Paternité — Vous devez citer le nom de l’auteur original de la manière indiquée par l’auteur de l’œuvre ou le titulaire des droits qui vous confère cette autorisation (mais pas d’une manière qui suggérerait qu’ils vous soutiennent ou approuvent votre utilisation de l’œuvre). Pas d’Utilisation Commerciale — Vous n’avez pas le droit d’utiliser cette création à des fins commerciales. Pas de Modification — Vous n’avez pas le droit de modifier, de transformer ou d’adapter cette création.
Les programmes figurant dans ce livre ont pour but d’illustrer les sujets traités. Il n’est donné aucune garantie quant à leur fonctionnement une fois compilés, assemblés ou interprétés dans le cadre d’une utilisation professionnelle ou commerciale.
La première image de couverture est une machine Z3 construite en 1941 par Konrad Zuse (Allemagne). Programmable, travaillant en binaire (et même en arithmétique flottante), elle est à base de relais électriques et est considérée comme ce qui s’approcherait le plus du « premier ordinateur ». Elle a été détruite lors d’un raid allié en 1943 mais une réplique fonctionnelle en a été faite dans les années 60 et se trouve au Deutsches Museum de Munich (Image courtesy of Computer History Museum). La seconde photo représente l’architecture Westmere des derniers processeurs Intel avec environ un milliards de transistors sur une puce (Image courtesy of Intel Corporation).

Sommaire
Introduction ii
1. Représentation des nombres 1
1. Calcul binaire et entiers positifs 2 2. Nombres négatifs 6 3. Nombres réels 9 4. Codage des caractères 11 5. Types et programmation 13 Problèmes et exercices 15
2. Circuits logiques 21 1. Fonctions booléennes 22 2. Circuits combinatoires 30 3. Circuits logiques séquentiels 34 Problèmes et exercices 40
3. Ordinateur et processeur 51 1. Architecture de von Neumann 52 2. Les instructions 59 3. UAL et registres 65 4. Séquenceur 68 5. Architectures évoluées 70 Problèmes et exercices 78
4. Exemple de langage assembleur 89 1. Description d’un processeur 90 2. Instructions 91 3. Programme d’assemblage 99 4. Extensions possibles 102 Problèmes et exercices 104
5. Mémoire 115 1. Caractéristiques 116 2. Mémoire à semi-conducteurs 119 3. Programmation et stockage en mémoire 123 Problèmes et exercices 127
6. Mémoire cache 135 1. Principe 136 2. Caractéristiques 138 3. Amélioration des caches 145 Problèmes et exercices 149
7. Mémoire virtuelle 161 1. Principe 162 2. Implémentation 164 3. Segmentation 172 Problèmes et exercices 175
8. Entrées/sorties 185 1. Bus 186 2. Interruptions 189 3. Gestion des entrées/sorties 192 4. Technologies de stockage 196
Problèmes et exercices 199
Bibliographie 201
Index 202

Sommaire i

Architecture de l’ordinateur ii Introduction L’architecture de l’ordinateur est le domaine qui s’intéresse aux différents composants internes des machines, en explicitant leur construction et leurs interactions. Un ordinateur est un outil complexe qui peut effectuer des tâches variées, et dont les performances globales dépendent des spécifications de tous ses éléments. Comprendre son architecture permet de savoir dans quelle mesure les caractéristiques propres à chaque composant influencent la réactivité de la machine en fonction de son usage : pourquoi ajouter de la mémoire accélère-t-il l’ordinateur ? Pourquoi le temps d’accès d’un disque dur n’est-il qu’un des paramètres permettant de mesurer son efficacité ? Comment les processeurs font-ils pour aller toujours plus vite ? L’utilité de ce domaine de connaissances est encore plus évidente pour les programmeurs qui développent des applications, de l’étudiant s’amusant sur son matériel personnel au professionnel écrivant des lignes de code au sein d’une équipe. La programmation dans des langages évolués est théoriquement indépendante des contraintes architecturales, mais dans les faits, celles-ci ont un impact sur l’écriture, la correction et les performances des programmes, via, par exemple, l’utilisation des pointeurs, le choix de la taille des variables ou de l’ordre des boucles. Négliger ou ignorer la structure de l’ordinateur amènera tôt ou tard à des déconvenues et à des erreurs. Cet ouvrage se veut une présentation générale de l’architecture de l’ordinateur et de ses éléments, associant les descriptions techniques au logiciel, qu’il soit système d’exploitation ou application personnelle. Après avoir exposé les briques de base que sont la représentation des nombres et les circuits logiques, il entreprend de décortiquer la pièce maîtresse de l’ordinateur, à savoir le processeur, ainsi que son langage de programmation spécifique, en incluant une illustration des architectures avancées des processeurs actuels. Mais un processeur isolé serait inutilisable sans l’ensemble des composants qui le soutiennent pour assurer le bon déroulement des programmes. Cet ouvrage décrit le système de stockage de l’information, depuis la mémoire cache jusqu’aux disques durs, en passant par la mémoire principale et la mémoire virtuelle. Pour finir, il présente le mécanisme des entrées/sorties, lié à la communication de l’ordinateur avec son environnement, aussi bien du point de vue matériel (contrôleur) que logiciel (pilote). Cet ouvrage est inspiré d’un enseignement délivré depuis de nombreuses années à des étudiants en informatique dans des formations professionnelles. Il a pour ambition de faire comprendre les mécanismes internes de l’ordinateur et leurs implications sur le développement des logiciels aux élèves de licence scientifique, et de façon plus générale de faire découvrir l’architecture des machines à tous ceux qui s’intéressent à ce sujet. À la fin de chaque chapitre, des exercices corrigés permettent d’appliquer directement les notions présentées, à travers l’étude ou l’écriture de programmes, des applications numériques et des constructions de circuits. L’auteur remercie chaleureusement les relecteurs, Daniel Chillet et Stéphane Nicolet, qui, par leurs conseils, remarques et documentation, ont largement amélioré les essais préliminaires. Merci à Karen, Kathy et Maude qui ont contribué, de mille et une manières, à l’écriture de ce livre.
LE PLAN
L’architecture des ordinateurs, les descriptions techniques et les interactions avec le logiciel sont exposées dans les huit chapitres de la façon suivante :
Chapitre 1 : Représentation des nombres. Ce chapitre est centré sur la représentation informatique des nombres usuels et des caractères. Il montre comment ceux-ci sont stockés en mémoire (et l’impact sur le logiciel) et les limites de leur représentation (valeurs admises, valeurs maximales).
Chapitre 2 : Circuits logiques. Ce chapitre présente les bases de la logique booléenne et son implémentation sous forme de circuits logiques, des premières portes logiques aux circuits élémentaires présents dans tous les circuits intégrés électroniques.

Chapitre 3 : L’ordinateur et le processeur. Après une vue d’ensemble de l’ordinateur, ce chapitre propose la construction d’un processeur simple. Seront présentés ses différentes unités fonctionnelles et son langage de programmation. Il sera également question des avancées architecturales des processeurs récents.
Chapitre 4 : Un exemple de langage assembleur. Ce chapitre est entièrement dévolu à la programmation en langage assembleur d’un processeur fictif. Les différentes instructions présentées montrent les possibilités du langage de commande du processeur. Elles seront mises en œuvre dans de nombreux exercices de programmation.
Chapitre 5 : La mémoire. Ce chapitre débute par une présentation des différentes zones de stockage dans un ordinateur, en les distinguant suivant leurs caractéristiques (technologies, performances). Il s’intéresse ensuite à la mémoire principale à semi-conducteurs et à son utilisation en programmation, en explicitant la façon dont un logiciel gère son espace de mémorisation des variables.
Chapitre 6 : La mémoire cache. La description des principes fondateurs de la mémoire cache est suivie par un inventaire exhaustif des caractéristiques de celle-ci (taille, organisation, remplacement, réécriture) et une illustration des techniques améliorant efficacité des caches (optimisation du code, caches multiniveaux…).
Chapitre 7 : La mémoire virtuelle. La mémoire virtuelle est à mi-chemin entre le matériel et le système d’exploitation. Ce chapitre en présente les principes théoriques (pagination, segmentation) ainsi que les techniques d’implémentation en insistant sur les optimisations effectuées.
Chapitre 8 : Les entrées/sorties. Le dernier chapitre se préoccupe des liens entre le processeur et son environnement, d’abord par l’étude succincte des bus de communication le reliant aux autres composants, puis par l’explication du fonctionnement des cartes d’entrées/sorties permettant de brancher des périphériques. Le côté logiciel comprend une description du mécanisme des interruptions, qui offre au processeur un moyen de réagir à un événement extérieur.
Introduction iii
Chapitre 1
Représentation des nombres
Pour comprendre comment fonctionne un
Représentation des nombres
ordinateur, il faut d’abord comprendre comment il
1. Calcul binaire et entiers positifs…………. 2
traite les nombres. La machine travaille uniquement
2. Nombres négatifs ……………………………….. 6 3. Nombres réels ……………………………………. 9 avec deux valeurs (0 ou 1), appelées « bits »,
4. Codage des caractères……………………… 11 mémorisées dans des cases de taille limitée.
5. Types et programmation ………………….. 13
Comment représenter et stocker des nombres
Problèmes et exercices positifs, négatifs, décimaux ou même des
1. Écrire dans différentes bases ……………. 15
caractères ? Voilà ce que vous allez découvrir dans
ce chapitre.
2. Représenter des entiers……………………. 15 3. Calculer en binaire ……………………………. 16 4. Débordement……………………………………. 16 Loin d’être enfouies dans les profondeurs du
5. Travailler avec des réels …………………… 17
matériel, ces notions resurgissent au moment de la
6. Approximation de réels ……………………. 18
programmation dans le choix des types des
7. Type des variables …………………………….. 19
variables.
Représentation des nombres 1
1. CALCUL BINAIRE ET ENTIERS POSITIFS
Depuis toujours, les ordinateurs calculent en binaire. Il s’agit de la base 2 dans laquelle seuls les symboles 0 et 1 sont utilisés pour écrire les nombres, sans bien sûr que cela limite la taille des nombres représentables. Ceux- ci vont être stockés dans des cases qui, elles, ont une taille fixée. L’ordinateur est donc limité dans ses capacités à exprimer n’importe quel nombre.
1.1 Calcul dans une base quelconque
Notre système décimal et le système binaire ne sont que deux possibilités de représentation des nombres et nous pouvons généraliser cette écriture à une base B quelconque.
Symboles De même qu’en décimal on utilise dix chiffres et que seuls deux symboles (0 et 1) sont permis en binaire, B symboles différents sont nécessaires pour exprimer un nombre quelconque en base B. Si B est inférieur ou égal à 10, on utilise évidemment les chiffres arabes classiques ; ainsi en base 8, on se sert des chiffres de 0 à 7. Si B est supérieur à 10, il faut définir de nouveaux symboles pour « compter » entre 10 et B. La seule base d’utilisation courante dans laquelle le problème se pose est la base 16 (voir section 1.2), qui utilise les lettres a, b, c, d, e et f pour les nombres de 10 à 15.
Valeur d’un nombre Une fois les symboles façon suivante :
choisis, on peut lire la représentation d’un nombre de n « chiffres » xn-1xn-2 … x1x0 de la
X = xn–1Bn–1 +xn–2Bn–2 +…+x1B+x0 = ∑
n–1xiBi i=0 Autrement dit, on multiplie chaque symbole avec les puissances successives de la base B.
Remarque
L’écriture d’un nombre est ambiguë si la base n’est pas explicite. Ainsi, la même écriture 101 peut valoir cent un si on lit le nombre en décimal, mais aussi 62 + 1 en base 6, soit trente-sept, ou cinq en binaire (22 + 1). Pour éviter cela, lorsque la base n’est pas évidente suivant le contexte, il est courant d’indicer le nombre par la base, ici 10110, 1016 ou 1012. Valeurs maximales Il est important de savoir quelle est la valeur maximale que l’on peut exprimer avec n symboles. Cela permet tout de suite de savoir si une case mémoire de l’ordinateur (qui a une taille fixée) sera assez grande pour contenir une valeur. Avec n symboles en base B, le plus grand nombre qu’il est possible de représenter s’écrit avec tous les symboles égaux à B – 1, ce qui donne la valeur Bn – 1 :
(B−1)Bn–1 +(B−1)Bn–2 +…+(B−1) = (B−1) ∑ n–10Bi
=(B−1) BB−1 n −1
= Bn −1
On peut donc écrire tous les nombres positifs de 0 à Bn – 1. Par exemple, en décimal, avec quatre chiffres, on peut compter de 0 à 9 999, tandis qu’en binaire, avec dix symboles binaires, on représente les nombres de 0 à 210 – 1 = 1 023.
1.2 Bases classiques en informatique
De même que la communication humaine n’utilise que la base 10 (et les bases 24 et 60 pour le décompte du temps), l’informatique ne se sert que de quelques bases bien précises.
Base 2 La première base fondamentale est la base 2, qui permet le calcul binaire. Chaque symbole d’un nombre binaire peut prendre la valeur 0 ou 1 et s’appelle un bit (de l’anglais BInary digiT, chiffre binaire). Par exemple, le nombre 101101012 se calcule en décimal comme 27 + 25 + 24 + 22 + 1 = 18110.
Architecture de l’ordinateur 2
Bit/octet de poids fort/faible.
1.3 Changement de base
L’ordinateur ne sait calculer qu’en base 2. Malheureusement, l’écriture binaire n’est ni pratique (à cause de la taille des écritures), ni intuitive (le cerveau humain ne calcule facilement qu’en base 10). On doit donc souvent effectuer des changements de base entre la base 2 et les bases 8, 10 ou 16. Le changement de base le plus simple est le passage entre la base 2 et les bases 8 ou 16. En effet, les valeurs 8 et 16 étant des puissances de 2 (8 = 23 ; 16 = 24), chaque bloc de 3 ou 4 bits correspond à un symbole octal ou hexadécimal.
Définition
Un nombre binaire composé de 8 bits s’appelle un octet et peut prendre des valeurs (décimales) de 0 à 255. Cette taille a son importance car c’est ce que peut contenir une case mémoire. Deux cases mémoire ensemble peuvent contenir 16 bits (permettant de stocker une valeur entre 0 et 65 535) et s’appellent parfois « mot binaire », un long mot étant alors quatre cases mémoire, soit 4 octets.
Complément
Le système de calcul binaire n’est évidemment pas naturel. Il s’est imposé parce qu’il est bien adapté aux contraintes des circuits électroniques. Il est en effet simple de distinguer deux valeurs de tension sur un fil. Si l’on avait souhaité reproduire directement le calcul décimal, dix valeurs différentes de la tension auraient été nécessaires, ce qui aurait rendu les circuits beaucoup plus complexes.
Bases 8 et 16 L’inconvénient majeur du calcul binaire est la place que prend l’écriture des nombres ! Pour exprimer un nombre N en binaire, il est nécessaire d’utiliser log2 N symboles binaires (plus précisément la valeur entière supérieure de log2 N), alors que son écriture décimale nécessite autant de chiffres que son logarithme en base 10 (log10 N). Le rapport entre ces deux valeurs indique que la représentation binaire d’un nombre emploie au moins trois fois plus de symboles que sa représentation décimale. Deux autres bases usuelles, prenant moins de place, ont été exploitées dans l’histoire de l’informatique : d’abord la base 8 (octale), qui utilise les chiffres de 0 à 7, puis la base 16 (hexadécimale), qui utilise tous les chiffres décimaux ainsi que les lettres de a à f (puisqu’il faut des symboles supplémentaires pour les nombres de 10 à 15). Par exemple, 21768 = 2 χ 83 + 82 + 7 χ 8 + 6 = 115010 = 4 χ 162 + 7 χ 16 + 14 = 47e16.
Complément
La base 8 n’est plus utilisée de nos jours alors que la base 16 l’est toujours (on verra pourquoi plus loin). Dans le langage de programmation C, on peut exprimer un nombre en octal en lui préfixant le symbole \ et un nombre hexadécimal en lui préfixant 0x.
Définition
Il est souvent utile de pouvoir désigner la partie la plus ou la moins importante d’un nombre (celle qui pèse le plus ou le moins dans le calcul de la valeur de ce nombre). Cela correspond aux symboles les plus à gauche ou les plus à droite dans l’écriture du nombre en question (quelle que soit la base). On parle alors du bit de poids fort et du bit de poids faible d’un nombre binaire, du chiffre de poids fort ou de poids faible d’un nombre décimal, du symbole hexadécimal de poids fort ou faible, etc. Par extension, on parle de l’octet de poids fort d’un nombre binaire écrit sur plusieurs octets, qui correspond aux 8 bits les plus à gauche dans l’écriture binaire de ce nombre, et de l’octet de poids faible (voir figure 1.1).
Figure 1.1
Représentation des nombres 3
Architecture Correspondance base 2 – base 8 ou 16 Prenons un exemple. Pour écrire le nombre binaire 101101000110 en base 8, on exprime chaque groupe de 3 bits (en partant des bits de poids faible) dans son équivalent octal. On obtient ici successivement de droite à gauche 110 → 6, 000 → 0, 101 → 5, 101 → 5, ce qui donne : 1011010001102 = 55068. On opère de la même façon pour le passage vers la base 16, en regroupant de bits n’est pas divisible par 3 ou 4, il est les alors bits quatre à nécessaire d’ajouter quatre : des (1011 bits 0100 nuls 0110)en 2 tête = b46du 16. Si le nombre nombre. Par exemple : pour passer 1101010de la base 2 = (001 8 ou 101 16 010)à la 2 base = 1522, 8 on en remplace octal et 1101010chaque 2 = symbole (0110 1010)octal 2 = ou 6ahexadécimal 16 en hexadécimal. par les À 3 l’inverse, ou 4 bits équivalents : par exemple 3278 = 110101112 et 4ce16 = 100110011102.
Remarque
La base 16 est bien adaptée pour exprimer les nombres en informatique car, comme l’unité de taille est l’octet, c’est-à-dire 8 bits, il suffit de deux symboles hexadécimaux pour écrire 1 octet. Pour cette raison, la base 8 n’est plus utilisée car il faut au moins trois symboles pour représenter 1 octet. En outre, cela permet (ce qui n’est pas souhaitable) d’écrire des nombres plus grands (sur 9 bits).
Correspondance base 2 – base 10 Le changement de base est ici plus compliqué car il n’y a pas de correspondance directe entre les bits et les chiffres décimaux. Il faut passer par une étape de calcul. Pour avoir la valeur décimale d’un nombre binaire, il suffit d’additionner les puissances de 2 correspondant aux bits mis à 1 dans l’écriture binaire : 101101000110garder le reste, 2 = qui 211 donne + 29 + 28 le + bit 26 + de 22 poids + 21 = 2886faible, 10. et Dans recommencer l’autre sens, il faut diviser le nombre décimal par 2, avec le quotient, jusqu’à arriver à un quotient égal à 1.
Figure 1.2
Conversion décimal vers binaire.
À la figure 1.2, on divise 117 par 2, ce qui donne un reste de 1 et un quotient de 58. On poursuit la division pour aboutir à un quotient de 1 (qui représente le bit de poids fort du nombre). On lit alors les bits en « remontant les divisions » : 11710 = 11101012.
Complément
Le passage de la base 10 vers la base 2 n’étant pas automatique, certains ordinateurs ont historiquement utilisé le codage BCD (Binary Coded Decimal, décimal codé binaire). Dans ce codage, chaque chiffre décimal est directement transformé en 4 bits (3 bits n’étant pas suffisants). Ce n’est plus un codage binaire (les bits ne représentent plus les puissances de 2), mais une simple réécriture des chiffres. Cela permet une transformation facile mais complique la programmation des opérations arithmétiques.
1.4 Arithmétique binaire
Maintenant que nous savons compter en binaire, nous allons étudier les opérations arithmétiques classiques. Elles se réalisent de la même manière qu’en décimal.
Addition De même que l’on additionne deux nombres décimaux chiffre à chiffre en obtenant un résultat et une retenue à reporter, pour additionner deux nombres binaires, il faut définir l’addition de 2 bits. Il n’y a que quatre cas à examiner :
• 0 + 0 donne 0 de résultat et 0 de retenue.
• 0 + 1 donne 1 de résultat et 0 de retenue.
• 1 + 0 donne 1 de résultat et 0 de retenue.
4 de l’ordinateur
• 1 + 1 donne 0 de résultat et 1 de retenue (de même qu’il y a une retenue lors de l’addition de deux chiffres décimaux quand le résultat est supérieur à 10). On effectue ensuite l’addition binaire bit à bit, de droite à gauche, en reportant les retenues, comme dans l’exemple suivant :

+
1 1 1 1 1 1 0101 1
1 1 0 1 1 1 0

1 0 0 1 1 0 0 1
On peut vérifier le résultat en décimal : 43 + 110 = 153.
Soustraction Le scénario est identique pour la soustraction de deux nombres binaires : la soustraction de 2 bits donne un bit de résultat et un bit de retenue de report sur la colonne suivante :
• 0 – 0 donne 0 de résultat et 0 de retenue.
• 0 – 1 donne 1 de résultat et 1 de retenue.
• 1 – 0 donne 1 de résultat et 0 de retenue.
• 1 – 1 donne 0 de résultat et 0 de retenue. On effectue la soustraction binaire bit à bit, de droite à gauche, en reportant les retenues, comme dans l’exemple suivant :

−
1 1 1 0 1 0 1 1 11 1 10 1 0 1 0 1 1 0 1 1

Nous parlerons du problème des nombres négatifs dans la prochaine section.
Multiplication La multiplication binaire peut s’effectuer comme une suite d’additions successives des produits partiels, comme une multiplication décimale. Cela dit, elle est plus simple à poser que la multiplication décimale car les tables de multiplication sont réduites à leur plus simple expression ! On multiplie soit par 0 (et le résultat est nul) soit par 1 (et on recopie le multiplicateur). Voici un exemple :
1 0 1 0 1 1 0
χ 1 1 0 1 0 1 1 1 1 1 1 101 0 1 1 0 •
+ 1 0 1 0 1 1 0 • • •
+ 1 0 1 0 1 1 0 • • • •
1 0 0 0 1 0 1 1 1 1 0 0
Cette manière d’opérer s’implémente facilement car elle consiste à ne faire que des décalages et des additions, opérations classiques sur les processeurs. L’inconvénient de la multiplication est qu’elle allonge fortement les nombres : multiplier deux nombres de n bits peut donner un résultat sur 2n bits. Il faut donc faire attention lorsque ces nombres sont stockés dans une case mémoire car le résultat, de taille double, peut ne plus tenir dans une case.
Division La division binaire est l’opération la plus compliquée. On opère comme en décimal : on soustrait le diviseur du dividende en commençant par les bits de poids fort. Elle nécessite une série de soustractions et de décalages pour donner un quotient et un reste.
Représentation des nombres 5
2. NOMBRES NÉGATIFS
Nous savons maintenant représenter en binaire des nombres entiers positifs. Mais comment faire pour travailler avec des nombres négatifs ? Dans l’arithmétique classique, ces nombres sont précédés d’un signe moins, mais c’est ici impossible car on ne peut mettre que des bits dans une case mémoire. Il faut donc trouver une écriture, une représentation des nombres négatifs, utilisant les bits disponibles.
2.1 Représentation « signe et valeur absolue »
La première idée est de reproduire le signe en utilisant le bit de poids fort (voir figure 1.1) du nombre pour le représenter.
Définition
Sur n bits, le bit de poids fort (aussi appelé « bit de signe ») indique le signe du nombre (selon une convention classique, ce bit est à 1 pour un nombre négatif) et les n – 1 bits restants donnent la valeur absolue binaire du nombre. Les mots binaires 01011001 = 89 et 10110100 = –52 sont deux exemples de nombres écrits dans cette représentation sur 8 bits.
Caractéristiques Notez que l’on ne représente pas plus de nombres ainsi : sur n bits, on représente toujours au maximum 2n valeurs différentes. Ce que l’on a fait est un décalage de la plage des nombres autorisés en passant de l’intervalle [0, 2n – 1] à l’intervalle [–(2n – 1 – 1), 2n – 1 – 1]. Il n’y a plus que 2n – 1 nombres exprimés car le zéro peut s’écrire de deux manières différentes : +0, c’est-à-dire 00…0, et –0 qui s’écrit 10…0.
Arithmétique Dans cette représentation, il est facile de savoir si un nombre est positif ou négatif puisqu’il suffit de regarder le bit de poids fort. Par ailleurs, changer le signe du nombre revient à inverser ce bit. En revanche, les opérations arithmétiques classiques sont plus compliquées qu’avec des nombres positifs car les règles d’addition des bits ne s’appliquent plus : cela reviendrait à additionner les valeurs absolues, et non les nombres eux-mêmes ! Avant d’additionner deux nombres, il faut regarder s’ils sont de signes opposés et, dans ce cas, procéder à une soustraction des valeurs absolues puis retrouver le signe du résultat en fonction de la taille respective des opérandes. Ces contraintes ralentissent les opérations arithmétiques et, pour cette raison, cette représentation n’est plus utilisée.
2.2 Représentation en complément à 2
C’est la représentation standard sur les ordinateurs pour exprimer les nombres entiers négatifs. Quand on parle de représentation signée ou d’entiers signés, ces derniers sont toujours exprimés à l’aide de la représentation en complément à 2.
Définition
Sur n bits, on exprime les nombres de l’intervalle [–2n – 1, 2n – 1 – 1]. On retrouve bien les 2n nombres possibles. Un nombre positif est représenté de façon standard par son écriture binaire. On représente un nombre négatif en ajoutant 1 à son complément à 1 (obtenu en inversant tous les bits) et en laissant tomber une éventuelle retenue finale.
Si l’on reprend l’exemple précédent, 89 (positif) s’écrit toujours 01011001, mais –52 (négatif) s’écrit maintenant 11001100. En effet, en binaire sur 8 bits, 52 s’écrit 00110100, ce qui donne un complément à 1 égal à 11001011 et un complément à 2 égal à 11001100. Dans le cas d’un nombre négatif, il est important d’indiquer sur combien de bits doit s’écrire le nombre car on ne rajoute pas des zéros en tête mais des uns (suite à l’inversion obtenue lors du calcul du complément à 1). La phrase « représentez –20 en complément à 2 » n’a pas de sens si l’on ne précise pas le nombre de bits de la représentation. Cela peut tout aussi bien être 101100 sur 6 bits que 11101100 sur 8 bits ou 1111111111101100 sur 16 bits (voir section 2.3).
Caractéristiques Les nombres positifs se représentent tels quels, c’est-à-dire par une écriture binaire sur n bits : de 0 = 000…00 à 2n – 1 – 1 = 011…11. Les entiers négatifs correspondent au complément à 2 de ces nombres : de –2n – 1 = 100…00 à –
Architecture de l’ordinateur 6
1 = 111…11. Il n’y a plus maintenant qu’une seule représentation de 0 ; d’ailleurs, si l’on essaie de prendre l’opposé de 0 = 000…00 en faisant son complément à 2, on retombe sur la même écriture binaire. Notez que l’on peut représenter plus de nombres strictement négatifs que de nombres strictement positifs, en l’occurrence un de plus. C’est parfaitement normal : avec 2n possibilités sur n bits, si l’on enlève le zéro, il reste un nombre impair d’écritures possibles ; on ne peut donc pas avoir autant de nombres positifs que de nombres négatifs. On aurait pu décider, pour le nombre binaire 100…00, de représenter 2n – 1 au lieu de –2n – 1, mais la convention choisie permet de considérer le bit de poids fort d’un nombre comme un équivalent de bit de signe : tous les nombres négatifs (de –2n – 1 à –1) ont ce bit de poids fort à 1 et tous les nombres positifs (de 0 à 2n – 1 – 1) ont ce bit à 0. Cela permet de déterminer facilement le signe d’un nombre en représentation signée.
Arithmétique en complément à 2 Le grand intérêt du complément à 2 est de simplifier les additions. Ainsi, on n’a plus à se préoccuper du signe des nombres avant d’effectuer l’opération. Voici un exemple. Pour effectuer l’addition de 118 et de –36, il suffit d’exprimer chacun des nombres en complément à 2 et d’effectuer l’addition bit à bit en laissant tomber une éventuelle retenue :
1 1 1 1 1 118 : 011101 1 0
+(−36) : 1 1 0 1 1 1 0 0
1 =82
0 1 0 1 0 0 1 0
Soustraire un nombre revient à additionner son opposé, c’est-à-dire son complément à 2. En revanche, la multiplication est plus délicate. La méthode la plus simple est de prendre la valeur absolue des deux nombres, de les multiplier par l’algorithme standard et de prendre l’opposé du résultat si les deux nombres étaient de signes contraires. Il existe un autre algorithme, appelé « recodage de Booth », qui profite des spécificités de la multiplication binaire pour accélérer le calcul au prix d’une circuiterie plus compliquée. Pour diviser, il faut passer par la division des valeurs absolues et repositionner les signes du quotient et du reste si nécessaire.
Note
La représentation en complément à 2 revient à lire un nombre binaire xn–1…x0 de la façon suivante :
X = xn–22n–2 +…+2×1 +x0 −xn–12n–1 = ∑ n–2xi2i
−xn–12n–1 i=0 Propriétés du complément à 2 On a la relation suivante, sur n bits : X + C2(X) = 2n complément à 2 d’un nombre en effectuant l’opération l’on prend deux fois le complément à 2 d’un nombre, calculer la valeur décimale d’un nombre binaire négatif, (d’où son nom). Cela permet de calculer facilement Con 2(X) retombe = 2n – X. sur On il suffit de prendre a une autre propriété intéressante ce nombre : son complément C2(C2(X)) à = 2 X. et Ainsi, l’on le : si pour a son opposé : C2(11001100) = 00110100 = 52 donc 11001100 = –52. Par ailleurs, on a une relation intéressante entre les lectures signée et non signée d’un nombre binaire négatif sur n bits. Soit VS(X) la valeur d’un nombre binaire, lu comme un entier négatif dans la représentation en complément à 2 ; soit VB(X) la valeur de ce même nombre binaire, mais lu comme un entier positif (c’est-à- dire en effectuant la simple somme des puissances de 2). On a alors l’égalité VB(X) – VS(X) = 2n. Par exemple, VB(10101010) = 170, VS(10101010) = –86 et l’on a bien 170 – (–86) = 256 = 28.
2.3 Extension de signe
Parfois, on a besoin d’étendre un nombre de n bits sur davantage de bits. Par exemple, pour additionner un nombre écrit sur 1 octet et un nombre écrit sur 2 octets, il faut étendre le premier nombre sur 16 bits avant d’effectuer l’addition. Un autre exemple est le chargement d’une case mémoire de 1 octet dans un registre (une zone de stockage à l’intérieur du microprocesseur) de 4 octets (32 bits). Comment faire pour que le nombre étendu représente bien la même valeur ? On doit effectuer ce que l’on appelle une extension de signe.
Nombres non signés Si le nombre n’est pas signé, il suffit d’ajouter des zéros en tête du nombre à étendre : par exemple 11010011 devient 0000000011010011 sur 2 octets.
Représentation des nombres 7
Architecture Représentation « signe et valeur absolue » Si l’on travaille avec des nombres signés représentés avec la convention « signe et valeur absolue », il suffit de reporter le bit de signe dans le nouveau bit de poids fort et de remplir les autres nouveaux bits par des zéros. 01101000 devient 0000000001101000 et 11111011 devient 1000000001111011 lorsqu’on les étend sur 2 octets.
Représentation en complément à 2 Pour les nombres signés standard, la règle est de recopier le bit de signe du nombre dans tous les nouveaux bits. En effet, si le nombre est positif, son bit de signe est nul et on ajoute des zéros en tête : 00100110 devient 0000000000100110 ; si le nombre est négatif, le bit de signe (c’est-à-dire le bit de poids fort) est égal à un et il faut le reporter : 10001111 devient 1111111110001111. Dans tous les cas, lorsque l’on calcule la valeur des nombres en complément à 2, on obtient bien le même résultat.
2.4 Débordement
Lorsqu’ils sont stockés en mémoire dans un ordinateur, les nombres binaires ont une taille limitée : souvent 1, 2 ou 4 octets. Parfois, le résultat d’une opération arithmétique, par exemple d’une addition, ne peut pas tenir dans la taille imposée. On dit alors qu’il y a débordement (overflow). Comment le détecter ? Cela dépend bien évidemment de la représentation des nombres.
Nombres non signés Sur n bits, on représente les nombres de 0 à 2n – 1. Si la somme de deux nombres dépasse cette valeur, il y a débordement. On peut facilement s’en apercevoir car cela est équivalent à la présence d’une retenue finale lors de l’addition. Voici un exemple sur 8 bits :
+8 de l’ordinateur 1 1 1 156 : 1 0011 1 0 0 168 : 1 0 1 0 1 0 0 0 1 68?
0 1 0 0 0 1 0 0
Le résultat de 156 + 168 dépasse 255 et ne peut donc pas s’exprimer sur 8 bits ; cela est matérialisé par la retenue finale. De la même façon, une soustraction peut amener à un résultat négatif, non représentable avec des nombres non signés. Là encore, une retenue finale indique un débordement.
−
27 : 0 0 0 1 1 0 1 1 100 : 10 11 1 0 10 1 0 0 183? 1 1 0 1 1 0 1 1 1
Dans les deux cas, le résultat obtenu n’est pas le résultat correct : il y a débordement. Il faut pouvoir le détecter pour, par exemple, arrêter le calcul.
Nombre signés en complément à 2 À cause de la présence des nombres négatifs, une opération peut générer une retenue finale sans qu’il y ait débordement. Ainsi, l’opération –60 + (–61) donne le résultat attendu :
+
1 −60 : 11 0 0 0 1 0 0
(−61) : 1 1 0 0 0 0 1 1 1 =−121
1 0 0 0 0 1 1 1
Il y a bien retenue finale mais le résultat exprimé sur 8 bits est correct. Inversement, l’absence de retenue finale ne garantit pas une opération correcte :
1 1 1 77 : 01 0 011 0 1
68 : 0 1 0 0 0 1 0 0
−111? 1 0 0 1 0 0 0 1
Il faut en fait comparer les signes des nombres additionnés et le signe du résultat. Les signes des nombres additionnés correspondant aux bits de poids fort, leur addition génère la retenue finale ; le signe du résultat est, quant à lui, généré par la dernière retenue (celle qui s’additionne aux bits de poids fort justement). La règle est simple :
• Si les deux retenues générées par l’addition des deux derniers bits de chaque nombre (ceux de poids fort) sont identiques (11 ou 00), il n’y a pas débordement.
• Si les deux retenues sont différentes (01 ou 10), il y a débordement. Dans le premier exemple, les deux dernières retenues valent 1 ; il n’y a donc pas débordement (le résultat exprimé sur 8 bits est correct). Dans le second, elles valent 0 et 1, ce qui est la preuve d’un débordement (effectivement, –111 n’est pas le résultat correct de la somme de 77 et 68).
3. NOMBRES RÉELS
Dans de nombreuses applications, on ne peut se contenter de calculer avec les nombres entiers, soit parce que l’on a besoin de nombres sortant de l’intervalle de représentation, soit parce que l’on utilise des nombres décimaux. Comme un ordinateur ne sait manipuler que des bits, il faut définir une représentation des nombres décimaux adaptée aux calculs. L’espace de stockage d’un nombre (son nombre de bits) étant limité, tous les nombres réels possibles ne sont pas représentables et il y a une limite à la précision des calculs. L’idée principale derrière la représentation des nombres décimaux est de définir l’emplacement d’une virgule séparant la partie entière et la partie décimale et de considérer que les bits à droite de cette virgule correspondent aux puissances négatives de 2 (de même qu’en décimal, les chiffres à droite de la virgule sont des dixièmes, des centièmes…).
3.1 Représentation en virgule fixe
Historiquement la première, la représentation en virgule fixe est facile à comprendre. Au lieu de faire commencer les puissances de 2 à 20 au bit de poids faible, comme pour les nombres entiers, on fixe un bit, quelque part dans l’écriture du nombre, à droite duquel se place la virgule. Les bits à gauche de la virgule correspondent alors aux puissances de 2 positives et les bits à droite de la virgule correspondent aux puissances de 2 négatives. Ainsi, sur n bits, on peut par exemple définir une virgule après les p bits de poids faible, ce qui donne, pour le nombre xn -p–1xn–p–2 … x1x0x–1 … x–p, la valeur :
X = xn–p–12n–p–1 +xn–p–22n–p–2 +…+x12+x0 +x–12–1 +…+x–p2–p = n–p–1∑
xi 2i i=–p
Le problème évident est que la plage des nombres représentables est assez limitée. On est entre 2–p et 2n – p – 2–p, avec peu de précision après la virgule. Pour y remédier, on a développé une autre représentation, appelée « représentation en virgule flottante ».
3.2 Représentation en virgule flottante IEEE 754
Il s’agit maintenant d’imiter ce que l’on appelle la notation scientifique. On va écrire le nombre voulu sous la forme ±1,M χ 2E, où 1,M s’appelle la mantisse du nombre et E l’exposant. Comme la mantisse commence toujours par une partie entière égale à 1, on ne l’écrit pas et on n’exprime que la partie fractionnaire, M, appelée « pseudo-mantisse ». Puisqu’il y a plusieurs manières d’écrire les différents champs, une normalisation a été adoptée qui définit deux principaux types de nombres en virgule flottante : la simple précision sur 32 bits et la double précision sur 64 bits. Les nombres en simple précision possèdent une pseudo-mantisse sur 23 bits (correspondant aux puissances négatives de 2, de 2–1 à 2–23), un exposant sur 8 bits et un bit de signe. Les nombres en double précision ont une pseudo-mantisse sur 52 bits, un exposant sur 11 bits et un bit de signe.
1 bit 8 (ou 11) bits 23 (ou 52) bits
signe exposant pseudo-mantisse
Représentation des nombres 9
Architecture de l’ordinateur 10 Lire et écrire un nombre en virgule flottante La pseudo-mantisse est la partie fractionnaire du nombre et il suffit d’additionner les puissances négatives de 2 pour calculer le résultat. Afin que l’on puisse exprimer les exposants négatifs, la valeur binaire dans le champ exposant est la valeur réelle décalée par excès d’un biais de 127 (1 023 pour les nombres en double précision). Il faut donc retrancher ce biais de la valeur indiquée pour obtenir l’exposant réel. Le bit de poids fort est un bit de signe, par convention à 1 quand le nombre est négatif. Voici trois exemples :
500=1,953125×28 =(1+2−1 +2−2 +2−3 +2−4 +2−6)×28
Cela donne 0 10000111 11110100000000000000000. On a un bit de signe égal à 0, un exposant égal à 8 + 127 et les premiers bits de la pseudo-mantisse qui exprime 0,953125.
−3,5=−1,75×21 =−(1+2−1 +2−2)×21
Cela donne 1 10000000 11000000000000000000000. On a un bit de signe égal à 1 car le nombre est négatif, un exposant égal à 1 + 127 et les premiers bits de la pseudo-mantisse qui exprime 0,75.
0,40625=1,625×2−2 =(1+2−1 +2−3)×2−2
Cela donne 0 01111101 10100000000000000000000. On a un bit de signe égal à 0, un exposant égal à –2 + 127 et les premiers bits de la pseudo-mantisse qui exprime 0,625.
Remarque
Par analogie avec les nombres entiers, on désigne souvent les « nombres représentés en virgule flottante » comme des « nombres flottants ».
Valeurs spéciales La plage de représentation est à peu près de 10–38 à 1038 en simple précision et de 10–308 à 10308 en double précision. Certaines configurations de bits signifient des valeurs spéciales :
Tableau 1.1
Exposant Pseudo-mantisse Valeur
0 0 ±0
0 différent de 0 nombre dénormalisé
entre 1 et 254 quelconque nombre normalisé standard
255 0 ±infini
255 différent de 0 NaN (Not a Number)
Format des nombres flottants dans la norme IEEE 754
Les valeurs de plus ou moins l’infini peuvent apparaître dans les calculs, et les règles arithmétiques correspondantes sont précisées dans la norme. Les nombres dénormalisés permettent d’exprimer un nombre encore plus petit que 10–38 en écrivant la mantisse 0,M plutôt que 1,M. Enfin les NaN signalent une erreur (division par zéro par exemple).
Arrondis En raison du nombre limité de bits de la représentation, les calculs en virgule flottante ne peuvent pas atteindre une précision infinie. Tous les nombres réels ne sont pas représentables et l’un des enjeux de la normalisation a été que les calculs soient reproductibles d’une machine à une autre. Or, en raison de la précision limitée, ceux-ci ne peuvent pas être systématiquement exacts. On a donc défini des mécanismes standard d’arrondi pour être sûr de toujours parvenir au même résultat. Ces mécanismes d’arrondi sont au nombre de quatre :
• arrondi à la valeur la plus proche (mécanisme par défaut) ;
• arrondi vers zéro ;
• arrondi vers plus l’infini ;
• arrondi vers moins l’infini.
Arithmétique en virgule flottante Les calculs sont ici beaucoup plus compliqués qu’en arithmétique entière. Du fait que les bits des nombres ont des significations différentes suivant leur place, il faut traiter séparément les différents champs. Voici à titre d’exemple les algorithmes pour la multiplication et l’addition.
Multiplication de deux nombres flottants 1. Multiplier les mantisses. 2. Additionner les exposants en soustrayant une fois le biais pour retomber sur un exposant biaisé. 3. Si nécessaire, renormaliser la mantisse sous la forme 1,M et décaler l’exposant. 4. Arrondir la mantisse (car la multiplication a généré plus de bits significatifs). 5. Ajuster le signe du résultat en fonction des signes des nombres à multiplier. Par exemple, multiplions 1,75 par 2,5. 1,75 = 1,75 χ 20, qui se représente ainsi : 0 01111111 11000000000000000000000. 2,5 = 1,25 χ 21, qui se représente ainsi : 0 10000000 01000000000000000000000. La multiplication des mantisses (il faut multiplier 1,112 par 1,012, et pas uniquement les pseudo-mantisses) donne 10,00112 et l’addition des exposants aboutit à un exposant biaisé de 128. On décale la mantisse vers la droite (en ajoutant 1 à l’exposant) pour renormaliser le nombre en 1,000112 χ 22, qui s’écrit alors 0 10000001 00011000000000000000000. Cela donne bien (1 + 2–4 + 2–5) χ 22 = 4,375. La division flottante s’effectue de façon semblable : on divise les mantisses et on soustrait les exposants.
Addition de deux nombres flottants L’addition de deux nombres flottants ne peut se faire que si les exposants sont égaux. L’algorithme est le suivant : 1. Décaler la mantisse d’un des nombres pour aligner les exposants. 2. Additionner les mantisses (attention au signe). 3. Si nécessaire, renormaliser la mantisse sous la forme 1, M et décaler l’exposant. 4. Arrondir la mantisse (car, à cause du décalage initial, la mantisse peut être sur plus de bits que la taille
autorisée). Par exemple, additionnons 1,75 et 2,5. Comme précédemment, 1,75 se représente ainsi : 1,112 χ 20, et 2,5 de la façon suivante : 1,012 χ 21. On décale le premier nombre en l’écrivant 0,1112 χ 21 pour aligner les exposants. L’addition des deux mantisses donne 1,012 + 0,1112 = 10,0012. On normalise en décalant vers la droite et en ajoutant 1 à l’exposant, ce qui amène à un résultat égal à 1,00012 χ 22, soit 4,25. On réalise la soustraction de façon identique, en établissant la différence les mantisses.
4. CODAGE DES CARACTÈRES
Les caractères, comme les nombres, doivent être représentés en vue d’être exploités par les ordinateurs. Comme on ne peut mettre que des bits dans les cases mémoire, on a associé un code numérique à chaque caractère. Évidemment, pour pouvoir échanger des informations entre ordinateurs, il faut que cette correspondance soit la même sur toutes les machines.
4.1 Code ASCII
La première tentative de standardisation date de la fin des années 60, avec la création du code ASCII (American Standard Code for Information Interchange). Cette table définit les équivalents numériques des caractères majuscules et minuscules de l’alphabet latin, des chiffres et de certains signes de ponctuation. Elle donne également le code de nombreux caractères de contrôle, utilisés à l’époque dans l’échange de données entre terminaux et ordinateurs ; non imprimables, ils servaient à régler les paramètres de la communication. Compte tenu du nombre de caractères à représenter, un code à 7 bits est nécessaire, permettant cent vingt- huit combinaisons différentes (voir tableau 1.2).
Représentation des nombres 11
Tableau 1.2
0 1 2 3 4 5 6 7
0 NUL DLE SP 0 @ P ` p
1 SOH DC1 ! 1 A Q a q
2 STX DC2  » 2 B R b r
3 ETX DC3 # 3 C S c s
4 EOT DC4 $ 4 D T d t
5 ENQ NAK % 5 E U e u
6 ACK SYN & 6 F V f v
7 BEL ETB ‘ 7 G W g w
8 BS CAN ( 8 H X h x
9 HT EM ) 9 I Y i y
A LF SUB * : J Z j z
B VT ESC + ; K [ k {
C FF FS , < L \ l | D CR GS – = M ] m } E SO RS . > N ^ n ~
F SI US / ? O _ o DEL
Table des caractères ASCII
Chaque caractère est codé sur 1 octet par deux symboles hexadécimaux. Le numéro de la colonne donne le symbole hexadécimal de poids fort et le numéro de ligne le symbole de poids faible. Ainsi, le caractère 4 a pour code numérique 3416, L le code 4C16 et m le code 6d16. Ce code est adapté à l’écriture anglo-saxonne : ni lettres accentuées ni lettres spéciales hors des vingt-six classiques. L’unité de stockage étant l’octet, soit 8 bits, les fabricants d’ordinateurs ont décidé d’utiliser le bit supplémentaire pour définir cent vingt-huit autres caractères, comme les lettres accentuées, les lettres d’autres alphabets ou même des caractères graphiques à afficher. Évidemment, chaque fabricant a construit sa propre table étendue et l’on a perdu la compatibilité entre ordinateurs, d’où les problèmes de transfert de fichiers au format texte contenant des caractères accentués. Cela a donné lieu à autre tentative de normalisation qui a aboutit à la norme ISO 8859 codifiant plusieurs alphabets d’Europe occidentale. La norme définit une quinzaine de tables différentes, chacune codant ses caractères sur 1 octet. Mais là encore, pour des raisons historiques de compatibilité, on emploie d’autres tables de correspondance, ce qui rend les transferts d’informations parfois problématiques.
4.2 Code Unicode
À la fin des années 80 démarre un projet visant à codifier de manière unique tous les caractères de toutes les langues écrites, en tenant compte du sens de lecture des langues (de gauche à droite ou l’inverse), des ligatures, etc. Ce travail aboutit au codage Unicode dans lequel chaque symbole est défini sur 2 octets. De portée mondiale, ce codage n’est pas encore universellement appliqué car de nombreux systèmes et applications ne savent pas encore traiter ces caractères étendus. Le langage de programmation C, ancien mais très utilisé, code ses caractères sur 1 octet alors que Java les code sur 2 octets et est donc compatible avec Unicode. Notez que dans un souci d’harmonisation, les deux cent cinquante-cinq premiers caractères Unicode reproduisent les deux cent cinquante-cinq caractères du codage ISO 8859–1 de l’alphabet latin.
Architecture de l’ordinateur 12
5. TYPES ET PROGRAMMATION
Chaque langage de programmation décrit des types de variables et une taille de stockage associée. Lorsque l’on programme, il est important de garder à l’esprit les tailles des variables utilisées et les valeurs minimale et maximale qu’elles peuvent prendre, afin d’éviter de leur attribuer une valeur numérique trop importante suite à un calcul ou une entrée extérieure. Dans le meilleur des cas, si cette erreur est prévue par le langage et que des sécurités sont installées par le compilateur, le programme s’arrête de lui-même en signalant une erreur. Mais le plus souvent, il continue comme si de rien n’était, en tronquant la valeur numérique fautive pour la coder dans la variable ; la valeur est alors faussée, entraînant des calculs incorrects.
5.1 Types usuels et tailles
Voici un résumé des principaux types de variables entières en C et Java avec leurs valeurs extrêmes les plus classiques.
Tableau 1.3
Type C Type Java Taille Valeur min. Valeur max.
char byte 1 octet –128 127 unsigned char n’existe pas 1 octet 0 255
short short 2 octets –32 768 32 767 unsigned short char 2 octets 0 65 535
long int 4 octets env. –2 milliards env. 2 milliards unsigned long n’existe pas 4 octets 0 env. 4 milliards
n’existe pas long 8 octets env. –1019 env. 1019
Types de variables entières en C et Java
La norme du langage C n’impose pas ces valeurs et laisse une certaine latitude lors de l’implémentation. Un compilateur peut décider que, par défaut, le type char peut être non signé ou bien que le type long peut être codé sur 64 bits. Nous n’avons pas inclus le type C int dans le tableau. Là encore, il n’est pas précisé dans la norme si les variables de ce type doivent être stockées sur 2 ou 4 octets ; cela dépend du système d’exploitation et du compilateur utilisé. Sur les ordinateurs actuels, le comportement par défaut est de les stocker sur 4 octets mais cela peut amener à des erreurs d’exécution avec d’anciens programmes susceptibles d’être recompilés.
5.2 Programmation
Chaque variable est typée et cette information (le type) est uniquement utilisée par le compilateur. Lorsqu’une valeur numérique est mise en mémoire, il n’y a aucune information sur son type. En d’autres termes, c’est le contexte d’exécution défini par le compilateur qui indique au processeur comment traiter la variable. Par conséquent, si le programmeur demande au compilateur de faire n’importe quoi, celui-ci indiquera au processeur de faire n’importe quoi ! Bien sûr, les langages de programmation sont plus ou moins permissifs et laissent le programmeur faire plus ou moins de bêtises. Mais il ne faut jamais supposer que le processeur connaît le type des variables sur lequel il travaille. C’est au programmeur de faire attention à ce sujet (taille limite, affichage…). Considérez le programme C suivant :
Listing 1.1
int main () {
float ff = 1.0; long ll = 999999999;
printf(  » Valeur de ff : %ld \n », ff); printf(  » Valeur de ll : %e \n », ll); }
On affiche une valeur, mais laquelle ?
Représentation des nombres 13
Architecture de l’ordinateur 14 Voici l’affichage après exécution : Valeur de ff : 1072693248 Valeur de ll : 1.418200e-21
Remarque
Les valeurs affichées suite à l’exécution du code précédent dépendent de la machine sur laquelle tourne le programme et de la façon dont les nombres sont stockés en mémoire. Mais dans tous les cas, elles seront fantaisistes. Reportez-vous au chapitre 5 pour plus d’explications.
Que se passe-t-il ? Simplement une petite erreur lors de l’affichage… Dans le premier printf, on demande bien d’afficher la valeur de ff mais en indiquant au compilateur, à l’aide du format %ld, qu’il s’agit d’un entier long. Celui-ci va donc demander au processeur d’interpréter les 32 bits du nombre comme un entier long signé. De même, le deuxième printf affiche un entier long signé ll en l’interprétant comme un nombre flottant à afficher en notation scientifique ; les 32 bits de ll n’ont alors plus la même signification puisque le processeur va les décrypter comme signe, exposant et pseudo-mantisse… alors qu’ils représentent simplement les puissances de 2 ! Ce genre de problème est typique du langage C, qui impose peu de règles au niveau de la vérification des types, et plus rare en Java, sans toutefois être exclu. Voici d’ailleurs un exemple. L’opérateur d’addition + ne travaille qu’avec des entiers au moins de type int ; cela explique que le programme suivant ne compile pas.
Listing 1.2
import java.util.*; public class Pgm_Java {
public static void main (String args[]) {
short i = 32767; i = i+1; System.out.println(« Valeur de i :  » + i); } }
On n’additionne pas des entiers courts
Lors de l’addition, la valeur de la variable i est promue au type int et le résultat de l’addition, étant du même type, ne peut se mettre dans la variable i de type short. En revanche, l’opérateur d’incrémentation ++ n’a pas de contrainte de type. On peut donc écrire le même programme en remplaçant une ligne :
Listing 1.3
import java.util.*; public class Pgm_Java {
public static void main (String args[]) {
short i = 32767; i++; System.out.println(« Valeur de i :  » + i); } }
Mais on peut les incrémenter
Le résultat (–32 768) est alors inattendu mais pas surprenant car un short est un entier signé sur 16 bits.
RÉSUMÉ
Les nombres sont au cœur de l’ordinateur. Il est facile de représenter les entiers positifs à l’aide des puissances de 2 et les nombres négatifs à l’aide de la convention de représentation du complément à 2. En écrivant les nombres décimaux sous la forme « mantisse et exposant », on peut également travailler avec un sous- ensemble des nombres réels. Les bits peuvent aussi servir à représenter des caractères même s’il n’y a pas vraiment de correspondance universelle valable sur toutes les machines et tous les systèmes. Dans tous les cas, il n’y a que des bits en mémoire et la manière de les lire n’est en aucun cas indiqué explicitement. C’est toujours le contexte, décidé par le programmeur, par le compilateur ou le processeur qui permet un calcul correct… ou complètement faux si ledit contexte n’est pas le bon.
Problèmes et exercices
Les exercices suivants permettent de jongler avec les différentes bases, décimale, binaire ou
hexadécimale. Vous allez compter en binaire et travailler avec des nombres négatifs et même
des décimaux… pour vous apercevoir qu’un ordinateur ne calcule jamais parfaitement, qu’il
peut déborder ou arrondir. Pour finir, vous verrez que c’est au programmeur de penser à la
taille des valeurs qu’il manipule pour trouver le type de stockage adapté.
Exercice 1 : Écrire dans différentes bases
Exprimez le nombre décimal 100 dans toutes les bases de 2 à 9 et en base 16.
On effectue les divisions successives de 100 par 2 (voir figure 1.3) :
Figure 1.3
100 en bases 2 et 3.
Cela donne 11001002 = 10010. Le travail s’effectue de la même manière en base 3 : 102013 = 10010. On obtient de façon identique les résultats suivants : 10010 = 12104 = 4005 = 2446 = 2027 = 1448 = 1219 = 6416. On peut obtenir certains résultats directement à partir d’autres. Ainsi, en regroupant les bits deux à deux, 01 10 01 00, on obtient le résultat en base 4 ; en les regroupant trois à trois, on obtient la base 8, et quatre à quatre (en n’oubliant pas le zéro en tête), on obtient l’hexadécimal. De même, on trouve la base 9 à partir de la base 3 en regroupant les symboles ternaires deux à deux (car 9 = 32) : 01 02 01 donne bien 1219.
Exercice 2 : Représenter des entiers
Exprimez les nombres décimaux 94, 141, 163 et 197 en base 2, 8 et 16. Donnez sur 8 bits les représenta- tions « signe et valeur absolue » et complément à 2 des nombres décimaux 45, 73, 84, –99, –102 et –118.
Toujours par la méthode des divisions et des regroupements de bits, on obtient :
9410 =10111102 =1368 = 5e16 14110 =100011012 = 2158 =8d16 16310 =101000112 = 2438 =a316 19710 =110001012 =3058 =c516
N’oubliez pas d’utiliser les symboles a à f pour représenter les valeurs 10 à 15.
Représentation des nombres 15
signe et v.a. compl. à 2 45 00101101 00101101 73 01001001 01001001 84 01010100 01010100 −99 11100011 10011101 −102 11100110 10011010 −118 11110110 10001010
Attention
Il ne faut pas confondre la représentation en complément à 2 et l’opération qui consiste à prendre le complément à 2, c’est-à-dire à inverser tous les bits du nombre et à ajouter 1. La représentation en complément à 2 consiste à écrire les nombres négatifs (et uniquement ceux-là) en prenant le complément à 2 de leur valeur absolue ; quelle que soit la représentation, les nombres positifs sont toujours écrits de la même façon.
Exercice 3 : Calculer en binaire
1) Effectuez la soustraction 122 – 43 dans la représentation en complément à 2 en n’utilisant que l’addition. 2) Multipliez les nombres binaires 10111 et 1011 ; vérifiez le résultat en décimal.
1) 122 – 43 = 122 + (–43). Il faut donc calculer le complément à 2 de 43. La première question à se poser est de savoir de combien de bits on a besoin pour exprimer –43 et 122. 7 bits permettent bien d’écrire les nombres de 0 à 127 mais, en complément à 2, c’est l’intervalle de –64 à 63 qui est représenté sur 7 bits. Il en faut donc au moins 8.
122 : 01 11 11 1 1 0 1 0
−43 : 1 1 0 1 0 1 0 1
=79 : 0 1 0 0 1 1 1 1
On laisse bien sûr tomber la retenue finale. 2) 101112 = 2310 et 10112 = 1110.
1 0 1 1 1
χ 1 0 1 1 1 1 11 01 11 1 1
+ 1 0 1 1 1 •
+ 1 0 1 1 1 • • •
1 1 1 1 1 1 0 1
Le résultat correct est bien 25310.
Exercice 4 : Débordement
On cherche à déterminer les cas de débordement lors d’une addition signée. On dit qu’il y a débordement lorsque le résultat obtenu (limité à la taille autorisée) n’est pas correct. 1) Effectuez en binaire sur 8 bits, en représentation en complément à 2, les opérations suivantes : 100 + 100, (–1) + (–2), (–1) + 16, (–100) + (–100). Dans quel(s) cas y a-t-il débordement ? 2) On additionne 8 bits A = a7 …a0 avec les 8 bits B = b7 …b0, en obtenant un résultat S = s7 …s0 et une retenue r. Si A et B sont de signes contraires, peut-il y avoir débordement ? Si A et B sont de même signe (distinguez), quelles valeurs peuvent prendre s7 et r ? Dans quel(s) cas y a-t-il débordement ? On
Architecture de l’ordinateur 16
s’intéresse maintenant aux deux retenues de poids fort : r et r6 (qui provient de l’addition de a6, b6 et r5, et s’ajoute débordement à aen 7 et fonction b7 pour donner de r6 et r.
s7 et r). En reprenant la question précédente, donnez l’expression du
1) Voici les calculs :
1 1 1 100 : 011 0 01 0 0
+ 100 : 0 1 1 0 0 1 0 0
: 1 1 0 0 1 0 0 0 →−56
1 1 1 1 1 1 −1 : 1111111 1
+ −2 : 1 1 1 1 1 1 1 0
: 1 1 1 1 1 1 0 1 →−3
1 1 1 −1 : 1111 1 1 1 1
+ 16 : 0 0 0 1 0 0 0 0
: 0 0 0 0 1 1 1 1 →15
1 1 1 −100 : 1 0 0111 0 0
+ −100 : 1 0 0 1 1 1 0 0
: 0 0 1 1 1 0 0 0 → 56
Il y a débordement dans le premier et le dernier cas. On pourrait croire que le résultat de 100 + 100, c’est-à-dire 110010002, est correct car il se lit bien 27 + 26 + 23 = 200. Mais il ne faut pas oublier qu’on est en représentation en complément à 2 et qu’on ne peut donc pas choisir de le lire de cette façon-là. Il faut lire le résultat comme un nombre négatif. 2) Il ne peut pas y avoir de débordement lorsque l’on additionne deux nombres de signes contraires car la valeur absolue du résultat est toujours inférieure aux valeurs absolues des deux opérandes ; elle est donc toujours représentable. Si A et B sont positifs, correct) ou 1 (le résultat a7 et est b7 valent négatif, toujours 1 débordement). et s7 peut On 0. r vaut il y a débordement). donc toujours 0 Si et A set 7 peut B valoir 1 (le a donc débordement valoir 0 (le sont négatifs, résultat est donc négatif, c’est correct) ou 0 résultat est donc (le a7 résultat et b7 valent est si les deux opérandes sont de mêmes signes et complémentaires.
positif, c’est 1. r vaut donc positif, il y a si s7 et r sont
Si les deux opérandes sont de signes contraires, alors égaux et il n’y a jamais débordement. Si l’un des deux bits de poids fort vaut les deux opérandes sont positifs, le 1 et l’autre bit de poids 0. fort r6 des et r deux sont
opérandes vaut 0 (donc r vaut 0) et le signe du résultat est identique à r6. Autrement dit, il y a débordement quand signe du r6 vaut résultat 1 et r vaut a la résultat, incorrect, positif). 0. Si les deux opérandes même valeur Au final, on que a bien r6. sont négatifs, le bit de poids fort vaut 1 (donc r vaut 1) et le
Il y débordement a donc débordement quand r vaut 1 quand r et r6 sont complémentaires.
et r6 vaut 0 (donnant un
Exercice 5 : Travailler avec des réels
On considère une représentation simplifiée des réels en virgule flottante. Un nombre réel X est représenté par 10 bits s eeee mmmmm où X = (-1)s χ 1,m χ 2e-7 avec un exposant sur 4 bits (0 < e ≤ 15, un exposant égal à zéro désigne le nombre zéro quelle que soit la mantisse) et une pseudo-mantisse sur 5 bits (représentant les puissances négatives de 2). 1) Quels sont le plus grand nombre et le plus petit nombre strictement positifs représentables ? 2) Comment se représente le nombre 1 ? La précision ε d’une représentation est l’écart entre 1 et le nombre représentable suivant. Combien vaut ε pour cette représentation ? 3) Peut-on représenter 7,2 et 57,6 ? Quels sont les nombres qui encadrent 7,2 et 57,6 dans cette représentation ? 4) Que donne en décimal la multiplication de 7,25 et 28,5 ? Écrivez 7,25 et 28,5 dans la représentation proposée et effectuez la multiplication. Quels sont les deux arrondis possibles pour le résultat et leur valeur décimale ?
1) Le plus grand nombre représentable est 0 1111 11111 = (1 + 2–1 + 2–2 + 2–3 + 2–4 + 2–5) χ 28 = 504. Le plus petit nombre strictement positif est 0 0001 00000 = 1 χ 2–6 = 0,015625. 2) 1 = 1 χ 20, donc 1 se représente 0 0111 00000. Le nombre représentable suivant est 0 0111 00001, qui vaut (1 + 2–5) χ 20, donc ε vaut 2–5.
Représentation des nombres 17
Architecture de l’ordinateur 18 3) 7,2 = 1,8 χ 22. Mais on ne peut pas écrire une pseudo-mantisse égale à 0,8. Elle se situe entre 110012 (qui vaut 0,78125) et 110102 (qui vaut 0,8125). Les deux nombres qui encadrent 7,2 dans cette représentation sont donc 1,78125 χ 22 = 7,125 et 1,8125 χ 22 = 7,25. De même, 57,6 = 1,8 χ 25 et on se retrouve dans la même situation, les deux nombres encadrant 57,6 étant alors 1,78125 χ 25 = 57 et 1,8125 χ 25 = 58. Remarquez que l’écart entre deux nombres de la représentation n’est pas constant mais augmente avec la valeur des nombres. 4) 7,25 χ 28.5 = 206,625. On a vu que 7,25 se représente exactement par 0 1001 11010 (1,8125 χ 22) et que 28,5 se représente exactement par 0 1011 11001 (1,78125 χ 24). La multiplication des deux mantisses 1,110102 et 1,110012 donne 11,0011101012 comme résultat, qu’il faut normaliser à 1,10011101012 en ajoutant 1 à l’exposant, qui devient 2 + 4 + 1 = 7. Le problème est que cette mantisse a trop de bits significatifs pour cette représentation et qu’il faut donc l’arrondir. On peut tronquer la mantisse à 1,100112 ou arrondir supérieurement à 1,101002. le premier cas donne 1,100112 χ 27 = 204 et le second 1,101002 χ 27 = 208. On s’aperçoit alors que même si deux nombres sont exactement représentables en virgule flottante, leur produit ne l’est pas forcément, d’où la nécessité d’avoir des règles d’arrondi très précises pour être sûr que les résultats soient reproductibles d’une machine à une autre.
Exercice 6 : Approximation de réels
On considère la suite numérique :
Un+1 =−38Un2 + 94Un − 38 1) Montrez que si U0 = 3 ou si U0 = 1/3, la suite est constante. 2) Programmez le calcul de la suite en C ou en Java et affichez les cent premières itérations. 3) Comment interprétez-vous les résultats ?. 4) Refaites l’exercice avec la suite :
Un+1 =− 49Un2 + 269 Un − 49
1) On calcule simplement U1 et, dans les deux cas, on aboutit à U1 = U0 :
−38 ×32 + 94×3− 38 =3 et −38 × 13⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2
+ 94× 13⎛ ⎝ ⎜ ⎞ ⎠ ⎟ − 38 = 13
La suite est donc constante. 2) Voici le code affichant les cent premières itérations en Java :
Listing 1.4
import java.util.*; public class test_flottant {
public static void Itere(double u0) {
double u = u0; int n; for (n = 0; n < 100; n++) {
System.out.println(« u » + n +  » =  » + u); u = -3.0*u*u/8.0 + 9.0*u/4.0 – 3.0/8.0; } }
public static void main (String args[]) {
double u;
System.out.println(« Hello World! »); Itere(3.0); System.out.println(« Et maintenant pour 1/3 »); Itere(1.0/3.0); } }
Calcul d’une suite
Le comportement est sans surprise pour U0 = 3, on obtient bien la valeur 3 pour les cent premières itérations. En revanche, lorsque U0 = 1/3, les premières valeurs tournent autour de 1/3 puis s’en éloignent et la valeur calculée finit par converger vers 3. 3) La suite est de la forme Un + 1 = ƒ (Un) et, si elle converge, c’est vers un point fixe de ƒ, c’est-à-dire une solution de l’équation ƒ (X) = X. En résolvant cette équation du second degré, on trouve que ƒ admet deux points fixes, 3 et 1/3. Le point fixe 3 est stable (la dérivée de ƒ en 3 vaut 0), ce qui implique que le calcul est numériquement stable : si on itère ƒ à partir d’une valeur proche de 3, les valeurs successivement obtenues se rapprochent du point fixe 3 ; c’est bien ce que l’on obtient avec le programme précédent. En revanche, le point fixe 1/3 est instable (la dérivée de ƒ en 1/3 vaut 2). En d’autres termes, des itérations commencées à une valeur proche de 1/3 s’en éloignent. Dans le programme précédent, on démarre les itérations avec la valeur 1/3 ; on devrait donc rester sur le point fixe, mais 1/3 n’est pas exactement représentable en puissances négatives de 2. Par conséquent, le programme débute le calcul avec une valeur binaire très proche de 1/3 mais pas parfaitement égale à 1/3. Cela suffit pour faire diverger le calcul vers l’autre point fixe, 3. 4) Il y a toujours deux points fixes, 4 et 1/4. On peut écrire le même programme pour calculer les itérations et, contrairement au premier exemple, que l’on commence avec 4 ou 1/4, toutes les itérations gardent la valeur de départ. Cela s’explique par le fait que maintenant, 1/4 se représente exactement en machine à l’aide des puissances de 2 : le calcul se fait à partir du point fixe et n’a donc aucune raison de diverger.
Exercice 7 : Type des variables
1) On considère l’opération décimale 101 + 99. Expliquez pourquoi un programme peut « donner » deux résultats différents. Quels sont ces résultats et de quoi dépend le fait que le programme donne l’un ou l’autre ? 2) Un nouveau programme est en train de compter le nombre de caractères d’un fichier, qui en réunit environ cinquante mille. Finalement le programme s’arrête et affiche –14 532. Quel bogue avez-vous fait et quel est le nombre de caractères du fichier ? 3) On considère le programme C suivant :
Listing 1.5
#include
main() {
char c; char str[500];
gets(str); /* récupère une chaîne et la met dans str */ c = strlen(str); /* renvoie la longueur de la chaîne */ printf(« longueur : %d\n », c); }
Un caractère, c’est peu
Ce programme affiche-t-il toujours la bonne valeur ? Quelles sont ses limites de fonctionnement ? 4) On considère le programme C suivant :
Listing 1.6
#include
main() {
short i; unsigned short j;
i = -1; j = i; printf(« %d\n », j); }
Signé ou non signé, il faut choisir
Quelle est la valeur affichée ? Quelle serait la valeur affichée si la représentation des nombres était « signe et valeur absolue » ?
Représentation des nombres 19
Architecture de l’ordinateur 20 1) Si tout se passe bien, le résultat est celui attendu, c’est-à-dire 200. Mais si les deux nombres 101 et 99 sont stockés sur un octet signé, le résultat est aussi stocké sur un octet signé, qui ne peut pas représenter 200 et donne comme résultat –56. La représentation binaire du résultat est toujours la même (11001000) mais le programme « lit » cette valeur de deux manières différentes suivant le type de la variable. Le seul type posant problème est l’octet signé (char en C) car il représente les nombres de –128 à 127 ; tous les autres types donnent un résultat correct, entre autres le type unsigned char. En Java, l’addition porte forcément sur des entiers de type int, donc sur 32 bits. Le résultat du calcul proposé est donc toujours correct. Mais s’il avait dépassé 231, le même problème se poserait. 2) En C ou en Java, on utilise une variable de type short qui stocke un nombre signé sur 16 bits, donc une valeur de –32 768 à 32 767. Il est impossible d’afficher une valeur proche de 50 000. Le nombre affiché est donc le complément à 2 du nombre réel, qui est de 65 536 – 14 532 = 51 004 caractères. 3) Une variable de type char en C peut stocker une valeur de –128 à 127. Si la chaîne récupérée fait moins de cent vingt-huit caractères, le programme affiche la bonne valeur ; si elle fait plus, le programme affiche soit une valeur négative (par exemple, si la chaîne a une longueur entre 128 et 255), soit le modulo 256 de la longueur (par exemple, si la chaîne a une longueur entre 256 et 384), voire une vague combinaison des deux si la chaîne est plus grande… Si l’on veut pouvoir mettre une chaîne de longueur inférieure à 255, il faut au minimum utiliser une variable de type unsigned char ; si la chaîne peut être plus longue, un short ou un int est nécessaire. Ici, théoriquement, la chaîne est limitée à cinq cents caractères par la taille du tableau mais gets() ne fait aucune vérification. Si l’utilisateur entre une chaîne plus longue, il y a des problèmes d’écriture mémoire sur une zone non prévue, mais ce n’est pas le sujet de l’exercice. 4) –1 se représente en binaire comme 11…11 (sur 16 bits). Comme j est un unsigned short, on doit le lire comme un nombre positif ; le programme affiche donc 65 535. Si la représentation était « signe et valeur absolue », –1 s’écrirait 100…001 et donc le programme afficherait 32 769.
Chapitre 2
Circuits logiques Le transistor, un interrupteur commandé par une
Circuits logiques
tension, est le composant de base des circuits
1. Fonctions booléennes……………………….. 22
électroniques au cœur de l’ordinateur. À l’aide des
2. Circuits combinatoires……………………… 30 3. Circuits logiques séquentiels…………….. 34 transistors, on construit des circuits logiques
élémentaires, des portes logiques, effectuant des
Problèmes et exercices
1. Construire une fonction logique………. 40 opérations simples. Ces circuits sont analysés grâce
2. Un circuit qui calcule ………………………… 41 à l’algèbre de Boole, outil mathématique puissant
3. Additionneur/soustracteur……………….. 42
qui permet de développer des circuits plus
complexes. Ces mêmes portes logiques sont
4. Multiplicateur…………………………………….. 44 5. Additionneur à retenue anticipée…….. 46 6. Comparateur de nombres………………… 47 utilisées pour réaliser des circuits séquentiels,
7. Bascules équivalentes………………………… 48
faisant intervenir une composante temporelle et
8. Bascule maître-esclave………………………. 49
introduisant ainsi la notion de mémorisation de
valeurs dans les systèmes.
Circuits logiques 21
Architecture de l’ordinateur 22 L’information véhiculée sur les fils internes de l’ordinateur peut prendre deux valeurs, 0 ou 1, correspondant à deux niveaux de tension. Classiquement, le 0 est associé au niveau bas de la tension, proche de 0 V, alors que le 1 est associé au niveau haut, historiquement de 5 V, mais qui a diminué et est maintenant proche de 1 V. Cette information circule à travers les différents circuits de l’ordinateur, travaillant en logique numérique, qui sont modélisés par l’algèbre de Boole. Cette logique numérique est à opposer au calcul analogique, dans lequel l’entrée peut prendre n’importe quelle valeur d’un intervalle continu. Le calcul analogique s’est développé au XIXe siècle et au début du XXe siècle mais a dû céder sa place en raison d’un manque de précision : comme toutes les valeurs sont autorisées, la moindre perturbation change le calcul ; à l’inverse, comme le numérique n’autorise que deux valeurs, une légère fluctuation de tension sur un fil ne modifie rien. Tous les circuits électroniques sont composés de transistors, de l’ordre du milliard dans les processeurs actuels. Comme il est impossible d’étudier leur comportement individuel, ils ont été modélisés et regroupés sous forme de circuits élémentaires que nous allons présenter. Tous les circuits intégrés sont composés, sur une grande échelle, de ces circuits élémentaires. Nous allons distinguer deux types de circuits logiques dont le fonctionnement est différent : les circuits combinatoires et les circuits séquentiels. Les premiers expriment simplement leurs sorties à partir de leurs entrées ; les seconds font dépendre leurs sorties de leurs entrées mais également des sorties précédentes.
1. FONCTIONS BOOLÉENNES
L’analyse des circuits logiques nécessite l’utilisation d’une algèbre spécifique, dite « booléenne », fruit des travaux du mathématicien anglais du XIXe siècle George Boole. Ces travaux ont défini un ensemble d’opérateurs de base, ainsi que leurs propriétés, qui composent une algèbre permettant de concevoir tout type de circuit. La construction de fonctions logiques répondant à des contraintes précises et leur représentation sous forme de circuits électroniques se font à l’aide d’opérateurs élémentaires.
1.1 Définitions
Alors que dans l’algèbre classique les variables et les fonctions peuvent prendre n’importe quelles valeurs, elles sont ici limitées aux valeurs 0 et 1. Une fonction de n variables booléennes va être définie de {0,1}n dans {0,1}. Elle est même entièrement définie par les valeurs qu’elle prend sur les 2n combinaisons possibles de ses variables d’entrée ; comme chaque valeur de la fonction ne peut être que 0 ou 1, il y a 22nfonctions différentes de n variables. On peut alors décrire une fonction (à n variables) donnée en explicitant ses 2n valeurs, par exemple par sa table de vérité. Il s’agit d’un tableau à 2n lignes, qui liste pour chaque combinaison possible des variables d’entrée (une ligne) la valeur prise par la fonction. Voici un exemple :
Tableau 2.1
a b c F(a,b,c)
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
Une table de vérité
L’ordre des lignes n’a pas d’importance mais, par tradition, et aussi pour faciliter la lecture et les comparaisons, on écrit souvent les 2n combinaisons dans l’ordre numérique, comme si elles représentaient un nombre binaire (de 0 à 7 dans le tableau 2.1).
Il peut être fastidieux de donner une table de vérité pour une fonction de plus de trois variables. Il est alors possible d’exprimer la fonction par son expression algébrique à partir de fonctions de base que nous allons présenter plus loin.
Note
La table de vérité décrit intégralement la fonction alors qu’une expression algébrique permet de la calculer. On peut donc comparer directement deux tables de vérité pour décider de l’égalité de deux fonctions. En revanche, comme deux expressions algébriques différentes peuvent représenter les mêmes fonctions, il est moins facile sur la base de ces expressions de décider de l’égalité des fonctions en question.
Un circuit logique a souvent plusieurs sorties. Dans le cas des circuits combinatoires, les sorties, ne dépendant que des entrées, sont donc indépendantes. On caractérise alors le circuit par plusieurs fonctions indépendantes, chacune représentant une sortie. La table de vérité du circuit contient toujours 2n lignes et autant de colonnes de sortie que de fonctions.
1.2 Fonctions et portes logiques élémentaires
Un certain nombre de fonctions booléennes forment les fonctions logiques de base qui permettent d’en construire des plus complexes. Ces fonctions de base peuvent être définies par leur table de vérité ou leur expression algébrique, mais elles ont également été implémentées sous forme de circuits électroniques, appelés « portes logiques » (de l’anglais gate), qui ont des symboles graphiques normalisés. Deux principales normes existent pour représenter ces portes de base : la première, la plus ancienne, affecte une forme géométrique différente à chacune des fonctions. La seconde dessine chacun des circuits sous une forme rectangulaire et les distingue via un symbole placé à l’intérieur du rectangle ; elle permet alors de représenter beaucoup plus de circuits différents. Nous présentons ici, pour chaque porte, les deux symboles, mais nous utiliserons ensuite la nouvelle norme.
Fonction NON (NOT) Cette fonction, la plus simple, a une entrée booléenne et une sortie, qui se définit simplement comme le complémentaire de l’entrée. Son expression algébrique est :
NON(a)=a
Elle se lit « a-barre » ou « non-a ». On dit aussi que la variable a est « complémentée ».
Tableau 2.2
a NON(a) 0 1 1 0
Table de vérité du NON
Les deux représentations graphiques de la porte NON sont données à la figure 2.1. Dans ces deux formes, le symbole important est en fait le petit rond se trouvant à la sortie et qui indique la négation (on le retrouvera dans d’autres symboles).
Fonction OU (OR) Cette fonction de deux variables prend la valeur 1 si l’une ou l’autre de ses entrées (ou les deux) est à 1. Elle vaut 0 si les deux entrées sont à 0. Son expression algébrique est :
OU(a,b)=a+b
Attention, elle se lit bien « a ou b », et non « a plus b » (cela n’a rien à voir avec l’addition). Les deux représentations graphiques de la porte OU sont données à la figure 2.1 et sa table de vérité au tableau 2.3.
Fonction ET (AND) Cette fonction de deux variables prend la valeur 1 si ses entrées sont l’une et l’autre à 1. Elle vaut 0 si au moins une des deux entrées est à 0. Son expression algébrique est :
ET(a,b)=a.b=ab
Elle se lit « a et b ». Le point séparant les deux variables est presque toujours omis.
Circuits logiques 23
Architecture de l’ordinateur 24
Tableau 2.3
a b ET(a,b) = ab OU(a,b) = a + b 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1
Tables de vérité du ET et du OU
Les deux représentations graphiques de la porte ET sont données à la figure 2.1.
Fonction OU-exclusif (XOR) Cette fonction de deux variables prend la valeur 1 si l’une ou l’autre de ses entrées est à 1, mais pas les deux. Elle vaut 0 si les deux entrées sont égales (à 0 ou à 1). Son expression algébrique est :
XOR(a,b)=a ⊕b
Elle se lit « a ou-exclusif b ».
Tableau 2.4
a b XOR(a,b) 0 0 0 0 1 1 1 0 1 1 1 0
Table de vérité du OU-exclusif
Les deux représentations graphiques de la porte OU-exclusif sont données à la figure 2.1.
Fonction NON-OU (NOR) En combinant les quatre fonctions de base précédentes, on peut construire des fonctions composées. En voici deux très utiles. La première est NON-OU. Elle correspond à une fonction OU suivie d’un NON. Elle prend donc la valeur 1 uniquement quand ses deux entrées sont à 0. Son expression algébrique est :
NON −OU(a,b)=a+b
Les deux représentations graphiques de la porte NON-OU sont données à la figure 2.1 et sa table de vérité au tableau 2.5. On retrouve dans ces dessins le symbole de la porte OU suivi du petit rond qui représente la porte NON.
Fonction NON-ET (NAND) La seconde est la fonction NON-ET. Elle correspond à une fonction ET suivie d’un NON. Elle prend donc la valeur 1 lorsqu’au moins une de ses deux entrées est à 0. Son expression algébrique est :
NON −ET(a,b)=a.b=ab
Tableau 2.5
a b NON-ET(a,b) NON-OU(a,b) 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0
Tables de vérité du NON-ET et du NON-OU
Les deux représentations graphiques de la porte NON-ET sont données à la figure 2.1. On a encore ici la première porte ET suivie du petit rond pour le NON.
Symboles des portes logiques.
1.3 Propriétés des fonctions
Les fonctions et les circuits logiques étant souvent définis à partir d’expressions algébriques, il est important de pouvoir simplifier celles-ci afin de réduire la complexité des circuits. À cet effet, un certain nombre de propriétés algébriques peuvent être obtenues à partir des définitions des fonctions. Pour prouver ces égalités, il suffit d’écrire les tables de vérité de chaque expression et de constater qu’elles sont identiques.
Remarque
Dans les expressions algébriques, l’opérateur ET est prioritaire sur l’opérateur OU. On peut donc souvent enlever les parenthèses et écrire ab + c plutôt que (ab) + c.
Tableau 2.6
Commutativité Associativité Distributivité
a+b= b+a ab= ba a ⊕ b= b⊕a
a+(b+c)=(a+b)+c =a+b+c a(bc)=(ab)c =abc a ⊕(b⊕c)=(a ⊕ b)⊕c =a ⊕b⊕c
a+(bc)=(a+b)(a+c) a(b+c)=(ab)+(ac)=ab+ac a(b⊕c)=(ab)⊕(ac)=ab⊕ac
Élément neutre Élément absorbant Idempotence
a+0=a 1.a =a a ⊕0=a
a+a =a aa =a
Complémentaire Lois de De Morgan Divers
a+a =1; aa =0
aa =a ; a+a =a a =a a ⊕a =1 a ⊕1=a
a+1=1 0.a =0
a+ab=a(a+b)=a a+(a b)=a+b; a(a +b)=ab a ⊕a =0 ab=a +b
a ⊕ b =a ⊕ b=a ⊕ b a+b=a b
a ⊕b =a ⊕ b a ⊕ b=ab +a b
a ⊕ b=ab+a b
Propriétés algébriques des opérateurs
Les lois de De Morgan sont très importantes car elles permettent de transformer un opérateur en un autre dans une expression algébrique. On peut donc, dans une expression, remplacer tous les opérateurs OU par des opérateurs ET (ou vice-versa). L’intérêt est par exemple de pouvoir choisir l’opérateur utilisé pour construire la fonction à partir de son expression, selon des portes logiques disponibles.
Figure 2.1
Circuits logiques 25
Architecture La propriété d’associativité permet de définir les opérateurs ET, OU, NON-ET et NON-OU à plus de deux entrées :
• La fonction OU donne un résultat égal à 1 si au moins une de ses entrées est à 1.
• La fonction ET donne un résultat égal à 1 si toutes ses entrées sont à 1.
• La fonction NON-OU donne un résultat égal à 1 si aucune de ses entrées n’est à 1.
• La fonction NON-ET donne un résultat égal à 1 si au moins une de ses entrées est à 0. Les schémas des circuits sont comparables qu’il y ait deux entrées ou plus : on ajoute simplement autant de lignes que de variables d’entrée supplémentaires. Le OU-exclusif peut également se généraliser à plus de deux entrées mais cela est beaucoup moins classique. Un circuit OU-exclusif à n entrées fournit une sortie égale à 1 s’il y a un nombre impair d’entrées qui ont la valeur 1 (voir tableau 2.7).
Tableau 2.7
a b c OU(a,b,c) ET(a,b,c) OU(a,b,c)
NON- 26 de l’ordinateur ET(a,b,c) NON-
XOR(a,b,c)
0 0 0 0 0 1 1 0
0 0 1 1 0 0 1 1
0 1 0 1 0 0 1 1
0 1 1 1 0 0 1 0
1 0 0 1 0 0 1 1
1 0 1 1 0 0 1 0
1 1 0 1 0 0 1 0
1 1 1 1 1 0 0 1
Fonctions à trois entrées
1.4 Construction d’une fonction quelconque
Une fonction booléenne est entièrement définie par sa table de vérité mais cela n’est pas d’une grande aide pour implémenter cette fonction sous forme de circuit combinatoire. En effet, les seuls circuits élémentaires à disposition sont les portes logiques et celles-ci reproduisent les opérateurs de base (NON, OU, ET…) qui sont dans l’expression algébrique d’une fonction. Il faut donc transformer la table de vérité de la fonction en expression algébrique afin de pouvoir la calculer et surtout de pouvoir physiquement l’implémenter à l’aide des portes logiques.
Mintermes et forme canonique disjonctive Soit une fonction définie par sa table de vérité, par exemple la fonction de trois variables suivante :
Tableau 2.8
a b c F(a,b,c) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0
La table de vérité de F
Nous allons nous intéresser aux lignes pour lesquelles la fonction vaut 1. Prenons par exemple la quatrième : la fonction vaut 1 quand a vaut 0, et b et c valent 1. Il existe donc une expression qui vaut 1 quand les variables ont exactement ces valeurs. Il s’agit de a bc . En effet, comme nous sommes devant un ET, il faut que les trois termes prennent la valeur 1 pour que le résultat soit 1 ; la variable a étant complémentée, elle doit en fait valoir 0. Cette expression s’appelle un « minterme ». C’est un ET de toutes les variables d’entrée de la fonction, où chaque variable est éventuellement complémentée. Un minterme prend la valeur 1 uniquement pour la combinaison indiquée des variables (si la variable est écrite directement, elle doit valoir 1 ; si elle est complémentée, elle doit valoir 0).
On peut maintenant écrire tous les mintermes correspondant aux cas où la fonction vaut 1. Il s’agit de : a b c , a b c , a bc , ab c et abc . On termine en exprimant le fait qu’il suffit d’être dans un de ces cas pour que F vaille 1 ; on doit se trouver dans le premier cas, ou le deuxième, ou le troisième, etc.
F(a,b,c)=a b c +a b c+a bc+ab c +abc
Cette écriture de la fonction s’appelle la « forme canonique disjonctive » ou « somme canonique ». Il est tout à fait possible (et même souhaitable) de simplifier ensuite l’expression algébrique de la fonction à l’aide des propriétés booléennes. On pourrait ainsi réduire F à l’expression suivante (plusieurs expressions réduites sont possibles, toutes équivalentes) :
F(a,b,c)=a b c +a b c+a bc+ab c +abc
=a b c +(a c+ac )b +(a c+ac )b =a b c +(a ⊕c)(b +b)=a b c +(a ⊕c)
=a+b+c+(a ⊕c)
Cela permet de dessiner le circuit combinatoire équivalent (voir figure 2.2).
Figure 2.2
Circuit combinatoire équivalent à F.
Opérateur complet Toute fonction logique (sauf la fonction nulle) peut se mettre sous sa forme canonique disjonctive, comme OU de mintermes. Quels sont alors les circuits nécessaires pour construire une fonction logique ?
• Les variables de chaque minterme sont éventuellement complémentée, il faut donc des portes NON.
• Chaque minterme est un ET des variables, il faut donc des portes ET à plusieurs entrées (ou par associativité, plusieurs étages successifs de portes ET à deux entrées).
• Pour finir, il faut une porte OU à plusieurs entrées afin de faire la « somme » de tous les mintermes. On peut donc calculer n’importe quelle fonction logique à l’aide de portes NON, ET et OU. Notez que l’on peut exprimer le NON à l’aide d’un NON-ET en dédoublant l’entrée : a =a.a. On peut faire de même pour le OU, à l’aide de NON et de NON-ET, en utilisant les lois de De Morgan. Pour preuve, l’expression suivante, qui n’emploie que des NON-ET :
a+b=a .b =aa.bb.
De même, le ET n’est qu’un NON-ET suivi d’un NON :
ab=ab=ab.ab
Les trois portes de base peuvent donc chacune être remplacée par une ou plusieurs portes NON-ET.
Circuits logiques 27
Architecture Comme il suffit de ces trois portes pour exprimer n’importe quelle fonction, on en conclut que le NON-ET est un opérateur complet, permettant d’écrire n’importe quelle fonction en n’utilisant que des portes NON-ET dans le circuit. Cette propriété peut être intéressante lors de la construction de circuits combinatoires pour minimiser le nombre de types différents de portes.
Remarque
On a exactement la même propriété pour l’opérateur complet NON-OU qui peut remplacer des NON, des ET et des OU.
Tableaux de Karnaugh Pour une fonction de deux ou trois variables, il est simple d’utiliser la table de vérité pour exprimer et ensuite simplifier l’expression algébrique de la fonction. Si l’on a une fonction de quatre ou cinq variables, il existe une méthode graphique permettant d’arriver au même résultat : le tableau de Karnaugh. Il s’agit de représenter la table de vérité sous forme matricielle, en réunissant deux variables sur quatre lignes et deux ou trois variables sur quatre ou huit colonnes. Chaque ligne et chaque colonne représente un état (0 ou 1) de la variable, une case du tableau étant alors la valeur de la fonction pour la combinaison indiquée des variables (voir deux exemples à la figure 2.3).
Figure 2.3
Tableaux de Karnaugh pour quatre et cinq variables.
Les lignes et colonnes ne sont pas disposées au hasard mais de telle sorte que, entre deux cases adjacentes (horizontalement ou verticalement), il n’y ait qu’une variable qui change d’état. On remplit ce tableau à l’aide des valeurs que prend la fonction. On peut donc développer la forme canonique en extrayant toutes les cases (et les mintermes correspondants) où la fonction vaut 1. Mais le principe de ces tableaux est de regrouper ces cases par ensembles de deux, quatre, huit, seize, etc., pour simplifier les mintermes. En regroupant deux cases contiguës, on peut éliminer une variable d’un minterme, en en regroupant quatre, en ligne ou en carré, on en élimine deux, et ainsi de suite. Considérons les deux tableaux de la figure 2.4.
Figure 2.4
28 de l’ordinateur Simplification de tableaux. Dans le premier tableau, on a choisi d’effectuer deux regroupements : le premier, en haut à gauche, permet d’éliminer la variable a dans deux mintermes pour aboutir au terme b c d ; le second regroupement, celui de quatre cases, élimine les variables b et d et donne ac. Avec les deux cases isolées restantes, on aboutit à l’expression algébrique de la fonction :
F1 = b c d +ac+a bcd +a bc d
Le second tableau montre un regroupement sur les cases extrêmes : la propriété d’adjacence (une seule variable change d’état) est également vérifiée entre les cases de bords opposés ; le tableau est en fait un tore (c’est-à-dire un carré dans lequel les bords opposés seraient voisins). On a deux regroupements de deux cases donnant les termes b cd et bcd, et les quatre cases extrêmes formant un carré, ce qui génère le terme a c . L’expression de la fonction est donc :
F2 = b cd +bcd+a c
Il est plus simple de travailler avec les tableaux de Karnaugh que sur les mintermes d’une fonction. À titre d’exemple, le tableau 2.9 donne la table de vérité de la première fonction. Il y a donc huit mintermes à écrire et à simplifier, pour aboutir à l’expression de la fonction obtenue directement à l’aide du tableau.
Tableau 2.9
a b c d F1(a,b,c,d) 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1
La table de vérité de la première fonction
Le troisième tableau de Karnaugh (voir figure 2.5), à cinq variables, est un peu spécial. Il faut le considérer comme deux sous-tableaux 4 χ 4 superposés pour choisir les regroupements. Ceux de huit cases peuvent se faire dans un même sous-tableau ou sous forme de « cube », deux paquets superposés de quatre cases, un dans chaque sous-tableau. Dans l’exemple de la figure 2.5, on voit quatre possibilités de groupes de huit en traits pleins. Le groupe en pointillés n’est pas valide car il ne correspond pas aux mêmes cases dans les deux sous- tableaux ; il faut le découper en deux carrés de quatre cases.
Figure 2.5
Regroupements dans un tableau à cinq variables.
Circuits logiques 29
Architecture de l’ordinateur 30 Au-delà de cinq variables, on ne peut plus utiliser de tableaux de Karnaugh. Il faut de nouveau partir de la table de vérité en espérant pouvoir simplifier l’expression, probablement « monstrueuse », obtenue pour la fonction. Note
Table de vérité incomplète Parfois, une fonction n’est pas complètement définie. Plus précisément, pour certaines combinaisons des entrées, les valeurs présentes sur certaines sorties n’ont pas d’importance. On peut alors jouer avec cela pour simplifier l’expression de la fonction. En forçant intelligemment les valeurs « libres » à 0 ou 1, on peut créer des regroupements dans le tableau de Karnaugh correspondant.
Optimisations On peut avoir plusieurs objectifs lorsque l’on cherche à simplifier l’expression algébrique d’une fonction. On peut souhaiter n’utiliser qu’un seul type de porte pour simplifier la fabrication du circuit. Si l’on veut au contraire réduire la place qu’il occupe, il faut minimiser le nombre de portes. Malheureusement, ce n’est pas aussi facile que cela car toutes les portes ne sont pas équivalentes en termes d’occupation physique. Paradoxalement, en raison de leur construction électronique, ce sont les portes NON-ET et NON-OU qui sont les plus petites ; une porte ET correspond souvent à un circuit NON-ET suivi de l’opérateur NON. On ne peut donc pas optimiser la fonction sans avoir des détails sur l’implémentation physique des circuits. Enfin, l’objectif de l’optimisation peut être la minimisation du temps de propagation électrique afin d’obtenir un circuit plus rapide. Nous avons jusqu’à présent fait la supposition que les portes réagissaient instantanément aux entrées alors qu’en réalité l’établissement de la ou des sorties prend un certain temps. Certes, ce temps peut sembler très faible, de l’ordre de la dizaine de nanosecondes, mais il est non négligeable à l’échelle de temps informatique. On peut donc souhaiter avoir le moins de portes entre les entrées et une sortie pour obtenir le délai de propagation le plus faible possible. Cela peut amener à redessiner le circuit autrement, avec plus de portes au total, mais disposées en parallèle, ce qui leur permet de travailler en même temps.
2. CIRCUITS COMBINATOIRES
La plupart des différentes opérations effectuées au sein d’un ordinateur sont implémentées sous la forme de circuits logiques construits à partir de portes logiques. Il est bien sûr impossible d’illustrer tous les circuits utilisés. C’est pourquoi nous nous contenterons de présenter dans cette section quelques circuits classiques que l’on retrouve systématiquement dans les machines, afin de montrer comment ils s’élaborent.
2.1 Décodeur
Le décodeur est un circuit qui permet de sélectionner une ligne à partir de son adresse binaire. Plus précisément, le décodeur n vers 2n a n entrées et 2n sorties. Lorsqu’un nombre binaire sur n bits se présente sur les entrées, le décodeur met un 1 sur la sortie dont le numéro correspond à cette valeur binaire. Une des principales applications du décodeur est la sélection de boîtiers mémoire. En effet, lorsque l’ordinateur fait référence à une case mémoire, il la désigne par son adresse binaire. Celle-ci doit être décodée pour qu’un et un seul boîtier mémoire soit sélectionné. Pour ce faire, on peut utiliser un circuit décodeur qui, à partir de l’adresse mémoire, met à 1 une et une seule des lignes de validation en sortie, lignes reliées aux différents boîtiers.
Tableau 2.10
a1 a0 s0 s1 s2 s3 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1
Table de vérité du décodeur
Il est simple de construire un décodeur, car chaque sortie est à 1 uniquement sur une combinaison précise des entrées. Par exemple, la sortie 0 est active lorsque toutes les entrées sont à 0, donc pour le minterme
Décodeur 2 vers 4.
2.2 Multiplexeur
Le multiplexeur 2n vers 1 permet de choisir une entrée parmi 2n et de la recopier sur la sortie. Pour la sélection de l’entrée, il y a n lignes de commande qui codent le numéro en binaire de l’entrée voulue. L’intérêt du multiplexeur est de pouvoir connecter plusieurs entrées à un même circuit et de sélectionner l’entrée voulue simplement en indiquant son adresse sur les lignes de commande. On peut ainsi relier plusieurs composants entre eux en minimisant les fils de connexion. Ce circuit est basé sur le même principe qu’un décodeur : il y a autant de portes ET que d’entrées mais chacune n’est activée que lorsque la combinaison correspondante est présente sur les lignes de commande. On réunit ensuite les sorties des ET sur un OU pour récupérer celle qui est valide. La figure 2.7 illustre un multiplexeur 4 vers 1 où les deux lignes de commande c1c0 indiquent quelle entrée parmi les quatre (e1, e2, e3 ou e4) doit être transférée sur la sortie.
Tableau 2.11
c1 c0 S 0 0 e0 0 1 e1 1 0 e2 1 1 e3
Table de vérité du multiplexeur
a n−1a n−2…a 1a 0. On a donc un simple ET à n entrées qui commande chaque sortie, les entrées de ce ET étant les variables d’entrée, éventuellement complémentées. La figure 2.6 montre un décodeur 2 vers 4. Les deux entrées a1a0 peuvent prendre les valeurs 0 ou 1, donnant quatre combinaisons possibles, chacune sélectionnant une sortie.
Figure 2.6
Circuits logiques 31
Multiplexeur 4 vers 1.
2.3 Additionneur
Un ordinateur fait des calculs et utilise pour cela des circuits logiques. La plus simple est l’addition qui nécessite deux types de circuits.
Demi-additionneur Pour additionner deux nombres binaires, il faut d’abord additionner les 2 bits de poids faible puis additionner les bits suivants sans oublier les retenues. On commence donc par écrire la table de vérité d’un circuit additionnant 2 bits (voir section 1.4).
Tableau 2.12
a b S R 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
Addition de 2 bits
Dans cette table, on reconnaît la fonction OU-exclusif pour la somme et le ET pour la retenue, d’où le demi- additionneur de la figure 2.8.
Additionneur complet Il faut maintenant être capable d’additionner 2 bits plus une retenue. Voici la table de vérité d’un tel circuit.
Tableau 2.13
a b r S R’ 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1
Architecture de l’ordinateur 32
Figure 2.7
1 1 0 0 1 1 1 1 1 1
L’additionneur complet
La sortie est à 1 s’il y a un nombre impair de bits à 1 en entrée ; cela est équivalent à prendre le OU-exclusif des entrées :
S=a ⊕b⊕r
La retenue R’ se calcule par sa forme canonique :
ʹ′ R =a br+ab r+abr +abr = r(a b+ab )+ab(r +r) = r(a ⊕ b)+ab
L’intérêt de la mettre sous cette forme est d’utiliser le même circuit pour S et R’. La figure 2.8 donne les schémas classiques de l’additionneur complet 1 bit, sous forme de portes logiques et de demi-additionneur.
Figure 2.8
Demi-additionneur et additionneur complet.
Additionneur 4 bits Pour finir, donnons un exemple de circuit plus complexe, un additionneur 4 bits, qui fait la somme de deux nombres binaires a3a2a1a0 et b3b2b1b0. Le construire directement à partir de la table de vérité est impossible : il y a huit entrées, soit deux cent cinquante-six combinaisons possibles, donnant chacune quatre sorties et une retenue finale. Il faut
Circuits logiques 33
Architecture simplement le construire en posant l’addition binaire et en effectuant la somme bit à bit. On retrouve alors les deux circuits que l’on vient de construire, le demi-additionneur pour le bit de poids faible et l’additionneur complet pour les autres. Il faut juste reporter la retenue d’un étage à l’autre comme à la figure 2.9.
Figure 2.9
Additionneur 4 bits.
Le circuit précédent a le mérite de la simplicité mais pas de la rapidité. À cause de la propagation de la retenue d’un étage à l’autre, la retenue finale n’est pas immédiatement disponible. D’autres circuits pour l’additionneur ont été proposés, dont un que vous trouverez en exercice. Tous les circuits arithmétiques présents au sein d’un processeur sont développés de la même manière, soit directement à partir de la table de vérité, soit par regroupement de fonctions plus simples.
Complément
On ne peut pas facilement connecter entre elles plusieurs sorties de circuits logiques sous peine d’éventuels conflits si des valeurs différentes sont présentes. Pour pouvoir le faire, on dote parfois les circuits d’une ligne de commande, qui permet de désactiver les sorties en les déconnectant des entrées. On parle alors de circuits fonctionnant en logique 3 états : deux correspondant aux valeurs 0 et 1, et un « état indéfini » dans lequel la sortie n’est plus reliée aux entrées.
3. CIRCUITS LOGIQUES SÉQUENTIELS
Un circuit séquentiel est un circuit construit à partir de portes logiques, dans lequel on introduit une rétroaction des sorties sur les entrées. Un rebouclage permet à une ou plusieurs sorties d’être renvoyées sur les entrées des portes. On ne peut alors plus calculer les valeurs de sortie uniquement à partir des valeurs des entrées comme pour les circuits combinatoires, puisqu’il faut également tenir compte des valeurs antérieures des sorties répercutées sur les entrées. Un nouveau paramètre temporel entre en jeu lors de l’étude du circuit.
3.1 Bascules élémentaires
Bascule RS De même que les portes logiques constituent les briques de base des circuits combinatoires, les circuits séquentiels sont construits à partir de cellules élémentaires servant à mémoriser un bit, connues sous la dénomination générique de bascules, car elles possèdent deux états stables. Considérons le circuit de la figure 2.10, formé de deux portes NON-OU.
34 de l’ordinateur
Bascule RS asynchrone.
Supposons que S = R = 0. Si Q = 0, la porte NON-OU inférieure génère 1 sur Q , qui est renvoyé sur l’autre porte NON-OU, confirmant le 0 de la sortie Q. De même, si, Q = 1, on obtient Q =0, renforçant la valeur de Q. Ces deux états sont donc stables et il n’en existe pas d’autre, Q et Q ne pouvant prendre la même valeur si S et R valent 0. Si S passe à 1 (R restant à 0), Q est forcé à 0 quelle que soit sa valeur précédente et Q passe à 1. Si R passe à 1 (S restant à 0), le résultat est inversé : Q passe à 1 et Q à 0. Si les deux entrées sont mises à 1, Q et Q deviennent nuls. Un problème survient lorsque les deux entrées repassent à 0. Le comportement est indéterminé : suivant celle qui passe à 0 en dernier (car il y a toujours au moins un infime décalage entre les deux entrées), Q peut valoir 0 ou 1. C’est pourquoi on considère le cas S = R = 1 comme interdit.
Tableau 2.14
R S Q+ 0 0 Q (mémorisation) 0 1 1 (mise à 1) – Set 1 0 0 (mise à 0) – Reset 1 1 X (interdit)
Table de vérité de la bascule RS
La bascule RS (pour Set et Reset) mémorise donc la dernière commande sur S ou R ; soit une mise à 1, soit une mise à 0, valeur que l’on retrouve sur Q. La bascule présentée à la figure 2.10 est appelée « bascule RS asynchrone » car elle réagit dès que les entrées sont modifiées.
Horloge On a souvent besoin d’effectuer des changements d’état à des instants déterminés, rythmés par une horloge, signal carré prenant régulièrement les valeurs 0 et 1 (voir à la figure 2.11 un exemple de signal d’horloge). On peut facilement modifier la bascule RS pour la rendre synchrone, c’est-à-dire ne permettre de changements que lorsque le signal d’horloge vaut 1 (voir la figure 2.11 où l’horloge est reliée à l’entrée Clk, Clock).
Figure 2.11
Bascule RS synchrone.
Figure 2.10
Circuits logiques 35
Architecture Si l’horloge vaut 0, les deux portes ET sont au repos et les deux entrées des portes NON-OU sont à 0, laissant la bascule dans son état stable, indépendamment de R et S. Si l’horloge vaut 1, les deux entrées R et S sont transférées aux entrées des NON-OU, permettant le fonctionnement habituel. On peut bien sûr complémenter l’entrée d’horloge pour rendre son état bas (valeur 0) actif. Le défaut de cette entrée d’horloge est de rester active pendant un long intervalle de temps, celui pendant lequel le signal est au niveau haut. Il serait plus intéressant d’avoir une activation à des instants bien précis, pour obtenir une synchronisation exacte des circuits. Pour ce faire, on peut utiliser le retard induit par le passage dans une porte logique (voir figure 2.12). Figure 2.12
Bascule RS synchrone sur front montant.
L’entrée Clk étant complémentée avant la porte ET, en théorie elle restitue toujours 0 en sortie, bloquant les entrées R et S. En pratique, lorsque Clk passe à 1, la porte NON change d’état avec un très léger retard, laissant 1 en sortie pendant un bref instant après le changement de l’entrée Clk. Pendant ce court instant, la porte ET voit ses deux entrées à 1 et génère une sortie à 1, activant R et S. On dit que l’horloge est active sur son front montant (lorsqu’elle passe de 0 à 1 et uniquement à cet instant très précis). Là encore, on peut complémenter cette entrée d’horloge pour commander la bascule sur un front descendant. À la figure 2.13 se trouvent les symboles graphiques de ces bascules. Figure 2.13
Symboles des bascules synchrones et asynchrones.
Les bascules synchronisées par des niveaux (haut ou bas) sont dites « latch » alors que les bascules déclenchées par un front sont dites « flip-flop ».
Bascule D La bascule D (D pour Data) est simplement une bascule RS dans laquelle on a forcé R et S à être complémentaires. Une des deux entrées R ou S étant toujours à 1, une bascule D asynchrone ne ferait que reproduire son entrée D sur la sortie et cela n’aurait pas vraiment d’intérêt. Il est plus intéressant d’échantillonner l’entrée D à des instants bien précis. Pour cela, il est préférable que la bascule soit synchronisée sur un front (voir figure 2.14).
36 de l’ordinateur
Bascule D.
Lorsque l’horloge passe de 0 à 1, l’entrée D se retrouve sur S et D sur R. Il y a donc mémorisation de D dans la bascule et sur Q à ce moment-là. Le reste du temps, quelle que soit la valeur du signal d’horloge, la bascule est bloquée.
Bascule T Une bascule T synchrone (T pour Toggle ou basculement) possède deux entrées d’activation, une entrée T et une entrée d’horloge : lorsque T vaut 0, la bascule est isolée, les sorties ne changent pas ; lorsque T est à 1, les sorties changent d’état (de 0 vers 1 et réciproquement) à chaque front montant de l’horloge. Souvent l’entrée T n’existe pas et la bascule change simplement d’état à chaque front montant (les deux constructions à partir d’une bascule D sont données à la figure 2.15).
Figure 2.15
Bascules T.
Bascule JK La bascule JK (J et K n’ont aucune signification) asynchrone est simplement une bascule RS pour laquelle la combinaison « interdite » des entrées J = K = 1 provoque une inversion de la sortie (voir la figure 2.16, où l’on a inversé l’emplacement des entrées de la bascule RS pour simplifier le dessin).
Figure 2.16
Bascule JK asynchrone.
Si J = K = 0, les deux entrées de la bascule RS sont à 0 et rien n’est modifié. Si J passe à 1, soit Q était égal à 1 et rien ne change, soit Q valait 0 et un 1 est transmis (via le 1 sur Q ) à l’entrée S forçant Q à 1. Le comportement est opposé si K vaut 1, forçant Q à 0. Dans les trois cas, la bascule est identique à une bascule RS. Si maintenant J = K = 1 et si Q vaut 1, l’entrée R est activée, remettant Q à 0, et si Q vaut 0, c’est l’entrée S qui s’active, mettant Q à 1. On a alors une série de basculements de la sortie qui vaut alternativement 0 et 1, tant que J = K = 1.
Figure 2.14
Circuits logiques 37
Tableau 2.15
K J Q+ 0 0 Q (mémorisation) 0 1 1 (mise à 1) 1 0 0 (mise à 0) 1 1 Q (basculement)
Table de vérité de la bascule JK
La bascule JK synchrone (sur front montant) se comporte comme la bascule RS synchrone sauf dans le cas J = K = 1 où la bascule change l’état de la sortie au moment du front.
Complément
Toutes les bascules précédentes peuvent se voir dotées d’entrées asynchrones permettant de forcer la valeur de la sortie. Ainsi il peut exister une entrée fixant la sortie principale Q à 1, souvent appelée Preset, indépendamment des valeurs des autres entrées et de l’horloge. De même, l’entrée asynchrone Clear permet de forcer la sortie Q à 0, là encore sans tenir compte ni des entrées principales ni de l’horloge. Ces entrées sont utiles pour fixer la valeur de sortie de la bascule avant utilisation.
3.2 Circuits séquentiels classiques
De même que les portes logiques servent à développer les circuits combinatoires, voici quelques exemples d’utilisation de bascules élémentaires au sein de circuits séquentiels classiques utilisés dans les ordinateurs.
Diviseur de fréquence En créant une cascade de bascules T, on réalise un diviseur de fréquence (voir figure 2.17) : lors de chaque front montant de l’horloge, la première sortie Q change d’état ; on a donc un front montant de Q tous les deux fronts montants de l’horloge. Le phénomène se reproduit sur chacune des bascules, divisant à chaque étage la fréquence par 2 (sans que cela soit très précis à cause des retards de propagation induits par les circuits logiques des bascules).
Compteur binaire En utilisant des bascules T activées par un front descendant, on peut construire un compteur binaire (voir figure 2.17) : lorsqu’une sortie Q passe de 1 à 0, la bascule suivante change d’état (elle voit un front descendant) comme s’il y avait propagation d’une retenue. Avec n bascules, les sorties a0 …an-1 prennent successivement les valeurs binaires de 0 à 2n – 1 à chaque front descendant de l’horloge.
Registre Un registre est un élément de stockage qui permet la mémorisation de n bits en parallèle. Cet élément est constitué sur la base d’une mise en parallèle de n bascules mémorisant chacune 1 bit. La figure 2.17 montre un registre de stockage de 4 bits. Il utilise des bascules D ayant une entrée asynchrone de remise à 0 (Clr).
Architecture de l’ordinateur 38
Circuits séquentiels.
Si W vaut 0, l’horloge n’est jamais transmise aux bascules et celles-ci mémorisent indéfiniment la valeur initialement enregistrée. Si W vaut 1 (Write), au prochain front montant de l’horloge, les bascules vont stocker la valeur e0e1e2e3 présente sur les entrées, valeur qui restera disponible quand W repassera à 0. L’entrée RAZ sert à remettre toutes les bascules à 0 via leur entrée asynchrone.
Complément
En plus de l’algèbre de Boole, l’analyse des circuits séquentiels fait appel à la théorie des automates, qui permet de tenir compte des évolutions temporelles des circuits à travers leurs états. L’utilisation de chronogrammes, donnant l’évolution temporelle complète de tous les signaux en continu, permet l’étude fine des portes logiques (et donc des problèmes de retard et de délai de propagation), mais n’est pas très utile pour avoir une vision synthétique d’un circuit.
RÉSUMÉ
Les valeurs de tension sur les fils sont interprétées comme des bits, ce qui permet d’utiliser l’algèbre de Boole comme outil d’analyse. Celle-ci permet de définir une algèbre sur des variables pouvant prendre deux valeurs, 0 ou 1. À l’aide des fonctions élémentaires sur ces variables, NON, ET, OU et XOR, n’importe quelle fonction logique peut être définie et son expression logique explicitée. Ces mêmes fonctions élémentaires existent physiquement sous la forme de portes logiques, qui modifient les caractéristiques électriques des signaux et donc des bits, permettant ainsi, toujours grâce à l’algèbre de Boole, d’implémenter des fonctions logiques de base, décodage, addition, etc., et de construire des circuits plus complexes. Les circuits logiques séquentiels utilisent la possibilité de réinjecter des sorties sur les entrées pour mémoriser des bits dans les portes. On peut ainsi construire des circuits, appelés « registres », mémorisant des informations.
Figure 2.17
Circuits logiques 39
Architecture de l’ordinateur 40 Problèmes et exercices Les exercices suivants permettent de construire des circuits logiques soit à partir
d’expressions booléennes, soit directement à partir de circuits classiques existants. Vous
allez ainsi étudier des opérations arithmétiques telles que la soustraction, la multiplication ou
la comparaison de nombres sous l’angle logique pour écrire leur table de vérité et dessiner
le circuit équivalent à base de portes logiques. L’un des exercices fait intervenir le délai de
propagation à travers une porte, ce qui oblige à concevoir différemment le circuit pour ne
pas être pénalisé d’un point de vue des performances.
Exercice 1 : Construire une fonction logique
Soit un entier de 0 à 7 représenté par 3 bits b2b1b0. Soit F la fonction logique dont les entrées sont ces 3 bits et qui prend la valeur 1 si la valeur de l’entrée vaut 0, 3, 4 ou 7 (codée en binaire), et 0 sinon. 1) Donnez la table de vérité de F, écrivez-la sous sa forme canonique et simplifiez l’expression obtenue. 2) Retrouvez le résultat précédent en écrivant la table de Karnaugh de F. 3) Dessinez le circuit logique calculant F, uniquement à l’aide de portes NON-ET.
Tableau 2.16
b2 b1 b0 F
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
La table de vérité de F
On obtient alors la forme canonique de F et sa simplification :
F = b 2b 1b 0 +b 2b1b0 +b2b 1b 0 +b2b1b0 =(b 2 +b2)(b 1b 0)+(b 2 +b2)(b1b0) = b 1b 0 +b1b0 = b1 ⊕b0 La table de Karnaugh de F est donnée à la figure 2.18.
Circuit logique équivalent à F.
Exercice 2 : Un circuit qui calcule
Soit une machine qui travaille sur des nombres binaires signés de 4 bits. La valeur signée d’un mot A = a3a2a1a0 est égale à a0 + 2a1 + 4a8 – 8a3 (c’est la représentation classique en complément à 2). On désire construire un circuit qui donne en sortie B = b3b2b1b0 = –2 χ A (par exemple, si l’on a la valeur 2 en entrée, on veut la valeur binaire –4 en sortie). 1) Toutes les valeurs binaires sont-elles autorisées en entrée ? Autrement dit, le circuit donne-t-il toujours une valeur correcte ? Donnez la table de vérité du circuit pour toutes les valeurs autorisées. 2) Donnez les expressions logiques des 4 bits de sortie en fonction des 4 bits d’entrée en ne tenant pas compte des valeurs interdites. 3) On désire avoir un bit de débordement (voir chapitre 1) qui indiquerait qu’une valeur interdite est présente sur les entrées. Écrivez la table de Karnaugh de ce bit et donnez-en une expression logique.
1) Seules les valeurs de –3 à 4 sont autorisées en entrée car, au-delà, on ne peut pas représenter le résultat sur 4 bits signés, comme c’est le cas, par exemple, pour –2 χ –4 = 8 et –2 χ 5 = –10. On peut donc écrire une table de vérité tronquée en ne mettant pas les valeurs interdites :
Tableau 2.17
A a3a2a1a0 b3b2b1b0 B
0 0000 0000 0
1 0001 1110 –2
2 0010 1100 –4
3 0011 1010 –6
Table de Karnaugh de F.
En effectuant les deux regroupements, on retrouve bien le résultat F = b 1b 0 +b1b0. La loi de De Morgan permet de transformer le OU en ET ; on obtient la formule et le circuit correspondants (voir figure 2.19).
F = b 1b 0.b1b0
Figure 2.19
Figure 2.18
Circuits logiques 41
Table du bit de débordement.
Les regroupements indiqués donnent l’expression suivante :
e=a3a 2 +a3a2a 1a 0 +a 3a2a 1a0 +a 3a2a1 On a donc réussi à obtenir l’expression algébrique des différentes sorties du circuit, ce qui permet de le construire, ainsi que l’expression du bit de débordement, indiquant que le circuit ne peut pas donner la valeur correcte.
Exercice 3 : Additionneur/soustracteur
On construit un circuit qui a deux entrées (a et b) et deux sorties (s et r) et une ligne de commande F tel que :
• Si F = 0, le circuit effectue une addition (a + b avec une sortie s et une retenue r).
• Si F = 1, le circuit effectue une soustraction (a – b avec une sortie s et une retenue r). 1) Donnez la table de vérité de ce circuit demi-additionneur/soustracteur. Montrez que s se calcule facilement avec une porte et r avec deux. 2) On construit maintenant un additionneur/soustracteur complet, c’est-à-dire un circuit à trois entrées (a, b et r), deux sorties (s et r’) et une ligne de commande F tel que :
• Si F = 0, le circuit effectue une addition (a + b + r avec une sortie s et une retenue r’).
• Si F = 1, le circuit effectue une soustraction (a – (b + r) avec une sortie s et une retenue r’).
4 0100 1000 –8
–3 1101 0110 6
–2 1110 0100 4
–1 1111 0010 2
La table de vérité
2) On a b0 = 0 et b1 = a0. En écrivant la forme canonique de b2, on obtient :
b2 =a 3a 2a 1a0 +a 3a 2a1a 0 +a3a2a 1a0 +a3a2a1a 0
=a 3a 2(a1 ⊕a0)+a3a2(a1 ⊕a0) =(a3 ⊕a2)(a1 ⊕a0) On peut en fait simplifier en :
b2 =(a1 ⊕a0)
en ne tenant pas compte des cas non autorisés (puisque les sorties peuvent alors prendre les valeurs que l’on veut). On voit également que le signe s’inverse dans tous les cas sauf pour 0. b3 est donc l’inverse de a3 sous réserve qu’au moins un des autres bits soit à 1 : b3 =a 3(a2 +a1 +a0)
3) La table de Karnaugh du bit de débordement est présentée à la figure 2.20.
Figure 2.20
Architecture de l’ordinateur 42
Écrivez la table de vérité de s pour la soustraction et comparez-la à celle de l’additionneur complet. Donnez l’expression logique de s. Écrivez la table de Karnaugh ainsi qu’une expression logique de r’. 3) À partir des deux circuits précédents, proposez une construction pour un additionneur/soustracteur sur n bits, c’est-à-dire un circuit avec deux fois n bits en entrée et qui effectue l’addition ou la soustraction de ces deux nombres suivant la valeur d’une ligne de commande.
1) Voici la table de vérité de l’addition et la soustraction de 2 bits.
Tableau 2.18
a b F s r
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 0 0
0 1 1 1 1
1 0 1 1 0
1 1 1 0 0
Le demi-additionneur/soustracteur
On obtient les deux expressions logiques :
s=a ⊕b r =abF +a bF = b(aF +a F)= b(a ⊕F)
2) La table de vérité de s, dans le cas de la soustraction de 3 bits, est identique à celle de l’additionneur complet. On obtient donc s=a ⊕b⊕ r. La table de Karnaugh de r’ se trouve à la figure 2.21 (avec le dessin du circuit complet) et permet d’obtenir l’expression suivante :
ʹ′ r = br+a b Fr+ab F r+abF r +a bFr
= br+(br +b r)(a F+aF ) = br+(b⊕r)(a ⊕ F)
Circuits logiques 43
Additionneur/soustracteur n bits.
On a donc réussi à construire un circuit commandé qui effectue l’addition ou la soustraction de deux nombres de n bits. Ce circuit pourrait servir à l’intérieur d’un ordinateur pour réaliser les opérations mathématiques de base.
Exercice 4 : Multiplicateur
1) On souhaite construire un multiplicateur 2 bits par 1 bit (représentant des nombres entiers positifs), c’est-à-dire un circuit à trois entrées a0, a1 et b, et deux sorties s0 et s1, tel que si b = 0, s0 = s1 = 0 et si b = 1, s0 = a0 et s1 = a1. Donnez le schéma d’un tel circuit (appelé M) en utilisant deux portes ET. 2) On veut maintenant construire un multiplicateur 2 bits par 2 bits. En décomposant cette multiplication en multiplications plus simples et en additions, montrez que l’on peut le construire avec deux circuits M et deux demi-additionneurs. 3) Donnez le schéma d’un multiplicateur 2 bits par n bits utilisant des circuits M, demi-additionneurs et additionneurs complets.
Architecture de l’ordinateur 44
Table de r’ et circuit complet.
3) On construit l’additionneur/soustracteur n bits exactement comme l’additionneur n bits, en reportant les retenues d’un circuit élémentaire à l’autre (voir figure 2.22).
Figure 2.22
Figure 2.21
1) Il suffit de placer b à l’une des entrées des deux portes ET pour construire le circuit M (voir figure 2.23). 2) Pour effectuer une multiplication 2 bits par 2 bits, on la pose en multipliant bit par bit :
a1 a0 b1 b0 a1b0 a0b0 a1b1 a0b1 s3 s2 s1 s0
Cela donne le circuit de la figure 2.23.
Figure 2.23
Multiplicateurs 2 par 1 et 2 par 2.
3) La multiplication 2 bits par n bits se pose également bit par bit, ce qui permet, en prenant chacune des multiplications et des additions élémentaires, de construire le circuit correspondant (voir figure 2.24) avec n circuits M, deux demi-additionneurs et n – 2 additionneurs complets.
a1 a0 bn−1 . . b1 b0 a1b0 a0b0 a1b1 a0b1 a0b2  a1bn−2 a1bn−1 a0bn−1 sn+1 sn sn−1 . s2 s1 s0
Circuits logiques 45
Multiplicateur 2 bits par n bits.
Là encore, on a construit un circuit capable d’implémenter une opération que l’ordinateur aura peut-être à effectuer.
Exercice 5 : Additionneur à retenue anticipée
1) On suppose que le passage d’un signal électrique dans une porte « coûte » 10 nanosecondes (c’est un ordre de grandeur réaliste compte tenu des technologies actuelles). On dit alors qu’un circuit travaille en p ns si tous les signaux en sortie sont disponibles en un maximum de p ns. En combien de temps un demi-additionneur, un additionneur complet et un additionneur 4 bits travaillent-ils ? 2) On va construire un additionneur 4 bits à retenue anticipée, c’est-à-dire un circuit où le calcul des retenues intermédiaires se fait plus rapidement. Soit une fonction de génération de retenue G = ab et une fonction de propagation de retenue P = a + b. Montrez que la retenue de sortie d’un additionneur complet peut se calculer par la formule r’ = Pr + G, où a et b sont les entrées et r la retenue d’entrée. 3) Dans l’additionneur 4 bits, on note Gi = aibi et Pi = ai + bi, et ri la retenue intermédiaire d’un étage, normalement calculée à partir des entrées ai, bi et de la retenue précédente ri – 1. Exprimez r0, r1, r2 et r3 = r en fonction de G0, G1, G2, G3, P0, P1, P2 et P3. 4) Supposons que l’on dispose de plusieurs portes OU et ET à deux, trois ou quatre entrées, et que chacune travaille en 10 ns. En combien de temps se fait le calcul des Gi, Pi et ri ? Est-ce intéressant ? Quelle différence y a-t-il entre le temps de travail d’un additionneur 8 bits normal et d’un additionneur 8 bits à retenue anticipée (avec les bonnes portes OU et ET) ?
1) Le demi-additionneur travaille en 10 ns car chaque sortie passe par une porte (un XOR pour la somme et un ET pour la retenue). Un additionneur complet travaille en 30 ns pour r’ et 20 ns pour s, soit 30 ns au total (mais il faut différencier les sorties pour la question suivante). Pour l’additionneur 4 bits, il ne faut pas se contenter d’additionner les valeurs des circuits le composant mais détailler au niveau de chaque porte, car les entrées ne sont pas disponibles en même temps sur chaque circuit. On a les chiffres suivants :
s0 : 10 ns s1 : 20 ns s2 : 40 ns s3 : 60 ns
r0 : 10 ns r1 : 30 ns r2 : 50 ns r3 : 70 ns
Soit 70 ns au total pour l’additionneur 4 bits. 2) Le calcul de la retenue de sortie de l’additionneur complet est le suivant :
r =ab+ar+br+abr =(a+b)r+ab(r+1)= Pr+G
Architecture de l’ordinateur 46
Figure 2.24
3) De même, les différentes retenues se calculent de la façon suivante :
r0 =a0b0 =G0 r1 =G1 +r0P1 =G1 +G0P1 r2 =G2 +r1P2 =G2 +(G1 +G0P1)P2 =G2 +G1P2 +G0P1P2 r3 =G3 +r2P3 =G3 +G2P3 +G1P2P3 +G0P1P2P3
4) Gi = aibi et Pi = ai + bi, donc chacun est disponible en 10 ns (passage par une porte). Les ri sont formés de OU à partir de ET sur les Gi et Pi, et se calculent donc tous en 30 ns. Donc s0 se calcule en 10 ns, s1 en 20 ns, s2 en 40 ns et s3 en 40 ns également. C’est plus rapide comparativement à l’additionneur 4 bits standard. Pour un additionneur 8 bits, le temps normal est de 150 ns. Avec un additionneur à retenue anticipée, le calcul se fait toujours en 40 ns, mais il faut des portes ET et OU à huit entrées.
Exercice 6 : Comparateur de nombres
On veut concevoir un circuit permettant de comparer deux nombres A et B de 4 bits (valant donc de 0 à 15), A = a3a2a1a0 et B = b3b2b1b0. Le circuit a deux sorties : G valant 1 si A > B et E valant 1 si A = B. 1) Soit a et b deux nombres de 1 bit. Soit un circuit à deux sorties : g valant 1 si a > b et e valant 1 si a = b. Donnez les expressions logiques de g et e et dessinez le circuit correspondant. 2) En utilisant des circuits de la question précédente ainsi que des portes logiques OU, ET (à deux, trois ou quatre entrées) et NON, concevez un circuit permettant de comparer deux nombres de 4 bits.
1) On dénombre un seul cas où a est plus grand que b : quand a vaut 1 et b vaut 0. On a donc g =ab . L’égalité des 2 bits se calcule par e=ab+a b =a ⊕ b, ce qui donne le circuit de la figure 2.25.
Figure 2.25
Comparateur 1 bit.
2) Pour que les deux nombres de 4 bits soient égaux, il faut qu’il y ait égalité deux par deux des bits composant les nombres. Pour savoir si A est plus grand que B, il faut comparer les bits en partant du bit de poids fort : soit a3 est plus grand que b3, soit a3 est égal à b3 et a2 est plus grand que b2, soit on a aussi a2 égal à b2 et a1 est plus grand que b1, soit a1 aussi est égal à b1 et a0 est plus grand que b0. Cela donne le circuit de la figure 2.26.
Circuits logiques 47
Comparateur 4 bits.
Exercice 7 : Bascules équivalentes
Comment peut-on utiliser une bascule JK pour construire une bascule T, et une bascule RS pour construire une bascule T ?
La bascule T change d’état à chaque front d’horloge quand T vaut 1. C’est aussi le comportement de la bascule JK quand les deux entrées sont à 1. Il suffit donc de relier les deux entrées de la bascule JK entre elles. Quant à la bascule RS, il faut la mettre à 0 quand la sortie est à 1 (donc relier Q à R) et la mettre à 1 quand elle est à 0 (donc relier Q à S) pour avoir le même phénomène de bascule d’état. Il suffit de commander ces deux liens par deux portes ET pour avoir la commande sur T (voir les deux circuits à la figure 2.27).
Figure 2.27
Architecture de l’ordinateur 48
Bascules T avec JK et RS.
Figure 2.26
Exercice 8 : Bascule maître-esclave
Décrivez le fonctionnement du circuit de la figure 2.28 (attention, les commandes se font à fronts inversés sur les deux bascules). Quelle peut être son utilité ?
Figure 2.28
Bascule JK maître-esclave.
Le circuit ressemble à une bascule JK avec le retour des sorties sur la commande des entrées. Cependant, la première bascule est commandée par un front montant alors que la seconde par un front descendant. Cela permet de découpler temporellement les entrées et sorties : une fluctuation des valeurs d’entrée au moment du front montant provoquera une fluctuation des sorties de la première bascule mais elle n’aura pas d’influence sur la seconde, qui ne sera activée que sur le front descendant. De même, une fluctuation lors du front descendant ne sera pas prise en compte par la première bascule, inactivée. Une autre utilisation est envisageable dans le cadre d’un couplage de bascules commandées par une même horloge. Si toutes les bascules sont reliées à une même horloge, à cause du délai de propagation au passage des portes, il est probable que les sorties des premières bascules arriveront trop tard sur les entrées des suivantes ou provoqueront ces fameuses fluctuations. Cette bascule JK maître-esclave (la première bascule RS est maître, la seconde esclave) permet d’éviter ces problèmes en ne commandant pas l’activation des entrées en même temps que la validation des sorties.
Circuits logiques 49
Architecture de l’ordinateur 50
Chapitre 3
Ordinateur et processeur
L’architecture d’un ordinateur est fondée sur le
Ordinateur et processeur
modèle de von Neumann : la machine est construite
1. Architecture de von Neumann ………… 52
autour d’un processeur, véritable tour de contrôle
2. Les instructions…………………………………. 59 3. UAL et registres ……………………………….. 65 interne, d’une mémoire stockant les données et le
4. Séquenceur ……………………………………….. 68 programme, et d’un dispositif d’entrées/sorties
5. Architectures évoluées …………………….. 70
nécessaire pour l’échange avec l’extérieur.
Problèmes et exercices
Le processeur exécute une par une les instructions
stockées sous forme numérique en mémoire,
1. Compilation ou interprétation …………. 78 2. Débit d’informations…………………………. 78 3. Décalages et multiplication……………….. 79 écrites par le programmeur ou le compilateur, en
4. Sauts et contrôle ………………………………. 79 utilisant ses éléments internes : séquenceur,
5. Instructions données……………………………………………..80
à une, deux ou trois
registres et unité arithmétique et logique. Vous allez
6. Divers modes d’adressage………………… 82 découvrir dans ce chapitre comment sont
7. Registre d’état et comparaison ………… 83
constitués les processeurs, de quelle manière ils
exécutent les instructions et quelles évolutions ont
8. Pile et paramètre de fonction…………… 83 9. Pipeline et branchements………………….. 84
10. Exécution multithread…………………….. 87 permis d’améliorer leurs performances.
Ordinateur et processeur 51
1. ARCHITECTURE DE VON NEUMANN
L’ordinateur est né pendant la Seconde Guerre mondiale des travaux de plusieurs ingénieurs et théoriciens. Il n’y a pas eu un pôle unique de développement mais plusieurs centres indépendants qui ont chacun tâtonné en essayant de construire des machines semblables à aucune autre existant à l’époque. Avant-guerre, Alan Turing (Angleterre) et Claude Shannon (États-Unis) avaient posé les fondements de la théorie du calcul, ouvrant la voie aux réalisations : Konrad Züse (Allemagne), John Atanasoff (États-Unis), Alan Turing et son équipe (Angleterre) ont développé entre 1940 et 1945 les premiers calculateurs. À base de relais électriques ou de tubes électroniques, programmables ou non, ces prototypes ont montré la faisabilité du concept d’ordinateur. Souvent isolés, ces inventeurs n’ont pas été soutenus mais ont permis la construction après-guerre des premiers ordinateurs, lorsque les ingénieurs ont de nouveau pu s’y intéresser. Même si des réalisations antérieures, plus ou moins semblables, ont existé, on attribue le titre de premier ordinateur (de manière quand même un peu arbitraire) à l’ENIAC (Electronic Numerical Integrator and Computer), œuvre de John W. Mauchly et de Prosper Eckert au sein de l’université de Pennsylvanie (États-Unis), finalisé en 1946. En raison de la très large publicité qui a été faite, l’ENIAC a attiré de nombreux visiteurs qui s’emploieront, de retour dans leurs laboratoires, à développer leurs propres machines, faisant ainsi avancer les connaissances. L’un de ces visiteurs les plus connus a été le mathématicien John von Neumann, qui a rédigé à la suite un rapport où il exposait ses vues sur l’organisation interne d’un ordinateur. Il a mis, entre autres, l’accent sur le concept de programme enregistré. L’architecture décrite dans son rapport est à la base des ordinateurs depuis 65 ans.
1.1 Typologie historique
Jusque dans les années 80, il était assez facile de caractériser les ordinateurs en fonction de leur taille. Les ordinateurs centraux, descendant des gros systèmes des années 60, occupaient une pièce entière et plusieurs techniciens étaient nécessaires pour assurer leur bon fonctionnement. Ces machines complexes, utilisées par les services de gestion, traitaient souvent de grosses bases de données : service du personnel, paie, logistique, stocks, etc. Le progrès technologique avait fait de ces ordinateurs des machines coûteuses mais puissantes, parfois même trop puissantes pour la tâche voulue. En réaction, des ingénieurs ont conçu à la fin des années 60 le mini- ordinateur. Beaucoup plus petit, moins puissant, mais plus simple et assez bon marché, il avait sa place dans un laboratoire ou un petit service, où il pouvait être utilisé par quelques utilisateurs à la fois, pour des travaux peu complexes, comme l’exécution de simples calculs mathématiques. Le même phénomène s’est reproduit dans les années 70 quand la disponibilité et la baisse des coûts des composants ont permis à quelques pionniers de construire des petites cartes électroniques à base de microprocesseurs. On ne voyait pas très bien à quoi ces micro-ordinateurs (« micro » est alors un terme péjoratif), peu puissants, sans affichage élaboré, sans logiciel, pouvaient servir. Il a fallu attendre le développement des premières applications, traitement de texte et tableur, pour s’apercevoir que ces machines convenaient bien à un usage individuel. Les années 80-90 voient la montée en puissance de ces micro-ordinateurs. Aidés par l’immensité du marché potentiel, ils finissent par faire disparaître les mini-ordinateurs et même par marcher sur les terres des gros systèmes. À l’heure actuelle, on peut grossièrement découper l’univers informatique en quatre catégories :
• Les micro-ordinateurs, représentant l’immense majorité du contingent, sont adaptés à un usage individuel. Leurs performances sont sans cesse améliorées par le progrès technologique, soutenu par des entreprises de taille mondiale (Intel, AMD, IBM, HP, Apple, Dell, Microsoft…).
• Les serveurs, aussi appelés « stations de travail », sont souvent de simples micro-ordinateurs, gonflés par l’ajout de mémoire, de disques accélérés, de cartes réseau plus rapides, de processeurs supplémentaires, etc. Ils sont pilotés par plusieurs utilisateurs simultanément et permettent un affichage graphique élaboré ou des accès rapides.
• Les gros systèmes sont toujours présents, mais relégués à de grosses applications de gestion dans des services de taille importante.
Architecture de l’ordinateur 52
• Enfin depuis toujours, il existe de superordinateurs, capables de prouesses mathématiques, au prix d’un surcoût important. Les micro-ordinateurs s’améliorent continuellement et restreignent les autres catégories à la portion congrue. Les serveurs sont fabriqués à partir de micro-ordinateurs et ces derniers, lorsqu’ils sont connectés par milliers, permettent de construire certains superordinateurs, à un prix nettement inférieur à celui des « vrais » supercalculateurs. Cependant, de nouveaux usages apparaissent ; le micro-ordinateur est parfois « trop puissant » et l’avancée technologique permet de trouver des débouchés pour des appareils plus petits : smartphones et netbooks par exemple.
1.2 Programme enregistré
On programmait les premiers ordinateurs en reliant physiquement par des câbles leurs différents composants et en positionnant manuellement des commutateurs sur les éléments fonctionnels. Suivant la nature et l’ordre de ces liaisons, la machine effectuait les opérations voulues par l’utilisateur, opérations dont la séquence était également contrôlée par le jeu de ces commutateurs. L’inconvénient majeur de cette technique était bien sûr que le passage à une autre tâche faisait perdre l’ensemble des connexions installées, qui étaient remplacées par celles nécessaires à l’exécution des nouveaux calculs. Si l’on voulait plus tard revenir à la première application, il fallait recâbler l’ensemble de la machine à la main avec le risque de se tromper à chaque fois. Après sa visite de l’ENIAC, von Neumann a été le premier (même si l’idée apparaissait déjà dans les travaux théoriques de C. Babbage au XIXe siècle) à décrire la notion de programme enregistré. Il ne fallait plus voir la suite des opérations à effectuer sur la machine comme une composante matérielle de celle-ci mais comme une série d’instructions à lui donner. Ces instructions devaient se mettre sous forme de codes numériques que l’on allait pouvoir laisser dans la mémoire de l’ordinateur où le processeur irait les chercher pour les traiter. L’avantage de cette technique était de pouvoir stocker, lorsque le travail est fini, cette suite d’instructions sur un support adéquat, cartes perforées à l’époque, disque dur maintenant, pour la réutiliser sans avoir à tout réécrire. Un autre intérêt était de pouvoir écrire des programmes automodifiants. Comme une suite d’instructions composant un programme était traduite sous forme de codes numériques et stockée en mémoire, telles des données, pour être exécutée, il était tout à fait envisageable d’avoir des instructions modifiant les données en mémoire mais également les propres instructions du programme. Cette technique permettait de simuler des instructions non disponibles et d’économiser la place occupée en mémoire (ressource rare au début de l’informatique) en adaptant lesdites instructions au cours de l’exécution du programme. De nos jours, les contraintes à l’origine de cette technique n’existant plus, les programmes automodifiants ne sont plus de mise et sont même considérés comme une mauvaise pratique. En effet, ils compliquent fortement le débogage (les instructions prévues sur papier sont modifiées en cours d’exécution et on a du mal à prévoir ce qui va se passer) et empêchent d’avoir les mêmes instructions exécutées par deux programmes en même temps (car chacun essaie de les modifier). De plus, des techniques récentes d’amélioration des performances telles que le préchargement des instructions (section 5) ou la mémoire cache (chapitre 6) sont difficilement compatibles avec les programmes automodifiants.
1.3 Cycle d’un programme
Assembleur Les premiers programmes étaient écrits directement en code machine, c’est-à-dire que les codes numériques correspondant aux instructions étaient entrés un par un en mémoire par l’utilisateur. Très rapidement, on est passé à la programmation en langage assembleur, dans laquelle des expressions symboliques, appelées « mnémoniques », remplaçaient les codes numériques. Ainsi, au lieu de saisir le code 5ef416 en hexadécimal (ou son équivalent binaire), on écrivait ADD A,B. Cette dernière formulation était beaucoup plus compréhensible pour le programmeur, qui voyait tout de suite qu’il s’agissait d’une addition entre deux nombres stockés quelque part. Cependant, l’ordinateur ne savait toujours travailler qu’avec des codes numériques et, même si ceux-ci avaient chacun un équivalent symbolique, il fallait les transformer pour qu’ils puissent être exécutés. C’était le rôle du programme d’assemblage, qui prenait comme entrée un autre fichier décrivant un programme à l’aide de mnémoniques et qui générait le code numérique équivalent (ou code binaire), permettant ainsi à l’ordinateur d’exécuter les instructions (voir figure 3.1).
Ordinateur et processeur 53
Note
La programmation à l’aide des mnémoniques s’appelle parfois « programmation en langage d’assemblage », et plus couramment « programmation en assembleur ». L’ensemble des codes numériques s’appelle classiquement « langage machine », même si pour certains, celui-ci fait par extension également référence au langage assembleur (par opposition aux langages évolués comme C, C++, Pascal, Java…).
La programmation en assembleur a quand même de sérieux inconvénients. D’abord, il est fastidieux d’écrire des lignes de code car, les instructions étant souvent peu puissantes, il faut en aligner beaucoup pour obtenir un résultat, même simple. Ensuite, les instructions sont spécifiques à un modèle de processeur et tout changement de machine implique une réécriture plus ou moins complète du code.
Compilateur Pour pallier ces défauts, des langages évolués (par exemple C, C++, Java, Pascal, Ada et leurs nombreuses variantes) ont été développés et, de nos jours, il est rare d’avoir à programmer directement en assembleur. Qu’ils soient orientés objet, déclaratifs ou encore impératifs, tous les langages évolués disposent de structures de données et de contrôle évoluées permettant aux développeurs de se concentrer sur l’algorithmique des applications, plutôt que sur l’écriture fastidieuse du code assembleur. Le prix à payer est bien sûr que ces instructions ne sont plus directement compréhensibles par l’ordinateur. Une phase de traduction en langage machine pour obtenir un programme exécutable est nécessaire. C’est le rôle du compilateur, un programme qui prend en entrée un fichier texte contenant le code source écrit en langage évolué pour produire un fichier exécutable formé de codes numériques propres à la machine. Au passage, on a gagné en portabilité. Les langages évolués sont relativement normalisés et le code source d’un programme peut facilement être « porté » sur un autre ordinateur, à la seule condition d’avoir le compilateur prévu pour ce langage, générant des instructions en langage machine adaptées à la nouvelle machine.
Interpréteur L’étape de compilation, nécessaire lors de chaque modification du programme, peut prendre un certain temps, d’autant plus grand que la taille du code est importante. D’autres langages (comme PHP, Perl ou Basic) proposent une autre méthode, qui consiste, non pas à traduire les instructions, mais à les exécuter au fur et à mesure via un interpréteur. Pour chaque ligne de code, ce dernier « simule » son exécution sur l’ordinateur. Il n’y a plus de délai de compilation, celle-ci n’existant plus, mais une exécution directe du programme, qui, malheureusement, tourne beaucoup plus lentement que s’il était compilé. En effet, l’interpréteur doit simuler le fonctionnement des instructions au lieu de laisser l’ordinateur le faire directement (voir figure 3.1). Pour cette raison, les langages interprétés sont plutôt réservés à l’écriture de petits programmes pour lesquels la facilité de développement (on modifie, on exécute), prime sur la rapidité d’exécution. La programmation Java utilise les deux techniques précédentes. Un fichier source en Java est d’abord compilé, mais au lieu de générer des instructions directement pour le processeur, le compilateur produit du code spécifique (appelé Bytecode) qui va ensuite être interprété par la machine virtuelle Java (comme ces instructions sont proches du langage assembleur, l’interprétation peut se faire rapidement). L’avantage se trouve dans la portabilité accrue : au lieu de devoir recompiler le programme sur toutes les machines où l’on désire le faire tourner, il suffit de diffuser le code compilé, sous réserve de disposer d’une machine virtuelle Java. Celle-ci peut être facilement installée sur tous les types d’ordinateurs, assistants personnels, téléphones portables, etc. (voir figure 3.1). Le langage Python fonctionne de manière similaire : chaque ligne de code d’un programme Python est traduite en Bytecode Python qui est immédiatement interprété par la machine virtuelle Python. Mais à la différence de Java, il n’y a pas séparation de ces deux étapes pour l’utilisateur.
Éditeur de liens À la figure 3.1, le compilateur génère ce que l’on appelle un fichier objet, qui n’est pas immédiatement exécutable. Ce fichier est bien constitué d’instructions machine, mais ne constitue pas forcément l’intégralité du programme. Celui-ci est souvent découpé en modules séparés, chacun sous la forme de code source. Une fois chacun d’entre eux compilé (sous forme de fichier objet), il faut les réunir en une seule application : c’est le rôle de l’éditeur de liens. Ce programme prend tous les fichiers objet, récupère diverses bibliothèques standard (parties de programme déjà écrites en langage machine) et regroupe le tout en gérant les dépendances (références intermodules) pour fournir au final une application complète, directement exécutable.
Architecture de l’ordinateur 54
Cycle d’un programme.
1.4 Structure simplifiée d’un ordinateur
La figure 3.2 illustre la structure classique d’un ordinateur actuel en séparant les différents composants en entités fonctionnelles.
Processeur Aussi appelé CPU (Central Processing Unit), le processeur est le véritable cerveau de l’ordinateur. Toutes les avancées technologiques se concentrent sur ce composant, qui travaille toujours plus vite et effectue des opérations de plus en plus compliquées. Autrefois agglomérat de circuits physiquement séparés, le microprocesseur est né en 1971 (là encore, le préfixe « micro », à l’origine synonyme de petite taille par rapport aux processeurs sur les gros systèmes, a disparu des dénominations courantes). On est passé de deux mille trois cents transistors (le composant de base des circuits informatiques) pour le premier microprocesseur à plusieurs centaines de millions actuellement. Le rôle du processeur est d’exécuter les instructions composant le programme. Il se charge de tous les calculs mathématiques et des transferts de données internes et externes. Il décide (en fonction bien sûr des instructions du programme en cours d’exécution) de ce qui se passe à l’intérieur de l’ordinateur.
Figure 3.1
Ordinateur et processeur 55
Architecture de l’ordinateur 56
Structure d’un ordinateur.
Stockage Des données peuvent être stockées dans plusieurs endroits sur l’ordinateur. La zone la plus importante en taille est le disque dur, où données et programmes sont archivés de façon permanente. Cependant, sa relative lenteur (par rapport à la vitesse de fonctionnement du processeur) ne permet pas son utilisation lors de l’exécution des programmes. Pour pouvoir exécuter une application, il faut amener les instructions la composant ainsi que les données dont elle a besoin dans une mémoire beaucoup plus rapide (c’est-à-dire d’où on peut extraire très vite une information précise) ; il s’agit de la mémoire principale. Elle est constituée de circuits intégrés (pièce électronique dans un boîtier composée de nombreux transistors gravés dans un matériau semi-conducteur) dont la cellule de base est une bascule (voir chapitres 2 et 5). L’unité de base est l’octet (8 bits) et on peut voir la mémoire comme un ensemble ordonné d’octets dans lequel chaque case mémoire (donc chaque octet) a une adresse numérique. La mémoire principale est un composant passif dans le sens où elle ne fait qu’obéir à des commandes. Le processeur peut lui demander de stocker une donnée à une adresse précise (écriture mémoire) ou de fournir une donnée se trouvant à telle ou telle adresse (lecture mémoire). Dans les deux cas, la mémoire effectue l’opération et attend la demande suivante. Le processeur est relié à la mémoire via le bus principal de l’ordinateur (ensemble de fils véhiculant les informations et les commandes). Comme le processeur est en permanence en train de travailler avec la mémoire (car il y récupère tout ce dont il a besoin, données et instructions), le bus doit être le plus efficace possible. L’augmentation des performances de l’ordinateur passe également par l’amélioration de la bande passante de ce bus. Celle-ci indique simplement le débit d’informations pouvant circuler sur le bus (en octets par seconde) ; plus il est important, plus le processeur peut travailler rapidement avec la mémoire. Le progrès technologique a permis de construire des boîtiers mémoire de grande capacité et pouvant répondre rapidement aux sollicitations du processeur. Mais cette amélioration est restée bien en deçà de la formidable accélération des processeurs. Ceux-ci passaient une bonne partie de leur temps à attendre que la mémoire réagisse aux demandes, d’où une perte d’efficacité importante due à ces temps d’attente. Il a donc fallu compliquer un peu le schéma en intercalant entre la mémoire principale et le processeur une mémoire encore plus rapide (mais plus chère et de capacité moindre), appelée « mémoire cache » ou simplement « cache ». Comme la contrainte majeure est la vitesse de réaction et de transfert, ce cache est directement en prise avec le processeur, comme illustré à la figure 3.2. Cette mémoire spéciale permet d’accélérer encore plus les échanges de données avec le processeur, utilisant celui-ci au maximum de ses capacités (voir chapitre 6).
Figure 3.2
Entrées/sorties Réduit au processeur et à la mémoire, un ordinateur ne présenterait guère d’intérêt dans ce sens qu’il lui manquerait la possibilité de communiquer avec l’extérieur. Le système d’entrées/sorties regroupe l’ensemble des composants (appelés « périphériques ») permettant à l’ordinateur d’échanger de l’information avec le monde extérieur (clavier, souris, scanner, écran, carte son, imprimante…) et de stocker des informations de manière permanente et de les relire (disque dur, CD/DVD, bandes magnétiques, clés amovibles…). Les entrées/sorties se caractérisent par leur variété et leur flexibilité. Il faut pouvoir connecter à l’ordinateur divers périphériques, répondant à des commandes différentes et fonctionnant sur une plage de « vitesses » extrêmement large. De plus, les entrées/sorties sont la partie la plus mouvante de l’ordinateur. Alors que le système processeur-mémoire forme un socle à peu près inchangé dans la vie d’un ordinateur, fréquemment l’utilisateur change de périphérique ou ajoute un nouveau dispositif d’entrées/sorties. Pour ces raisons, on ne peut pas relier directement les entrées/sorties au bus principal car cela figerait complètement les possibilités d’évolution. De plus, on peut sans inconvénient découpler tout le système d’entrées/sorties, qui fonctionne à des vitesses bien moins importantes que le reste, et le bus principal, donc la caractéristique première est de permettre les échanges de données les plus rapides possibles. On branche donc les différentes entrées/sorties sur un bus d’entrées/sorties secondaire, normalisé suivant des standards internationaux, afin de garantir une compatibilité de tous les matériels et une évolution aisée. La seule exception à cette règle est maintenant la carte vidéo car les besoins en visualisation ont augmenté de façon exponentielle. La complexité des affichages graphiques actuels (taille de l’écran, profondeur des couleurs, plusieurs images par seconde, textures réalistes, 3D…) nécessite un énorme débit d’informations entre le processeur et la carte vidéo (chargée de piloter l’affichage), débit que ne pourrait offrir le bus d’entrées/sorties beaucoup trop lent. Ainsi, la carte vidéo se retrouve connectée directement au bus principal de l’ordinateur via le contrôleur système (voir figure 3.2). Un dernier composant apparaît à la figure 3.2 : il s’agit du contrôleur système. Avec l’ensemble des éléments qui essaient de communiquer avec le processeur, il risquerait d’y avoir des conflits d’accès au bus principal. Le contrôleur gère donc les différentes demandes pour garantir à chacun un libre accès au bus. Il permet également le passage des informations du bus d’entrées/sorties au bus principal (et réciproquement) en gérant les différences de format de données et de vitesse de transfert entre les deux bus.
1.5 Structure interne d’un processeur
Sur la puce en silicium regroupant quelques centaines de millions de transistors, on trouve à peu près les éléments présentés sur le schéma de la figure 3.3 : une unité de calcul (UAL), une zone de stockage des données (registres) et un élément dirigeant le tout (séquenceur).
Calcul et mémorisation On peut distinguer des zones fonctionnelles bien définies à l’intérieur du processeur. Citons d’abord l’unité arithmétique et logique (UAL), où s’effectuent les opérations mathématiques. Comme on peut le voir sur la figure, l’UAL prend les opérandes des calculs depuis les registres et renvoie le résultat également dans les registres. Ceux-ci correspondent à une zone de stockage interne du processeur, ce qui permet un accès rapide (beaucoup plus rapide que si les données provenaient directement de la mémoire). Pour alimenter ces registres, le processeur cherche les données en mémoire principale et les ramène via le bus principal. À l’arrivée, ces informations sont traitées par le composant marqué « interface avec le bus », qui adapte les signaux circulant entre le processeur et l’extérieur. En fonction de ce qui arrive, il dispatche les bits sur l’une ou l’autre des zones internes. Ainsi, si une donnée provenant de la mémoire est acheminée jusqu’au processeur pour un calcul mathématique, elle est d’abord envoyée dans l’un des registres pour ensuite se retrouver au niveau de l’UAL. Réciproquement, le résultat d’un calcul est temporairement mis dans l’un des registres (ce qui permet une réutilisation immédiate pour un autre calcul) et peut ensuite être renvoyé vers le bus pour un stockage de plus longue durée en mémoire principale. Tous ces liens sont indiqués à la figure 3.3 en traits doubles car ils correspondent à un transfert, non pas de 1 bit, mais de plusieurs en parallèle (leur nombre étant lié à la taille des registres et de l’UAL). L’UAL, à base de circuits combinatoires, n’a pas de capacité propre de mémorisation. Il faut cependant garantir la présence sur ses entrées des opérandes pendant le temps nécessaire au calcul. C’est le rôle des tampons (buffer) situés avant l’UAL. Simples mini-registres de stockage, ils assurent la présence (en les mémorisant temporairement) aux entrées de l’UAL des données provenant des registres principaux. De même, un tampon en sortie de l’UAL permet d’être sûr de disposer du résultat le temps qu’un registre le mémorise, libérant au passage l’UAL.
Ordinateur et processeur 57
Architecture de l’ordinateur 58
Structure interne d’un processeur.
Commande Les registres et l’UAL sont régis par des commandes. L’UAL doit savoir quel calcul effectuer (addition, soustraction, multiplication…) et un registre sélectionné peut avoir à envoyer l’information mémorisée sur l’une des entrées de l’UAL ou bien à la transférer vers le bus principal. Le séquenceur, aussi appelé « unité de contrôle », est le chef d’orchestre du processeur. Il a en charge l’envoi des commandes aux différents circuits internes en fonction des instructions à exécuter. À cet effet, il récupère les instructions (en mémoire principale) depuis l’interface via le bus et les stocke une à une dans le registre d’instructions (RI) pendant l’exécution. Il décide alors quels sont les transferts de données nécessaires (registre vers UAL, bus vers registre…) et les commandes à envoyer (lecture ou écriture dans un registre, opération de calcul…), d’où les liens qui le relie à tous les autres circuits. Le séquenceur est LE composant actif du processeur : il décide ce qui doit se passer à l’intérieur. C’est non seulement le plus important mais le plus compliqué des circuits internes. Plus le processeur est puissant, plus il peut effectuer d’opérations, et plus le séquenceur doit être complexe car il doit gérer des ordres internes élaborés. Le travail du séquenceur est régi par une horloge, c’est-à-dire un circuit électronique qui rythme l’activité de l’unité de contrôle par des tops électroniques à intervalles réguliers. Le rôle du séquenceur est alors de produire les commandes pour les autres circuits internes du processeur. Plus l’horloge est rapide, plus le séquenceur et donc le processeur peuvent travailler vite. Mais, bien sûr, cela nécessite des circuits plus compliqués, prenant plus de place sur la puce, consommant plus de courant et chauffant davantage. Pour finir, on trouve à la figure 3.3 un registre PC, qui sert à récupérer la prochaine instruction à exécuter (voir sections suivantes) ainsi que la mémoire cache de niveaux 1 et 2 (historiquement séparée du processeur mais maintenant intégrée à la puce) qui sert à accélérer les transferts entre la mémoire principale et le processeur (voir chapitre 6).
Figure 3.3
2. LES INSTRUCTIONS
Chaque processeur est capable d’exécuter des instructions se trouvant en mémoire principale. Si elles n’y sont pas, on va d’abord les y mettre en les chargeant depuis leur support de stockage (disque dur, CD/DVD, bande magnétique, clé amovible…). Une instruction se caractérise par son code numérique correspondant à l’opération requise. Les codes sont stockés en mémoire à la suite les uns des autres dans des cases mémoire successives. On peut ainsi repérer chaque instruction par son adresse, en l’occurrence celle de sa case de stockage. Pour exécuter une instruction, le processeur envoie un ordre de lecture à la mémoire en indiquant l’adresse de l’instruction souhaitée. La mémoire renvoie alors le code numérique au processeur, qui exécute l’instruction et passe à la suivante. L’ensemble des instructions qu’un processeur peut exécuter, autrement dit son jeu d’instructions (Instruction Set), et la correspondance entre chacune d’entre elles et son code numérique, sont définis par le constructeur du processeur et lui sont propres. Ainsi, un programme, c’est-à-dire une suite de codes numériques d’instructions, ne peut s’exécuter que sur un ou plusieurs modèles précis de processeurs. Classiquement, un constructeur cherche une compatibilité ascendante lors de l’évolution de sa gamme : un processeur plus récent voit son jeu d’instructions élargi par de nouvelles fonctionnalités, qui s’ajoutent aux précédentes, ce qui permet d’exécuter des programmes prévus pour un processeur plus ancien. Parfois un constructeur fabrique volontairement un processeur ayant un jeu d’instructions identique à celui d’un processeur concurrent : mêmes instructions et mêmes codes numériques. Il peut ainsi exploiter les mêmes programmes.
2.1 Types d’instructions
Nous allons présenter, dans les sections suivantes, les différents types d’instructions que l’on trouve classiquement dans le jeu d’instructions des processeurs. Nous les avons regroupées selon cinq catégories, qui correspondent à des grands domaines d’actions différents.
Transfert de données Le programmeur a la possibilité de demander explicitement le transfert de données entre la mémoire et un registre (ou entre deux registres). L’instruction spécifie la case mémoire cible, le registre, ainsi que la taille de la donnée à transférer. En effet, chaque case mémoire correspond à 1 octet alors que les registres ont souvent une taille égale à 4 ou 8 octets. Le programmeur doit donc indiquer dans l’instruction le nombre d’octets à transférer : si c’est plus d’un, on va les chercher dans des cases mémoire successives. Quand on ne remplit pas complètement un registre, il faut indiquer s’il est nécessaire de prévoir une extension de signe pour compléter les bits du registre (voir chapitre 1, section 2.3).
Opérations arithmétiques et logiques, décalages et rotations Les instructions arithmétiques et logiques permettent d’effectuer les calculs sur des données se trouvant dans les registres. Il est ainsi possible de faire une addition, une soustraction, une multiplication ou une division sur des nombres entiers. Les mêmes opérations existent sur des nombres flottants, ainsi que des fonctions mathématiques classiques (racine carré, fonctions trigonométriques et exponentielles…). Chaque instruction permet une opération. On définit des calculs plus élaborés instruction par instruction en veillant aux transferts des différents opérandes et des résultats intermédiaires entre registres et UAL. L’UAL est également capable de réaliser les opérations booléennes de base (NON, ET, OU, XOR) sur des données se trouvant dans les registres. Comme ces opérateurs travaillent au niveau du bit, la donnée du registre n’est plus considérée comme un nombre entier mais comme une suite de bits indépendants. Ainsi, un ET entre deux registres prend chacune des deux valeurs stockées et effectue l’opération sur chacun des bits en parallèle (voir figure 3.4).
Figure 3.4
ET sur 8 bits en parallèle.
Ordinateur et processeur 59
Architecture L’UAL est également capable d’exécuter des instructions de décalage ou de rotation des bits de la donnée d’un registre. La rotation consiste à remplacer chaque bit par celui situé directement à gauche ou à droite (suivant le sens de l’opération). Le bit qui n’a pas de voisin « fait le tour » et prend la place du bit opposé (voir figure 3.5). Hormis cette dernière étape, le décalage est identique à la rotation, à ceci près qu’un bit disparaît et un 0 (éventuellement un 1, voir chapitre 4 pour un exemple) est mis dans le premier bit (voir figure 3.5). Cette opération est intéressante car un décalage à gauche représente une multiplication par 2 (chaque bit vient occuper la place correspondant à la puissance de 2 supérieure), qui s’exécute beaucoup plus rapidement qu’une opération de multiplication proprement dite. De même, un décalage vers la droite est équivalent à une division par 2 (mais beaucoup plus rapide que la version classique) de la valeur sur laquelle s’opère le décalage.
Figure 3.5
Rotation et décalage d’un registre.
Tests et comparaisons Les instructions de tests permettent de comparer deux données (égalité, inégalité) afin de définir un comportement différent suivant le résultat de la comparaison. Les données ne sont pas modifiées, mais le résultat du test est indiqué dans un registre spécial (le registre d’état, voir section 3) que l’on pourra examiner lors d’instructions suivantes pour permettre des exécutions différenciées.
Ruptures de séquence Le processeur exécute normalement les instructions successives en mémoire. Cependant, ce comportement ne permet pas d’avoir des exécutions différentes suivant les données. Il est nécessaire de s’affranchir de cette linéarité en autorisant des ruptures de séquence. Il s’agit d’instructions dont le seul objectif est d’indiquer l’adresse de la prochaine instruction à exécuter (en lieu et place de celle, en mémoire, qui aurait dû l’être, rompant ainsi le comportement par défaut). Prenons pour exemple la résolution d’une équation du premier degré Ax+B=0. L’algorithme pour trouver la solution est le suivant : 1. Tester si A est nul. 2. Si c’est le cas, tester si B est nul. 3. Si c’est le cas, il y a une infinité de solutions, sinon il n’y en a pas. 4. Si A est différent de 0, la solution de l’équation est x =− AB. On peut en donner une représentation graphique (voir figure 3.6).
Figure 3.6
Organigramme de la résolution de l’équation.
Il est cependant nécessaire de la transposer sous une forme linéaire pour pouvoir charger le programme en mémoire. Il faut alors écrire les différentes branches d’exécution les unes après les autres. Pour autant, il ne s’agit pas de les exécuter à la suite, mais d’en sauter certaines compte tenu des résultats des tests. On dispose
60 de l’ordinateur
Programme de la résolution de l’équation.
Les symboles 1, 2 et 3 désignent un endroit dans la séquence d’instructions, c’est-à-dire une instruction précise ; on les appelle « étiquettes ». Lors de la traduction en langage machine d’un programme, le programme d’assemblage associe à chaque étiquette l’adresse mémoire de l’instruction correspondante afin de pouvoir remplacer l’étiquette, dans les instructions de branchement, par l’adresse de l’instruction cible.
Instructions divers Les autres instructions d’un jeu standard concernent les entrées/sorties (possibilité d’envoyer directement une commande à un périphérique), le contrôle du processeur (arrêter ou redémarrer un processeur), la gestion des interruptions (voir chapitre 8), etc.
2.2 Format des instructions
Une instruction processeur peut être découpée en deux parties : l’opération elle-même et les données sur lesquelles elle porte. La première partie, appelée « code opération », correspond au mnémonique utilisé par l’assembleur (ADD, MOV, SUB…), alors que la seconde doit être spécifiée via des modes d’adressage qui permettent d’indiquer où sont les données (en mémoire, dans un registre, mises explicitement dans l’instruction…). Chacune de ces deux parties intervient dans le code numérique final de l’instruction. Par exemple, les 8 premiers bits de l’instruction peuvent indiquer le code opération voulu tandis que les 24 autres bits décrivent les données. Ce découpage est le fait du constructeur lorsqu’il définit le jeu d’instructions de son processeur.
Code opération Ce code indique au processeur quelle opération effectuer parmi toutes celles autorisées. Le mnémonique correspondant se traduit en une valeur numérique dont les bits spécifient quelles actions (transfert de données, calcul…) doivent intervenir à l’intérieur du processeur pour l’exécution de l’instruction. Ces bits du code opération sont utilisés par le séquenceur pour l’envoi des commandes aux différents composants internes du processeur.
Nombre d’opérandes La plupart des opérations arithmétiques nécessite de spécifier trois données : les deux sur lesquelles portent l’opération (addition, soustraction…) ainsi que l’emplacement où ranger le résultat (qui, sinon, est perdu). Par exemple, le concepteur d’un jeu d’instructions peut décider que ADD r1,r2,r3 additionne les valeurs se trouvant dans les registres r2 et r3, et place le résultat dans le registre r1. C’est une convention assez classique d’indiquer, comme ici, la destination en premier dans la liste des données d’une instruction, mais le concepteur peut décider qu’il faut écrire ADD r2,r3,r1 pour obtenir le même résultat. Quasiment tous les processeurs actuels proposent cette souplesse d’utilisation, en autorisant la mention de plusieurs registres dans les instructions, mais cela a deux inconvénients : d’abord, la gestion interne des transferts de données au sein du processeur s’en trouve compliquée puisque tous les chemins deviennent
de deux types de ruptures de séquence : les sauts (aussi appelés « branchements ») inconditionnels, qui transfèrent systématiquement l’exécution à une autre adresse (au lieu que s’exécute l’instruction suivante en mémoire), et les sauts conditionnels, qui s’effectuent uniquement si une condition est vérifiée (par exemple, si certains bits du registre d’état ont des valeurs précises) ; dans le cas contraire, le saut n’est pas effectué et l’exécution se poursuit normalement à l’instruction suivante en mémoire. La figure 3.7 présente l’écriture « linéaire » de l’algorithme de résolution de l’équation (les flèches illustrent les sauts mais ne font pas partie du programme, bien sûr).
Figure 3.7
Ordinateur et processeur 61
Architecture de l’ordinateur 62 possibles pour une donnée, obligeant à avoir un séquenceur plus conséquent ; ensuite, il faut prévoir une taille suffisante pour les codes numériques des instructions puisqu’il y a trois données à spécifier par des valeurs numériques. Historiquement, la mémoire principale n’était pas conséquente dans les ordinateurs et ce dernier désavantage était ressenti comme un gros handicap. Il fallait absolument minimiser la place mémoire occupée par un programme et l’une des méthodes était de minimiser la taille des instructions. Celles-ci ne pouvaient bien souvent expliciter que deux adresses de données, l’une des deux servant implicitement de destination : ADD r1,r2 additionnait la valeur des registres r1 et r2 et rangeait le résultat dans r1 (par convention). Ce que l’on gagnait en place mémoire (deux données à spécifier au lieu de trois, d’où des codes numériques d’instructions plus courts), on le perdait en souplesse d’utilisation puisque le programmeur devait jongler avec l’affectation des registres.
Remarque
Parmi les premiers processeurs, certains avaient poussé le concept encore plus loin en imposant un registre spécial (appelé « accumulateur »), qui servait implicitement pour toutes les opérations arithmétiques et logiques. On ne devait plus le spécifier dans l’instruction : ADD r1 additionnait le registre r1 avec l’accumulateur et mettait le résultat dans ce dernier. Les possibilités de programmation étaient encore plus rigides (il fallait constamment transférer les données entre la mémoire et les registres), mais les instructions prenaient peu de place et le séquenceur était simple, ce qui était important à une époque où la place sur la puce (en nombre de transistors) était restreinte.
Taille des instructions Toutes les instructions ne font pas intervenir trois données. Certaines opérations arithmétiques (prendre l’opposé d’un nombre par exemple) ou logique (calculer le NON d’une valeur binaire) n’en nécessitent que deux : le nombre source sur lequel s’exécute l’opération, et la destination. De même, les transferts de données se font entre deux endroits à spécifier. Les sauts, quant à eux, n’ont besoin que d’une information, l’adresse cible où poursuivre l’exécution. Il y a donc un nombre variable de données pour les instructions et, de plus, toutes les données ne nécessitent pas le même nombre de bits (il en faut beaucoup plus pour indiquer des adresses mémoire que des registres, moins nombreux). Il est donc naturel de prévoir des instructions de longueur variable utilisant le nombre de bits nécessaire : peu s’il y a peu de données dans l’instruction, beaucoup si elles sont nombreuses ou compliquées. Et c’est effectivement ainsi que fonctionnaient les anciens processeurs, la mémoire étant occupée de façon efficace par un programme. Malheureusement, cela voulait aussi dire qu’il était lent et compliqué pour le processeur d’exécuter une instruction car il ne pouvait pas savoir à l’avance ce qui l’attendait lorsqu’il récupérait un code numérique : fallait-il charger 2, 3, 4, voire plus d’octets pour avoir l’instruction en totalité ? Où étaient les limites des adresses de chaque donnée dans cette suite de bits ? Le résultat était un séquenceur lent et complexe, qui devait être capable de traiter tous les cas. Le désir d’accélérer les processeurs a conduit à une simplification radicale du jeu d’instructions de la plupart des processeurs (aidée par l’augmentation des capacités mémoire qui rendait moins problématique l’accroissement de la taille des programmes) sous la forme d’instructions de taille fixe, souvent 32 bits. En rationalisant l’expression des données des instructions, on a paradoxalement simplifié le séquenceur et donc permis son optimisation.
2.3 Modes d’adressage
Chaque processeur possède plusieurs modes d’adressage pour les instructions, qui permettent de préciser, dans celles-ci, la localisation des données. L’existence de modes d’adressage variés pour l’accès aux données s’explique souvent par un souci de simplification des accès aux structures de données complexes des langages évolués, permettant ainsi au compilateur une traduction plus facile des programmes en code assembleur.
Adressage immédiat Le plus simple est de pouvoir préciser la donnée directement dans l’instruction, sans avoir à la stocker quelque part (mémoire ou registre) avant. Ainsi, une instruction ADD r1,r2,#3 ajoute la valeur 3 (précisée dans l’instruction) au registre r2 et range le résultat dans r1. Le terme « adressage immédiat » vient du fait que la donnée est immédiatement disponible dans l’instruction sans que le processeur ait besoin de faire un nouvel accès mémoire pour la récupérer. L’inconvénient est qu’elle doit être indiquée dans l’instruction et ne peut donc pas dépendre d’un calcul antérieur ; c’est donc forcément une constante. Il est assez classique d’utiliser le caractère # pour symboliser une donnée immédiate, et pas un numéro de registre ou une adresse mémoire (même si certains programmes d’assemblage ont une convention différente). De même, l’écriture de la constante est souvent en hexadécimal par défaut.
Adressage par registre L’un des endroits où une valeur peut être stockée est bien sûr l’un des registres du processeur. Il faut donc avoir la possibilité de le désigner comme source ou destination dans les instructions. Tous les programmes d’assemblage permettent d’utiliser le mode d’adressage par registre simplement en indiquant le nom du registre voulu. Chaque processeur a sa propre convention de nommage : des modèles anciens, avec peu de registres, attribuaient à chacun une simple lettre comme A ou B (ADD A,B affecte la somme du registre A et du registre B à A) et leur confiaient des rôles spécifiques (certains pour les opérations arithmétiques, d’autres pour les accès mémoire) ; mais il est maintenant plus courant d’avoir des registres ayant des fonctions identiques, et portant un numéro : D0 à D7, r0 à r255, etc.
Adressage direct On peut faire référence à une case mémoire précise directement dans l’instruction en donnant son adresse. L’instruction MOVE r1,3afc (notez l’absence de #) prend la donnée se trouvant en mémoire à l’adresse hexadécimale 3afc16 pour la mettre dans le registre r1. Dans le modèle de processeur de la figure 3.3, l’UAL ne pouvant être alimentée que par les registres, on ne pourra pas utiliser ce mode d’adressage direct pour des instructions arithmétiques, mais seulement pour des instructions de transfert mémoire vers un registre, ou l’inverse. L’inconvénient de ce mode d’adressage est bien sûr qu’il faut connaître l’adresse souhaitée lors de l’écriture du programme. Or celle-ci peut dépendre de l’emplacement où va être chargé le programme au moment de son exécution. On peut alors remplacer l’écriture littérale de l’adresse par une étiquette (préalablement définie et associée à une case mémoire) et laisser le programme d’assemblage faire la correspondance avec l’adresse mémoire. Un autre inconvénient de ce mode d’adressage est qu’il oblige à avoir beaucoup de bits dans l’instruction pour coder l’adresse. C’est pourquoi on lui préfère souvent le mode d’adressage qui suit pour les références mémoire.
Adressage indirect par registre Au lieu d’utiliser directement une adresse mémoire dans l’instruction, on peut indiquer où trouver cette adresse, dans un registre par exemple. Il faut distinguer ce mode d’adressage indirect du mode d’adressage par registre. En mode registre, la donnée utilisée dans l’instruction est la valeur contenue dans le registre alors qu’en adressage indirect, c’est l’adresse mémoire de la donnée qui est dans le registre (voir figure 3.8).
Figure 3.8
Adressage indirect par registre.
Pour les distinguer, on note le mode d’adressage indirect en mettant le registre entre parenthèses ou entre crochets : MOVE r3,(r2) charge dans le registre r3 la valeur située en mémoire à l’adresse se trouvant dans r2. Il y a deux avantages à spécifier ainsi les adresses : d’abord l’instruction nécessite moins de bits car il n’y a qu’un numéro de registre à indiquer ; ensuite il est facile de changer cette adresse par une simple opération arithmétique sur le registre. Si l’on veut parcourir un tableau d’octets en mémoire, il suffit d’initialiser le registre avec l’adresse du premier élément, puis de l’incrémenter pour qu’il « pointe » sur l’octet suivant (c’est-à-dire qu’il contienne son adresse). Les modes d’adressage précédents sont universels et existent sur tous les processeurs. On peut également trouver, suivant les modèles, des modes d’adressage plus « exotiques » et donc moins systématiques.
Adressage indirect avec déplacement On peut combiner le mode d’adressage indirect avec un décalage. C’est le mode indirect avec déplacement. L’adresse de la donnée est la somme de l’adresse contenue dans un registre (mode indirect) et d’un
Ordinateur et processeur 63
Architecture déplacement immédiat indiqué dans l’instruction. MOVE r5,8(r2) met dans r5 la valeur dont l’adresse mémoire est obtenue en ajoutant 8 à celle contenue dans r2 (voir figure 3.9)
Figure 3.9
Adressage indirect avec déplacement.
Une utilisation classique est l’accès à une structure de données composée de plusieurs champs. On initialise le registre avec l’adresse mémoire du début de la structure et les différentes valeurs du déplacement permettent d’accéder aux différents champs sans changer la valeur du registre.
Adressage indirect avec post-incrémentation ou pré-décrémentation L’adressage indirect est tellement utile pour parcourir un tableau que certains processeurs le décline sous deux formes :
• Avec post-incrémentation, il permet, en une seule instruction, non seulement d’accéder à une donnée en mémoire dont l’adresse est dans un registre (mode indirect), mais en plus d’incrémenter le registre de la taille de l’élément pointé (souvent 1, 2 ou 4 octets). On peut ainsi préparer l’accès à l’élément suivant (en ayant maintenant son adresse dans le registre). On le note (r0)+.
• L’adressage symétrique, dit « indirect avec pré-décrémentation » et noté -(r0), retranche la taille de l’élément avant d’accéder à la mémoire. On parcourt ainsi un tableau en sens inverse.
Adressage indirect indexé L’adressage indirect avec déplacement souffre du même défaut que l’adressage direct : la valeur du déplacement doit être indiquée « en dur » dans l’instruction et ne peut pas être calculée dynamiquement lors de l’exécution. Pour cela, il faudrait qu’elle soit dans un registre. C’est exactement ce que permet l’adressage indirect indexé. L’adresse mémoire de la donnée est la somme du contenu d’un registre de base (mode indirect) et d’un registre jouant le rôle d’un déplacement (voir figure 3.10) : MOVE r7,(r2,r1).
Figure 3.10
64 de l’ordinateur Adressage indirect indexé. Certains processeurs autorisent même un mode indexé avec déplacement : MOVE r4,4(r0,r3) somme les deux registres r0 et r3 avant d’ajouter la valeur 4 pour trouver l’adresse mémoire de la donnée voulue. Plus le processeur propose de modes d’adressage différents et complexes, plus le séquenceur a de travail pour décoder les instructions et plus il est difficile de l’optimiser pour améliorer ses performances.
3. UAL ET REGISTRES
L’UAL et les registres font partie des composants internes du processeur qui obéissent aux commandes du séquenceur, envoyées en fonction des instructions exécutées.
3.1 Construction d’une UAL
L’UAL est un circuit logique combinatoire formé de portes logiques prenant deux nombres en entrée et générant un nombre en sortie en fonction de signaux de commande indiquant l’opération, arithmétique ou logique, à effectuer. Une UAL peut être caractérisée par sa taille et ses possibilités. Sa taille, ou largeur, correspond au nombre maximum de bits que peuvent occuper les entrées, autrement dit à la taille maximale des nombres que l’UAL peut traiter. Elle est évidemment fortement liée à la taille des nombres que les registres peuvent stocker puisque ce sont les mêmes qui passent par l’UAL. Il est toujours possible de travailler avec des nombres plus grands, mais il faut alors découper l’opération : on peut additionner de deux nombres de 64 bits dans une UAL de 32 bits de large en ajoutant d’abord les 32 bits de poids faible puis les 32 bits de poids fort, mais cela nécessite au moins deux instructions. Inversement, calculer sur des nombres de 32 bits dans l’UAL ne présente pas d’intérêt si les registres ne peuvent pas stocker plus de 16 bits. Les possibilités de l’UAL correspondent simplement aux différentes commandes qu’elle reconnaît : elle peut certainement faire une addition et une soustraction, mais qu’en est-il des multiplications et divisions ? Toutes les fonctions logiques sont-elles possibles ? Le constructeur d’un processeur a toujours la possibilité d’étendre les capacités de l’UAL (en autorisant des opérations plus complexes) ou d’augmenter sa taille (pour permettre la manipulation de nombres plus grands). Mais cela implique d’utiliser plus de portes logiques et donc d’occuper plus de place sur la puce, au détriment des autres circuits. Un dernier paramètre crucial de l’UAL est sa vitesse de fonctionnement. Puisqu’elle est sollicitée à chaque instruction de calcul, sa rapidité influence directement la vitesse d’exécution. Il faut donc en premier lieu optimiser ce critère.
Exemple d’UAL 1 bit La figure 3.11 montre un exemple d’UAL 1 bit simplifiée. Elle est capable de calculer le ET et le OU de 2 bits, le NON du second bit, et la somme des 2 bits avec une retenue d’entrée. Le choix parmi ces quatre opérations se fait via les deux lignes de commandes f0 et f1. Suivant la valeur de ces 2 bits, un décodeur active une des quatre lignes de sortie, sélectionnant soit une des trois fonctions logiques (ab, a + b, b ), soit la retenue et la sortie de l’additionneur.
Figure 3.11
UAL 1 bit simplifiée.
Ordinateur et processeur 65
Architecture de l’ordinateur 66 Pour concevoir une UAL plus large, il suffit de « chaîner » plusieurs UAL 1 bit, reliant la retenue de sortie d’un étage à la retenue d’entrée du suivant.
Plusieurs UAL L’exemple précédent concernait une UAL effectuant une addition sur un nombre entier. Les circuits nécessaires au calcul sur des nombres flottants sont totalement différents et on ne gagnerait rien à les incorporer au même circuit combinatoire. Les processeurs ont donc maintenant deux UAL distinctes, une pour les opérations logiques et pour les calculs entiers, une autre pour les opérations en virgule flottante. L’avantage est de pouvoir accélérer les traitements en effectuant deux calculs simultanés, un dans chaque UAL.
3.2 Registres
Les registres sont une zone de stockage temporaire des données située dans le processeur. Ils sont construits à l’aide de circuits logiques séquentiels afin de pouvoir mémoriser des bits. Leur intérêt principal est de pouvoir travailler avec des données localisées directement dans le processeur et donc d’un accès beaucoup plus rapide que celles situées en mémoire principale.
Registres généraux Les registres généraux (regroupés dans un banc de registres) sont à la disposition du programmeur en assembleur (ou du compilateur si l’on code en langage évolué), qui les utilise à sa guise dans les instructions pour manipuler des données. On a évidemment intérêt à travailler au maximum avec les registres généraux et à n’utiliser le stockage en mémoire qu’en dernier ressort car cela ralentit fortement l’exécution des instructions. Suivant les processeurs, on dispose d’une dizaine à une centaine de registres généraux. Plus ils sont nombreux, moins le programme fait appel à la mémoire, mais plus les circuits prennent de la place sur la puce. Ces registres sont caractérisés, comme l’UAL, par leur taille : combien de bits peuvent-ils stocker ? Depuis plusieurs années, les processeurs sont capables de travailler avec des nombres de 32 bits et les registres pour les nombres entiers sont classiquement de cette largeur, comme l’UAL correspondante. Les processeurs récents possèdent maintenant des registres de 64 bits. Cependant, deux problèmes se présentent. D’abord il n’y a aucun moyen de distinguer, une fois mis dans un registre, un nombre entier d’un nombre flottant ; or les calculs doivent se faire dans des UAL différentes. Ensuite, il existe une norme de représentation des flottants sur 64 bits et il faut bien pouvoir les mémoriser dans le processeur. Ces deux raisons font qu’il existe deux bancs de registres dans un processeur : l’un pour stocker les nombres entiers, reliés à l’UAL entière, et l’autre pour les nombres flottants, reliés à l’UAL flottante. Chaque banc de registres est situé au plus près de l’UAL correspondante ; les transferts s’en trouvent accélérés. Il faut alors pouvoir distinguer les registres entiers et flottants dans les instructions et les modes d’adressage. C’est pourquoi on les nomme différemment, par exemple r0 pour un registre de type entier et f0 pour un flottant. Les instructions arithmétiques agissant sur chaque type portent également des noms différents de sorte qu’on ne les confonde pas (ADD et FADD par exemple). Ces bancs de registres sont un peu plus complexes que les circuits séquentiels traditionnels car, comme chaque instruction peut avoir deux registres comme source (par exemple ADD r1,r2,r3), chaque banc autorise deux accès simultanés permettant de récupérer les deux valeurs souhaitées en une seule opération. En plus des registres généraux, chaque processeur possède des registres spécialisés nécessaires au bon déroulement des instructions.
Registre d’instruction Lorsqu’une instruction est récupérée en mémoire pour être exécutée dans le processeur, elle est mémorisée dans un registre spécial : le registre d’instruction (RI ou IR, Instruction Register, voir figure 3.3). Le séquenceur utilise ce lieu de stockage pour disposer de l’instruction et des bits la composant pendant tout le temps de son exécution. Il gère entièrement l’utilisation de ce registre et le programmeur n’y a jamais accès.
Compteur ordinal Avant son exécution, un programme est mis en mémoire, ses instructions étant placées les unes à la suite des autres. Chacune est donc à une adresse précise, qu’il faut envoyer au boîtier mémoire lorsque le processeur veut récupérer ladite instruction pour l’exécuter. Il doit donc à tout moment savoir quelle est la prochaine instruction à exécuter et surtout quelle est son adresse. Un registre spécial, appelé « compteur ordinal » (ou
encore, suivant les modèles de processeurs, « PC » pour Program Counter, ou « IP » pour Instruction Pointer) contient l’adresse en question (voir figure 3.3). Pour exécuter une instruction, le processeur commence par envoyer un ordre de lecture mémoire associé à la valeur contenue dans PC (d’où le lien entre PC et l’interface avec le bus à la figure 3.3) avant de récupérer l’instruction. Le processeur incrémente alors PC de la taille de l’instruction pour que le registre pointe sur la suivante (rappelons que chaque adresse mémoire correspond à 1 octet et qu’une instruction est longue de plusieurs octets ; PC doit donc être augmenté du nombre d’octets de l’instruction, et non de 1). La figure 3.12 montre le début de l’exécution d’une instruction : sa récupération à l’adresse contenue dans PC, le stockage dans RI et l’incrémentation de PC.
Figure 3.12
Incrémentation de PC.
Le programmeur n’a pas directement accès à ce registre mais peut le modifier via les instructions de branchement. Celles-ci déroutent le processeur de son parcours normal, géré automatiquement par le séquenceur (exécution linéaire des instructions par incrémentation de PC), pour lui faire reprendre l’exécution à une autre adresse mémoire. Il suffit, pour ce faire, de remplacer la valeur de PC par l’adresse cible du saut, indiquée dans l’instruction de branchement.
Registre d’état Le registre d’état (State Register ou Program Status Word) est tel que ses bits ne forment pas de valeur numérique mais servent d’indicateurs (aussi appelés « drapeaux » ou flags) sur l’état du processeur. Certains bits peuvent être positionnés par le programmeur pour demander un comportement particulier (par exemple fixer un niveau de masquage des interruptions, voir chapitre 8), d’autres (appelés « bits conditions ») sont automatiquement mis à jour par le séquenceur à la fin de l’exécution de chaque instruction. Ils sont utilisés pour les sauts conditionnels en liaison avec les instructions de test et de comparaison. La « condition » liée à un branchement conditionnel consiste toujours en un test d’une valeur particulière d’un ou plusieurs bits conditions, positionnés par l’instruction précédente. Certains de ces bits, tels ceux qui suivent, sont suffisamment universels pour qu’on les retrouve sur tous les modèles de processeurs (mais leur nom peut varier) :
• Le bit Z (Zero). Il est mis à 1 si le résultat de l’instruction est nul, sinon il est mis à 0.
• Le bit C (Carry). Il est mis à 1 si l’instruction génère une retenue finale, sinon il est mis à 0.
• Le bit N (Negative). Il est mis à 1 si le résultat de l’instruction est négatif, sinon il est mis à 0 ; c’est la recopie du bit de poids fort du résultat.
• Le bit V (oVerflow). Il est mis à 1 si l’instruction génère un débordement arithmétique, sinon il est mis à 0. L’utilisation de ces bits conditions se fait toujours de la même manière : d’abord, on effectue un calcul, un test ou une comparaison, positionnant les bits conditions suivant le résultat que l’on veut obtenir, puis l’on effectue un saut conditionnel sur ces bits. Supposons par exemple que l’on veuille tester si le registre r1 est nul. On peut écrire le code de la façon suivante :
ADD r0,r1,#0 JZS adresse_cible La première instruction additionne r1 et 0 et met le résultat dans r0. Ce résultat ne peut être nul que si r1 lui- même était nul au départ. Le bit Z n’est donc à 1 après cette instruction que si r1 était nul. Le branchement n’est effectif que si le bit Z est à 1 (JZS signifie Jump if bit Z Set, soit « sauter si le bit Z est à 1 »). On a donc bien deux exécutions différentes suivant la valeur de r1 : s’il est non nul, le processeur continue avec les instructions situées après le branchement ; s’il est nul, le programme se poursuit à l’adresse cible indiquée dans le branchement emprunté.
Ordinateur et processeur 67
Architecture Notez que, dans certains processeurs, de plus en plus nombreux, les tests sont directement réalisés sur le contenu des registres, et non plus sur un registre d’état dont la mise à jour est délicate dans le cas d’une architecture incluant un pipeline, une exécution dans le désordre, etc.
Registre pointeur de pile Lors de l’exécution de programmes, le processeur doit parfois stocker de l’information en mémoire, non pas à la demande explicite du programmeur, mais afin d’assurer le bon fonctionnement des instructions. Un exemple typique est l’appel de fonction : dans un langage évolué, le programme est dérouté pour que s’exécute ladite fonction puis reprend normalement là où il s’était arrêté (à l’inverse d’un saut qui le déroute définitivement à une autre adresse). Le même mécanisme existe en assembleur ; il faut alors mémoriser la valeur de PC avant d’exécuter la fonction pour pouvoir reprendre le programme après l’appel. À cette fin, une structure de pile est implémentée en mémoire et un registre spécial du processeur (appelé « pointeur de pile » ou SP, Stack Pointer) pointe sur le haut de la pile, c’est-à-dire sur la première case mémoire libre à son sommet. Là sont empilées ou dépilées des informations, soit automatiquement par le séquenceur, soit à la demande du programmeur. Des instructions spéciales (PUSH ou POP) sont à sa disposition, qui accèdent à la mémoire via le registre SP par un adressage indirect. La figure 3.13 illustre l’usage de SP lors de l’appel d’une fonction pour mémoriser l’adresse de retour. De façon générale, la pile sert également à passer des paramètres à une fonction et à stocker ses variables locales : ces deux types d’informations n’ont pas d’existence en dehors de la fonction en question et, à l’entrée de celle-ci, la pile permet justement de les créer (par empilement), et de les détruire à la sortie (par dépilement).
Figure 3.13
Appel de fonction.
4. SÉQUENCEUR
Le séquenceur est directement lié à la puissance du processeur puisqu’il est responsable du bon déroulement des instructions. Il doit prendre en charge tous les transferts de données et l’envoi de toutes les commandes aux autres composants internes.
68 de l’ordinateur
4.1 Cycle d’instruction
L’exécution d’une instruction peut se décomposer en un certain nombre d’étapes composant le cycle d’instruction :
• récupération de l’instruction et mise à jour de PC (Fetch 1) ;
• décodage de l’instruction (Decode) ;
• récupération des données (Fetch 2) ;
• exécution de l’instruction (Execute) ;
• écriture du résultat et modification des bits conditions (Write). Chaque étape est gérée par le séquenceur et transformée en ordres internes. La figure 3.14 présente un exemple de l’exécution en interne de l’instruction ADD r1,r2,r3.
Figure 3.14
Exécution de ADD r1,r2,r3.
Chaque instruction demande ainsi de nombreux ordres et transferts internes, entièrement contrôlés par le séquenceur et rythmés par son horloge. Plus les instructions du processeur sont compliquées, plus elles nécessitent d’étapes internes et plus le séquenceur est complexe.
4.2 Séquenceur câblé
Les premiers microprocesseurs avaient des séquenceurs simples, qui calculaient les commandes internes à envoyer en fonction du code numérique de l’instruction à exécuter. Ces séquenceurs étaient composés de simples circuits logiques combinatoires, qui généraient les ordres à l’aide de fonctions logiques à partir des bits composant le code numérique de l’instruction. Ceux-ci n’étaient donc pas choisis au hasard mais devaient correspondre aux lignes de commande à activer (transfert de données, commande à l’UAL…) ; ils s’agissait de séquenceurs câblés. Ce système de séquenceur est assez simple, ne nécessite pas de circuits compliqués, mais a une puissance limitée. En effet, on ne peut pas obtenir une infinité de fonctions logiques différentes à partir des bits du code de l’instruction et cela restreint les possibilités pour les commandes internes. Une instruction processeur complexe, demandant de nombreuses étapes internes pour son exécution, ne peut être implémentée avec un séquenceur câblé. Pour ce faire, il faut mettre en place un séquenceur plus compliqué, capable d’exécuter des micro-instructions.
4.3 Séquenceur microprogrammé
Une instruction peut se décomposer en plusieurs micro-instructions, chacune correspondant à une action interne du processeur. Pour augmenter les possibilités de ce dernier, on a transformé le séquenceur en processeur miniature, exécutant, pour chaque instruction, un programme formé des micro-instructions. À l’intérieur du séquenceur se trouve une mémoire de microprogramme contenant la traduction en micro- instructions de chaque instruction processeur, ainsi qu’un microcompteur ordinal chargé de gérer l’exécution de celles-ci. Lorsqu’une instruction processeur est récupérée, son code numérique localise l’adresse de début du microprogramme d’exécution dans cette mémoire. Le microcompteur ordinal exécute alors les micro-
Ordinateur et processeur 69
instructions dans l’ordre, chacune opérant un transfert interne de données ou envoyant une commande à un composant du processeur. L’avantage de cette technique est de pouvoir proposer des instructions processeur plus complexes car il n’y a aucune limite au nombre de micro-instructions traduisant une instruction processeur. En revanche, cela complique et ralentit fortement le séquenceur, qui occupe beaucoup plus de place sur la puce (au détriment des autres entités fonctionnelles) car il faut y mettre la mémoire de microprogramme ainsi que les circuits nécessaires à l’exécution des micro-instructions. La mémoire de microprogramme est bien sûr conçue une bonne fois pour toutes par le constructeur du processeur et n’est pas modifiable. Le programmeur n’y a pas accès, ce mécanisme étant totalement invisible pour lui ; en d’autres termes, le niveau des instructions processeur est à sa portée, mais pas le niveau inférieur. Les processeurs actuels essaient de combiner les deux techniques de contrôle en exécutant les instructions processeur simples par des circuits logiques rapides et en réservant le découpage en micro-instructions aux instructions processeur les plus complexes.
4.4 RISC contre CISC
Durant la décennie 1970-1980, les processeurs ont progressé en complexité, profitant de l’intégration poussée des transistors pour offrir des jeux d’instructions plus complets et un séquenceur microprogrammé, malheureusement au détriment des autres composants internes, restreints à la portion congrue sur la puce. Entre autres, les données des instructions pouvaient se trouver en registre bien sûr, mais également en mémoire, même pour les opérations arithmétiques (d’où les liens en pointillés à la figure 3.3, entre l’UAL et l’interface avec le bus). En 1981, deux universitaires ont suggéré de réduire drastiquement le jeu d’instructions des processeurs, par exemple en interdisant les opérandes situés en mémoire, sauf pour les transferts, en limitant les modes d’adressage possibles, et en proscrivant les instructions trop compliquées. Ils avaient constaté que seulement 20 % du jeu d’instructions était utilisé dans 80 % des instructions d’un programme standard. Ils ont alors proposé de construire un processeur ayant un jeu d’instructions réduit (RISC, Reduced Instruction Set Computer) par opposition aux processeurs existants (CISC, Complex Instruction Set Computer). Cela devait permettre de simplifier fortement le séquenceur, de revenir à un séquenceur câblé, d’introduire un pipeline (voir section suivante), d’optimiser le tout pour accroître la vitesse d’horloge, et d’utiliser la place libérée sur la puce pour augmenter le nombre de registres (et par là même limiter le nombre d’accès mémoire) et introduire la mémoire cache directement dans le processeur. La réduction du jeu d’instructions entraînant un allongement des programmes (car certaines instructions disponibles sur les processeurs CISC doivent être simulées par plusieurs instructions successives sur les processeurs RISC), les promoteurs de ces processeurs espéraient alors que le ralentissement induit serait plus que compensé par l’accélération des performances des processeurs. En fait, le passage d’un processeur CISC à un processeur RISC transférait la complexité du séquenceur au compilateur, qui devait optimiser le code pour utiliser le pipeline et profiter des nombreux registres. Pendant longtemps, les partisans des deux types de processeurs se sont affrontés sur le terrain des performances pour aboutir à une synthèse dans les ordinateurs actuels : les techniques des processeurs RISC (séquenceur câblé, pipeline, nombreux registres, cache…) ont été intégrées à tous les processeurs, tandis que les instructions CISC sont toujours présentes via un séquenceur plus compliqué, réservé à leur usage.
5. ARCHITECTURES ÉVOLUÉES
Le modèle de processeur présenté précédemment est fonctionnel mais peu efficace. Depuis une vingtaine d’années, de nombreuses techniques ont été introduites, visant à améliorer les performances et la vitesse d’exécution des processeurs. Ces avancées n’ont été possibles que grâce au progrès technologique, permettant d’intégrer toujours plus de transistors sur la puce et autorisant une complexification progressive des circuits. Parmi toutes ces techniques, nous allons rapidement en présenter quelques-unes que nous avons jugées importantes et de complexité abordable. Nous traiterons donc ici de l’introduction d’instructions spécialisées, du traitement pipeline, des processeurs superscalaires et de l’exécution multithread.
5.1 Opérateurs et instructions spécialisés
Architecture de l’ordinateur 70
Les processeurs ont profité des possibilités offertes par l’adjonction de transistors supplémentaires pour implémenter l’exécution d’instructions arithmétiques plus compliquées. Il y a d’abord eu l’inclusion de l’UAL flottante directement dans le processeur, ce qui a permis d’effectuer rapidement des calculs sur les nombres réels, en commençant par les opérations simples puis en ajoutant progressivement des fonctions mathématiques complexes (racine carrée, fonctions trigonométriques et logarithmiques…). Devant le développement des applications multimédias, tous les fabricants de processeurs ont ensuite inclus des instructions spécifiques à ces applications dans les jeux d’instructions de leurs processeurs. Ces instructions donnent au développeur et au compilateur la possibilité d’effectuer certains calculs spécialisés en une seule opération. Ces extensions sont de deux types : des instructions mathématiques particulières et le calcul vectoriel. De nombreuses applications de traitement du son et de l’image utilisent des algorithmes mathématiques classiques pouvant se programmer à l’aide des instructions habituelles, mais qui sont en fait généralement composés des mêmes suites d’opérations. Il est donc intéressant d’ajouter dans le processeur les circuits nécessaires pour que ces suites d’opérations, codées maintenant chacune par une instruction, puissent s’effectuer le plus rapidement possible. Prenons par exemple une instruction effectuant une multiplication et une addition (S = X χ Y + Z) ; cette opération peut se programmer avec les instructions standard, en deux étapes (une multiplication suivie d’une addition). L’existence d’une instruction particulière implémentant ce calcul permet une amélioration de tous les programmes fondés sur des algorithmes utilisant spécifiquement ladite opération. Ces nouvelles instructions ne sont bien sûr pas choisies au hasard, mais en fonction des algorithmes que l’on souhaite plus performants et qui les intègrent : applications multimédias, traitement d’images, etc. Le calcul vectoriel consiste à effectuer simultanément la même opération sur plusieurs données différentes. Ce type d’exécution est régulièrement mentionné sous le terme SIMD (Single Instruction Multiple Data, un seul flot d’instructions et plusieurs flots de données) ou SWP (SubWord Parallelism, parallélisme appliqué à des sous- mots). Cela est particulièrement utile lorsque l’algorithme utilisé applique le même traitement à toutes les données d’un tableau. C’est le cas, par exemple, dans de nombreuses applications de traitement d’images où un même calcul est fait sur tous les pixels. Pouvoir traiter ainsi trois ou quatre pixels simultanément permet une importante accélération. Pour ce faire, le processeur intègre les UAL et les registres correspondants. Là encore, l’amélioration ne concerne pas tous les programmes, mais ceux fondés sur ce schéma. Tous les processeurs actuels incluent des instructions de ce type ; il s’agit des extensions appelées MMX, SSE2, Altivec, 3D!Now!, etc.
5.2 Traitement pipeline
Chaque instruction peut être décomposée en plusieurs étapes (la lecture de l’instruction, son décodage, son exécution, etc. ; voir section 4.1), nécessitant chacune des circuits différents. Ces derniers travaillent pendant une partie du temps d’exécution, mais restent inactifs lorsque l’instruction n’est pas à l’étape concernée. Le principe du traitement pipeline consiste à ne pas attendre la fin de l’exécution d’une instruction pour lancer la suivante, en profitant de l’inactivité des circuits ayant déjà traité l’instruction en cours. C’est l’idée du travail à la chaîne : un circuit effectue une étape d’exécution et enchaîne immédiatement la même étape avec l’instruction suivante pendant que la première avance dans la chaîne de traitement. La figure 3.15 illustre ce concept en décomposant une instruction en cinq étapes. Chaque chiffre correspond à une instruction avançant dans le pipeline et dont l’exécution se termine à sa sortie.
Figure 3.15
Traitement pipeline.
Le gain ne se fait pas directement sur la vitesse de traitement d’une instruction (elle doit toujours passer par les cinq étapes du pipeline) mais sur le nombre d’instructions par seconde qui sont exécutées. Dans le meilleur
Ordinateur et processeur 71
Architecture des cas, le processeur peut traiter cinq fois plus d’instructions qu’un système non pipeliné. De plus, les circuits propres à chaque étape, plus simple, peuvent être optimisés pour fonctionner à une vitesse d’horloge plus rapide et accroître la vitesse du processeur. On a donc tout intérêt à fractionner le plus possible le pipeline pour augmenter le nombre d’instructions en cours d’exécution et optimiser au maximum les circuits correspondant à chaque étape. Certains processeurs ont ainsi des pipelines pouvant contenir une vingtaine voire une trentaine d’étapes. Plusieurs écueils peuvent quand même perturber cette belle organisation et freiner l’exécution des instructions.
Aléa d’étapes différenciées Pour que le pipeline fonctionne à plein rendement, il faut décaler toutes les instructions simultanément d’une étape, ou autrement dit alimenter le pipeline continuellement (à chaque cycle) en instructions. Celui-ci doit donc être conçu de sorte que, pour toutes les instructions, chaque étape dure aussi longtemps. Malheureu- sement, les instructions ne sont pas équivalentes : il est plus long de récupérer une donnée en mémoire que dans un registre ; une multiplication prend plus de temps qu’une addition, etc. Des instructions demandant plus de temps pour s’exécuter et introduisant des retards dans le pipeline empêchent celles qui suivent de progresser. Une solution peut être de faire progresser les instructions suivantes en « doublant » l’instruction lente, mais cela complique la gestion du pipeline, qui doit à un moment remettre les instructions dans le bon ordre (voir section suivante).
Dépendances Les instructions successives dans le pipeline ne sont pas indépendantes et font probablement appel aux mêmes ressources. On peut donc avoir un conflit si l’une d’entre elles a besoin d’une valeur calculée par une autre, qui la précède (pour poursuivre un calcul par exemple). Prenons l’exemple de la figure 3.16.
Figure 3.16
Dépendances dans un pipeline.
L’instruction 2 modifie le registre r1, utilisé (avec sa nouvelle valeur) par l’instruction 3. Celle-ci ne peut donc pas quitter l’étape de récupération des données (Fetch 2) avant que r1 ne soit réécrit par l’instruction 2, c’est-à- dire lorsqu’elle passe l’étape 5 (Write). Lorsque le processeur modifie r1, il envoie en même temps la valeur à l’étape 3 pour l’instruction 3 (mécanisme de bypass), qui peut progresser au prochain top. L’instruction 3 est donc retardée d’un top d’horloge, induisant le retard sur tout le pipeline. Le même phénomène apparaît pour l’instruction 4, qui utilise r5, modifié par l’instruction 3. Pour remédier à ce problème, le processeur peut essayer de réorganiser le flot d’instructions arrivant dans le pipeline en détectant les dépendances et en exécutant d’abord les instructions qui ne dépendent pas de résultats antérieurs. À la figure 3.16, le processeur pourrait avancer l’instruction 5, qui utilise un registre totalement indépendant des autres instructions, et profiter du « trou » créé par la 3 pour exécuter la 5. Cette technique complique fortement le séquenceur, qui doit récupérer plusieurs instructions en même temps, détecter les dépendances, réorganiser l’ordre des instructions et les exécuter, tout cela le plus rapidement possible (voir section suivante).
Branchements À chaque instant, le processeur doit alimenter le pipeline avec les prochaines instructions à exécuter. C’est évidemment facile lorsque les instructions sont en séquence, mais cela se complique si le processeur tombe sur une rupture de séquence. Dans ce cas, il ne peut pas récupérer les nouvelles instructions avant d’avoir calculé l’adresse cible du branchement, opération effectuée normalement lors de l’étape d’exécution du pipeline. Il faut donc retarder l’exécution des instructions suivant le branchement jusqu’à ce que le processeur connaisse leur adresse (voir figure 3.17).
72 de l’ordinateur
Branchement dans un pipeline.
Dans le cas d’un branchement inconditionnel, le processeur peut accélérer le traitement en détectant la présence du saut dès le début du pipeline et en calculant immédiatement l’adresse cible. Cela lui permet de récupérer sans délai les instructions suivantes, au prix là encore de circuits supplémentaires au niveau du séquenceur. Le problème est plus délicat avec les sauts conditionnels : on peut disposer de l’adresse cible dès la récupération de l’instruction de saut, mais on ne sait pas avant l’étape d’exécution si le saut va être effectif ou pas, car cela dépend des bits conditions qui vont être modifiés par les instructions précédentes. Il est cependant inacceptable de laisser le pipeline vide comme à la figure 3.17, car cela ralentirait fortement le processeur, d’autant plus que le nombre d’étapes est important. La seule solution est alors de faire une hypothèse sur le saut et de récupérer les instructions suivantes en conséquence : soit on suppose que le saut n’est pas réalisé et le processeur commence à exécuter les instructions qui suivent le saut en mémoire, soit on suppose qu’il va dérouter le processeur et celui-ci calcule l’adresse cible par anticipation (comme pour le saut inconditionnel) avant de récupérer les instructions correspondantes. Cette technique, appelée « prédiction de branchement », consiste à prédire au mieux le comportement du branchement avant son exécution effective. À la fin de l’étape d’exécution du saut conditionnel, le processeur vérifie l’hypothèse, c’est-à-dire si le branchement est pris ou non. Si la prédiction est correcte, le processeur a injecté dans le pipeline les bonnes instructions et aucun retard n’est à déplorer ; si le processeur s’est trompé (prédiction fausse), il doit vider le pipeline, qui ne contient pas la suite effective du programme, pour reprendre les instructions qui sont à exécuter après le saut. Le retard est alors évidemment maximal. L’optimisation des circuits chargés de la prédiction de branchement a un impact prépondérant sur les performances du pipeline et donc du processeur. La qualité du prédicteur de branchement doit augmenter avec la taille du pipeline. En effet, plus le pipeline est long, plus le nombre de cycles perdus est important en cas de mauvaise prédiction. L’objectif est alors de limiter ce nombre de mauvaises prédictions en proposant des techniques de calcul d’hypothèse de branchement (ou de prédiction de branchement) toujours plus efficaces. Le plus simple est de faire de la prédiction statique : suivant la direction du saut conditionnel (en avant ou en arrière dans le programme), on décide si le branchement est pris ou non. Très souvent, un retour en arrière dans le programme correspond à une fin de boucle ; comme celle-ci sera exécutée plusieurs fois, le saut sera effectué, sauf au dernier passage dans la boucle. La prédiction statique la plus classique consiste donc à dire qu’un saut arrière sera réalisé alors qu’un saut vers l’avant ne le sera pas. Bien sûr, il y a des exceptions, mais cela permet déjà d’améliorer les performances du pipeline. Mieux encore, le processeur peut faire de la prédiction dynamique : un historique est associé à chaque saut et permet de savoir si celui-ci a le plus souvent été effectif ou non. On peut ainsi atteindre un pourcentage élevé de prédictions correctes, permettant de profiter au maximum du pipeline. Les processeurs actuels disposent ainsi de schémas de prédiction de branchement complexes à plusieurs niveaux. L’objectif est d’atteindre des taux de bonnes prédictions allant de 95 % à 99 %.
5.3 Processeur superscalaire
Un pipeline permet de traiter plus d’instructions par cycle mais chacune d’elles se trouve à une étape de traitement différente. Pour pouvoir traiter plusieurs instructions en même temps (on parle alors d’exécution parallèle), les processeurs superscalaires ont été dotés de multiples unités d’exécution dans leur pipeline, voire de plusieurs pipelines complets (voir figure 3.18). L’objectif de ces processeurs consiste alors à alimenter,
Figure 3.17
Ordinateur et processeur 73
Architecture à chaque cycle, chaque unité d’exécution. Dans ces conditions, le processeur délivre le maximum de sa puissance puisque aucune unité d’exécution ne reste inoccupée durant les cycles.
Figure 3.18
Processeur superscalaire.
Avoir plusieurs circuits chargés de l’exécution permet de traiter une instruction compliquée (prenant beaucoup de temps), comme une addition flottante, sans bloquer le reste du pipeline, qui peut passer par les autres unités d’exécution. Il faut pour cela que les instructions successives n’aient pas de liens de dépendance et ne fassent pas appel aux mêmes circuits. On pourra ainsi probablement exécuter en parallèle une opération arithmétique entière et une opération flottante qui n’utilisent pas la même UAL et ne font pas référence aux mêmes registres. De plus, la duplication des unités d’exécution permet de dédier ces dernières au traitement d’instructions du même type (par exemple, une unité d’exécution entière pour toutes les instructions manipulant des données entières, une unité d’exécution flottante pour la manipulation des données flottantes, une unité d’accès mémoire pour les lecture et écriture de données en mémoire…). Cette spécialisation des unités d’exécution permet d’espérer un accroissement des performances et une meilleure utilisation globale du processeur.
Exécution dans le désordre Si le séquenceur est construit autour de plusieurs pipelines, il peut exécuter complètement plusieurs instructions en parallèle, chacune utilisant un pipeline. Bien sûr, on a toujours les problèmes liés aux dépendances et à l’accès aux mêmes ressources (UAL, registres…), obligeant le processeur à retarder temporairement l’une des instructions ou à intervertir leur ordre d’exécution. Pour une utilisation optimale des différents pipelines, l’ordonnancement des instructions est déterminé dynamiquement lors de leur chargement. Un buffer de préchargement permet de récupérer plusieurs instructions simultanément dans le cache de niveau 1, laissant un stock d’instructions à disposition de la logique du processeur, à charge pour celle-ci de déterminer l’ordre dans lequel elles vont être exécutées. Cela implique une gestion très lourde de leur exécution : quelles sont celles qui vont effectivement être exécutées (si elles sont derrière un branchement, peut-être celui-ci sera-t-il pris et qu’elles seront ignorées), quels registres vont être utilisés et modifiés, et dans quel ordre (une dépendance, liée à l’utilisation d’un même registre dans deux instructions, peut parfois être éliminée par un renommage du registre dans l’une des instructions, renommage effectué par le séquenceur au moment de l’exécution), quelle instruction peut être lancée à un instant précis (en fonction de la disponibilité des unités d’exécution) ? Ce mode de fonctionnement, avec le traitement pipeline, est à l’origine de la plus grande partie de l’augmentation des performances des processeurs depuis les années 1990, au prix d’une importante complexité de la logique interne du composant.
Processeur VLIW Dans le mode d’exécution précédent, toute la complexité se trouve dans le processeur, qui doit déterminer le parallélisme de l’application (la possibilité d’exécuter simultanément des instructions dans chaque unité fonctionnelle) dynamiquement lors de son exécution. Certains processeurs rejettent le travail sur le
74 de l’ordinateur

Télécharger gratuitement L’Architecture de l’ordinateur(assembleur)