Circuits et architecture 2023/2024 – Journal du cours
Table des matières
Ce fichier est disponible au format HTML.
1. Cours 01
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-23-24
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.
(Ce support 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 du support de M. Carton et du journal ne peut se substituer à 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 |
| 2023 | M2 Ultra | Apple | 64 bits | 3,5 GHz | 134G | ARM, 24c |
Beaucoup d'autres choses à l'époque et depuis 2003 : essor puis déclin puis retour des architectures RISC ; récemment essor de puissants concurrents à x86-64 (ARM, Apple, 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". L'addition dans 𝔹 vérifie donc \(x + x = x\), contrairement à l'addition des entiers par exemple ; cette propriété de l'addition s'appelle idempotence.)
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
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
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 expliquer cette réalisation, nous allons un peu de physique et d'électronique.
Plus précisément, nous allons 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, cette explication sera 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 semi-conducteur 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 booléenne
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, un tel circuit doit être modélisé par une contrainte régissant les valeurs autorisées sur les fils. Une telle 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. Les autres cas correspondent à des problèmes électriques : ∅ modéliser un court circuit, {0, 1} un circuit instable (non-déterministe).
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\).
- 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.
- Entiers relatifs
On a le choix entre plusieurs représentations.
- 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.
- 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 \]
- 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) ?
- 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
- Magnitude signée
- Opérations arithmétiques
- 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]\).
- 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.
- 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.
- Somme d'entiers non signés
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
- 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.
- 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 :
- 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 ;
- 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 codeCOMBINING CEDILLA(0x327) précédé du point de code deC(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
Csuivi deCOMBINING CEDILLAne 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- toute séquence est équivalente à sa forme normale (\(s \equiv \mathit{nf}(s)\)),
- deux séquences équivalentes ont la même forme normale (\(s_1 \equiv _2 \Rightarrow \mathit{nf}(s_1) = \mathit{nf}(s_2)\)),
- 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
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
4.1. Additionneurs, première partie (§6.4)
4.1.1. Détection du dépassement de capacité
On rappelle que sur \(k\) bits, la représentation en complément à 2 code l'intervalle \([-2^{k-1}, 2^{k-1}-1]\) de \(\matbb{Z}\). Soient \(x\) et \(y\) deux entiers appartenant à cet intervalle. On s'intéresse à la somme \(x + y\) : dans quelle cas ne peut-elle pas être représentée sur \(k\) bits ?
Supposons tout d'abord que \(x\) est positif et \(y\) négatif. On a donc \(x \in [0, 2^{k-1}-1]\) et \(y \in [-2^{k-1}, 0]\). La somme \(x + y\) est donc maximale lorsque \(x = 2^{k-1}-1\) et \(y = 0\), auquel cas \(x + y = 2^{k-1} - 1\). Elle est minimale lorsque \(x = 0\) et \(y = -2^{k-1}\), auquel cas \(x + y = 2^{k-1}\). Donc \(x + y\) est toujours codable sur \(k\) bits. De plus, on peut remarquer que dans ce cas, la retenue du bit de poids fort est forcément 0, tandis que la retenue sortante est également 0 puisque les bits de signes sont les mêmes.
L'addition étant commutative, le raisonnement précédent est le même pour \(x\) strictement négatif et \(y\) positif. On vient donc de montrer que lorsque deux nombres sur \(k\) bits sont de signes différents, leur somme est toujours codable sur \(k\) bits.
Considérons maintenant le cas où \(x\) et \(y\) sont tous les deux positifs. On a donc \(x, y \in [0, 2^{k-1}-1]\). Le plus grand entier obtenu est \(2 (2^{k-1} - 1) = 2^k-2\) qui n'est pas codable avec moins de \(k+1\) bits. Plus généralement, on souhaite détecter les cas où \(x + y \in [2^{k-1}, 2^k-2]\). Pour cela, il suffit de réfléchir à cette somme en considérant
Par exemple
| c | 0 | 1 | 1 | 0 |
|---|---|---|---|---|
| a | 0 | 0 | 1 | |
| b | + | 0 | 1 | 1 |
| s | 1 | 0 | 0 |
4.2. Additionneurs, deuxième partie (§6.5–§6.9)
5. Cours 05
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 performance (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é.
- 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 !
- Verrou D
Le verrou D a deux entrées data (\(\mathit{D}\)) et write (\(\mathit{W}\)). On le 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.
- 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)
- 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\).
- 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
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.
6.1.1. Principe (§8.1)
6.1.2. Horloge (§8.2)
6.1.3. Exemple (§8.3)
- 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 !
- Automates finis
On va voir plusieurs façons de coder un automate. Elles partagent la même conception : on code l'état de l'automate sur un certain nombre de bits, disons \(n\), et on programme une fonction de transition \(f\) qui détermine les \(n\) bits du nouvel état, noté \(s'\), ainsi que la sortie courante, en fonction des entrées courantes et de l'état précédent \(s\). Autrement dit, si les entrées sont codées sur \(i\) bits et les sorties sur \(o\) bits, on a
\[ f : \mathbb{B}^n \times \mathbb{B}^i \to \mathbb{B}^n \times \mathbb{B}^o. \]
On implémente facilement l'automate avec un circuit cyclique utilisant \(n\) bascules D pour stocker l'état courant. Les notes de cours en donnent une vision graphique, qu'on peut également écrire symboliquement comme l'équation ci-dessous.
\[ (s', o) = f(\mathit{flipflop}^n(s'), i) \]
- Automate déterministe
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.
- Codage logarithmique
On code un automate complet à \(k\) états sur \(n = \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 \to 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 \to Y\) sur \(b\) 0 1 1 0 1 0 \(Y \to Z\) sur \(c\) 0 1 1 1 1 1 1 0 0 0 0 1 \(Z \to 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*}La sorte \(\mathit{OK}\) de la fonction de transition détermine l'acceptation. Elle est vraie si et seulement si on est dans l'état \(Z\).
\[ \mathit{ok} = s_Z = s_1 \overline{s_0} \]
- Codage "one hot"
On utilise \(n = 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 & = \overline{l_1} \overline{l_0} \cdot s_X + \overline{l_1} l_0 \cdot s_Y + l_1 \overline{l_0} \cdot s_Z \\ s'_Z & = l_1 \overline{l_0} \cdot s_X \end{align*}On peut aussi écrire, de façon plus lisible,
\begin{align*} s'_X & = 0 \\ s'_Y & = a \cdot s_X + b \cdot s_Y + c \cdot s_Z \\ s'_Z & = c \cdot s_X \end{align*}où on a abrégé les codages \(a = \overline{l_1} \overline{l_0}\), \(b = \overline{l_1} l_0\) et \(c = l_1 \overline{l_0}\).
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, comme on va le voir tout de suite.
- Codage logarithmique
- Automate non-déterministe
Considérons maintenant l'automate non-déterministe à 4 états suivant, qui reconnaît un certain langage sur l'alphabet \(\{ a, b, c \}^*\). L'automate a quatre états \(X\), \(Y\), \(Z\) et \(D\) avec \(X\) initial et \(Z\), \(K\) finaux. Les transitions sont les suivantes :
État courant Lettre Nouvel état X a Y X a K Y c Y Y b Z Z a K K c Y K c Z K a K On peut procéder au codage "one hot", qu'on devrait plutôt appeler "many hot" dans le cas précédent : plutôt que de déterminiser l'automate, on va accepter que celui-ci se trouve dans plusieurs états simultanément, dans une superposition d'états. Autrement dit, plusieurs bits \(s_X\), \(s_Y\), \(s_Z\) et \(s_K\) peuvent se trouver dans le même état.
\begin{align*} s'_X & = 0 \\ s'_Y & = a \cdot s_X + c \cdot s_Y + c \cdot s_K \\ s'_Z & = b \cdot s_Y + c \cdot s_K \\ s'_K & = a \cdot s_Z + a \cdot s_K \\ \end{align*}On accepte dès lors qu'on est dans un état final.
\[ \mathit{OK} = s_Z + s_K \]
- À propos des automates non déterministes
Considérons l'automate précédent et notons \(s\) pour le vecteur de 4 bits \(\langle s_X, s_Y, s_Z, s_K \rangle\).
La fonction de transition de notre automate, déterministe ou pas, vérifie l'équation
\[ f(s_1 + s_2, i) = f(s_1, i) + f(s_2, i) \]
où \(s_1\) et \(s_2\) sont des vecteurs d'états quelconques. Cette équation exprime simplement que l'ensemble des états qu'on peut atteindre en un pas à partir de l'union des états décrits par \(s_1\) et de ceux décrits par \(s_2\) est l'union de l'ensemble des états qu'on peut atteindre en un pas à partir de \(s_1\) avec l'ensemble des états qu'on peut atteindre en un pas à partir de \(s_2\).
Une telle fonction qui préserve les sommes, est dite linéaire. Ici, la somme est le OU logique, mais on peut malgré tout exploiter certaines techniques issues de l'analogie de l'algèbre linéaire. Par exemple, le codage proposé n'est rien d'autre qu'une multiplication de matrice.
\begin{align*} \underbrace{\left( \begin{matrix} s'_X \\ s'_Y \\ s'_Z \\ s'_K \\ \end{matrix} \right)}_{s'} & = \underbrace{\left( \begin{matrix} 0 & 0 & 0 & 0 \\ a & c & 0 & c \\ 0 & b & 0 & c \\ 0 & 0 & a & a \\ \end{matrix} \right)}_{A} \cdot \underbrace{\left( \begin{matrix} s_X \\ s_Y \\ s_Z \\ s_K \\ \end{matrix} \right)}_{s} \end{align*}On peut aussi répondre à des questions intéressantes. Par exemple : comment décrire facilement le même automate mais modifié pour lire deux lettres à la fois en une transition ? Il suffit de calcule la composition de l'automate avec lui-même, c'est-à-dire le carré de la matrice de transition. On code par \(l_0 l_1\) la première lettre et \(l_0' l_1'\) la seconde.
\begin{align*} \underbrace{\left( \begin{matrix} 0 & 0 & 0 & 0 \\ a' & c' & 0 & c' \\ 0 & b' & 0 & c \\ 0 & 0 & a' & a' \\ \end{matrix} \right)}_{A'} \cdot \underbrace{\left( \begin{matrix} 0 & 0 & 0 & 0 \\ a & c & 0 & c \\ 0 & b & 0 & c \\ 0 & 0 & a' & a' \\ \end{matrix} \right)}_{A} & = \left( \begin{matrix} 0 & 0 & 0 & 0 \\ ac' & cc' & ac' & cc' + ac' \\ ab' & cb' & ac & cb' + ca \\ 0 & ba' & aa' & ca' + aa' \\ \end{matrix} \right) \end{align*}
- Automate 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. 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.