Project 4: Machine Language, Building a Computer Part I, and Annotation

Due on Thursday February 3rd, 2022 at 11:59pm PST

Part 0: Get the Starter Materials

To complete this assignment, you will need to use git to access the starter materials that have been pushed to your repository by the course staff. First, run git status and see if it reports any changes. If you have any, you'll need to commit them before proceeding (git add . followed by git commit -m "Your message here"). Then, run:

• git pull (download any commits on the Gitlab server to your local repository)

After running that command, you have synchronized the local copy of your repo with the copy on the server. Very rarely, you may get a "merge conflict" where git can't automatically figure out how to combine the changes we pushed to the server. If that happens, feel free to email the staff list to resolve the issue.

Part I: Annotation

This week’s project requires you to read and annotate this spec for Project 4. We recommend to get the annotations done at least two days before the project is due. As you are reading the spec, complete the following:

1. Annotate the spec. Either print out or digitally mark-up the Project 4 spec as you read. Identify at least 5 key annotation strategies that you used while annotating the spec, and evaluate how useful each strategy was in helping you understand/approach the assignment. Some examples of strategies you could use:

   • Digitally annotating the spec
   • Handwriting your annotations
   • Color coding
   • Creating a checklist for yourself of tasks to do
   • Estimating time or dividing the spec into more manageable milestones
   • Using arrows or bullet points
   • Drawing diagrams
   • Placing important info in boxes/bubbles
   • Summarizing ideas in your own words
   • Jotting down notes about implementation ideas
   • Writing down questions you have

   In your upcoming 1:1 TA meeting, please be prepared to share your annotations. You will be asked to explain your annotation choices as well as discuss which strategies helped you approach the Project 4 spec most effectively.

2. Fill out the Assignment Timeline. After you have finished annotating the spec, make a detailed plan of when you will work on each part of the project. It's up to you to decide how you will divide up the assignment and much you want to do in a single day. Be ready to reflect on this timeline with your TA at your next 1:1 meeting! Edit the file projects/4/assignment_timeline "in place" and submit by pushing to Gitlab.
3. Complete the Annotation Reflection. Reflect and evaluate the annotation strategies that you used in engaging with the Project 4 spec. Be sure to reflect on each of the strategies that you used and address the reflection questions. Edit the file projects/4/annotation_reflection "in-place" and submit by pushing to Gitlab.
4. Submit a photo of your annotated spec. If you handwrite your annotations, insert a picture of your notes within the reflection document. If you made annotations digitally, either insert a link within the document that allows us to access your annotations or include them as a separate file in your repo and clearly indicate within the reflection document where we can find them.
5. In your upcoming 1:1 TA meeting, please be prepared to explain your annotation choices as well as discuss which strategies helped you approach Project 4 effectively.

Part II: Machine Language

Background

Every hardware platform is designed to execute commands in a certain machine language, expressed using agreed-upon binary codes. Writing programs directly in binary code is possible, but also unnecessary, tedious, and highly error-prone. Instead, we can write such programs using a low-level symbolic language, called assembly, and have them translated into binary code by a program called an assembler. In this project you will write a simple low-level assembly program, and will be forever thankful for high-level languages like Java and Python. (Actually, assembly programming can be highly rewarding and useful in certain situations, allowing direct and complete control of the underlying machine.)

Overview

This section will be a brief departure from building chips — instead, you will act as a client of the computer and write code in a low-level machine language to execute. The purpose of this is to familiarize yourself with the capabilities that the computer will provide to its programmer; later, when you build the computer hardware itself, you will draw on this project to understand why each feature exists.

You will write and test the following program (starter code and tests can be found in the projects/4/ directory):

Program	Description	Guidelines / Tests
Max.asm	In the Hack computer, the top 16 RAM words (RAM[0]...RAM[15]) are also referred to as R0...R15. With this terminology in mind, this program determines the max of the values (comparing them as unsigned integers) stored in R0 and R1, stores the max value in R2, and stores the address of the max value in R3. If the two values in R0 and R1 are equal, then R0 should be considered the max. The program assumes that 0<=R0<32768 and 0<=R1<32768. Your program need not test these conditions, but rather assume that they hold.	Use a text editor to write your Max.asm program using the Hack assembly language. Use the supplied Hack Assembler to translate your Max.asm program, producing a Max.hack file containing binary Hack instructions. Next, load the supplied Max.tst script into the CPU Emulator. This script loads the Max.hack program, and executes it. Run the script. If you get any errors, debug and edit your Max.asm program. Then assemble the program, re-run the Max.tst script, etc.

Contract

Write and test the program described above. When executed on the supplied CPU emulator, your program should generate the results specified by the tests.

Resources

To complete this part of the assignment, you will likely find the specification of the Hack assembly language in Chapter 4 useful.

In the tools directory of your repo, you will need to use 2 new tools. One is the Assembler tool, which converts Hack assembly language (.asm) to Hack binary code (.hack). You will also need the CPUEmulator tool, which loads .hack files and allows you to step through, examine the state of the emulated computer, and run test scripts. Note the CPUEmulator can theoretically be used to load and run a .asm file directly (implicitly assembling it), but the test scripts always load the underlying .hack file on disk which is produced by the Assembler. Therefore, we recommend you always use the Assembler to convert from .asm to .hack before emulating so as to avoid inconsistent results between the file you're seeing in the CPUEmulator and what the test script is evaluating on.

We recommend familiarizing yourself with the tools through experimentation, but if you'd prefer a more structured way to learn about their features you can check out the Assembler Tutorial (PPTX, PDF) and CPUEmulator Tutorial (PPTX, PDF) developed by the Nand2Tetris project.

Tips

The supplied Hack Assembler can be used in either command mode (from the command shell), or interactively. Both allow creating a persistent .hack file on disk for your .asm code. The latter mode of operation allows observing the translation process in a visual and step-wise fashion, as shown below:

The supplied CPU Emulator includes a ROM (also called Instruction Memory) representation, into which the binary code is loaded, and a RAM representation, which holds data. For ease of use, the emulator enables the user to view the loaded ROM-resident code in either binary mode, or in symbolic / assembly mode. In fact, the CPU emulator even allows loading symbolic code written in assembly directly into the ROM, in which case the emulator translates the loaded code into binary code on the fly. This utility seems to render the supplied assembler unnecessary, but this is not the case. First, the supplied assembler shows the translation process visually, for instructive purposes. Second, the assembler generates a persistent binary file. This file can be executed either on the CPU emulator, as shown below, or directly on the hardware platform, as we'll do in the next project.

Part III: Building a Computer Part I

Background

In previous projects we've built the computer's basic processing and storage devices (ALU and RAM, respectively). In this project and project 5, we will put everything together, yielding the complete Hack Hardware Platform. The result will be a general-purpose computer that can run programs written in the Hack machine language.

Overview

Like projects 1, 2, and 3, building a computer will require you to build a set of HDL chips. This time, you will build the highest-level chips in the whole system, culminating with the "Computer" chip itself. As usual, you should construct these chips using the chips listed in previous projects (with a few exceptions that will be noted, see the "Tips" section for more details). In project 4, you will build only one of these chips, the Memory chip, which encompasses the entire RAM address space (note that even though this is part of project 4, Memory.hdl and its tests are stored in the directory projects/5/ so that they can be used in your future project 5 implementations as well). Later, in project 5, you will build the CPU and then tie everything together to build the final computer.

Chip Name	Description	Testing
Memory.hdl	Entire RAM address space. Estimated Difficulty: Medium.	Test your chip using the provided Memory.tst test script (which tests against Memory.cmp).

Contract

Your implementation of Memory.hdl should pass the provided tests.

Resources

See Chapter 5 for details about the computer's implementation (particularly the section on the Memory design for this project). Per usual, use the HDL Reference or HDL Survival Guide to look up details of the language. You may also find the Hack Chip Set reference useful to remember chip interfaces.

Tips

The Memory chip includes three chip-parts: RAM16K, Screen, and Keyboard. The Screen and the Keyboard are available as built-in chips, and thus there is no need to implement them. Although the RAM16K chip was built in Project 3, we recommend using its built-in version, as it provides a debugging-friendly GUI (i.e. don't copy in your solution from project 3).

Additionally, even though the Memory interface may be intimidating at first, the implementation strategies and techniques are very similar to those you've used in previous projects.

Submitting

To submit your project, make sure you commit and push your changes, then tag them as project-4 and push that tag as well:

• git add . (stage all your changes)
• git commit -m "Finish project 4" (bundle those changes as a commit; the message is up to you!)
• git push (push that commit to the Gitlab server)
• git tag project-4 (add the project-4 tag to that last commit)
• git push --tags (push the tag to the Gitlab server)

Then, verify that the tag and all your code is uploaded correctly by checking on gitlab.cs.washington.edu.

Project Skills and Passing Requirements

Below are the skills you need to demonstrate in order to pass this project, along with concrete tasks we expect you to complete to demonstrate each skill. Remember that in order to receive a passing grade for the class, you must receive a passing grade on each project. Only completing the bare minimum to pass a project will result in a low grade. See the syllabus for more details and let us know if you have any questions.

• Practice your annotation skills and reflect on their impacts
  • Complete/submit your annotations, assignment timeline, and reflection for this spec
• Write a simple assembly program that includes control flow
  • Attempt an implementation of Max.asm that includes an attempt at a test/jump, and an if/else branch
• Learn about memory mapping abstractions
  • Complete Memory.hdl