Lecture de la notation. Une capacité s'écrit toujours sous la forme (nombre de mots × largeur d'un mot). « 4K × 16 » signifie donc 4096 mots de 16 bits. Le second nombre est la largeur du bus de données, le premier se déduit du bus d'adresses.

1. Lignes nécessaires.

• Lignes de données : elles portent un mot, donc leur nombre est la largeur du mot, soit 16 lignes $D_0 \ldots D_{15}$.
• Lignes d'adresses : il faut pouvoir désigner chacune des 4096 cases. Or $4096 = 2^{12}$, donc il faut 12 lignes d'adresses $A_0 \ldots A_{11}$.

La règle générale est $m$ lignes d'adresses pour $2^m$ mots, et $n$ lignes de données pour des mots de $n$ bits.

2. Capacité en octets. La capacité totale en bits est le produit des deux :

$4096 \times 16 = 65\,536\ \text{bits} = \frac{65\,536}{8} = \mathbf{8192\ \text{octets}} = 8\ \text{Ko} .$

Ce qu'il faut retenir. La conversion bits → octets divise par 8, et elle ne dépend pas de la façon dont la mémoire est organisée : une mémoire 2K × 32 contient aussi 65 536 bits, soit 8 Ko, mais avec 11 lignes d'adresses et 32 lignes de données. Deux mémoires de même capacité en octets peuvent donc avoir des bus très différents — et c'est cette organisation, pas la capacité, qui détermine la façon de les câbler à un processeur.

Nombre de circuits. On compare les deux dimensions séparément :

• en profondeur : il faut $4096 / 1024 = 4$ fois plus de mots ;
• en largeur : il faut $16 / 8 = 2$ fois plus de bits par mot.

Les deux extensions sont indépendantes et se multiplient :

$4 \times 2 = \mathbf{8\ \text{circuits}} .$

Chaque circuit apporte 8 des 16 bits d'un mot, et quatre groupes de deux circuits se partagent la plage d'adresses.

Capacités.

• Un circuit : $1024 \times 8 = 8192$ bits $= 1024$ octets $= \mathbf{1\ \text{Ko}}$.
• La mémoire réalisée : $4096 \times 16 = 65\,536$ bits $= \mathbf{8\ \text{Ko}}$. On retrouve bien $8 \times 1$ Ko.

Adresses. La mémoire complète compte 4096 mots, donc 12 lignes d'adresses $A_{11} \ldots A_0$. Chaque circuit ne contient que 1024 mots, donc 10 lignes d'adresses : ce sont les lignes basses $A_9 \ldots A_0$, communes à tous les circuits. Les deux lignes hautes $A_{11}A_{10}$ sélectionnent le banc :

Au sein d'un banc, les deux circuits reçoivent les mêmes adresses et sont activés par le même signal de sélection : l'un pilote $D_0 \ldots D_7$, l'autre $D_8 \ldots D_{15}$. C'est l'extension en largeur, réalisée en parallèle.

Le point de méthode. Deux extensions, deux câblages différents. Pour augmenter la profondeur, on ajoute des circuits et on décode des adresses hautes pour n'en activer qu'un à la fois : les bus de données sont partagés et mis en haute impédance quand le circuit n'est pas sélectionné. Pour augmenter la largeur, on ajoute des circuits activés simultanément, chacun fournissant une tranche de bits. Confondre les deux mène à un câblage qui « a l'air » de fonctionner mais ne lit jamais les bons bits.

Exercice 4.

Étape 1 — combien de bits pour chaque boîtier ? Un boîtier de 16k contient $16 \times 1024 = 16\,384 = 2^{14}$ mots. Il lui faut donc 14 lignes d'adresses, $A_{13} \ldots A_0$, communes à tous les boîtiers. Les deux lignes hautes $A_{15}A_{14}$ font le décodage.

Étape 2 — lire les plages en binaire.

Étape 3 — le décodage. Un décodeur 2 vers 4 commandé par $A_{15}A_{14}$ produit les quatre sélections, dont trois sont utilisées. Chaque sortie est combinée avec le signal MEM (actif à 0) par une porte OU : la sélection n'est active que si MEM et la sortie du décodeur sont actifs simultanément. En logique active-bas, cela s'écrit CS = MEM + SEL_i — un OU, pas un ET, ce qui est l'erreur classique.

Étape 4 — les deux EPROM. Chacune est un boîtier de 16k × 16, et il en faut deux pour couvrir les 32 bits du mot : elles partagent les mêmes adresses et sont activées ensemble par la même sélection, l'une fournissant $D_0 \ldots D_{15}$ et l'autre $D_{16} \ldots D_{31}$. C'est une extension en largeur, comme dans l'exercice 2. Leurs $A_{13} \ldots A_0$ et leur $CS$ sont donc câblés en parallèle.

Étape 5 — le bus de données. Le bus est de 32 bits. La RAM et la ROM le pilotent en entier ; les EPROM n'en pilotent que la moitié, mais comme elles vont par deux, l'ensemble est cohérent. Le point délicat est la haute impédance : tout boîtier non sélectionné doit relâcher le bus, sans quoi deux boîtiers le piloteraient en même temps et le résultat serait un conflit électrique, pas une valeur logique.

Exercice 5.

Étape 1 — dimensionner. Le processeur a 8 bits de données, donc un mot par adresse. Chaque boîtier de 8K contient $8192 = 2^{13}$ mots et demande 13 lignes d'adresses $A_{12} \ldots A_0$.

Étape 2 — la ROM, 0000–7FFF. Cette plage fait 32K octets, soit quatre boîtiers de 8K. Il faut donc deux lignes supplémentaires pour choisir le boîtier : $A_{14}A_{13}$ sélectionnent l'un des quatre, et $A_{15} = 0$ valide la plage.

Étape 3 — la RAM, 8000–9FFF. Cette plage fait 8K octets, soit un seul boîtier de 8K : $A_{15} = 1$ et $A_{14} = 0$ et $A_{13} = 0$ suffisent à l'identifier. C'est le cas le plus simple : un seul boîtier, pas de sélection interne à décoder.

Étape 4 — les entrées/sorties, FFF8–FFFF. Ces huit adresses occupent le haut de l'espace. En binaire, FFF8 = 1111 1111 1111 1000 et FFFF = 1111 1111 1111 1111 : les treize bits de poids fort $A_{15} \ldots A_3$ valent tous 1, et seuls $A_2 \ldots A_0$ varient. La détection est donc un ET de toutes les lignes hautes :

$\text{SEL}_{E/S} = A_{15} \cdot A_{14} \cdot A_{13} \cdots A_3 .$

C'est exactement le motif d'un décodeur de type « une seule plage en haut de l'espace », et c'est ainsi que les microcontrôleurs réservent leurs registres de périphériques : le plan mémoire de l'ATmega2560 place les registres étendus d'entrée/sortie de $0100 à $01FF, et les registres internes de $0020 à $005F.

Étape 5 — le trou. La plage A000–FFF7 n'est affectée à rien. Il faut décider explicitement de son comportement : soit elle n'est pas décodée, soit elle est décodée vers un boîtier absent, soit elle est volontairement laissée en défaut pour déclencher une exception en cas d'accès erroné. Une plage non décodée qui n'est pas documentée est un bogue en attente : un pointeur perdu y écrit et personne ne s'en aperçoit.

Méthode. Une ROM n'est rien d'autre qu'une table de vérité câblée : chaque combinaison d'entrées est une adresse, chaque sortie est un bit du mot. Pour dimensionner la ROM, il faut donc compter les entrées et les sorties.

Entrées. L'opération porte sur deux opérandes de 4 bits, $A_3 \ldots A_0$ et $B_3 \ldots B_0$, soit 8 bits. À cela s'ajoute le choix de l'opération — addition ou soustraction — qui est une entrée supplémentaire de 1 bit. Total : $8 + 1 = 9$ bits d'entrée.

La ROM doit donc contenir

$2^9 = \mathbf{512\ \text{mots}} .$

Sorties. Le résultat est un mot de 4 bits, $S_3 \ldots S_0$, auquel s'ajoute l'indicateur de retenue $R$, soit $4 + 1 = 5$ bits.

Taille de la ROM : 512 mots × 5 bits.

Vérification par le contenu. Vérifions que 512 mots suffisent bien à contenir toute la fonction. Pour l'addition, le résultat maximal est $15 + 15 = 30$, qui s'écrit sur 5 bits (11110) — donc 4 bits de somme plus 1 bit de retenue suffisent, et aucune combinaison n'est perdue. Pour la soustraction, on peut soit produire le complément à deux sur 4 bits avec un indicateur de signe, soit réserver le bit supplémentaire à la retenue empruntée. Dans les deux cas, 5 bits de sortie couvrent exactement l'ensemble des résultats possibles.

Le commentaire à faire. Cette ROM coûte 2560 bits de stockage pour une fonction qu'un additionneur à retenues anticipées réalise avec quelques centaines de portes. La ROM gagne en temps d'accès constant — quel que soit le couple d'opérandes, le résultat sort en un cycle — et en simplicité de conception : on remplit une table, on ne simplifie rien. Elle perd en surface et en consommation, et surtout elle n'est pas modifiable sans reprogrammer la mémoire. C'est exactement le compromis que tranche un FPGA avec ses tables de correspondance (LUT), qui sont des ROM de quelques bits.

1. Arbre d'évaluation. La racine est la soustraction, dont le sous-arbre gauche est $b^2$ et le sous-arbre droit est $4ac$ :

1              sub2            /     \3         mult      mult4        /    \     /   \5       b      b   4    mult6                       /  \7                      a    c

La structure de l'arbre impose l'ordre des opérations : on évalue d'abord les deux multiplications, puis la soustraction.

La convention de pile, à fixer d'abord. C'est le point délicat de l'exercice, et il n'est pas symétrique. La convention retenue — celle du cours, vérifiée sur l'implémentation du PGCD au chapitre 5 — est la suivante : la pile se lit | gauche droite, l'opérateur dépile d'abord l'opérande droite (le sommet), puis l'opérande gauche (l'élément en dessous), calcule gauche op droite, et empile le résultat. La preuve en est donnée par l'implémentation du PGCD : sur une pile | A B, l'instruction CMP teste $A - B$ — donc $A$, plus profond, est bien l'opérande gauche.

2. Programme. En parcourant l'arbre en profondeur :

1push b        ; | b2push b        ; | b b3mult          ; | b²4push 4        ; | b² 45push a        ; | b² 4 a6push c        ; | b² 4 a c7mult          ; | b² 4 ac8mult          ; | b² 4ac9sub           ; | b² − 4ac10pop delta     ; | (vide), delta contient b² − 4ac

3. Contenu de la pile, étape par étape.

Vérification sur un exemple. Prenons $a = 1$, $b = 5$, $c = 6$ : le discriminant vaut $25 - 24 = 1$, donc deux racines réelles distinctes. Prenons $a = 1$, $b = 2$, $c = 3$ : $\Delta = 4 - 12 = -8$, donc aucune racine réelle. Le programme doit produire $-8$, ce qui exige que la soustraction soit faite dans le bon sens : inversée, elle donnerait $+8$, et l'erreur ne serait détectée que sur les cas où le discriminant est négatif — un bogue redoutable, car il ne se manifeste que sur la moitié des données.

Le commentaire à faire. L'arbre d'évaluation et la pile sont isomorphes : chaque feuille de l'arbre devient un push, chaque nœud interne un opérateur. C'est ce qui rend les machines à pile si élégantes pour compiler des expressions — mais l'ordre des opérandes devient une convention, et une convention non écrite est une source de bogues. Une machine à registres généraux, elle, nomme explicitement ses opérandes (SUB Rd, Rr) : l'ordre est dans l'instruction, pas dans la discipline du programmeur.

1. Alternative simple. Le schéma est toujours le même : on teste la négation de la condition et on saute par-dessus le bloc « alors ».

1        cpi  r0, 41        ; comparer r0 à 412        brlo sinon         ; si r0 < 41, c'est-à-dire r0 <= 40 : aller à sinon3        mov  r1, r2        ; bloc « alors »4        sub  r1, r3        ; r1 = r2 − r35        rjmp finsi6sinon:  ldi  r15, 257finsi:

Trois points de méthode. D'abord, la comparaison est non signée avec brlo ; pour des valeurs signées il faudrait brlt. Choisir la mauvaise famille est l'erreur la plus fréquente, et elle ne se voit que sur les valeurs négatives. Ensuite, brlo branche si $r_0 < 41$, ce qui est bien la négation de « $r_0 > 40$ » — attention au sens strict de la comparaison : comparer à 40 au lieu de 41 laisserait passer le cas $r_0 = 40$ dans la mauvaise branche. Enfin, plutôt que d'inverser mentalement chaque condition, on écrit la négation telle qu'elle se lit : « si $r_0$ n'est pas strictement supérieur à 40, alors… ».

2. Condition simple. $0\times5B = 91$.

1        cpi  r16, 0x5C     ; comparer r16 à 922        brlo suite         ; si r16 < 92, c'est-à-dire r16 <= 91 : rien à faire3        subi r19, -20      ; r19 = r19 + 204suite:

Même précaution : « supérieur à $0\times5B$ » exclut la valeur 91 elle-même, d'où la comparaison à 92. L'astuce subi r19, -20 mérite d'être notée : le jeu d'instruction AVR ne propose pas d'instruction addi (addition immédiate), seulement subi. Soustraire $-20$ revient à ajouter 20 — c'est le moyen standard d'écrire une addition immédiate sur AVR. Le piège est que subi travaille sur des entiers non signés de 8 bits : pour des valeurs signées, il faut passer par adiw sur une paire de registres ou charger la constante dans un registre.

3. Condition composée (ET logique). La structure change : avec un ET, chaque condition fausse doit sauter hors du bloc. Pour « $r_{16} > r_{17}$ », on compare dans l'ordre inverse afin d'obtenir directement la négation :

1        cp   r17, r162        brsh pasfais       ; si r17 >= r16, c.-à-d. r16 <= r17 : sauter3        cp   r19, r204        brne pasfais       ; si r19 != r20 : sauter5        ldi  r21, 0        ; les deux conditions sont vraies6pasfais:

Pour un OU, la structure est différente : chaque condition vraie saute dans le bloc. Retenir ces deux formes — ET = « sauter si faux », OU = « sauter si vrai » — évite de se tromper en écrivant une condition composée, où l'inversion de la logique est la source d'erreur classique.

4. Boucle « tant que $r_1 \neq r_0$ ». Le test est en tête : si la condition est fausse au départ, le corps n'est jamais exécuté.

1tantque: cp   r1, r02         breq fintantque3         ; ... corps de la boucle ...4         rjmp tantque5fintantque:

5. Boucle « faire … tant que $r_2 > r_3$ ». Le test est en pied : le corps est exécuté au moins une fois. Là encore on compare dans l'ordre inverse pour brancher directement sur la condition :

1faire:   ; ... corps de la boucle ...2         cp   r3, r23         brlo faire         ; si r3 < r2, c.-à-d. r2 > r3 : recommencer

La différence entre les deux formes n'est pas cosmétique : elle change le nombre d'exécutions du corps quand la condition est fausse dès le départ. Une boucle « tant que » s'exécute zéro fois, une boucle « faire … tant que » s'exécute une fois.

6. La boucle d'attente. Le programme fait décroître R23 de 255 jusqu'à 0 en ne faisant rien d'autre qu'un nop entre chaque décrément, puis sort quand R23 atteint 0.

Calcul du nombre de cycles. Avec les temps du jeu d'instruction : subi = 1 cycle, nop = 1 cycle, brne = 2 cycles si le branchement est pris et 1 sinon.

• Une itération complète prise : $1 + 1 + 2 = 4$ cycles.
• La dernière itération : le brne n'est pas pris, donc $1 + 1 + 1 = 3$ cycles.
• R23 passe de 255 à 0, soit 255 itérations.

$(254 \times 4) + 3 = 1016 + 3 = \mathbf{1019\ \text{cycles}} .$

À 16 MHz, cela représente $1019 / 16 \times 10^6 \approx 64\ \mu s$ — une temporisation très courte, obtenue sans aucune instruction spécialisée. C'est la brique de base de toutes les temporisations du TP 1 : pour clignoter une LED à un rythme visible, il faut empiler ces boucles.

Pourquoi 255 et pas 256 ? ldi R23, 255 charge la valeur maximale d'un octet non signé. La boucle s'exécute donc 255 fois, pas 256 : subi décrémente et positionne le drapeau Z quand le résultat est nul. C'est une boucle « jusqu'à zéro », la forme la plus efficace sur AVR, car elle n'a pas besoin d'une comparaison supplémentaire.

Ce que change le mode d'adressage. Le calcul est toujours le même — lire a, ajouter 15, écrire le résultat — mais la façon de désigner l'adresse varie. C'est précisément l'objet de l'exercice : montrer que le même algorithme s'écrit différemment selon l'architecture sous-jacente, et que le mode d'adressage disponible détermine la longueur et la lisibilité du code.

1. Adressage direct. L'adresse de l'opérande est écrite en clair dans l'instruction. Sur AVR, la mémoire de données s'adresse par les instructions LDS/STS.

1lds  r16, 1000        ; r16 <- mem[1000]      (lire a)2subi r16, -15         ; r16 <- r16 + 15       (pas de ADDI sur AVR)3sts  1001, r16        ; mem[1001] <- r16      (écrire b)

Trois instructions, et l'adresse est figée : si l'on veut répéter l'opération sur dix valeurs consécutives, il faut dix blocs d'instructions distincts. C'est le mode le plus simple et le moins souple.

2. Adressage indirect. L'adresse est dans un registre pointeur (X, Y ou Z, soit les paires r27:r26, r29:r28, r31:r30).

1ldi  r26, lo8(1000)   ; charger l'adresse basse dans XL2ldi  r27, hi8(1000)   ; charger l'adresse haute dans XH3ld   r16, X           ; r16 <- mem[X]         (lire a)4subi r16, -155st   X, r16           ; mem[X] <- r16

Ici le calcul de l'adresse est séparé de l'instruction d'accès : le pointeur peut être modifié à l'exécution, ce qui rend le mode indirect indispensable pour parcourir un tableau.

3. Indirect avec déplacement constant. AVR propose LDD/STD avec un déplacement constant de 0 à 63 appliqué au pointeur Y ou Z :

1ldi  r28, lo8(1000)2ldi  r29, hi8(1000)3ldd  r16, Y+0         ; lire mem[Y + 0] = a4subi r16, -155std  Y+1, r16         ; écrire mem[Y + 1] = b

Le déplacement est dans l'instruction, donc aucune instruction n'est dépensée pour calculer l'adresse de b : c'est le mode le plus économique quand l'écart entre les deux cases est connu à la compilation. Sa limite est la plage du déplacement — 63 octets — et le fait qu'il ne s'applique qu'à Y et Z.

4. Indirect avec post-incrémentation. L'instruction incrémente le pointeur après l'accès, ce qui enchaîne naturellement deux cases consécutives :

1ldi  r26, lo8(1000)2ldi  r27, hi8(1000)3ld   r16, X+          ; lire mem[1000], puis X <- 10014subi r16, -155st   X+, r16          ; écrire mem[1001], puis X <- 1002

Après ces instructions, X pointe sur 1002 : le pointeur est prêt pour la valeur suivante. C'est le mode de tous les parcours de tableau — une seule instruction d'accès, aucune instruction d'incrémentation, donc le code le plus court et le plus rapide.

Synthèse.

Ce que l'exercice démontre. Les quatre programmes font exactement la même chose. Le choix n'est donc pas une question de correction mais de coût : deux instructions de chargement du pointeur sont payées une fois, et amorties sur tout le parcours. Sur une seule valeur, l'adressage direct gagne ; sur mille, l'adressage indirect avec post-incrémentation gagne largement. C'est la conclusion générale du TD 2 : l'implémentation d'un algorithme dépend fortement de l'architecture qui effectue les manipulations de données.

1. Produit scalaire.

Le calcul. Le produit scalaire de deux vecteurs de 4 composantes est $\sum_{k=0}^{3} A_k B_k$. Les deux tableaux sont contigus : $A$ occupe les adresses 1024 à 1027, $B$ les adresses 1028 à 1031. La distance entre $A_k$ et $B_k$ est constante, égale à 4 — donc l'adressage indirect avec déplacement est le plus adapté.

1        ldi  r26, lo8(1024)     ; X pointe sur A[0]2        ldi  r27, hi8(1024)3        ldi  r28, lo8(1028)     ; Y pointe sur B[0]4        ldi  r29, hi8(1028)5        clr  r18                ; accumulateur, octet bas6        clr  r19                ; accumulateur, octet milieu7        clr  r20                ; accumulateur, octet haut8        clr  r22                ; registre à zéro, pour propager la seule retenue9        ldi  r21, 4             ; compteur de boucle10 11boucle: ld   r16, X+            ; r16 <- A[k], X pointe sur A[k+1]12        ld   r17, Y+            ; r17 <- B[k], Y pointe sur B[k+1]13        mul  r16, r17           ; R1:R0 <- A[k] * B[k]14        add  r18, r0            ; accumuler l'octet bas

Les trois points techniques. D'abord, mul sur AVR place un produit 8 × 8 = 16 bits dans la paire R1:R0 : il faut donc accumuler sur plusieurs octets, avec add pour l'octet bas et adc pour les suivants — c'est la propagation de la retenue qui est ici essentielle, et l'oublier est l'erreur classique.

Ensuite, le troisième octet demande une attention particulière. Le produit n'occupe que deux octets : la contribution à l'octet haut se réduit donc à la seule retenue sortie de l'octet milieu. Écrire adc r20, r1 serait une faute — cela rajouterait r1, déjà comptabilisé dans r19. On introduit pour cela un registre à zéro (r22), et l'instruction adc r20, r22 ne propage que la retenue. Ce détail est invisible sur de petites valeurs, où la retenue ne sort jamais de l'octet milieu.

Enfin, les deux pointeurs X et Y avancent en parallèle grâce au post-incrément, sans aucune instruction supplémentaire.

Le piège de dimensionnement. Vérifions que le résultat tient sur trois octets. Le maximum du produit scalaire est atteint quand les huit octets des deux vecteurs valent 255 :

$\sum_{k=0}^{3} 255 \times 255 = 4 \times 65\,025 = 260\,100 .$

Or $2^{16} = 65\,536 < 260\,100$ : le résultat ne tient pas sur 16 bits, et il faut au moins 18 bits, donc trois octets à partir de l'adresse 1032. Écrire le résultat sur deux octets « parce que mul produit 16 bits » est une erreur d'un facteur 4 sur la plage couverte — et elle ne se voit que sur les grandes valeurs, donc rarement pendant les tests. Si l'on veut se limiter à deux octets, il faut le démontrer : par exemple borner les entrées à $< 128$, ce qui donne $4 \times 128 \times 128 = 65\,536$, tout juste dans l'intervalle. Ce raisonnement préalable — quelle est la valeur maximale du résultat ? — doit précéder tout choix de format.

2. Adressage d'une matrice.

La formule d'adressage. La matrice est rangée ligne par ligne (row-major) à partir de l'adresse 2048. La ligne $i$ occupe donc 8 octets, et l'élément $(i, j)$ se trouve à

$\text{adresse}(i,j) = 2048 + 8 \times i + j .$

Vérification aux bornes : $(0,0)$ donne 2048, le premier élément ; $(15,7)$ donne $2048 + 120 + 7 = 2175$, le dernier — et $2175 - 2048 + 1 = 128 = 16 \times 8$, ce qui confirme que la matrice occupe bien 128 octets contigus.

Le programme. L'astuce est de calculer l'adresse par décalages : multiplier par 8 revient à décaler de trois rangs vers la gauche.

1        lds  r16, 0             ; r16 <- i2        lds  r17, 1             ; r17 <- j3        clr  r18                ; r18 = octet haut de l'adresse4        lsl  r16                ; i * 25        rol  r18                ;   (propager dans l'octet haut)6        lsl  r16                ; i * 47        rol  r188        lsl  r16                ; i * 89        rol  r1810        add  r16, r17           ; + j  (aucune retenue possible, voir ci-dessous)11        subi r16, low(-2048)    ; ajouter 2048 à l'adresse12        sbci r18, high(-2048)13        movw r30, r16           ; Z <- adresse calculée14        ldi  r17, 65            ; caractère 'A'

Ce qu'il faut remarquer. La multiplication par 8 se fait par trois décalages, chacun suivi d'une rotation dans l'octet haut : c'est la façon standard de multiplier par une puissance de 2 sur un processeur 8 bits, et elle ne coûte que 6 cycles. Le rol r18 est le point qu'on oublie : sans lui, une adresse dépassant 255 serait tronquée — le bogue ne se manifeste que sur les grandes valeurs, donc rarement pendant les tests.

L'addition de $j$ se fait par un simple add, sans propagation de retenue. Ce n'est pas une négligence : c'est une conséquence de la formule. Comme $i \leq 15$, le produit $8i$ vaut au plus 120, et comme $j \leq 7$, la somme $8i + j$ vaut au plus 127 — elle ne peut donc jamais dépasser 255, et aucun report vers l'octet haut n'est possible. Ajouter un adc inutile serait non seulement superflu mais dangereux : il consommerait la retenue précédente et propagerait une valeur parasite. Savoir qu'une retenue ne peut pas se produire vaut mieux que la propager par précaution.

L'ajout de 2048 utilise l'idiome AVR standard : subi/sbci avec la constante négée, l'assembleur calculant les octets bas et haut. Enfin, movw (copie de mot, 1 cycle) est plus efficace que deux mov pour charger le pointeur Z.

La formule générale à retenir. Pour une matrice de $L$ lignes et $C$ colonnes rangée ligne par ligne à partir de l'adresse de base $B$, l'élément $(i,j)$ est à $B + C \times i + j$. Le produit $C \times i$ est le seul calcul non trivial, et il se fait par décalages quand $C$ est une puissance de 2 — ce qui explique pourquoi les dimensions des matrices en traitement du signal sont presque toujours des puissances de 2.

1. Déroulement.

Le programme calcule donc la somme de 15 et 10, et range le résultat 25 dans r20. L'usage de r18 comme registre de retour est une convention implicite : rien dans le jeu d'instruction ne l'impose.

2. Pourquoi ce n'est pas correct. Le sous-programme détruit r16 sans le sauvegarder. L'appelant avait placé 15 dans r16 et le retrouve à 25 après l'appel : la valeur d'origine est perdue. Rien ne le signale — l'assembleur ne dit rien, et le programme « marche » tant que l'appelant n'a plus besoin de r16.

Trois défauts, du plus visible au plus insidieux :

• L'appelant ne peut pas savoir ce qui sera détruit. Le sous-programme modifie r16 et r18 ; s'il en modifiait vingt, la liste ne serait écrite nulle part. C'est un contrat implicite, et un contrat implicite n'est pas un contrat.
• Les paramètres passent par des registres fixes. addition lit r16 et r17 : ce n'est pas une fonction réutilisable, c'est un fragment de code qui suppose qu'on a bien voulu lui préparer ces registres. Impossible de l'appeler deux fois de suite avec des valeurs différentes sans recharger les registres — et c'est précisément ce que fait la boucle boucle3 de la temporisation.
• La conséquence est intermittente. Le bogue ne se manifeste que si l'appelant réutilise r16 après l'appel. C'est la signature des bogues d'assemblage : ils apparaissent quand on ajoute du code, pas quand on l'écrit.

3. Solution. Deux disciplines, qui se combinent.

Sauvegarder dans le sous-programme — c'est au sous-programme de rendre l'état qu'il a trouvé :

1addition: push r16            ; sauvegarder ce qu'on va abîmer2          add  r16, r173          mov  r18, r164          pop  r16            ; restaurer AVANT le ret5          ret

Ou documenter et respecter une convention d'appel, comme le fait avr-gcc : les paramètres passent dans r24, r22, etc., le résultat revient dans r24, et les registres r18 à r27 (dits call-saved) doivent être préservés par le sous-programme. Ce n'est plus de la sauvegarde systématique, c'est un partage des responsabilités : l'appelant sauvegarde les registres volatils qu'il utilise encore, l'appelé sauvegarde les autres. Cette convention est la version matérielle de ce que le langage C appelle une ABI.

L'ordre compte, et c'est un piège. La pile est LIFO : si l'on empile r16 puis r17, il faut dépiler r17 puis r16. Inverser l'ordre ne provoque aucune erreur de compilation — le programme restaure simplement les mauvaises valeurs dans les mauvais registres, et le bogue se manifeste plus tard, ailleurs. Pour sauvegarder plusieurs registres, l'ordre de restauration est toujours l'inverse de l'ordre de sauvegarde.

Le lien avec les processus. Ce que fait un appel de sous-programme à petite échelle — empiler une adresse de retour, sauvegarder quelques registres, restaurer à la sortie — le noyau le fait à grande échelle lors d'un changement de contexte : il empile tous les registres, le compteur programme et le registre d'état, puis restaure ceux d'un autre fil d'exécution. La pile est le mécanisme, et c'est pourquoi sa taille est une ressource critique.

1. Coût des instructions. Avec le jeu d'instruction du ATmega2560 : ldi = 1 cycle, subi = 1 cycle, brne = 2 cycles si le branchement est pris, 1 sinon.

2. Boucle interne. r17 part de 255 et décroît jusqu'à 0, soit 255 itérations. Chacune coûte subi + brne pris = 3 cycles, sauf la dernière où brne n'est pas pris :

$(254 \times 3) + 2 = 762 + 2 = \mathbf{764\ \text{cycles}} .$

Boucle externe. Chaque itération comprend ldi r17, 255 (1), la boucle interne (764) et subi r16, 1 (1), soit 766 cycles, plus le brne final (2 ou 1). r16 part de 255 et décroît jusqu'à 0, soit 255 itérations :

$255 \times 766 + (254 \times 2) + 1 = 195\,330 + 508 + 1 = 195\,839\ \text{cycles} .$

En ajoutant le ldi r16, 255 initial, le corps de tempo1 coûte 195 840 cycles.

Durée. Le Makefile distribué en TP fixe F_CPU = 16000000UL, soit 16 MHz pour la carte Arduino Mega : c'est cette valeur qui sert à convertir les cycles en temps. Une période d'horloge vaut donc $1/16 \times 10^6 = 62{,}5$ ns, et la temporisation dure

$t = \frac{195\,840}{16 \times 10^6} \approx 12{,}2\ \text{ms} .$

3. En faire un sous-programme. Il faut ajouter ret à la fin, et — pour respecter la discipline de l'exercice précédent — sauvegarder les registres utilisés si l'appelant peut en avoir besoin :

1tempo1:  push r162         push r173         ldi  r16, 2554boucle2: ldi  r17, 2555boucle1: subi r17, 16         brne boucle17         subi r16, 18         brne boucle29         pop  r1710         pop  r1611         ret

Coût : le corps (195 840) plus ret (5) plus les quatre instructions de sauvegarde/restauration (push et pop = 2 cycles chacun) :

$195\,840 + 5 + 4 \times 2 = 195\,853\ \text{cycles} \approx 12{,}24\ \text{ms} .$

4. La temporisation d'une seconde.

Que fait le programme ? tempo2 charge X dans r16, puis appelle tempo1 X fois : chaque itération appelle la temporisation de 12 ms, décrémente r16 et reboucle jusqu'à zéro. call tempo1 est donc exécuté exactement X fois.

Coût d'une itération de boucle3 : call (5 cycles) + tempo1 complet (195 853, ret inclus) + subi (1) + brne pris (2) = 195 861 cycles.

Valeur de X. On veut $t \approx 1$ s, soit $16 \times 10^6$ cycles :

$X = \frac{16\,000\,000}{195\,861} \approx 81{,}7 .$

La dernière itération n'a pas de brne pris, ce qui retire 1 cycle : le total vaut $X \times 195\,861 - 1$.

On retient $X = 82$, seule valeur entière donnant une durée au moins égale à la seconde visée. La précision obtenue est de $\pm 0{,}4\ \%$ — largement suffisante pour un clignotement de LED, insuffisante pour une horloge. Et c'est précisément la limite de cette méthode : la temporisation par boucle est bloquante (le processeur ne fait rien d'autre) et imprécise (elle dépend de la fréquence d'horloge, des interruptions et du compilateur). Pour une mesure du temps fiable, on utilise un timer matériel avec interruption, ce qui libère le processeur et se cale sur l'horloge du quartz.

Temporisations de 10 et 100 secondes. Il suffit d'empiler un niveau supplémentaire : une troisième boucle appelant tempo2 dix fois donne 10 s, cent fois donne 100 s. La structure est récursive, et chaque niveau multiplie la durée par son compteur. Attention toutefois à la profondeur de pile : chaque call empile 2 octets (ou 3 sur ATmega2560, dont le compteur programme fait 3 octets), et chaque sous-programme empile ses registres sauvegardés. Sur un microcontrôleur, la pile vit dans la SRAM — 8 Ko sur l'ATmega2560 — et un débordement de pile corrompt silencieusement les données.

Chenillard — graphe d'état. L'automate de Moore a quatre états formant un cycle : A → B → C → D → A, chacun portant le motif de LED indiqué. Chaque transition consomme une période d'horloge.

1     1001        0101        1010        01002   ( A )  --->  ( B )  --->  ( C )  --->  ( D )3     ^                                      |4     +--------------------------------------+

Programme. La structure est celle d'une machine de Moore sans entrée : un état interne, une table de sorties, et une transition inconditionnelle à chaque tour.

1        ; r20 = état courant (0..3)2        clr  r203boucle:4        ; --- table de sorties : motif selon l'état ---5        ldi  r30, lo8(motifs)6        ldi  r31, hi8(motifs)7        add  r30, r20            ; Z <- motifs + état8        clr  r1                  ; r1 = 0, indispensable pour l'adc9        adc  r31, r110        lpm  r16, Z              ; r16 <- motif[état]11        out  PORTB, r16          ; l'afficher sur le port12 13        ; --- transition : état suivant ---14        inc  r20

Trois points de méthode. Le modulo 4 se fait par un ET avec 0b11 : plus court et plus rapide qu'une comparaison, et c'est la raison pour laquelle les automates cycliques se codent sur un nombre d'états qui est une puissance de 2. La table de motifs est rangée en mémoire de programme et lue par lpm (load program memory) : c'est ainsi qu'on évite une cascade de comparaisons. Et clr r1 avant adc r31, r1 n'est pas décoratif : l'addition de l'indice à l'adresse de la table peut produire une retenue qu'il faut reporter sur l'octet haut, et adc ajoute la retenue plus son second opérande. Il faut donc un registre garanti à zéro — c'est le rôle de r1, qui est le registre à zéro de la convention AVR-GCC. L'oublier fait propager une valeur parasite dans l'octet haut de l'adresse, et le bogue ne se manifeste que lorsque la retenue se produit réellement.

Moteur pas-à-pas — graphe d'état. L'automate a huit états, un par ligne du tableau. Une propriété remarquable apparaît immédiatement : chaque transition ne change qu'un seul bit. Vérifions-le sur les trois premières :

• 0011 → 0111 : B2 passe de 0 à 1 ;
• 0111 → 0110 : B0 passe de 1 à 0 ;
• 0110 → 1110 : B3 passe de 0 à 1.

Et la propriété tient aussi pour le retour cyclique 1011 → 0011 (B3 passe de 1 à 0). La séquence est donc un cycle de Gray sur 4 bits, ce qui n'est pas un hasard : une seule bobine commute à la fois, donc un seul transistor de puissance change d'état à chaque pas. Cela limite les pics de courant d'alimentation et les perturbations électromagnétiques — exactement la raison pour laquelle le code de Gray est utilisé dans les capteurs de position. C'est le lien direct entre l'électronique numérique de première année et la commande de puissance.

Programme. Même structure que le chenillard, avec huit motifs :

1        clr  r202boucle:3        ldi  r30, lo8(phases)4        ldi  r31, hi8(phases)5        add  r30, r206        clr  r17        adc  r31, r18        lpm  r16, Z9        out  PORTB, r1610 11        ; --- temporisation : la vitesse du moteur dépend d'elle ---12        call tempo113 14        inc  r20

Le lien vitesse / temporisation. « A chaque commutation des bobines, le rotor tourne d'un angle constant. La vitesse du moteur est donc directement liée à la fréquence de commutation. » Avec huit états par tour électrique et une temporisation de 12,2 ms entre deux commutations, la période d'un tour complet vaut $8 \times 12{,}2 = 97{,}6$ ms, soit environ 10 tours par seconde. Diviser la temporisation par deux double la vitesse — et c'est exactement ainsi qu'on pilote un moteur pas-à-pas : par la fréquence, jamais par l'amplitude.

Le point commun des deux exercices. Les deux automates se programment avec la même structure : un compteur d'état, une table de motifs, une transition. C'est la traduction logicielle de la machine de Moore du cours : l'état interne détermine la sortie, et une fonction de transition détermine l'état suivant. Changer d'automate ne change que la table et la loi de transition.

1. Les deux problèmes. Un automate fini déterministe complet doit satisfaire deux conditions sur chaque état :

• complétude : la somme des conditions de toutes les transitions sortantes doit être égale à 1 — autrement dit, quel que soit le mot d'entrée, l'automate a toujours une transition à prendre ;
• déterminisme : le produit deux à deux des conditions sortantes doit être égal à 0 — autrement dit, jamais deux transitions ne sont simultanément valides.

Or l'automate de l'énoncé viole les deux.

Défaut de complétude. Les transitions étiquetées « ? » ne précisent aucune condition : on ne sait pas ce qui doit se passer. En pratique, cela signifie qu'aucune transition n'est définie pour certaines combinaisons d'entrées. Le programme résultant n'a alors aucun cas à exécuter : il ne fait rien, ou pire, il tombe dans une transition choisie par défaut. C'est exactement le problème de l'état inutilisé d'une machine séquentielle : une situation non prévue où le système se perd.

Défaut de déterminisme. Sur un même état, a.b et a.b.c peuvent être vraies simultanément — il suffit que $a = 1$, $b = 1$ et $c = 1$. Deux transitions sortantes sont alors valides, et l'automate doit en choisir une. Cette situation n'est pas « imprévisible » au sens matériel : dans un programme, l'ordre des tests décide. Mais c'est un choix implicite, qui dépend de l'ordre dans lequel le programmeur a écrit ses comparaisons. Modifier cet ordre change le comportement du système sans que rien ne le signale.

2. Comment les résoudre. Deux méthodes, à choisir explicitement et à documenter.

Rendre les conditions exclusives. On réécrit les transitions de façon que leurs conditions soient deux à deux incompatibles. Ici, la transition a.b.c est incluse dans a.b : il suffit de restreindre la première à ce qui la distingue, a.b.\bar{c}, et de laisser a.b.c couverte par la transition générale a.b. Les deux conditions deviennent alors exclusives.

Définir une priorité. On décide explicitement qu'une transition est prioritaire, on la teste en premier, et on documente le choix. C'est la solution adoptée dans les corrigés de l'UE pour ce type de conflit : « il faut rendre une des transitions prioritaire, sinon on ne pourra jamais implémenter le système ». La condition de priorité s'écrit alors dans le code par l'ordre des tests, et le commentaire qui l'accompagne devient une pièce du cahier des charges.

Compléter les « ? ». On remplace chaque « ? » par une condition explicite, et on ajoute une transition « autre » qui couvre tous les cas restants :

1        ; conditions de l'état courant, testées dans l'ordre de priorité2        sbic PIND, 0            ; test du bit a3        rjmp cas_a4        sbic PIND, 1            ; test du bit b5        rjmp cas_b6        rjmp cas_defaut         ; « autre » : aucune condition satisfaite

La transition « autre » est ce qui rend l'automate complet : elle garantit qu'il y a toujours une action à exécuter, même si les entrées prennent une valeur non prévue.

3. Ce que cela enseigne. Un automate mal spécifié n'est pas un automate difficile : c'est un automate non programmable. Le passage du graphe d'état au programme oblige à lever toutes les ambiguïtés, et l'exercice du TD est fait pour le montrer. La règle est la même pour une machine séquentielle matérielle : un état inutilisé doit toujours avoir une transition définie vers un état de reprise, sans quoi la machine peut s'y perdre définitivement. Et la leçon vaut au-delà de l'automatique : un comportement non spécifié n'est pas un comportement laissé libre, c'est un comportement laissé au hasard — dans le meilleur des cas l'ordre des tests, dans le pire la valeur résiduelle d'un registre non initialisé.

Ce que l'algorithme demande. Trois opérations : une comparaison d'égalité, une comparaison d'ordre, et une soustraction — plus deux branchements conditionnels. C'est un cas d'école, car il ne demande aucune multiplication ni division : toute la difficulté est dans les branchements et la conservation des deux valeurs.

Invariant et terminaison. Avant d'écrire le code, il faut le justifier : $A$ et $B$ restent des entiers strictement positifs (l'invariant de boucle), et $|A - B|$ décroît strictement à chaque itération. Une suite d'entiers positifs strictement décroissante est finie : la boucle termine. Ce raisonnement est exigible, et il est indépendant de l'architecture.

1. Machine à pile. Avec la convention de pile | gauche droite et op = « dépiler droite, dépiler gauche, calculer, empiler » :

1        push A2        push B3Bcl:    CMP              ; teste A − B, pile inchangée4        BEQZ Done        ; si Z = 1, A = B : terminé5        BLTZ Else        ; si A < B, aller à Else6        SWAP             ; | B A7        OVER             ; | B A B8        SUB              ; | B A−B9        BT   Bcl10Else:   OVER             ; | A B A11        SUB              ; | A B−A12        BT   Bcl13Done:   DROP             ; | A14        POP  PGCD

Les primitives de manipulation de pile (swap, over, drop, roll, dup) font tout le travail : elles réorganisent les opérandes sans jamais toucher à la mémoire. Le conseil du cours est explicite — « moins il y aura de références mémoires, mieux cela vaudra », et « trouver l'ordre des variables qui fait ressortir l'invariant de boucle » — car c'est cet ordre qui détermine combien de manipulations sont nécessaires.

2. Machine à accumulateur. Un seul registre de calcul : il faut donc conserver les deux variables en mémoire et recharger à chaque fois.

1        LOAD  A2        STORE sauvA      ; mem[sauvA] = A3        LOAD  B4        STORE sauvB      ; mem[sauvB] = B5Bcl:    SUB   sauvA      ; Accu = B − A6        BEQ   Done       ; si Z = 1, A = B7        BLT   Then       ; si le résultat est négatif, A > B : aller à Then8        STORE sauvB      ; sinon A < B : sauvB = B − A9        B     Bcl10Then:   NEG              ; Accu = A − B11        STORE sauvA      ; sauvA = A − B12        LOAD  sauvB      ; recharger B13        B     Bcl14Done:   LOAD  sauvA

Le coût est frappant : chaque itération touche la mémoire plusieurs fois, alors que la machine à pile ne touchait que la pile. L'astuce intéressante est l'usage du drapeau de signe : SUB sauvA calcule $B - A$, et si le résultat est négatif c'est que $A > B$ — la comparaison d'ordre est donc gratuite, obtenue comme sous-produit de la soustraction.

3. Machine à registres généraux. C'est le cas le plus confortable : les deux valeurs tiennent dans des registres, et l'ALU accepte deux registres quelconques.

1        LDI  r16, A2        LDI  r17, B3Bcl:    CP   r16, r174        BREQ Done          ; A = B : terminé5        BRLO sinon         ; A < B6        SUB  r16, r17      ; A ← A − B7        RJMP Bcl8sinon:  SUB  r17, r16      ; B ← B − A9        RJMP Bcl10Done:   ; pgcd dans r16

Aucune référence mémoire dans la boucle : tout se passe dans les registres, et CP fournit les drapeaux dont BREQ et BRLO se servent directement. C'est la version la plus courte et la plus rapide des trois.

Comparaison. Le même algorithme, trois programmes qui n'ont presque rien en commun :

La conclusion à retenir. L'implémentation d'un algorithme donné dépend fortement du type d'architecture qui effectue les manipulations de données. Ce n'est pas une remarque théorique : c'est la raison pour laquelle un compilateur doit connaître précisément la cible, et pourquoi le même code C peut produire des binaires de performances très différentes selon la machine visée. Les machines à pile ont longtemps prospéré dans les calculatrices, mais n'ont quasiment jamais été réellement accélérées ; ce sont les architectures à registres généraux qui ont emporté le marché.

Vérification. Sur $A = 48$ et $B = 18$ : $48 - 18 = 30$, $30 - 18 = 12$, $18 - 12 = 6$, $12 - 6 = 6$, donc $\text{pgcd} = 6$ — ce qui est bien $\gcd(48, 18)$. Le programme du TP 2 propose de compter les allumages de LED : faire clignoter la LED un nombre de fois égal au PGCD calculé permet de vérifier le résultat sans afficheur, ce qui est la seule solution disponible quand on n'a qu'une sortie binaire à disposition.

Structure de l'algorithme. Un parcours classique de recherche de maximum : initialiser le maximum au premier élément, puis comparer chaque élément suivant et retenir le plus grand.

1max <- T[0]2pour k de 1 à 9 :3    si T[k] > max alors max <- T[k]

Le point de départ délicat. Initialiser le maximum à 0 serait un bogue latent : sur un tableau de valeurs négatives — ou de valeurs non signées inférieures à celles qu'on aurait choisies — le résultat serait faux. La bonne pratique est d'initialiser avec le premier élément du tableau, qui existe toujours.

Programme. Les données sont en mémoire de programme (déclarées par .byte dans la section .text), donc lues par LPM avec le pointeur Z.

1        ldi  r30, lo8(Tableau)2        ldi  r31, hi8(Tableau)3        lpm  r18, Z+           ; r18 <- T[0], maximum initial ; Z pointe sur T[1]4        ldi  r20, 9            ; 9 éléments restants5 6boucle: lpm  r16, Z+           ; r16 <- T[k], Z avance7        cp   r16, r188        brlo pasmax            ; si T[k] < max, on garde l'ancien9        mov  r18, r16          ; nouveau maximum10pasmax: dec  r2011        brne boucle12 13        ; --- test final : max > 50 ? ---14        cpi  r18, 50

Trois points techniques.

lpm r16, Z+ lit en mémoire de programme avec post-incrémentation : le pointeur avance tout seul, aucune instruction supplémentaire. C'est l'équivalent exact, pour la mémoire de programme, de ld r16, X+ pour la mémoire de données — et cela montre que le choix du mode d'adressage est le même problème quel que soit l'espace mémoire.

*brlo est un branchement non signé : T[k] < max au sens des entiers naturels. Pour des valeurs signées, il faudrait brlt. Comme les données du TP sont des entiers 8 bits non signés (1 à 10), brlo est correct — mais le commenter évite une erreur silencieuse si le tableau change.

sbi et cbi mettent un bit à 1 ou à 0 dans un registre d'entrée/sortie. DDRB doit avoir été configuré en sortie au préalable, sinon PORTB ne pilote rien : c'est le premier programme du TP 1, et l'erreur classique du débutant est d'oublier la configuration de direction.

Vérification. Le tableau déclaré est $\{1, 2, \ldots, 10\}$, donc le maximum vaut 10. Comme $10 < 50$, la LED doit rester éteinte. Pour tester l'autre branche, il suffit de modifier la déclaration, par exemple .byte 1, 2, 3, 4, 5, 6, 7, 8, 9, 100 : le maximum vaut 100 et la LED doit s'allumer. C'est exactement la consigne du TP — « testez-le avec l'allumage de la LED puis avec l'extinction de la LED » — et c'est la bonne façon de tester un programme sans afficheur : choisir les données pour parcourir chaque branche, plutôt que d'espérer que le cas se présente.