Aller au contenu

Little man computer

Un article de Wikipédia, l'encyclopédie libre.
Simulation d'un Little Man Computer.

Le Little Man Computer (LMC) est un ordinateur à vocation éducative, créé par le Dr Stuart Madnick (en) en 1965[1]. Le LMC est généralement utilisé pour enseigner aux étudiants, car il modélise un ordinateur simple avec une architecture de von Neumann - qui possède toutes les fonctionnalités élémentaires d'un ordinateur moderne. Il peut être programmé en code machine (bien que sous forme décimale plutôt que binaire) ou en assembleur[2],[3],[4].

Architecture du système

[modifier | modifier le code]

Le modèle du LMC est basé sur le concept d'un petit homme enfermé dans une petite pièce ou un ordinateur. Au bout de la pièce, il y a 100 boîtes aux lettres (la mémoire), numérotées de 0 à 99, qui peuvent chacune contenir une instruction ou donnée de 3 chiffres (allant ainsi de 000 à 999). De plus, il y a deux boîtes aux lettres à l'autre bout marquées INBOX (boîte de réception) et OUTBOX (boîte d'envoi) qui sont utilisées pour recevoir et envoyer des données. Au centre de la pièce, il y a une zone de travail contenant une calculatrice simple à deux fonctions (addition et soustraction) appelée Accumulateur et un compteur qu'il est possible de remettre à zéro appelé Compteur de Programme. Le Compteur de Programme contient l'adresse de la prochaine instruction que le Petit Homme va effectuer. Le Compteur de Programme est normalement incrémenté de 1 après chaque instruction exécutée, permettant au Petit Homme d'exécuter le programme séquentiellement. Les instructions de section permettent aux itérations (boucles) et structures conditionnelles d'être incorporées dans un programme. La dernière en assignant au Compteur de Programme une adresse de mémoire non séquentielle si une condition particulière est satisfaite (habituellement si la valeur mémorisée dans l'accumulateur est positive ou nulle). Comme indiqué par l'architecture de von Neumann, la mémoire contient à la fois les instructions et les données. Il est par conséquent nécessaire de faire attention à bien empêcher le Compteur de Programme d'atteindre une adresse mémoire contenant des données autrement le Petit Homme tentera de la traiter comme une instruction. Afin d'utiliser le LMC l'utilisateur charge des données dans les boîtes aux lettres et fait signe au Petit Homme de commencer l'exécution, en commençant par l'instruction mémorisée à l'adresse mémoire zéro. Remettre à zéro le Compteur de Programme relance le programme.

Cycle d'exécution

[modifier | modifier le code]

Afin d'exécuter un programme, le Petit Homme effectue ces étapes :

  1. Vérifier le Compteur de Programme pour récupérer le numéro de la boîte aux lettres qui contient une instruction du programme (par exemple zéro)
  2. Aller récupérer l'instruction dans la boîte aux lettres avec ce numéro.
  3. Incrémenter le Compteur de Programme (de façon qu'il contienne le numéro de la boîte aux lettres contenant la prochaine instruction)
  4. Décoder l'instruction (cela inclut trouver le numéro de la boîte aux lettres pour les données sur lesquelles cette instruction va opérer, par exemple "récupérer les données depuis la boîte 42")
  5. Récupérer les données dans la boîte aux lettres avec le numéro trouvé dans l'étape précédente (par exemple, enregistrer les données dans l'accumulateur)
  6. Exécuter l'instruction
  7. Enregistrer les nouvelles données dans la boîte aux lettres dans laquelle les anciennes données ont été récupérées
  8. Répéter le cycle ou s'arrêter

Même si le LMC reflète le véritable fonctionnement des processeurs binaires, la simplicité des nombres décimaux a été choisie afin de minimiser la complexité pour les étudiants qui ne seraient pas habitués à travailler en binaire ou en hexadécimal.

Instructions

[modifier | modifier le code]

Certains simulateurs de LMC sont programmés en utilisant directement les instructions numériques à 3 chiffres et d'autres utilisent des codes mnémoniques à 3 lettres et étiquettes. Dans un cas comme dans l'autre, l'ensemble des instructions est délibérément très limité (avec habituellement environ dix instructions) afin de simplifier la compréhension. Si le LMC utilise des codes mnémoniques et des étiquettes alors ils sont convertis en instructions numériques à 3 chiffres quand le programme est assemblé. Le premier chiffre d'une instruction numérique représente la commande à effectuer et les deux derniers chiffres représentent l'adresse mémoire de la boîte aux lettres concernée par cette commande.

Le tableau ci-dessous montre un ensemble d'instructions habituel et les codes mnémoniques correspondants.

Code Numérique Code Mnémonique Instruction Description
1xx ADD ADD Ajoute la valeur mémorisée dans la boîte aux lettres xx à la valeur actuellement sur l'accumulateur (calculateur).
Note : le contenu de la boite aux lettres n'est pas modifié et les actions de l'accumulateur (calculateur) ne sont pas définies pour des instructions d'addition qui impliquent des sommes plus grandes que 3 chiffres.
2xx SUB SUBTRACT Soustrait la valeur mémorisée dans la boîte aux lettres xx à la valeur actuellement sur l'accumulateur (calculateur).
Note : le contenu de la boite aux lettres n'est pas modifié et les actions de l'accumulateur (calculateur) ne sont pas définies pour des instructions de soustraction qui donnent des résultats négatifs - cependant, un flag négatif peut être assigné de façon que 8xx (BRP) puisse être utilisé correctement.
3xx STA STORE Enregistre le contenu de l'accumulateur dans la boîte aux lettres xx (instruction destructive)
Note : le contenu de l'accumulateur (calculateur) n'est pas modifié (non destructif), mais le contenu de la boîte aux lettres est remplacé quelle que soit la valeur qui y était mémorisée (destructif).
5xx LDA LOAD Charge la valeur de la boîte aux lettres xx (chargement non destructif) et l'inscrit dans l'accumulateur (inscription destructive).
6xx BRA BRANCH (non conditionnelle) Fixe le compteur de programme à l'adresse donnée (valeur xx). Ainsi, la valeur xx sera l'adresse de la prochaine instruction exécutée.
7xx BRZ BRANCH IF ZERO (conditionnel) Si l'accumulateur (calculateur) contient la valeur 000, fixe le compteur de programme à la valeur xx, ne fait rien autrement.
Note : étant donné que le programme est stocké en mémoire, les données et les instructions du programme ont toutes le même format d'adresse/position.
8xx BRP BRANCH IF POSITIVE (conditionnel) Si l'accumulateur (calculateur) est positif ou nul, fixe le compteur de programme à l'adresse xx, ne fait rien autrement.
Note : étant donné que le programme est stocké en mémoire, les données et les instructions du programme ont toutes le même format d'adresse/position.
901 INP INPUT Va à la Boîte de Réception (INBOX), récupère la valeur de l'utilisateur et la stocke dans l'accumulateur (calculateur).
Note : cela écrasera toute valeur qui était dans l'accumulateur (écriture destructive).
902 OUT OUTPUT Copie la valeur de l'accumulateur dans la Boîte d'Envoi (OUTBOX).
Note : le contenu de l'accumulateur n'est pas modifié (copie non destructive).
000 HLT/COB HALT/COFFEE BREAK Arrête le fonctionnement.
DAT DATA C'est une instruction d'assembleur qui charge simplement la valeur donnée dans la prochaine boîte aux lettres disponible. DAT peut également être utilisé en conjonction avec des étiquettes pour déclarer des variables. Par exemple, DAT 465 stockera la valeur 465 dans la boîte aux lettres à l'adresse de l'instruction DAT.

En utilisant des codes d'instruction numériques

[modifier | modifier le code]

Ce programme (instruction 901 jusqu'à 000) est écrit uniquement en utilisant les codes numériques. Le programme prend deux nombres en entrée et retourne la différence. Remarquons que l'exécution commence à la Boîte aux Lettres 00 et finit à la Boîte aux Lettres 07. Les inconvénients de programmer le LMC en utilisant des codes d'instructions numériques sont expliquées ci-dessous.

Boîte aux Lettres Code Numérique Opération Commentaires
00 901 INBOX → ACCUMULATEUR Entrer (INPUT) le premier nombre, le placer dans le calculateur (en effaçant ce qui s'y trouvait).
01 308 ACCUMULATEUR → MÉMOIRE[08] Stocker (STORE) la valeur actuelle du calculateur (afin de se préparer pour la prochaine étape).
02 901 INBOX → ACCUMULATEUR Entrer (INPUT) le second nombre, le placer dans le calculateur (en effaçant ce qui s'y trouvait).
03 309 ACCUMULATEUR → MÉMOIRE[09] Stocker (STORE) la valeur courante du calculateur (afin de se préparer, encore une fois, pour la prochaine étape).
04 508 MÉMOIRE[08] → ACCUMULATEUR (Maintenant que les valeurs entrées sont stockées dans les boîtes aux lettres 08 et 09)

Recharger (LOAD) la première valeur dans le calculateur (en effaçant ce qui s'y trouvait).

05 209 ACCUMULATEUR = ACCUMULATEUR - MÉMOIRE[09] Soustraire (SUBSTRACT) le second nombre à la valeur actuelle du calculateur (qui vient juste d'être fixée à celle du premier nombre entré).
06 902 ACCUMULATEUR → OUTBOX Envoyer (OUTPUT) le résultat du calculateur dans la Boîte d'Envoi (OUTBOX).
07 000 (aucune opération effectuée) Arrêter (HALT) le LMC.

En utilisant les codes d'instruction mnémoniques et les étiquettes

[modifier | modifier le code]

Le langage d'Assemblage est un langage de programmation de bas niveau qui utilise des mnémoniques et des labels au lieu de codes d'instruction numériques. Même si le LMC n'utilise qu'un ensemble limité de ces mnémoniques, le confort d'utiliser une mnémonique pour chaque instruction est rendu apparent par le langage d'assemblage du même programme montré ci-dessous - le programmer n'a plus besoin de mémoriser un ensemble de codes numériques anonymes et peut maintenant programmer avec un ensemble de codes mnémoniques plus facile à se souvenir. Si la mnémonique est une instruction qui concerne une adresse mémoire (soit une instruction de section ou un chargement/enregistrement de données) alors l'étiquette est utilisée afin de nommer l'adresse mémoire.

Ce programme d'exemple peut être compilé et tourne sur le simulateur LMC[5] disponible sur le site web de l'Université York (Toronto, Canada) ou sur l'application bureau écrite par Mike Coley. Tous ces simulateurs incluent toutes les instructions et des programmes d'exemples, un assembleur pour convertir le code d'assemblage en code machine, des interfaces de contrôle afin d'exécuter et contrôler les programmes et un pas-à-pas détaille de chaque instruction LMC.
INP
STA TERME1
INP
STA TERME2
LDA TERME1
SUB TERME2
OUT
HLT
TERME1 DAT
TERME2 DAT

Étiquettes

[modifier | modifier le code]

Sans les étiquettes le programmeur devrait manuellement calculer les adresses des Boîtes aux Lettres (mémoire). Dans le code numérique d'exemple, si de nouvelles instructions devaient être insérées avant l'instruction HLT finale alors cette instruction HLT serait déplacée depuis l'adresse 07 vers l'adresse 08 (l’étiquetage des adresses commence à la position 00). Supposons que l'utilisateur a entré 600 à la première entrée. L'instruction 308 signifierait que cette valeur serait stockée à l'adresse 08 et effacerait l'instruction 000 (HLT). Étant donné que 600 signifie "bifurque vers l'adresse de boîte aux lettres 00" le programme, au lieu de s'arrêter, se bloquerait dans une boucle infinie.

Afin de contourner cette difficulté, la plupart des langages d'assemblages (en incluant celui du LMC) combinent les mnémoniques avec les étiquettes. Une étiquette est simplement un mot qui est utilisé pour nommer une adresse mémoire où une instruction ou des données sont stockées, ou pour se référer à cette adresse dans une instruction.

Quand un programme est assemblé:

  • Une étiquette à gauche d'une instruction mnémonique est convertie vers l'adresse mémoire de l'instruction ou donnée qui y est stockée (par exemple debutboucle INP)
  • Une étiquette à droite d'une instruction mnémonique remplace la valeur de l'adresse mémoire référée ci-dessus (par exemple BRA debutboucle)
  • Une étiquette combinée à une expression DAT fonctionne comme une variable, cela étiquette l'adresse mémoire à laquelle la mémoire est stockée (par exemple un DAT 1 ou nombre1 DAT)

Dans l'exemple en langage d'assemblage qui utilise des mnémoniques et des étiquettes, si une nouvelle instruction est insérées avant l'instruction HLT finale alors la position de l'adresse est étiquetée TERME1 serait maintenant à l'emplacement mémoire 09 au lieu de 08 et l'instruction STA TERME1 serait convertie en 309 (STA 09) plutôt que 308 (STA 08) quand le programme est assemblé.

Les étiquettes sont ainsi utilisées pour:

  • Identifier une instruction particulière comme cible pour une instruction de bifurcation (BRANCH).
  • Identifier un emplacement mémoire particulier comme une variable nommée (en utilisant DAT) et charge éventuellement des données dans le programme au moment de l'assemblage afin qu'elles soient utilisées par le programme (il n'est par exemple pas possible de rajouter 1 un compteur à moins de le définir ainsi un DAT 1 ou le demander à l'utilisateur, ce qui n'est pas très pratique).

Exemple

Ce programme prend une entrée utilisateur et décompte jusqu'à zéro.

        INP
BOUCLE  SUB UN   // Étiqueter cette adresse mémoire BOUCLE, l'instruction soustraira la valeur stockée à l'adresse UN à l'accumulateur.
        OUT
        BRZ QUIT // Si la valeur de l'accumulateur est 0, sauter à l'adresse mémoire étiquetée QUITTER
        BRA LOOP // Si la valeur de l'accumulateur n'est pas 0, sauter à l'adresse mémoire étiquetée BOUCLE
QUITTER HLT      // Étiqueter cette adresse mémoire QUITTER
UN      DAT 1    // Stocker la valeur 1 à cette adresse mémoire et l’étiqueter UN (déclaration de variable).

Ce programme prend une entrée utilisateur, l'élève au carré, retourne la réponse et recommence. Entrer la valeur zéro termine le programme. (Note: une entrée qui résulte en une sortie plus grande 999 causera une erreur due à la limite des nombres de 3 chiffres du LMC).

DEBUT     LDA ZERO     // Initialisation pour permettre d'exécuter le programme plusieurs fois
          STA RESULTAT
          STA COMPTEUR
          INP          // Entrée fournie par l'utilisateur
          BRZ END      // Saute au programme END si l'entrée est égale à zéro
          STA VALEUR   // Stocke l'entrée dans VALEUR
LOOP      LDA RESULTAT // Load the RESULTAT
          ADD VALEUR   // Ajoute VALEUR, l'entrée fournie par l'utilisateur à RESULTAT
          STA RESULTAT // Stocke le nouveau RESULTAT
          LDA COMPTEUR // Charge le COMPTEUR
          ADD UN       // Ajoute UN au COMPTEUR
          STA COMPTEUR // Stocker le nouveau COMPTEUR
          SUB VALEUR   // Soustraire la nouvelle VALEUR entrée par l'utilisateur au COMPTEUR
          BRZ ENDLOOP  // Si zéro (VALEUR a été ajouté au RESULTAT VALEUR fois), aller à FINBOUCLE
          BRA LOOP     // Aller à BOUCLE pour continuer à ajouter VALEUR à RESULTAT
FINBOUCLE LDA RESULTAT // Charger RESULTAT
          OUT          // Sortir RESULTAT
          BRA START    // Aller à START afin de réinitialiser et de récupérer une autre entrée VALEUR
END       HLT          // Arrêt (HALT) - un zéro a été entré, le programme est donc terminé.
RESULTAT  DAT          // Résultat calculé (0 par défaut)
COMPTEUR  DAT          // COMPTEUR (0 par défaut)
UN        DAT 1        // Constante, valeur de 1
VALEUR    DAT          // Entrée fournie par l'utilisateur, la valeur à être mise au carré (0 par défaut)
ZERO      DAT          // Constante, valeur de 0 (0 par défaut)

Note: Si aucune valeur n'est donnée après une déclaration DAT alors la valeur par défaut 0 est stockée à l'emplacement mémoire.


Références

[modifier | modifier le code]
  1. « Little Man Computer »(Archive.orgWikiwixArchive.isGoogleQue faire ?), Illinois State University, (consulté le )
  2. DOI noedit
  3. DOI noedit
  4. DOI noedit
  5. Stephen Y. Chen et William C Cudmore, « The Little Man Computer », York University (consulté le )

Liens Externes - Simulateurs

[modifier | modifier le code]