Leçons Interactives de Mathématiques et Sciences

← Informatique

Un processeur miniature : le Little Man Computer

Le programme occupe les mêmes cent cases mémoire que les nombres qu’il manipule. Faites-le avancer pas à pas : chaque transfert du cycle de recherche–décodage–exécution s’éclaire. Une case lue apparaît en bleu, une case où l’on écrit en ambre ; la prochaine instruction est encadrée de violet.

Chargement de la simulation interactive...

Leçon

La théorie — Un processeur miniature : le Little Man Computer

Le cycle de recherche–décodage–exécution décrit le traitement de chaque instruction par un processeur. La recherche copie PC dans MAR, lit la case désignée dans MDR, copie le contenu de MDR dans CIR et ajoute 1 à PC. Le décodage sépare l’instruction en une opération, donnée par le chiffre des centaines, et une adresse, donnée par les deux derniers chiffres. Seuls 901, 902 et 000 font exception : ce sont les codes complets de INP, OUT et HLT, qui ne désignent aucune case. L’exécution réalise l’opération demandée, avec éventuellement une lecture ou une écriture dans une case supplémentaire, par l’intermédiaire de MAR et MDR.

Ce que signifie chaque symbole

PC
compteur ordinal : l’adresse de la prochaine instruction à lire
MAR
registre d’adresses mémoire : l’adresse de la case où va avoir lieu une lecture ou une écriture
MDR
registre de données mémoire : la valeur qui vient d’être lue ou qui va être écrite
CIR
registre d’instruction courant : l’instruction en cours d’exécution
ACC
accumulateur : le registre où ADD, SUB et LDA placent leur résultat
Suppose
Le Little Man Computer de Stuart Madnick (MIT, 1965) ne précise pas ce qui se passe lorsque SUB donne un résultat négatif ou qu’ADD dépasse 999. Dans ce simulateur, l’accumulateur peut contenir une valeur de −999 à 999 : BRP teste donc son signe. Un résultat hors de cet intervalle provoque un dépassement de capacité et arrête l’exécution, sans retour à l’autre extrémité de l’intervalle. Les simulateurs pédagogiques diffèrent sur ce point. Un programme dont l’accumulateur reste entre 0 et 999 se comporte de la même façon dans tous.

La machine ne distingue pas un nombre d’une instruction 🖖

Cliquez sur Données comme code. Le programme contient LDA n et OUT pour afficher 105 une seule fois, mais son auteur a oublié HLT. PC passe donc à la case 02, où se trouve 105. La machine y lit une instruction comme dans toute autre case : 105 correspond à ADD 05, et la case 05 contient 20. La ligne DAT suivante contient 902, le code de OUT : la machine affiche donc 125. Celle d’après contient 0, le code de HLT. Rien dans une case mémoire n’indique si son contenu est une instruction ou un nombre. PC y arrive ? Ce contenu est exécuté comme une instruction. LDA, ADD ou SUB désigne cette case ? Il est lu comme une donnée. La première instruction a lu ce 105 comme un nombre ; la troisième l’a exécuté. C’est le principe du programme enregistré, mis en œuvre pour la première fois sur le Manchester Baby en juin 1948.

Pour lire l’élément suivant d’une liste, ce programme se réécrit 🖖

Cliquez sur Somme d’une liste et observez la case 00. Elle contient d’abord 517, soit LDA 17, qui charge le premier nombre de la liste. Une instruction LMC contient directement son adresse ; aucun registre ne permet à l’instruction de prendre cette adresse ailleurs. Impossible, donc, de demander « la case qui suit celle que je viens de lire ». Écrire LDA 17, ADD 18, ADD 19, etc., convient à cette liste, mais pas à une liste plus longue. Pour calculer la somme avec une seule boucle, quel que soit le nombre d’éléments, le programme charge sa propre première instruction comme un nombre, lui ajoute 1 et la remet à sa place. 517 devient 518, soit LDA 18. Les cinq passages réécrivent cinq fois la case 00. La dernière version, LDA 22, n’est jamais exécutée : le compteur atteint zéro avant. Les processeurs réels peuvent lire une adresse dans un registre, ce qui permet de parcourir une liste sans modifier le programme.

L’essentiel des lectures sert à lire le programme lui-même 🖖

Avant toute action, chaque instruction exige une lecture mémoire : c’est la recherche de l’instruction. LDA, ADD et SUB lisent une case supplémentaire ; STA écrit dans une case. Les branchements, INP et OUT n’effectuent aucun accès mémoire supplémentaire. Dans Multiplier par addition, le calcul 6 × 7 demande ainsi 65 recherches d’instructions, 30 lectures d’opérandes et 16 écritures. La lecture des instructions représente 58,6 % des échanges entre le processeur et la mémoire. Pour toutes les paires d’entrées dont le produit ne dépasse pas 999, cette part reste comprise entre 57,2 % et 69,2 %. Programme et données empruntent le même chemin vers la même mémoire, à tour de rôle. John Backus a donné à ce passage le nom de goulot d’étranglement de von Neumann dans sa conférence de réception du prix Turing en 1977.

Problème entièrement résolu

  1. Pourquoi 2 × 99 demande 801 instructions et 99 × 2 seulement 25 4 étapes

    Cliquez sur 2 × 99, méthode lente, puis remplacez les valeurs d’entrée par 99 et 2. Dans les deux cas, le programme affiche 198. Comptez les instructions exécutées à chaque fois, trouvez la formule et déterminez combien d’instructions exige l’ordre des facteurs le moins favorable pour un produit qui tient dans une boîte aux lettres.

    Ouvrez ce problème dans l'outil

    1. Avant la boucle, le programme exécute 2 INP et 2 STA, soit 4 instructions. Le corps de la boucle contient LDA b, BRZ, SUB one, STA b, LDA total, ADD a, STA total, BRA loop : 8 instructions, exécutées autant de fois que la valeur de b.

    2. Lorsque b atteint zéro, la boucle n’exécute plus que LDA b et BRZ. LDA total, OUT et HLT terminent ensuite le programme : 5 instructions supplémentaires. Le total est donc 4 + 8b + 5 = 8b + 9. La valeur de a n’intervient pas.

    3. Pour b = 99, on obtient 8 × 99 + 9 = 801 ; pour b = 2, on obtient 25. Le tableau des résultats affiche 801 dans le premier ordre et 25 dans le second.

    4. Le plus grand produit qui tient dans une case est 999. Avec 1 puis 999 en entrée, la boucle effectue 999 passages : 8 001 instructions. Avec 999 puis 1, elle ne passe qu’une fois : 17.

    Réponse

    8b + 9 instructions, où b est la seconde entrée. Pour obtenir le même produit, 999, il faut 8 001 instructions dans un ordre et 17 dans l’autre, soit environ 470 fois plus. Si le programme comparait d’abord ses entrées pour faire porter la boucle sur la plus petite, le coût ne dépasserait jamais 8 × 31 + 9 instructions, auxquelles s’ajouterait la comparaison : le plus petit facteur d’un produit inférieur ou égal à 999 ne dépasse pas 31.

Parcours

Comment un ordinateur exécute un programme

Références (4)

· Vérifié sur des sources publiées. Corrections bienvenues.