Circuits et architecture 2022/2023 – Journal du cours

Table des matières

Ce fichier est disponible au format HTML.

1. Cours 01 <2022-09-16 Fri>

1.1. Introduction

Bienvenue dans le cours Circuits et architecture !

Les années précédentes, vous avez utilisé des outils et concepts comme des boîtes noires, sans forcément comprendre leur fonctionnement interne. Par exemple, vous avez programmé en C sans que l'on vous explique comment ce langage était implémenté exactement. Durant vos deux prochaines années d'études, vous allez ouvrir ces boîtes noires, et découvrir comment elles fonctionnent sous le capot.

En l'occurence, l'objectif du cours Circuit et architecture est d'expliquer le fonctionnement des machines à calculer programmables appelées ordinateurs. Le cours débute des couches matérielles très basses jusqu'à remonter au niveau du langage C.

1.1.1. Supports et organisation

Tous les documents (support, projet, feuilles de TD, etc.) sont disponibles sur le dépôt Git du module.

https://gaufre.informatique.univ-paris-diderot.fr/aguatto/architecture-m1-22-23

Il contient notamment un résumé (syllabus) du module, qui résume toutes les informations pratiques du cours et propose un plan des sujets traités séance par séance. Prenons le temps de le lire ensemble.

Comme écrit dans le syllabus, l'enseignement reprend pour l'essentiel le contenu du cours dispensé par M. Carton les années précédentes. Il s'appuie en particulier sur le support de cours rédigé par ce dernier :

https://www.irif.fr/~carton/Enseignement/Architecture/archi.pdf

(Il existe aussi au format HTML, voir la page de M. Carton.)

Le dépôt Git du cours contient également un journal (que vous êtes en train de lire !) qui résume succinctement les points traités en cours chaque semaine. La notation §X.Y fera référence à la section X des notes de M. Carton. Le journal sera plus détaillé lorsque le cours s'éloignera un peu des dites notes.

Attention : la lecture des notes de M. Carton et du journal ne remplace pas la présence en cours. Les notes contiennent à la fois plus et moins d'information que les cours magistraux. Elles sont là pour vous permettre de vous concentrer sur une prise de notes active, et en particulier vous évite d'avoir à recopier les schémas dessinés au tableau.

Autre remarque : le cours ne contient aucun concept vraiment difficile. En revanche, on va manipuler beaucoup de niveaux d'abstraction différents, des portes logiques jusqu'à des questions de programmation système. La principale difficulté est de comprendre l'articulation de ces niveaux, qui sera nécessaire pour réaliser le projet !

1.2. Le cours

1.2.1. Historique général (§2.1)

Une histoire des machines à calculer, concept très ancien.

Dès le début, le développement des machines à calculer est motivé par des besoins concrets, commerciaux et administratifs puis militaires (XXème).

Les progrès théoriques (Boole, Turing, Gödel, Church) sont parallèles aux progrès pratiques mais ne les rencontrent que tardivement (1950+). En particulier, si les contributions théoriques d'Alan Turing sont immenses, et ses contributions pratiques grandes, on ne peut pas dire qu'il a inventé l'ordinateur (= programmable) comme on l'entend parfois.

Une histoire des processeurs passe nécessairement par une histoire des compagnies qui fabriquent les processeurs. L'architecture des ordinateurs est dominée par l'industrie et le domaine militaire (supercalculateurs).

Une sélection biaisée vers x86 de quelques microprocesseurs :

Année Nom Fabricant Mot Freq. Trans. Notes
1971 4004 Intel 4 bits 108 KHz 2,3K 1er μ-proc
1972 8008 Intel 8 bits 200 KHz 3,5K  
1978 8086 Intel 16 bits 5 MHz 29K 1er x86
1985 80386 Intel 32 bits 12 MHz 275K 1er x86-32
1995 Pentium Intel 32 bits 60 MHz 3,1M  
2003 Opteron AMD 64 bits 1,4 GHz 106M 1er x86-64
2022 M1 Ultra Apple 64 bits 3,2 GHz 114G ARM, 20c

Beaucoup d'autres choses à l'époque et depuis 2003 : essor puis déclin des architectures RISC ; récemment essor de puissants concurrents à x86-64 (ARM, Nvidia) ; nouveaux segments (mobiles) ; optimisation de la consommation énergétique ; l'embarqué devient dominant en volume dans les années 1990 (x86 y est inexistant).

1.2.2. Les portes logiques

Après ces quelques éléments de contexte, rentrons dans le vif du sujet : construire un ordinateur numérique programmable. On va adopter une démarche ascendante (ou bottom-up) : on commence avec le niveau d'abstraction le plus bas, puis on remonte vers le logiciel.

(À nuancer : il y a presque toujours plus bas, à moins de descendre à une description quantique de la matière subatomique. Ce ne sera évidemment pas le propos du cours.)

Il faut dejà nous demander ce que veut dire "numérique". De quels nombres parle-t-on ? Vous connaissez déjà différents systèmes de nombres.

ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ (⊆ … ?)

Certains de ces ensembles sont de même cardinal ("taille"), comme ℕ, ℤ ou ℚ qui sont de même cardinal strictement plus petit que celui de ℝ et ℂ. On va commencer avec un ensemble de "nombres" de cardinal fini : les booléens.

Ce sera notre niveau d'abstraction de base : la numération booléenne, bâtie sur l'ensemble 𝔹 = { 0, 1 }. C'est un système de nombre un peu étrange, mais qui a l'avantage de pouvoir aussi être vu sous un angle logique.

En effet, les opérateurs logique NOT, AND, OR, XOR, NOR, NAND peuvent aussi être compris comme des opérateurs arithmétiques. Pour cette raison, on note · pour AND et + pour OR. L'analogie avec l'arithmétique est moins claire pour NOT et XOR, et les notations sont donc moins fixées : pour NOT on utilisera le symbole ¬ ou la barre de surlignement, pour XOR le symbole ⊕.

Ces opérateurs sont des fonctions booléennes, de la forme 𝔹ⁿ → 𝔹.

On rappelle qu'une fonction mathématique f : X → Y est défini comme un ensemble de couples (a, b) ∈ X × Y tel que pour tout a ∈ X, il existe un unique b ∈ Y tel que (a, b) ∈ f. Si X et Y sont infinis, f l'est aussi, mais dans le cas des fonctions booléennes X = 𝔹ⁿ qui est fini (de cardinal 2ⁿ) et Y = 𝔹 (de cardinal 2) également, donc on peut représenter la fonction comme l'ensemble fini des couples entrées/sortie. C'est sa table de vérité.

Q : donner les tables de vérité de NOT, AND, OR, XOR, NOR, NAND.

(On peut remarquer que comme 1 + 1 = 1, si on souhaite voir les booléens comme des nombres, on peut éventuellement penser à "0" comme dénombrant "zéro éléments" et à "1" comme dénombrant "beaucoup d'éléments".)

Il est facile de vérifier que les opérateurs vérifient certaines lois algébriques (découvertes par MM. Boole et de Morgan) : la négation est involutive, le NOT distribue et transforme AND/OR en OR/AND, etc, AND et OR sont idempotents, etc.

Il est clair que certaines de ces portes peuvent être exprimées à partir des autres. Littéralement, on a NAND = NOT AND, NOR = NOT OR. Et les autres ?

Q : comment exprimer XOR à partir de NOT, AND, OR ?

R : XOR(a, b) = (a OR b) AND NOT (A AND B) = (a + b) · ¬ab = a

Q : connaissez-vous un autre opérateur logique que ceux de la liste ?

A : l'implication a ⇒ b = OR(NOT(A), B).

Ces opérateurs booléens peuvent également être vu comme des portes dans circuits où chaque fil transporte un bit. Ces circuits sont orientés, au sens où les fils transportent les bits dans une direction bien définie. On peut voir les lois booléennes comme des transformations de circuits. Voir les notes pour les notations, que vous connaissez sûrement déjà.

Q : montrer que NAND est un opérateur universel, capable d'exprimer tous les autres.

A : NOT(a) = NAND(a, a), OR(a, b) = NAND(NOT(a), NOT(b)), AND s'exprime avec NOT et OR par de Morgan, XOR et NOR s'expriment en fonction de NOT, OR et AND.

Q, à faire chez vous : même question pour le NOR.

On a donc notre jeu de portes logiques élémentaires, qui (si on le souhaite) peut être réduit au NOR ou bien au NAND. Mais quid des fonctions booléennes en général ? Étant donnée une fonction / table de vérité quelconque, peut-on l'exprimer avec les portes précédentes ? La réponse est oui. Voyons une méthode très simple, en commençant par poser le problème.

Soit f : 𝔹ⁿ → 𝔹.

On veut coder cette fonction par une formule booléenne sur n variables x₁, …, xₙ telle que, pour tout (a₁, …, aₙ) ∈ 𝔹ⁿ, la valeur de vérité de la formule où l'on a remplacé xᵢ par aᵢ est égale à f(a₁, …, aₙ).

Considérons l'ensemble dom(f) ⊆ 𝔹ⁿ des n-uplets de bits a tel que f(a) = 1. Chaque n-uplet (a₁, …, aₙ) peut être décrit par une conjonction de n atomes, où un atome est une variable propositionnelle ou sa négation. Le i-ème atome est xᵢ si aᵢ = 1, ¬xᵢ si aᵢ = 0. La formule obtenue en prenant la disjonction de toutes ces conjonctions a bien la propriété recherchée.

Donc toute fonction booléenne s'écrit comme une disjonction de conjonction d'atomes, i.e., en forme normale disjonctive (FND). De plus, cette forme normale fournit une caractérisation unique (f = g ssi FND(f) = FND(g)), pour un ordre d'énumération des entrées fixé.

Attention : la méthode décrite n'est pas une bonne méthode en pratique. L'expression est énorme en général, par exemple si on donne la fonction constante 1, on a une disjonction de 2ⁿ conjonctions, chacune de celle-ci comprenant n atomes. On verra des méthodes plus efficaces en TD, comme celle des tableaux de Karnaugh.

La semaine prochaine, on verra comment réaliser physiquement les portes logiques en termes de transistors.

2. Cours 02 <2022-09-23 Fri>

2.1. Des transistors aux portes logiques (§4)

2.1.1. Introduction

C'est à partir des portes logiques et fonctions booléennes qu'on va construire le reste de l'informatique. Toutefois, les portes logiques sont des objets idéaux qu'il va falloir réaliser physiquement pour s'en servir. Il va donc falloir parler un peu de physique et d'électronique.

L'idée est d'expliquer le fonctionnement du transistor, brique de base des circuits intégrés (formés de millions voire milliards d'entre eux !). Comme la physique-chimie dépasse largement le cadre du cours, on va en donner une vision simplifiée et toujours très idéalisée.

2.1.2. Semi-conducteurs, diodes et transistors

(Les notes de cours contiennent beaucoup plus de détails sur les aspects physiques et chimiques de cette partie du cours, et Wikipédia encore plus.)

Un semi-conducteur est un matériau dont la conductivité électrique est située entre celle des isolants et celle des métaux. On peut le traiter chimiquement (dopage) pour modifier ses propriétés, et obtenir un semi-conducteur de type n, qui a des électrons en trop, ou un semi-conducteur de type p, qui a des électrons manquants, des "trous".

En branchant un semi-conducteur p et un n, on obtient une diode, qui ne laisse passer le courant que dans un seul sens. En appliquant une tension à l'anode et à la cathode d'une diode, on peut la rendre conductrice ou non-conductrice. Cela rend la diode contrôlable par un signal extérieur.

Les transistors généralisent le fonctionnement de la diode. Ils sont eux aussi de deux types, p et n. Les deux types de transistors ont trois pates, nommées "grille", "source" et "drain". Leur comportement, pour ce qui nous intéresse, est simplement celui d'un interrupteur, et on peut en donner une description abstraite.

Dans un transistor de type n, lorsque la grille reçoit une tension de 2,9V, l'interrupteur est fermé et source et drains sont connectés (source = drain, le transistor agit comme un fil). Si la grille ne reçoit pas de tension (0V), l'interrupteur est ouvert et il n'y a aucun lien entre source et drain. Les transistors p agissent de façon symétrique, connectant source et drain lorsque la tension de la grille est 0V, et la fermant à 0V.

(Le comportement complémentaire des transistors n et p explique le nom donné aux circuits qui en sont composés : Complementary Metal-Oxyde Semiconductors, ou CMOS.)

On peut donc comprendre le comportement des transistors de façon purement logique. La tension 2,9V correspond au booléen 1, et 0V au booléen 0. Le transistor n peut être décrit par la formule

grille ⇒ (source = drain)

et le transistor p par la formule

¬grille ⇒ (source = drain).

où "source = drain" est OR(AND(drain, source), AND(¬drain,¬source)).).

On peut donc donner un sens purement logique, extra-physique, aux circuits composés de transistors. Toutefois, attention : ces circuits, contrairement à ceux de la section précédents, ne sont pas orientés. Il n'y a pas d'entrée et de sorties bien définies à ce niveau, le courant se propageant dans toutes les directions simultanément. Du point de vue logique, notre circuit correspond à une contrainte sur les valeurs possibles sur les fils, contrainte qui peut avoir 0, 1, ou plusieurs solutions.

On peut donc les comprendre comme des circuits où chaque fil transporte un ensemble de bits, c'est-à-dire un sous-ensemble de 𝔹. Ces sous-ensembles sont faciles à énumerer : ∅, {0}, {1} et {0,1}. Les cas {0} et {1} correspondent au sous-cas des circuits déterministes.

Supposons qu'un fil A transporte le sous-ensemble V, et un fil B transporte le sous-ensemble W. Que se passe-t-il lorsqu'on connecte A et B ? On force les valeurs transportées par A et B à être les mêmes, et donc les valeurs transportées par A et B à être à la fois dans V et W. Autrement dit, les valeurs transmises sont celles qui appartiennent à V ∩ W.

Que se passe-t-il par exemple, si l'on connecte par un fil le générateur à la terre ? Les valeurs qui circulent sont dans {0} ∩ {1} = ∅, ce qui correspond logiquement à un circuit qui n'a pas de solution et, d'un point de vue plus pragmatique, à un court-circuit.

2.1.3. Les portes logiques (§4.5)

Voir les notes.

2.2. Représentation des types de données scalaires (§3)

Maintenant qu'on a quelque idée de comment manipuler des bits individuels, il est temps de passer à la représentation des types de données scalaires, comme les nombres positifs ou relatifs, les réels, les caractères.

(N.B. : ce sujet est placé avant celui des portes logiques et transistors dans les notes de cours).

2.2.1. Nombres entiers

Supposons qu'on souhaite représenter les entiers par \(k\) bits numérotés \(b_{k-1} \dots b_0\).

Il existe différents codages qui se valent en théorie mais pas en pratique. Pour chaque codage \(X\), on définit une fonction \(\mathit{decode}_X\).

  1. Entiers naturels (positifs)

    Sur \(k\) bits, on représente \(2^k\) valeurs, soit l'intervalle \([0, 2^k-1]\), en utilisant la représentation en base 2 habituelle.

    \[ \mathit{decode}_{\mathit{unsigned}}(b_{k-1} \dots b_0) = \sum_{i = 0}^{k - 1} b_i 2^i \]

    Cette représentation est dite non-signée (unsigned en anglais), par opposition aux représentations des entiers relatifs qui vont souvent utiliser un bit de signe.

  2. Entiers relatifs

    On a le choix de plusieurs représentations.

    1. Magnitude signée

      Le bit de poids fort sert à indiquer le signe du nombre, le reste des bits code un entier positif.

      \[ \mathit{decode}_{\mathit{signedmagnitude}}(b_{k-1} \dots b_0) = -1^{b_{k-1}} \sum_{i = 0}^{k - 2} b_i 2^i \]

      Problèmes : redondant (0 est encodé par \(00\dots0\) et \(10\dots0\)), difficile d'implémenter les opérations arithmétiques.

    2. Représentation biaisée

      On compte de 1 en 1 à partir de -2ᵏ⁻¹.

      \[ \mathit{decode}_{\mathit{biased}}(b_{k-1} \dots b_0) = -2^{k-1} + \sum_{i = 0}^{k - 1} b_i 2^i \]

    3. Complément à 2

      C'est la représentation utilisée en pratique, assez ingénieuse.

      L'idée est de conserver la formule du cas positif, mais d'inverser le signe du bit de poids fort.

      \[ \mathit{decode}_{twoscomplement}(b_{k-1} \dots b_0) = -b_{k - 1} 2^{k-1} + \sum_{i = 0}^{k - 2} b_i 2^i \]

      On va voir que cette représentation jouit de bonnes propriétés, ce qui facilite l'implémentation des opérations arithmétiques.

      Par exemple, que se passe-t-il si on additionne la représentation d'un nombre et celle de son opposé sans se soucier du bit de signe (comme on le ferait pour des entiers non-signés) ?

    4. Récapitulatif
      Nom Min représenté Max représenté
      Non signée \(0\) \(2^k-1\)
      Magnitude signée \(-2^{k-1}+1\) \(2^{k-1}-1\)
      Représentation biaisée \(-2^{k-1}\) \(2^{k-1}-1\)
      Complément à 2 \(-2^{k-1}\) \(2^{k-1}-1\)

      Exemple de codage pour k = 3.

      Bits Naturel Magnitude signée Représentation biaisée Complément à 2
      000 0 0 -4 0
      001 1 1 -3 1
      010 2 2 -2 2
      011 3 3 -1 3
      100 4 -0 0 -4
      101 5 -1 1 -3
      110 6 -2 2 -2
      111 7 -3 3 -1
  3. Opérations arithmétiques
    1. Somme d'entiers non signés

      L'algorithme est le même que celui qu'on a appris à l'école primaire, à ceci près que les chiffres sont dans \([0, 1]\) plutôt que \([0, 9]\).

    2. Opposé en complément à deux

      Quel entier la négation bit-à-bit de \(b_{k-1} \dots b_0\) code-t-elle, lorsqu'on utilise la représentation en complément à deux ?

      \begin{align*} \mathit{decode}_{twoscomplement}(\overline{b_{k-1} \dots b_0}) & = -\overline{b_{k - 1}} 2^{k-1} + \sum_{i = 0}^{k - 2} \overline{b_i} 2^i \\ & = -(1 - b_{k - 1}) 2^{k-1} + \sum_{i = 0}^{k - 2} (1 - b_i) 2^i \\ & = -2^{k-1} + b_{k - 1} 2^{k-1} + \left(\sum_{i = 0}^{k - 2} 2^i\right) - \left(\sum_{i = 0}^{k-2} b_i 2^i\right) \\ & = -2^{k-1} + 2^{k-1}-1 + b_{k - 1} 2^{k-1} - \left(\sum_{i = 0}^{k-2} b_i 2^i\right) \\ & = -\mathit{decode}_{twoscomplement}(b_{k-1} \dots b_0) - 1 \end{align*}

      On en déduit immédiatement un algorithme commode pour le calcul de l'opposé sur la représentation en complément à deux.

    3. Somme d'entiers signés

      Intérêt du complément à deux : la somme est calculée sans traiter spécifiquement le bit de signe, à part pour ce qui est de la détection de dépassement de capacité. Voir le tableau des notes en §3.1.4.3.3 pour l'exemple de k = 3.

      Observation : le plus petit entier qui peut résulter de l'addition de \([-2^{k-1}, 0]\) avec un entier dans \([0, 2^{k-1}-1]\) est \(-2^{k-1}\), tandis que le plus grand est \(2^{k-1}-1\). Donc, aucun dépassement de capacité ne peut résulter de l'addition d'un positif et d'un négatif.

      Supposons qu'on calcule la somme des bits \((a_i)_{0 \le i < n}\) et \((b_j)_{0 \le j < n}\) pour obtenir les bits résultat \((s_i)_{0 \le i < n}\) et les bits de retenue \((c_i)_{0 \le i < n + 1}\).

      \(a_{k-1}\) \(b_{k-1}\) \(c_{k-1}\) \(s_{k-1}\) \(c_k\) dépassement ?
      0 0 0 0 0 non
      0 0 1 1 0 oui
      0 1 0 1 0 non
      0 1 1 0 1 non
      1 1 0 0 1 oui
      1 1 1 1 1 non

      On constate que les cas de dépassement sont exactements ceux où \(c_k \ne c_{k-1}\), c'est-à-dire où \(c_k \oplus c_{k+1}\) est vrai.

2.2.2. Nombres réels et virgule flottante (§3.3)

(Cette partie n'a pas été traitée en cours mais abordée en travaux dirigés.)

Par nature, le problème du codage des nombres réels dans un nombre fini de bits est plus difficile que celui des nombres entiers, puisqu'il y en a strictement plus. Pire, contrairement au cas des entiers, on ne pas espérer décrire exactement un intervalle de réels dans un nombre fini de bits. Se poseront donc des questions épineuses de calcul d'arrondi.

Un bon compromis entre performance et précision est fourni par les formats de la norme IEEE-754. On dit que ce format utilise la virgule flottante parce que la valeur de l'exposant, qui détermine le nombre de chiffre, n'est pas fixée. (Il existe d'autres formats dits à virgule fixe où le nombre de chiffres après la virgule est le même pour tous les nombres représentés, ce qui mène en général à des opérations moins précises mais plus simples à implémenter et donc populaires dans le contexte des systèmes embarqués.)

La représentation utilise trois champs de taille distincte : un champ signe, un champ exposant, un champ mantisse (partie fractionnaire). La taillle de ces champs dépend du format de précision adopté. La norme IEEE-754 en propose trois : précision simple, double ou étendue. Ci-dessous, la taille des champs pour la précision simple, qui correspond au type float en Java ou en C.

\(b_{31}\) \(b_{30} b_{29} b_{28} b_{27} b_{26} b_{27} b_{24} b_{23}\) \(b_{22} b_{21} b_{20} b_{19} b_{18} b_{17} b_{16} b_{15} b_{14} b_{13} b_{12} b_{11} b_{10} b_{9} b_{8} b_{7} b_{6} b_{5} b_{4} b_{3} b_{2} b_{1} b_{0}\)
1 bit 8 bits 23 bits
signe \(s\) exposant \(e\) mantisse \(m\)
\(s\) \(e_{7} e_{6} e_{5} e_{4} e_{3} e_{2} e_{1} e_{0}\) \(m_{22} m_{21} m_{20} m_{19} m_{18} m_{17} m_{16} m_{15} m_{14} m_{13} m_{12} m_{11} m_{10} m_{9} m_{8} m_{7} m_{6} m_{5} m_{4} m_{3} m_{2} m_{1} m_{0}\)
     

\[ \mathit{decode}_{ieee754single}(\langle s, e, m \rangle) = (-1)^s \cdot (1,m) \cdot 2^{e-127} \mbox{ où } 1,m = 1 + \sum_{i = 1}^{23} m_{23-i} 2^{-i} \mbox{ et } e \not\in \{ 0, 255 \} \]

Les cas où l'exposant est \(0\) ou \(255\) correspondent à des valeurs spéciales, par exemple des nombres très petits appelés sous-normaux, ou encore \(\infty\), ou encore la valeur indéfinie Not-a-Number (NaN) qui sert à propager des erreurs.

Les détails fins du format IEEE-754 dépassent le cadre du cours. Si vous êtes intéressé, l'article What Every Computer Scientist Should Know About Floating-Point Arithmetic de David Goldberg fournit une introduction raisonnablement détaillée. La page IEEE-754 de la Wikipédia anglophone est aussi de bonne qualité.

2.2.3. Interlude : représentations numériques de taille variable

Pour finir, une remarque importante : les représentations numériques décrites précédemment sont de taille bornée, ce qui est un prérequis pour une implémentation en matériel. En conséquence, elles ne peuvent décrire qu'un sous-ensemble fini de ℕ ou ℝ.

En logiciel, on peut représenter une portion de ℕ ou ℝ limitée uniquement par la quantité de mémoire disponible. Par exemple, la bibliothèque GNU MP propose des vrais entiers mathématiques de taille arbitraire, et la bibliothèque GNU MPFR fait de même pour les nombres à virgule flottante.

2.2.4. Caractères

  1. ASCII

    Le jeu de caractère ASCII (American Standard Code for Information Interchange) encode 128 caractères sur 7 bits. Il a été et reste très répandu, mais ses origines américaines le rendent inadapté à l'informatique moderne : il se restreint à l'alphabet latin, sans accents.

  2. Unicode

    Le consortium Unicode propose une norme capable de gérer un très grand nombre de caractères (149186 en septembre 2022). La norme divise le travail de codage en deux aspects :

    1. chaque caractère se voit assigné un entier unique compris entre 0 et 0x10FFFF (soit un maximum théorique de 1,114M caractères), son point de code, indépendamment de tout codage concret ;
    2. un codage concret des entiers encodant chaque caractère, qui peut être plus ou moins complexe à coder/décoder.

    Pour ce qui est du premier aspect, précisons qu'Unicode comprend beaucoup plus que des caractères issus d'alphabets, puisqu'il contient aussi les diacritiques (accents, trémas, cédilles, etc.), les caractères mathématiques, les emojis, etc.

    Pour ce qui est du second, citons au moins deux codages intéressants.

    Le codage UTF-32 code tout caractère sur 32 bits. Il s'agit donc d'un codage coûteux mais qui a l'avantage de la simplicité et rend certaines opérations efficaces, comme par exemple le calcul de la longueur d'une chaîne (si l'on ignore le problème de la normalisation, voir plus bas).

    Le codage UTF-8 est un codage de longueur variable. Il est compatible avec ASCII : les caractères codables en ASCII sont codés sur 1 octet en UTF-8 et avec la même représentation. Les autres caractères sont codés sur 2 à 4 octets.

    La norme Unicode est complexe. Par exemple, un même "caractère" (au sens humain) peut être réalisé par la combinaison de plusieurs points de code. Par exemple, le caractère Ç dispose d'un point de code dédié (0xC7), mais peut aussi être réalisé par le point de code COMBINING CEDILLA (0x327) précédé du point de code de C (0x43). Petite illustration en Python ci-dessous : 

    >>> "\u00C7"
Ç
>>> "\u0043\u0327"
Ç
>>> "\u0043"
C
>>> "\u0327"
 ̧

    Ainsi, les séquences de points de code doivent être considérées modulo une relation d'équivalence qui exprime que C suivi de COMBINING CEDILLA ne doit pas être distingué de Ç. Pour cette raison, la norme Unicode décrit un algorithme de normalisation qui calcule pour toute séquence de points de code une autre séquence, sa forme normale. Cet algorithme vérifie des propriétés très classiques ; en écrivant \(\equiv\) pour l'équivalence et \(\mathit{nf}\) pour l'algorithme de normalisation, on a que

    1. toute séquence est équivalente à sa forme normale (\(s \equiv \mathit{nf}(s)\)),
    2. deux séquences équivalentes ont la même forme normale (\(s_1 \equiv _2 \Rightarrow \mathit{nf}(s_1) = \mathit{nf}(s_2)\)),
    3. la normalisation est idempotente, une forme normale est sa propre forme normale (\(\mathit{nf}(\mathit{nf}(s)) = \mathit{nf}(s)\)).

    Le fragment de code Python montre un exemple de normalisation unicode. On doit spécifier la notion exacte de forme normale à utiliser, car la norme en propose plusieurs (ici Normal Form Canonical Composition ou NFC, qui recompose les combinaisons de caractère). 

    >>> len("\u0043\u0327")
2
>>> from unicodedata import normalize
>>> normalize("NFC", "\u0043\u0327")
'Ç'
>>> len(normalize("NFC", "\u0043\u0327"))
1

3. Cours 03 <2022-09-30 Fri>

3.1. Circuits élémentaires (§5)

3.1.1. Décodeur et multiplexeur

Soit \(k\) le nombre de bits d'entrée.

Circuit #NOT #(AND₂+OR₂) \(\Theta\)(profondeur)
Décodeur plat \(k\) \(2^k(k-1)\) \(\log_2(k)\)
Décodeur dichotomique \(2^k-1\) ou \(k\) \(2^{k+1}-2\) \(k\)
Multiplexeur plat \(k\) \(2^k(k-1)+1\) \(\log_2(k)\)
Multiplexeur dichotomique \(2^k-1\) ou \(k\) \(3 \cdot 2^k\) \(k\)

3.2. Additionneurs, première partie (§6.1–§6.4)

3.2.1. Demi-additionneur et additionneur complet

3.2.2. Additionneur k bits par propagation de retenue

3.2.3. Calcul des drapeaux

4. Cours 04 <2022-10-07 Fri>

4.1. Additionneurs, deuxième partie (§6.5–§6.9)

5. Cours 05 <2022-10-14 Fri>

5.1. Mémoires (§7)

Les supports mémoire peuvent être caractérisés selon des axes distincts.

  • Labilité : contenu fixé en usine ou bien réinscriptible ?
  • Durabilité : information persistante ou volatile ?
  • Mode d'accès : séquentiel ou aléatoire ?

Notons que ces axes ne sont pas indépendants : quelle serait l'utilité d'une mémoire non-persistante dont le contenu est fixé en usine ? Pour cette raison, la terminologie du domaine a tendance à rabattre certains axes sur d'autres, ce qui peut donner des résultats incohérents.

Caractéristique Read-Only Memory (ROM) Random-Access Memory (RAM) Erasable Programmable ROM (EPROM) Electrically EPROM (EEPROM)/Flash Ruban magnétique (historique)
Labilité fixé en usine réinscriptible réinscriptible via ultraviolets réinscriptible (électriquement) réinscriptible
Durabilité persistant volatile persistant persistant persistant
Mode d'accès quelconque/aléatoire aléatoire quelconque/aléatoire quelconque/aléatoire séquentiel

Ces technologies et leurs variations se distinguent aussi par leur coût de production à taille de données fixée, ainsi que leur performances (latence, débit). Ces caractéristiques réservent certaines technologies à certaines utilisations. Par exemple, on va voir qu'il existe deux types de RAM, la RAM dynamique (DRAM) réservée à la mémoire principale de l'ordinateur (objet physique extérieur au processeur), et la RAM statique (SRAM) utilisée pour les composants internes du processeur (p. ex., son cache).

5.1.1. RAM dynamiques (§7.1)

Une RAM dynamique de 1 bit est réalisée en associant un transistor, pour permettre la commande, et un condensateur, pour permettre de stocker une charge électrique.

Une DRAM peut être synchrone ou asynchrone, selon son mode d'interaction avec le processeur. Dans les deux cas, il y a ping-pong : le processeur envoie une adresse à la DRAM, elle répond avec la donnée à cette adresse.

Dans le cas asynchrone, la réponse arrive après un laps de temps inconnu, le processeur doit donc attendre la réponse.

Dans le cas synchrone, la DRAM répond au bout d'un nombre de cycles d'horloge fixé. (On détaillera bientôt la notion d'horloge.) Ce fonctionnement permet les accès pipelinés, comme lors d'un travail à la chaîne. Supposons par exemple que la mémoire prenne trois cycles d'horloge à répondre, et que la mémoire contienne la valeur \(v_i\) à l'adresse \(a_i\).

GET \(a_1\) GET \(a_2\) GET \(a_3\)     GET \(a_4\)       …
    OK \(v_1\) OK \(v_2\) OK \(v_3\)       OK \(v_4\)  
                   

Cet exemple illustre la différence de deux mesures de performance : le nombre de données transmises par unité de temps (le débit) d'une part, et le temps d'attente d'une réponse (la latence) de l'autre. Le fonctionnement pipeliné n'améliore pas la latence mais permet un débit de 1 donnée par cycle.

5.1.2. RAM statiques (§7.2)

Elles sont réalisables uniquement en utilisant uniquement des transistors.

Attention : il s'agit toutefois de circuits cycliques dont les sorties vont dépendre des valeurs présentes précédemment sur les fils impliqués dans le cycle, et éventuellement du temps de propagation de l'information. Par exemple, le circuit

x = NOT(y) y = NOT(X)

a deux états stables, respectivement x = 1 et y = 0 ou bien x = 0 et y = 1, et, si le circuit commence dans un état instable comme par exemple x = 0 et y = 0, il atteindra un état stable indéterminé.

  1. Verrou SR

    Le circuit précédent n'est pas très intéressant, parce qu'on ne peut pas contrôler l'état stable du circuit. Le verrou SR (Set-Reset latch) y remédie en introduisant deux entrées SET et RESET. On peut l'implémenter avec des NOR ou avec des NAND. La table suivante décrit son comportement. On voit que la sortie \(B\) dépend de la valeur \(B_p\) présente juste avant le changement de \(S\) et \(R\).

    \(S\) \(R\) \(B_p\) \(B\) \(\overline{B}\)
    \(0\) \(0\) \(x\) \(x\) \(\overline{x}\)
    \(1\) \(0\) \(x\) \(1\) \(0\)
    \(0\) \(1\) \(x\) \(0\) \(1\)
    \(1\) \(1\) \(x\) \(1\) \(1\)

    La dernière ligne est interdite puisque \(\overline{B}\) n'est plus la négation de \(B\). Plus grave, le passage de \(R = S = 1\) à \(R = S = 0\) est très périlleux : si les deux entrées passent à \(0\) au même moment, le résultat obtenu dépend du temps de propagation des données sur les fils !

  2. Verrou D

    Le verrou D a deux entrées data (\(\mathit{D}\)) et write (\(\mathit{W}\)). On la réalise à l'aide d'un verrou SR dont on contrôle les entrées comme suit.

    \[ R = \overline{D} W \\ S = D W \]

    Observons en particulier que \(RS\) n'est jamais vrai.

  3. Bascule D

    Elle a deux entrées, data (\(D\)) et clock (\(\mathit{Clk}\)). Elle est obtenue en mettant deux verrous D en série, et en contrôlant l'une des deux entrées \(W\) par \(\mathit{Clk}\) et l'autre par sa négation.

    On obtient ainsi un composant mémorisant qui retarde l'entrée D d'un cycle d'horloge, c'est-à-dire d'un front descendant de \(\mathit{Clk}\). L'exemple sera développé en travaux dirigés.

5.1.3. Organisation de la mémoire (§7.3)

  1. Mémoires \(k \times n\) bits

    Remarque : le cas \(n = 1\) est particulièrement intéressant parce que c'est celui qui est réalisé en pratique pour les circuits élémentaires. Les cas \(n > 1\) sont obtenus en assemblant des mémoires de largeur \(n = 1\).

  2. Mémoires \(1\) bit

    La solution en grille coûte \(2^(k/2+1) (k-1)\) transistors tandis que celle en une seule colonne coûte \(2^k (k - 1)\) transistors !

5.1.4. Mémoires associatives

Cette partie n'a pas été traitée en cours.

6. Cours 06 <2022-10-20 Thu>

6.1. Circuits séquentiels (§8)

Un circuit combinatoire n'a aucune notion de temps, à part le temps de propagation de l'information le long des fils.

Par oppostion, un circuit séquentiel dispose d'un fil distingué qui lui transmet son horloge. L'horloge est un signal périodique dont les fronts montants (ou descendants, au choix) contrôlent le changement des éléments mémorisants (bascules D, etc.) du circuit.

Pour générer un signal suffisamment périodique pour servir d'horloge, on a besoin d'un oscillateur le plus stable possible. La solution la plus répandue est d'utiliser un cristal de quartz : il a la spécificité de se déformer lorsque soumis à un champ électrique, puis de reprendre sa forme initiale une fois le champ coupé. Ce phénomène produit une tension. L'alternance répétée entre l'état déformé et l'état reformé génère le signal d'horloge.

Pour plus d'information sur les oscillateurs à base de quartz, voir la page Wikipédia anglaise, très complète.

https://en.wikipedia.org/wiki/Crystal_oscillator

6.1.1. Principe (§8.1)

6.1.2. Horloge (§8.2)

6.1.3. Exemple (§8.3)

  1. Guirlande lumineuse

    Remarque : le circuit rend explicite la différence entre \[ S = \mathtt{if}~\mathit{Cmd}~\mathtt{then}~S + 1~\mathtt{else}~S - 1 \] et \[ S = A + (\mathtt{if}~\mathit{Cmd}~1~\mathtt{else}~- 1) \] où on a économisé un additionneur. En logiciel, c'est la même chose !

  2. Automate

    On se propose de réaliser l'automate déterministe complet qui reconnaît le langage \((a b^* c)^+ \subseteq { a, b, c }^*\). L'automate a quatre états X, Y, Z et D avec X initial et Z final. Les transitions sont les suivantes :

    État courant Lettre Nouvel état
    X a Y
    Y b Y
    Y c Z
    Z a Y

    Dans tous les autres cas, on va dans l'état D.

    1. Codage logarithmique

      On code un automate complet à \(k\) états sur \(\log_2 k\) bits, et on l'implémente en calculant sa table de transition.

      Les lettres sont également codées sur 2 bits.

      On écrit \(s\) pour l'état au début du cycle d'horloge courant, \(s'\) pour l'état à la fin du cycle d'horloge courant. La fonction de transition exprime \(s'\) en fonction de \(s\) et de la lettre courante \(l\).

      \(s_1\) \(s_0\) \(l_1\) \(l_0\) \(s'_1\) \(s'_0\) Commentaire
      0 0 0 0 0 1 X -> Y sur A
      0 0 0 1 1 1  
      0 0 1 0 1 1  
      0 0 1 1 1 1  
      0 1 0 0 1 1  
      0 1 0 1 0 1 Y -> Y sur B
      0 1 1 0 1 0 Y -> Z sur C
      0 1 1 1 1 1  
      1 0 0 0 0 1 Z -> Y sur A
      1 0 0 1 1 1  
      1 0 1 0 1 1  
      1 0 1 1 1 1  
      1 1 0 0 1 1  
      1 1 0 1 1 1  
      1 1 1 0 1 1  
      1 1 1 1 1 1  

      On en déduit les équations suivantes.

      \begin{align*} s'_1 & = \overline{ \overline{s_1} \overline{s_0} \overline{l_1} \overline{l_0} + \overline{s_1} s_0 \overline{l_1} l_0 + \overline{s_1} s_0 l_1 l_0 } \\ s'_0 & = \overline{ \overline{s_1} \overline{s_0} \overline{l_1} \overline{l_0} + \overline{s_1} s_0 \overline{l_1} l_0 + \overline{s_1} s_0 l_1 l_0 } \end{align*}
    2. Codage "one hot"

      On utilise \(k\) bits pour représenter \(k\) états. Le bit $s_U exprime "l'automate est dans l'état \(U\)".

      \begin{align*} s'_X & = 0 \\ s'_Y & = s_X \overline{l_1} \overline{l_0} + s_y \overline{l_1} l_0 + s_z l_1 \overline{l_0} \\ s'_Z & = s_X l_1 \overline{l_0} \end{align*}

      Inconvénient : exponentiellement plus coûteux en espace.

      Avantages : les formules de l'automate ont tendance à être plus simples ; n'a pas besoin que l'automate soit complet ou déterministe.

6.2. Architecture générale d'un micro-processeur (§9)

L'exécution d'une instruction se décompose très schématiquement en trois grandes étapes LIRE / CALCULER / ÉCRIRE, qui elles-même se subdivisent en plusieurs sous-étapes : accès à la mémoire (aussi bien pour lire l'instruction courante que ses opérandes), accès aux registres, stockage des resultats en mémoire, etc.

6.3. Micro-processeur LC-3 (§10)

On couvre jusqu'aux paragraphes introductifs de §10.4 (avant §10.4.1).

6.4. TODO Pour la prochaine fois

  • Amener son ordinateur portable à la prochaine séance de TD/TP.
  • De préférence, installer Logisim avant la séance.

7. Cours 07 <2022-10-28 Fri>

7.1. Instructions du LC-3 (§10.4)

On termine cette section.

7.1.1. Remarque culturelle

L'instruction Load Effective Adresse (LEA) appartient également au jeu d'instruction x86(-64). C'est même l'une des plus utilisées !

7.1.2. Sauts indirects (JMP)

C'est utile dans absolument tous les langages de programmation généralistes, quels qu'ils soient. Ils ont tous besoin de sauts indirects pour implémenter l'appel à un fragment de code statiquement inconnu, construction au coeur de la programmation modulaire.

7.2. Programmation du LC-3 (§11)

7.2.1. Remarque terminologique

Informellement, on utilise souvent le terme "assembleur" pour parler du langage textuel formé par le jeu d'instruction de l'architecture considérée. Rigoureusement, il faudrait plutôt parler de langage d'assemblage.

Le terme "assembleur" devrait être réservé pour le logiciel qui lit un fichier contenant du langage d'assemblage (textuel, donc) et produit un fichier contenant du langage machine (binaire, donc). Dans le cas du LC-3, `lc3-as` est l'assembleur ; sur votre ordinateur personnel, vous disposez sans doute de `gas`, l'assembleur du projet GNU.

L'assembleur effectue une tâche très simple et mécanique puisque les instructions du langage d'assemblage et celles du code machine sont en bijection, ou quasiment (cf. RET vs. JMP R7). En plus du codage, l'assembleur remplit une autre tâche très utile : remplacer les étiquettes utilisées dans le format textuel au niveau des sauts par des offsets qu'il a calculés.

On s'arrête avant §11.1.1.

8. Cours 08 <2022-11-18 Fri>

8.1. Programmation du LC-3 (§11)

Une version des lc3tools est fournie dans le répertoire tools/lc3 du cours. Ils peuvent être compilés suivant la recette UNIX classique. 

$ cd tools/lc3
$ ./configure
$ make

Les exemples de code programmé durant ce cours sont disponibles dans le sous-répertoire tools/lc3/examples/.

8.1.1. Longueur d'une chaîne, version 1

On voit comment adapter le code C naïf en le traduisant littéralement en assembleur. On peut ensuite essayer d'optimiser. Mais optimiser quoi ?

Si l'on pense à notre implémentation très simple du LC-3, on voit que toutes les instructions ont le même coût, soit 2 cycles. Optimiser, pour nous, ce sera donc simplement réduire le nombre d'instructions exécutées.

(Ce n'est pas le cas de processeurs plus sophistiqués où les instructions ont un temps d'exécution (une latence) variable ; c'est déjà le cas pour le processeur LC-3 décrit dans le livre de Patt & Patel, où les accès mémoires peuvent prendre bien plus de deux cycles !)

Notre code passe l'essentiel de son temps dans la boucle, du moins si la chaîne de caractère est longue. Notre but est donc de réduire le nombre d'instructions dans le code de la boucle, quitte à augmenter d'un facteur constant la longueur du code englobant.

8.1.2. Réduire le nombre de sauts

Peut-on éviter de faire deux sauts dans le corps de la boucle ? Oui, grâce à une observation générale sur l'équivalent des boucles while en assembleur. La boucle while générique ressemble au code suivant. 

loop: ...               ; code mettant à jour rflags pour le test de sortie
      BR[n][z][p] exit  ; test de sortie de boucle
      ...               ; corps de la boucle
      BR loop           ; itération suivante
exit: ...               ; code après la boucle

Une astuce classique pour réduire le nombre d'instructions dans le corps de la boucle consiste à sortir le test pour éviter d'avoir deux branchements. 

      ...               ; code mettant à jour rflags pour le test de sortie
      BR[n][z][p] exit  ; test de non prise de la boucle
loop: ...               ; corps de la boucle
      ...               ; code mettant à jour rflags pour le test de sortie
      BR[n][z][p] loop  ; test de sortie/continuation de boucle
exit: ...               ; code après la boucle

Cette astuce revient à réécrire l'équivalent des boucles while (cond) { body } en if (cond) { do { body } while (cond) }. On gagne en taille de code si le test de fin de boucle est petit par rapport au code.

  1. Deuxième astuce

    On peut éviter d'avoir deux incrémentations en calculant une différence dans la sortie de la boucle.

8.1.3. Multiplication

L'implémentation itérative naïve de \(x \cdot n\) ne pose pas de problème mais est très lente, au point d'être probablement inutilisable en pratique.

On va exploiter une méthode logarithmique en la valeur de \(n\), et donc linéaire en la taille de \(n\), c'est-à-dire en son nombre de bits.

  1. Schéma de Horner

    Soit \(P[X]\) un polynôme

    \[ P[X] = a_0 + a_1 X + a_2 X^2 + \ldots + a_{n-1} X^{n-1} + a_n X^n \]

    de degré \(n\). Pour évaluer \(P\) en un point \(x\), on peut bien sûr substituer substituant \(x\) pour \(X\) dans la formule ci-dessus. Le calcul du monome de degré \(i\) nécessite alors \(i\) multiplications, et l'évaluation exige donc

    \[ \sum_{i = 0}^n i = \frac{n(n + 1)}{2} \]

    multiplications en tout.

    Une autre solution, souvent appelée schéma de Horner, consiste à factoriser les multiplications par les puissances de X pour diminuer le nombre de produits.

    \[ P[X] = a_0 + X(a_1 + X (a_2 + \dots X(a_{n-1} + X a_n))). \]

    On retombe à \(n\) multiplications.

  2. Application à la multiplication rapide

    On applique l'idée du schéma de Horner à la multiplication de \(a\) par \(b\). Écrivons \(b\) en base \(2\) comme \(b = \sum_{i = 0}^k b_i 2^i\). On a alors

    \begin{align*} a \cdot b & = a \cdot \sum_{i = 0}^{k-1} b_i 2^i \\ & = \sum_{i = 0}^{k-1} a b_i 2^i \end{align*}

    On reconnaît l'évaluation du polynôme \(P[X] = \sum_{i = 0}^{k-1} (a b_i) X^i\) en \(2\). On peut donc utiliser le schéma de Horner.

    On pose \[ x_i = \sum_{j = i}^{k-1} a b_j 2^{j-i} \] où chacun des \(x_i\) représente une des étapes du schéma de Horner. En particulier, on a \(x_k = 0\) et \(x_0 = a \cdot b\). La nature récursive du schéma de Horner s'exprime par l'équation suivante, qui suppose \(i > 0\).

    \begin{align*} x_{i-1} & = \sum_{j = i-1}^{k-1} a b_j 2^{j-i+1} \\ & = a b_{i-1} + \sum_{j = i}^{k-1} a b_j 2^{j-i} 2 \\ & = a b_{i-1} + 2 x_i \\ & = \begin{cases} a + 2 x_i & \mbox{si } b_{i-1} = 1 \\ 2 x_i & \mbox{si } b_{i-1} = 0 \end{cases} \end{align*}

    Le code fourni calcule \(x_{i-1}\) à partir de \(x_i\), pour \(i\) variant de \(16\) à \(1\). Le calcul termine en 16 itérations dans tous les cas, alors que la multiplication naïve termine en \(2^{15}\) étapes dans le pire cas.

9. Cours 09 <2022-11-25 Fri>

9.1. Les sous-routines et la pile (§12)

On traite de toute cette partie des notes.

9.1.1. Emplacements mémoire réservé (§12.3.2)

Note : une routine f() est "réentrante" lorsque le flot de contrôle peut se trouver dans plusieurs appels à f() simultanément. Cela peut se produire soit en cas de récursion, soit en cas de multitâche.

10. Cours 10 <2022-12-02 Fri>

10.1. Entrées/sorties et interruptions (§10)

10.1.1. Introduction

Les cours précédents ont concerné la réalisation des calculs et manipuler de l'information présente en mémoire. Un système informatique qui ne disposerait que de ces capacités ne serait pas très utile, puisque son exécution mènerait nécessairement à un résultat fixe (les entrées étant fixées) qu'il ne pourrait même pas afficher.

Pour cette raison, les systèmes réels disposent de fonctionnalités dites d'entrée-sortie. Le terme est très large et recouvre l'accès à divers périphériques par divers bus, interfaces et protocoles (par exemple USB ou PCI-Express). Les périphériques peuvent permettre de stocker des résultats sur une mémoire de stockage (p. ex. SSD, disques durs), de communiquer sur un réseau, d'afficher des images sur un écran, etc. Dans un système embarqué, les périphériques permettraient plutôt d'accéder aux valeurs mesurées par des capteurs, ou de contrôler des dispositifs physiques (p. ex. des moteurs).

Le fonctionnement précis des mécanismes d'entrée-sortie et des différentes formes de communication entre un processeur et ses périphériques sont souvent très techniques et dépassent le cadre de ce cours. On va se concentrer sur le fonctionnement du LC-3 et de ses deux périphériques idéalisés : l'écran et le clavier. (Le LC-3 dispose aussi d'un minuteur dont on ne traitera pas ici.)

10.1.2. Comment accéder aux périphériques ?

Une première possibilité serait d'avoir des instructions réservées. C'est le cas de certaines architectures historiques comme par exemple le Zilog Z80, micro-processeur 8 bits populaire dans les années 70 et 80. Ces instructions reçoivent deux opérandes : le périphérique à affecter, identifié par un numéro appelé "port", et le registre de destination (pour les lectures) ou de source (pour les écritures). Le problème de cette approche est que les instructions dédiées coûtent cher, surtout sur les architectures où la taille d'une instruction est petite. De plus, le mécanisme est assez ad-hoc et rend l'accès aux périphériques difficile à contrôler par le système d'exploitation.

Les processeurs modernes exposent les périphériques aux programmes via l'espace mémoire. Autrement dit, certaines cases mémoires n'en sont pas vraiment : elles jouent le rôle d'interfaces de communication avec les périphériques. Pour parler très figurativement, ce sont des fenêtres qui permettent d'observer l'état du périphérique, et de le modifier. Cet état prend la forme de ce qu'on appelle les registres d'entrée-sortie.

Sur les processeurs modernes, l'assignation des registres d'entrée-sortie aux adresses mémoires est flexible et sous le contrôle du logiciel (voir IOMMU). Sur les processeurs simples comme le LC-3, celle-ci est fixe. Dans l'annexe A du livre de Patt et Patel figure un tableau dont vous trouverez un extrait ci-dessous.

Adresse Registre E/S Fonction
xFE00 Keyboard Status (KBSR) Le bit de poids fort indique qu'un nouveau caractère peut être lu.
xFE02 Keyboard Data (KBDR) Les huit bits de poids faible contiennent le code ASCII du dernier caractère lu.
xFE04 Display Status (DSR) Le bit de poids fort indique que le dernier caractère envoyé peut être affiché.
xFE06 Display Data (DDR) Les huits bits de poids faible contiennent le code ASCII du prochain caractère à afficher.

Pour illustrer le fonctionnement des accès au clavier, voici un fragment de code extrait du fichier lc3os.asm fourni avec les lc3tools. Il implémente l'appel système GETC, de code \(x20\). 

OS_KBSR: .FILL xFE00
OS_KBDR: .FILL xFE02

TRAP_GETC: LDI R0, OS_KBSR
           BRzp TRAP_GETC
           LDI R0, OS_KBDR
           RET

Ce code est typique : on attend que le registres E/S KBSR nous indique qu'un nouveau caractère est disponible, puis on lit celui-ci depuis KBDR. Cette dernière action réinitialise implicitement le bit de poids fort de KBSR, ce qui assure qu'il ne sera pas lu deux fois.

10.1.3. Les interruptions

Dans le code précédent, processeur et le périphérique communiquent par un protocole très simple, par scrutation (ou encore attente active) du registre KBSR par le processeur. On comprend bien que ce n'est pas très efficace, en particulier si l'on garde en tête que le processeur est significativement plus rapide que le clavier (et l'utilisateur !).

Une alternative est l'utilisation du mécanisme d'interruption du processeur, qui permet au périphérique de signaler au processeur qu'un traitement a été complété ou qu'un événement vient de se produire. Par exemple, qu'un caractère a été entré au clavier.

Lorsque l'interruption se déclenche, l'exécution du programme est… interrompue, pour se poursuivre avec l'exécution d'un fragment de code prédéclaré, la routine d'interruption. L'adresse de la routine d'interruption qui traite une classe particulière d'interruptions (par exemple, celles déclenchées par une frappe clavier) est spécifiée à une adresse mémoire fixée qui correspond à un indice dans la table des interruptions, située de x0100 à x01FF.

Bien sûr, un problème se pose : que se passe-t-il si un processeur en déjà en train d'exécuter une routine d'interruption lorsqu'il est interrompu ? Chaque interruption a une priorité fixe, qui est un entier positif codé sur 3 bits. Seule une interruption strictement plus prioritaire que l'interruption courante peut interrompre cette dernière.

Les détails de l'invocation et de la sortie des routines d'interruption sont assez délicats. En particulier, comme le code utilisateur peut être interrompu à n'importe quel moment, la sous-routine d'interruption ne doit pas écraser les registres, ou bien doit les sauvegarder puis restaurer, comme lorsqu'on écrit une fonction avec une convention d'appel où les registres sont callee-save.

10.2. Mémoires cache (§17)

10.2.1. Introduction

Dans le circuit en Logisim que vous traitez pour le projet, toutes les instructions ont la même durée (deux cycles d'horloge). C'est possible uniquement parce qu'on suppose que la mémoire fonctionne à la même cadence que le processeur, et est capable de servir une requête par cycle.

En réalité, les mémoires sont fabriquées avec des technologies spécifiques (cf. cours 5), fonctionnent à une cadence différente du processeur, et sont situées sur des circuits séparés du processeur. Pour toutes ces raisons, un accès mémoire, requête puis réponse, peut occuper le processeur pendant des dizaines voire des centaines de cycles. (C'est d'ailleurs pour cette raison entre autres que l'architecture dispose de registres !)

À votre avis, combien de chargements mémoires dans vos programmes, en pourcentage du nombre total d'instructions ?

Cent pourcents, puisque toutes les instructions doivent être chargées. La vitesse des accès mémoires est donc vitale. Heureusement, en pratique les motifs formés par les accès mémoires des programmes au cours du temps sont loin d'être aléatoires, et on va exploiter ce fait pour améliorer nettement les performances.

10.2.2. La localité

Reprenons l'exemple des accès mémoires qui correspondent à des chargements d'instruction. La plupart du temps, après avoir chargé une instruction, on va charger l'instruction qui suit, puis celle d'après, etc. Autrement dit, on va lire des zones mémoires contiguës. Cette propriété de la suite des accès mémoires d'un programme s'appelle la localité spatiale.

Dans quel cas ne charge-t-on pas l'instruction suivante ? Lorsqu'on vient d'exécuter un branchement, qui a modifié PC. Pensez à un programme simple, par exemple compilé depuis C : de quelles constructions de haut niveau ces branchements sont-ils issus ?

  • Conditionnelles.
  • Boucles (for ou while ou do while).
  • Appels de fonctions (y compris récursifs).
  • Appels de pointeur de fonctions.

Les plus fréquents sont, presque par définition, les branchements qui implémentent les boucles. Les instructions qui constituent le corps de la boucle vont être répétées, et donc chargées plusieurs fois. On parle de localité temporelle pour désigner le fait que les accès mémoire à une adresse donnée ont tendance à se répéter.

C'est une caractéristique des chargements qui est également vrai des chargements de données. Le code va avoir tendance à relire les mêmes variables, par exemple.

10.2.3. Caractéristiques des caches

Le cache est une petite mémoire placée directement sur le CPU. Elle s'interpose entre le reste du CPU et la mémoire principale, et contient une copie de certaines données.

Le cache est organisé sous forme de lignes, chaque ligne contenant les données associées à plusieurs adresses mémoires contiguës.

Les caches se distinguent par les caractéristiques suivantes :

  • le nombre de lignes et leur taille,
  • l'associativité,
  • la politique d'éviction,
  • la politique d'écriture (write-back ou write-through).

L'associativité est un entier compris entre \(1\) et \(L\), où \(L\) est le nombre de lignes du cache. Elle désigne le nombre de lignes à laquelle une adresse donnée peut être stockée. Dans un cache L-associatif, ou pleinement associatif, n'importe quelle adresse peut être assignée à n'importe quelle ligne. Dans un cache 1-associatif, ou direct, elle ne peut être assignée qu'à une seule ligne.

La politique d'éviction détermine quelle ligne va être remplacée par la nouvelle ligne lors d'un défaut de cache.

La politique d'écriture détermine si l'on transmet les écritures à la mémoire principale immédiatement (write-through) ou bien si l'on attend l'éviction (write-back). La deuxième politique est plus efficace en moyenne mais plus coûteuse à implémenter.

Auteur: Adrien Guatto

Created: 2022-12-02 Fri 20:00

Validate