luo.box

From the Transistor to the Blockchain

Published:

Inspired by: From the Transistor to the Web Browser.

Hiring is hard, a lot of modern CS education is really bad, and it’s hard to find people who understand the modern computer stack from first principles.

Now cleaned up and going to be software only. Closer to being real.

(Optional) Section 0 - Programming Languages

Learn how to learn a programming language properly

Basic programming language concepts

Study the fundamental concepts that appear in one form or another in almost every programming language.

We mainly study two axes: statically-typed languages vs. dynamically-typed languages, and functional vs. object-oriented programming.

A statically-typed functional programming language

Learn Haskell.

Apply functional programming to a dynamically-typed language

Nix.

A object-oriented programming language.

JavaScript/Ruby/Python.

A multi-paradigm language

Finally, Rust.

Section 1 - Intro (0.5 Week)

Cheating our way past the transistor.

So about those transistors

Course overview. Describe how FPGAs are buildable using transistors, and that ICs are just collections of transistors in a nice reliable package. Understand the LUTs (Look-Up Tables) and related concepts. Provide a brief introduction to the theory of transistors, emphasizing that all projects must build on each other, thus we can’t build a transistor from scratch in this course.

Emulation

Discuss the limitations of building on real hardware and introduce emulation as a solution. Explain how using tools like Verilator allows anyone with a computer to participate in the course by emulating hardware.

Section 2 - Bringup (0.5 week)

What language is hardware coded in?

Blinking an LED (Clash, 10)

Your first program: Blinking an LED. Get the simulator working and learn the basics of Clash. This simple task helps you understand the workflow and tools required for hardware description languages.

Building a UART (Clash, 100)

Dive deeper into Clash by copying a real UART. Introduce the concept of MMIO (Memory-Mapped I/O). Implement a serial test echo program and LED control to solidify your understanding.

Section 3 - Processor (3 Weeks)

What is a processor anyway?

Coding an assembler (Rust, 500)

Write an assembler in Rust. This straightforward but essential task teaches you RISC-V assembly. Initially, the assembler outputs binary files, but it will be extended to support linking later.

Building a RISC-V CPU(Clash, 1500)

Break this into subchapters. Start with a simple pipeline: decode, fetch, execute. Discuss memory requirements and constraints, like BRAM and SRAM. Ensure the CPU is both simulatable and synthesizable.

Coding a boot ROM(Assembly, 40)

Write a boot ROM in assembly to allow code download into RAM over the serial port. This ROM will be baked into the FPGA image and will run simple test programs.

Section 4 - Compiler(3 weeks)

A “high” level language

Building a C compiler(Haskell, 2000)

Cover the basics of compiler design by writing a C compiler in Haskell. This section includes writing a parser and generating RISC-V assembly. Break this task into subchapters for better understanding.

Building a linker(Rust, 300)

Write a linker in Rust to generate ELF files. This task should be straightforward if you understand the basics of linking. Use the linker for testing with QEMU and semihosting.

libc + malloc(Rust, 500)

Implement basic libc functions like memcpy, memset, and printf, along with a simple malloc. This forms the gateway to more complex programs.

Building an ethernet controller(Clash, 200)

Interface with a real PHY and carefully design the MMIO. This task involves both hardware and software components.

Writing a bootloader(Rust, 300)

Write a bootloader in Rust to boot the kernel over UDP. The bootloader will initially download over the serial port but will be embedded in the FPGA image later.

Section 5 - Operating System(3 weeks)

Software we take for granted.

Building an MMU(Clash, 1000)

Design an RISC-V MMU. Explain the role of TLBs (Translation Lookaside Buffers) and other related concepts. Depending on the FPGA, you may also need to build a memory controller. Integrate the MMU with your bootloader, adding initialization code.

Building an operating system(Rust, 2500)

Develop a UNIX-like operating system with basic user-space threads. Implement system calls such as open, read, write, close, fork, execve, wait, sleep, exit, mmap, munmap, and mprotect. Consider the debugging interface you are using, ranging from printf statements to possibly a gdbremote stub in the kernel. Break this task into subchapters for better understanding.

Talking to an SD card(Clash, 150)

Implement the final hardware module: an SD card interface and driver.

FAT(Rust, 300)

Implement a simple file system like FAT (File Allocation Table). This involves handling basic file operations such as reading, writing, and directory management.

init, shell, download, cat, ls, rm(Rust, 250)

Develop your first user-space programs. Implement basic utilities like init, a simple shell, and commands such as download, cat, ls, and rm. These programs will provide a basic user interface for interacting with the operating system.

Section 6 - Browser(1 week)

Coming online.

Building a TCP stack(Rust, 500)

Implement a TCP stack, likely coded in the kernel. Integrate the Ethernet driver into the kernel and add support for networking system calls such as send, recv, bind, and connect.

telnetd, the power of being multiprocess(Rust, 50)

Write a simple telnetd daemon in Rust. This allows multiple users to connect simultaneously using telnet, essentially creating a bind shell.

Space saving dynamic linking(Rust, 300)

Explain and implement dynamic linking to save space. Demonstrate how a dynamic linker can be a user-space program. Discuss the required changes to the linker.

So about that web(Rust, 500+)

Create a “nice” text-based web browser using ANSI and terminal features. The browser should be dynamically linked and as feature-rich as desired, focusing on rendering web content in a terminal.

Section 7 - Physical(1 week)

Running on real hardware.

Talking to an FPGA(Rust, 200)

Write a small program to control the USB MCU to bit-bang JTAG commands, allowing communication with the FPGA.

Building an FPGA board

Design and build an FPGA board. This includes FPGA BGA reflow, FPGA flash, a 50MHz clock, a USB JTAG port and flasher (using a Cypress USB MCU for JTAG), LEDs, a reset button, a USB-powered serial port (USB-FTDI), an SD card slot, and an Ethernet port.

Optionally, design an expansion board with additional features like a host USB port, NTSC TV out, an ISA port, and a PS/2 connector. Use a toaster oven and a multimeter thermometer for reflow soldering.

Bringup

Compile and download the Clash code to the FPGA board. This step involves testing and verifying the hardware functionality.

Section 8 - Parallel and distributed computing(3 week)

Making your browser parallel(Rust, 200)

Modify your web browser to utilize parallel processing, improving performance and responsiveness.

A multithreaded web server(Rust, 200)

Develop a multithreaded web server in Rust. This server should be capable of handling multiple concurrent connections efficiently.

A parallel map-reduce(Rust, 500)

Implement a parallel Map-Reduce framework in Rust. This will involve tasks such as splitting jobs, distributing them across multiple threads or processes, and aggregating the results.

A distributed key-value storage(Rust, 500)

Create a distributed key-value storage system using the RAFT consensus algorithm to ensure data consistency and fault tolerance.

Section 9 - Blockchain(3 week)

Exploring the foundations and applications of blockchain technology.

Basic cryptographics

ntroduce and explain the fundamental concepts of cryptography that are crucial for understanding blockchain technology. This includes:

Other consensus algorithms

Explore various consensus algorithms beyond the well-known Proof of Work (PoW). This includes:

Your first blockchain(Rust, 500)

Implementing a simple blockchain from scratch in Rust.

#learning