NandGame – Comment construire un ordinateur à partir de zéro

 (nandgame.com)
5 points par GN⁺ 2024-11-02 | 1 commentaires | Partager sur WhatsApp
  • NandGame est un jeu de réflexion éducatif dans lequel on part de simples composants logiques pour assembler, au final, un ordinateur programmable
  • Chaque niveau consiste à créer un composant qui fonctionne selon les spécifications, et la pièce terminée devient le bloc de construction de l’étape suivante
  • Aucune connaissance préalable en architecture informatique ou en logiciel n’est nécessaire, et en mathématiques le niveau addition et soustraction suffit, même si certains défis peuvent prendre du temps
  • Le premier défi consiste à implémenter un composant nand avec des fils et des relais, de sorte que la sortie soit 0 uniquement lorsque les entrées a et b valent toutes deux 1
  • Les composants de la boîte à outils se placent par glisser-déposer dans la zone bleue, et le glisser-déposer ainsi que l’annulation se contrôlent avec la barre d’espace, les flèches directionnelles et Escape

Des composants de base à l’ordinateur

  • NandGame progresse en combinant des composants de base pour créer des pièces de plus en plus puissantes, jusqu’à construire à la fin un ordinateur programmable
  • Il est divisé en plusieurs niveaux, et à chaque étape il faut créer un composant qui fonctionne conformément aux spécifications données
    • Le composant terminé devient ensuite une pièce utilisable dans les niveaux suivants
    • Le point de départ est le composant logique le plus simple

Connaissances préalables nécessaires et difficulté

  • Aucune connaissance préalable en architecture informatique ou en logiciel n’est requise
  • Les mathématiques ne vont pas au-delà de l’addition et de la soustraction
  • Certains défis peuvent demander du temps à résoudre, et exigent donc de la patience

Premier défi : créer un nand

  • Le premier défi consiste à implémenter un composant nand à l’aide de fils et de relais
  • Il faut relier les entrées a et b à la sortie tout en construisant un circuit dont le comportement respecte les spécifications
  • 1 signifie qu’un courant circule, et 0 qu’aucun courant ne circule
  • L’entrée V fournit un courant constant valant toujours 1

Spécification du nand

  • La sortie de nand vaut 0 uniquement lorsque les deux entrées valent 1
  • Les spécifications exactes d’entrée/sortie sont les suivantes
a b sortie
0 0 1
0 1 1
1 0 1
1 1 0

Commandes

  • Les composants de la boîte à outils se placent par glisser-déposer dans la zone bleue
  • Appuyez sur la barre d’espace pour saisir un élément déplaçable
  • Pendant le glisser-déposer, déplacez l’élément avec les flèches directionnelles
  • Appuyez de nouveau sur la barre d’espace pour le poser à son nouvel emplacement, ou sur Escape pour annuler

À lire aussi

1 commentaires

 
GN⁺ 2024-11-02
Commentaires sur Hacker News

  • J’ai tellement aimé ce jeu que j’ai acheté une petite carte de développement FPGA pour essayer de créer moi-même un jeu d’instructions et un CPU logiciel.
    Ce n’était pas vraiment pratique, mais c’était un exercice amusant, et j’ai choisi une carte iCE40 parce que l’écosystème open source est correct et que le prix est bas : https://www.digikey.com/en/products/detail/lattice-semicondu...
    Il existe peut-être de meilleures options aujourd’hui.

    • Niklaus Wirth a fait quelque chose de similaire : son prétexte était qu’il ne trouvait pas de boîtier commercial capable de communiquer avec sa souris souvenir Xerox PARC préférée.
      La plupart des gens auraient bricolé un adaptateur USB, mais Wirth a voulu faire les choses proprement : il a pris une carte FPGA, créé un CPU logiciel, puis installé dessus un OS, un système de fenêtres, une chaîne d’outils de langage, etc.
      Cela lui a permis de faire tourner une application de conception matérielle et un éditeur de texte, et d’expérimenter davantage de conceptions de CPU logiciels avec sa souris favorite.
    • L’étape suivante serait sans doute Tiny Tapeout : https://www.tinytapeout.com/

  • J’ai essayé un jeu similaire, Turing Complete, et c’était vraiment amusant : https://store.steampowered.com/app/1444480/Turing_Complete/
    C’est très proche du livre Nand2Tetris.

    • Ce n’est qu’après avoir passé 30 heures sur Turing Complete que j’ai réalisé ce qui s’était passé.
      J’avais fait évoluer la machine vers des instructions 32 bits, et même rédigé la documentation du langage assembleur correspondant.
      C’est un excellent jeu, même s’il est encore en accès anticipé.
    • Turing Complete est clairement recommandable.
      Il est beau, bien fini, et assez addictif.
      C’est bien aussi qu’il soit sur GOG : https://www.gog.com/game/turing_complete

  • Articles liés :
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=36862274 - juillet 2023
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=31055307 - avril 2022
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=25282507 - décembre 2020
    Show HN: Online challenge: Build a CPU from scratch - https://news.ycombinator.com/item?id=17508151 - juillet 2018

    • Je ne sais pas comment j’ai pu manquer les anciens articles, mais j’ai lu le livre et j’ai aussi implémenté un ordinateur moi-même.
      C’est un exercice vraiment amusant.

  • Voir ça me rappelle amèrement tout ce que j’ai oublié.
    J’ai fait de l’électrotechnique à l’université il y a plus de 20 ans, avec une spécialisation en architecture des ordinateurs, mais je ne m’en suis jamais servi professionnellement et je suis parti vers le logiciel.
    Je ne me souvenais absolument plus comment faire les choses présentées ici, et après pas mal d’essais-erreurs, j’ai à peine réussi à construire un demi-additionneur.

    • Je comprends cette réaction, mais je pense que les études que tu as faites auparavant t’ont aidé à prendre, à plusieurs reprises, des décisions dans la bonne direction.
      C’est un peu comme se reprocher de ne plus se souvenir de qui a fait adopter les Corn Laws, ou de qui a lancé le transport frigorifique aux États-Unis.
      Si tu as en tête le récit de fond — par exemple que la guerre exige de l’ingénierie, que la révolution agricole mène à la révolution industrielle, et que l’histoire est une lutte des classes — les nouvelles informations se mettent en place comme des fragments dans un champ magnétique.
      Donc ne sois pas trop dur avec toi-même ; tu peux te montrer un peu plus indulgent.

  • Ce n’est qu’après avoir fait à la fois ce jeu et le cours Nand2Tetris que j’ai compris qu’ils implémentaient le même ordinateur.
    Ce jeu en est une version graphique interactive, tandis que le Nand2Tetris original consiste à écrire du HDL textuel au lieu de cliquer-déposer des connexions entre portes logiques.
    Les deux étaient amusants et pédagogiques, mais NandGame était plus fun.
    Cela dit, il est utile de connaître le lien entre les deux. Après avoir terminé NandGame, on peut enchaîner avec les exercices suivants de Nand2Tetris, c’est-à-dire travailler sur les couches logicielles supérieures de l’ordinateur, et cela facilite aussi le partage d’expérience et de contenu avec les personnes qui ont fait l’autre version.

    • J’ai essayé nand2tetris, et même si j’étais plutôt bon dans les cours de matériel à l’université, ce cours et ce livre ressemblaient beaucoup à « dessiner le reste du hibou ».
      Pour faire les exercices, j’ai dû ressortir des manuels universitaires et des sujets d’examen, puis j’ai abandonné à peu près au moment où il fallait presque terminer la partie centrale du CPU.
      Franchement, j’ai trouvé les cours et le texte très insuffisants ; je ne sais pas si c’est devenu normal à l’ère d’Internet, mais je m’attendais à ce que le cours et le manuel soient raisonnablement autoportants.
    • Il existe au moins un autre simulateur en glisser-déposer compatible avec Nand2Tetris.
      C’est LogicSimX/Logic Simulator 2, basé sur desktop, d’Andrew Wilkes : https://logicsimx.com/about/ https://andrew-wilkes.itch.io/logic-simulator-2
      Ça a l’air correct, mais je ne le connais pas assez pour l’évaluer sérieusement.

  • À titre de réflexion, si l’on met de côté, dans la première étape, la partie où l’on fabrique réellement des portes NAND, une fois ce processus terminé on obtient finalement une forme très proche d’un réseau de neurones
    Il faut 2 neurones pour représenter une porte NAND, et cela ressemble à une structure avec n couches de profondeur, beaucoup de zéros dans la matrice de poids, et un peu d’espace de stockage
    La question est la suivante : étant seulement donnée la sémantique des entrées/sorties au niveau assembleur, pourrait-on entraîner un réseau de neurones vide pour qu’il prenne une structure de ce genre ? La rétropropagation ne fonctionnerait évidemment pas, mais une certaine forme de recherche directionnelle ne serait-elle pas possible ?

    • L’an dernier, j’ai essayé de faire ça avec un ami
      Nous avons essayé des portes à majorité 3 et plusieurs autres portes, mais dès qu’on dépassait une couche, la rétropropagation ne marchait pas bien, probablement faute d’une précision suffisante sur les bits
      Le problème de l’« entraînement sans rétropropagation » est en fait assez difficile, et nous avons fini par abandonner
      Existe-t-il une bonne méthode pour entraîner un réseau de neurones sans rétropropagation ? Il semble y avoir un certain goulot d’étranglement informationnel, mais il est difficile d’évaluer l’information mutuelle sans réseau de neurones
    • Il y a plusieurs décennies, certaines des premières expériences sur les réseaux de neurones visaient à montrer qu’ils pouvaient modéliser avec succès des portes logiques

  • Je n’ai aucune expérience dans ce domaine, donc j’aimerais qu’on m’explique ce que fait chaque composant
    Je ne sais pas ce que fait un relais, ni ce que sont c et in
    Je ne comprends pas non plus pourquoi, alors qu’il y a une alimentation séparée, le simple fait de connecter a ou b à l’alimentation et de l’activer suffit à alimenter le circuit

    • Un relais est un interrupteur commandé électriquement
      Quand la bobine (c) est alimentée, l’état de l’interrupteur passe de son état par défaut à l’état opposé
      Un interrupteur normalement fermé transmet la valeur de in vers la sortie quand c = 0, mais si c = 1, la bobine est alimentée et l’interrupteur s’ouvre, ou se coupe
      Un interrupteur normalement ouvert fonctionne à l’inverse
      c est la bobine, et lorsqu’elle est alimentée, elle fait basculer l’interrupteur
      in est la valeur qui passe lorsque l’interrupteur est fermé, ici 1 ou 0
      L’alimentation séparée est nécessaire pour obtenir une valeur 1 indépendamment des deux entrées
      Par exemple, si l’on veut toujours sortir 1 lorsque les deux entrées valent 0, il faut une valeur haute à tirer vers le haut ; c’est le rôle de l’alimentation
    • C est probablement le C de coil ou de control
      Un relais est un interrupteur mécanique commandé par un électroaimant constitué d’une bobine enroulée autour d’un noyau de fer
      Quand un courant traverse la bobine, elle attire un ressort métallique, ce qui peut permettre au courant de circuler de in vers la sortie, ou au contraire l’interrompre
      Les deux types de composants relais proposés représentent précisément ces deux comportements

  • Vraiment excellent. Je recommande à tout le monde de jeter aussi un œil à MHRD, voire d’y jouer
    https://store.steampowered.com/app/576030/MHRD/

  • Ça a l’air génial. Je regrette de ne pas être allé jusqu’au bout du livre, et j’ai envie d’essayer davantage avec ça