Oct 06

Nand2Tetris: project 4 completed

Module 4 in Nand2Tetris is an interruption in the construction of the computer, in order to discover and understand the instruction set architecture (i.e. the computer’s binary language) that is chosen, before completing the hardware architecture that will realize it. Not surprisingly, the operations allowed on the registers match very closely the operations offered by the ALU previously constructed (in project 2).
As usual, the projects exercises are perfectly picked:

  • Implementation of the multiplication operator in assembly (the ALU is voluntarily simplistic, and does not include multiplication). Since I have never worked with a processor that did not have multiplication (not that I recall anyway), I had never done that. This is a milestone in my life. :-)
  • Implementation of an assembly program that blackens the (simulated) screen when one presses a key on the (simulated) keyboard, and clears it when releasing all keys. The screen and the keyboard are memory mapped, so that makes for a conveniently accessible low level interface.

When manipulating the registers, I couldn’t help starting to imagine how the whole thing would look like if it was a stack machine instead. After all, I did fall in love with RPN in 1989 when I started to use my HP-28S, and I recall the long hours spent programming it to calculate the pH of aqueous solutions or the greatest common divisor of two integers with nostalgia.

But there is a module 13 in Nand2Tetris, called “More Fun to Go”, including an empty project entitled “It’s your call!”, so who knows what will happen when I get there?

Oct 05

Nand2Tetris: project 3 completed

Oh my! Now I have 32 KB RAM and a program counter. That course is just going too fast…
A few comments:

  • The hardware simulator showed some hanging when I was testing my RAM64 and RAM512 (implemented in pure HDL down to 1-bit register, which implied many chips in my own computer’s RAM). The workaround was to stop running the script, single step a few times, and restart the script from there.
  • The claim that one gets to build all chips from the ground up from Nand gates in the course has one exception: the data flip-flop. That chip is given, and I am not sure whether one actually can build it and run it in the simulator, since it is the lowest level chip that interacts with the clock.
  • The program counter implementation was particularly interesting. I started simply, then got the feeling that using a 4-way Mux16 could be clever, implemented such a solution, which worked, didn’t like its complexity, and went back to the simpler solution. The simpler solution worked too, but was well… simpler and actually used fewer gates.

Gotta go back to read about this instruction set architecture we’re gonna choose…

Oct 05

Nand2Tetris: ALU implemented and verified (project 2)

My project 2 of Nand2Tetris is now completed, and I have a working ALU. In the process of implementing it, I also created 2 more chips. I had interpreted the book‘s instructions as an encouragement to build at least one separate chip as a building block that would be used at least twice in the ALU.
As mentioned in previous posts, the course is entirely free and open, and I am taking it as self studies at home. Ironically, although my academic education (that ended more than 20 years ago) is highly ranked (at least in France, where I took it), I did not have many courses at that level of quality, or many teachers who were as inspiring as Shimon Schocken.
This course is just amazing, and I urge anyone interested in computer science to take it.
Anyway, the ALU is now working. So I should be able to implement it in Minecraft red stone, right? :-) Well, I do have other things to do in my life.
After all, I have to add some sequential logic to that computer I am building.

Oct 04

Nand2Tetris: project 1 completed

After my previous article about Nand2Tetris, I jumped directly into module 1. As a matter of routine, I first read the chapter in the book, browse through the slides that can be found on the web site (the book chapters can actually also be found on the web site), and then follow the project instructions (also on the web site).

I am now very proud of having built and verified the following logic gates:

  1. Not gate
  2. And gate
  3. Or gate
  4. Xor gate
  5. Mux gate
  6. DMux gate
  7. 16-bit Not
  8. 16-bit And
  9. 16-bit Or
  10. 16-bit multiplexor
  11. Or(in0,in1,…,in7)
  12. 16-bit/4-way mux
  13. 16-bit/8-way mux
  14. 4-way demultiplexor
  15. 8-way demultiplexor

I won’t tell how, that would be against Nand2Tetris’ policy (students have to find the solutions for themselves).
I guess I am now ready to dig into Boolean arithmetic (module 2, as opposed to Boolean logic, which was the topic of module 1).

Oct 04

Building a Modern Computer from First Principles

The free and open source NAND to Tetris course has been teasing me for a few months.
I believe I first heard about it in the text attached to the following video.

The video shows an implementation of the ALU from the course in Minecraft, which is pretty amazing, but more importantly it made me aware of the course. The course site in its turn made me discover that designing one’s own general purpose computer from scratch was apparently not beyond reach. I will humbly admit that before discovering that course, although I have an academic degree in computer science, I would not have thought that one could design a general purpose 16-bit computer in the scope of a one-semester course homework.
After watching several videos by Shimon Schocken, a sympathetic human being who is one of the two professors behind the course (see Quick presentation, Google talk and TED talk), I was convinced.

Designing my own general purpose computer ranks very high on the list of my fantasies (had I already mentioned I was a nerd?), but I do not think I could achieve that without some serious support. That course might just be the support I need. One needs to be aware of that the hardware built in the course only exists in a simulator when the course is completed. It is built with the help of a Hardware Description Language (called HDL). Generating real hardware from the chips described in HDL in the course has however been done, and the way it was done is very much like modern real life hardware construction: by burning the design synthesized from HDL (or actually Verilog, a real life variant of HDL) to an FPGA.
Of course, the design in the course is not my design, but who knows how much inspiration I could get from taking the course?

Anyway, I decided to give it a go and have taken module 0 today. :-)
The hardware simulator works on my Linux computer (written in Java like all the tools for the course). Scrolling horizontally in the text editor windows does not work for me (the text is no longer displayed correctly when I move the sliders), but it was still usable, and editing the HDL code requires an external editor anyway.
Thanks a lot to the Nand to Tetris team!