Unit 1.10 · about 8 h
239 / 324Binary logic and machine language with Nand2Tetris
This is optional repair, not a second systems curriculum. Assume Programming's integers-pointers-spans and compile-link-abi units. First derive XOR's four rows and trace @7; D=A; @3; M=D; @3; D=M; @END; D;JEQ. If both are correct without notes, skip this unit; otherwise repair logic and machine execution through Projects 1 and 4 only.
- implement
You can now
- Derive basic Boolean gates from Nand and verify every input row.
- Trace Hack A/D registers, addressed RAM and conditional jumps separately.
- Implement and test the two selected projects only when the binary/instruction entry check reveals a gap.
Covers
- Binary logic and machine-language repair through two Nand2Tetris projects
Study, in this order
3 steps
- Project 1: Boolean LogicNand2Tetris - Projects 1 and 4 only
Objective; Chips; Contract; Resources; Tips
Depth · Use the primitive Nand and supplied interfaces/tests to implement the listed gates. Stop before Project 2; built-in primitive behavior is a logical contract, not transistor timing.
- Project 4: Machine LanguageNand2Tetris - Projects 1 and 4 only
Objective; Programs:
Mult.asmandFill.asm; Contract; Resources; Proposed ImplementationDepth · Use the linked Chapter 4 machine-language specification for A/C instructions and memory map. Mult assumes nonnegative inputs and product below 32768. Do not add assembler, CPU or compiler projects.
- Official simulator accessNand2Tetris - Projects 1 and 4 only
Online IDE; official link to https://nand2tetris.github.io/web-ide/chip/
Depth · Use the online chip and CPU tools, or the desktop suite, which needs Java. The truth-table and interpreter checks below do not replace the supplied
.tst/.cmptests.
Focus on
- Nand is false only when both inputs are true. Check each truth table independently of HDL wiring. Bus gates act bitwise; mux/demux routes values rather than adding them. Keep widths and pin directions explicit.
- An A instruction loads A. In a C instruction, M refers to RAM addressed by A, while D and A are registers. Loading an address is not dereferencing it.
- Mult uses repeated addition with a loop invariant; Fill repeatedly examines the keyboard and updates screen words. Neither task models a host CPU pipeline or operating system.
- Use entry-check failure to justify this detour. Exit as soon as the selected official tests and explanation pass; do not follow the full hardware/software sequence.
Reproduce closed-book
Mult.asm: clear R2, copy R1 into a count variable; at LOOP exit to END when count is zero, otherwise add R0 into R2, decrement count and jump to LOOP; END jumps to itself. Trace (R0,R1)=(0,7),(6,7),(1,0),(181,181), expecting R2=0,42,0,32761 with R0/R1 preserved. Check those traces with a small interpreter of your own covering exactly the used A/C instructions, including 16-bit arithmetic and label addresses; run taskset -c 2 python3 -I logic-oracle.py. State that this is a subset oracle you wrote, not the official simulator. For actual project completion, run the named official tests in practice and retain their results; no official simulator run is claimed here.Traps
- Confusing
@7;D=Awith@7;D=M. One copies the constant address, the other readsRAM[7]. - Treating repeated addition as a signed-overflow-safe general multiplier. Stay within the stated Project 4 input contract.
- Calling your own oracle an official .tst/.cmp pass, or turning an optional repair into all twelve projects.
Practice
Nand2Tetris Project 1: the supplied gate test suite
Chips and Contract; supplied .tst and .cmp for Not through DMux8Way, excluding primitive Nand
Implement the listed scalar/bus logic, mux and demux chips in HDL. Run each supplied test and save comparisons. Only undertake this repair if the entry check failed.
Nand2Tetris Project 4: Mult.asm and Fill.asm
Programs: Mult.tst; Fill.tst (interactive, no compare file); FillAutomatic.tst and FillAutomatic.cmp; Contract
Test Mult within its stated bounds, then Fill with keyboard released and pressed in the CPU emulator. Use the automatic comparison plus the interactive screen check; save which tool and tests actually ran. Skip all intervening and subsequent projects.
Self-test
-
What are XOR outputs for (0,0),(0,1),(1,0),(1,1)?
0,1,1,0. The four-Nand construction uses \(t=\text{Nand}(a,b)\), then \(\text{Nand}(\text{Nand}(a,t),\text{Nand}(b,t))\). -
After the entry-check instructions, what are A, D and RAM[3], and is JEQ taken?
A holds the END label's ROM address, D is 7 and RAM[3] is 7. JEQ is not taken because D is not zero. END's numeric address depends on the complete program. -
What invariant proves the repeated-addition loop?
After \(k\) additions, \(R2=k \times R0\) and \(\text{count}=\text{original }R1-k\). At count zero, \(R2=R0 \times \text{original }R1\). The stated bounds keep the result within the nonnegative Hack contract. -
Why does Fill keep polling the keyboard after painting the screen?
The input can change. The program must repeatedly choose black or white and repaint; one keyboard read or one screen write cannot implement the continuing contract.
Completion criterion
Stop when
Either both entry checks pass and you skip the repair, or the selected Project 1 gate comparisons and Project 4 multiplication/screen tests pass and you can explain register, memory and branch effects without notes.
Mark passed, then open 2.1 Only mark this when you can do it without notes.Leads to
- 1.1 Instruction pipelines, branches and SIMD Return to instruction dependencies once register and memory effects are concrete.
Resources for this unit
- Nand2Tetris - Projects 1 and 4 only Use Project 1 for Boolean logic and Project 4 for machine-language execution only if the binary or instruction-level entry check fails. Do not take the full course as a second systems curriculum.
Also in this section
- Operating Systems: Three Easy Pieces - selected foundations Read Chapters 4-7, 13-15, 18-21, 36, 39-40, 42 and 45. Work from process state to address translation, devices, files, journaling and integrity. For every chapter, draw the owned state and one failure boundary instead of collecting summaries.
- MIT 6.1810 - selected xv6 process and memory labs Use Fall 2025 Lectures 1, 3-6, 8 and 10-11. Complete the util lab, one syscall task, and the page-table inspection plus ugetpid task from pgtbl. Add cow only if copy-on-write remains unclear. Keep all work in your own course checkout and stop before the full xv6 sequence.
- OSTEP homework - process, paging, disk and integrity simulators Solve process-run.py, paging-linear-translate.py, paging-policy.py, disk.py, fsck.py and checksum.py for at least two seeds each before using the answer flag. Then reproduce one prediction using strace, /proc or a small local program.
- AlgoMaster Operating Systems - selected observation route After OSTEP, use the matching lessons as a second explanation and recall check: fork, exec, wait, and exit; Zombies and Orphans; Signals; Context Switching; The Process Address Space; Paging; The TLB: Hits, Misses, and Invalidation; Page Faults; Copy-on-Write; mmap and Memory-Mapped Files; How malloc Works; VSZ, RSS, PSS, and What They Mean; File Descriptors; The Page Cache and Write-Back; Durability and fsync; Crash Consistency; Linux Namespaces; Control Groups; PID 1 and Signal Handling; Container Resource Failures; and the Investigating lessons. Treat quizzes as recall checks and keep your own traces as evidence.
- Linux proc and strace references Use proc(5), getrusage(2), mmap(2), fsync(2), rename(2), wait(2) and signal(7) while tracing a parent-child pipe, page faults, file publication and a resource-limit failure. Record exact commands and raw observations.
- Algorithmica - Algorithms for Modern Hardware Use the Instruction-Level Parallelism, SIMD Parallelism and RAM & CPU Caches chapters for measured pipeline, branch, vectorization, bandwidth, latency and cache-line effects. The figures are the author's Zen 2 measurements at a fixed 2 GHz: predict and measure your own.
- MIT 6.S894 Accelerated Computing - Throughput Processors Use Lecture 2 for the processor model behind this section: superscalar issue, out-of-order execution, speculation and SIMD's need for coherent control. The labs run on the course's remote machines and target AVX-512 and NVIDIA GPUs, so they belong to the GPU track.
- Auto-Vectorization in LLVM Use The Loop Vectorizer Usage and Diagnostics sections for the Clang remarks the pipelines unit asks for; the Features list is optional depth.
- AlgoMaster: hardware and container storage companions Use Memory Ordering, Barriers, and False Sharing (coherence and false-sharing headings only); Huge Pages, NUMA, and ASLR (NUMA headings only); Storage Hardware; RAID Fundamentals (comparison and backup boundaries); and Container File Systems. These fill hardware and image-layer gaps outside the pool's selected OS revision lessons.