Tiny Tapeout 02 | Biko's House of Horrors

2D rendering of the final silicon layout

Back in November the Tiny Tapeout project opened its doors for the second time. The project is a way to get a (simple) chip design manufactured on actual silicon for a (somewhat) affordable price.

Since I wanted to try my hand at Verilog for some time, naturally I jumped on this opportunity...

At the last possible moment.

TL;DR: I implemented a 5-bit Galois LFSR and a 16-bit CPU in Verilog. The code is here, and a 3D rendered GDS is here.

Shift into high gear
There's no more time
Hack
The Plan
We'll fit
Appendix: Hack ISA
- A-Instruction
- C-Instruction

Shift into high gear

It is evening, November 13th. The submission deadline is November 14th, 19:00. What can I do in two evenings with virtually zero experience in Verilog?

A counter that increments the digit on the 7-segment display every second? I did that once on an FPGA, so that's a no. I want something new.

How about an LFSR? It's still basically a counter, but the sequence it generates is pseudo-random. Here's a nice video that explains the basic operation (in fact, that was the inspiration).

The plan is to have a configurable LFSR: the user should be able to set both the initial state and the taps. How wide (in bits) can we make it?

We'll need two registers: one to store the taps, another to store the LFSR's current state. Since on power-up the contents of the registers are undefined, we'll also need two reset signals to initialize them: one reset will initialize the taps register from the user input, the other will initialize the initial state. Another signal is reserved for the clock. So we're left with 5 inputs to work with.

And here it is¹:

module lfsr #(
    parameter BITS = 8,
    parameter TICKS = 1
) (
    input clk,

    input reset_lfsr_i,
    input [BITS-1:0] initial_state_i,

    input reset_taps_i,
    input [BITS-1:0] taps_i,

    output [BITS-1:0] state_o
);
    reg [BITS-1:0] taps;
    reg [BITS-1:0] lfsr;

    localparam TICK_BITS =
        ($clog2(TICKS) == 0) ? 1 : $clog2(TICKS);
    reg [TICK_BITS-1:0] tick_count;

    assign state_o = lfsr;

    always @(posedge clk) begin
        if (reset_taps_i) begin
            taps <= taps_i;
        end else if (reset_lfsr_i) begin
            tick_count <= 0;
            lfsr <= initial_state_i;
        end else begin
            if (tick_count == TICKS - 1) begin
                tick_count <= 0;

                // Advance the LFSR
                if (lfsr[0]) begin
                    lfsr <= (lfsr >> 1) ^ taps;
                end else begin
                    lfsr <= (lfsr >> 1);
                end
            end else begin
                tick_count <= tick_count + 1;
            end
        end
    end
endmodule

The gist is this:

On every clock cycle:
1. Check whether either of the reset signals is asserted.
  1. If so, initialize the appropriate register.
  2. If not, check the tick counter.
    1. If we've not yet counted enough ticks for a full second, advance the counter.
    2. Otherwise, reset the counter and advance the LFSR.

For example, if we have an 8-bit LFSR with a clock frequency of 4 Hz, we might see something like this:

For a 5-bit LFSR there are enough choices of taps for a maximal-length sequence, so we should be able to have a pretty light display 🚦.

The whole thing was submitted on November 14th, at exactly 19:00:²

Screenshot of GitHub commits list. The highlighted commit was made at the exact time of the deadline.

There's no more time

And then, ~1 hour after the submission deadline, this arrives in the mail:

I just heard from Efabless that the November 14th Tapeout deadline has been pushed back to the end of the month.

Oof.

But okay, the design is done, it works (in simulation), no need to touch it.

I'll just leave it as it is.

It's fine.

Hack

Hack, as defined in the Nand2Tetris course, is a very simple 16-bit Harvard architecture machine:

CPU capable of basic arithmetic operations:
1. Addition
2. Subtraction
3. Bitwise AND
4. Bitwise OR
5. Bitwise NOT
ROM with 32K 16-bit words for storing the program.
RAM with 16K 16-bit words.
512x256 black and white (1 bit) display.
Keyboard.

And that's about it. There isn't even a shift operation! Additionally:

The RAM and ROM can only be accessed by individual words. It's impossible to access a single byte, for example.
There is no instruction for reading from ROM, so it can't be used for storing constants.
All arithmetic operations are signed. There are no unsigned operations.

(See the appendix for more info.)

But even though the CPU is extremely limited, people managed to do really impressive things with it. I mean, here's a raytracer: https://blog.alexqua.ch/posts/from-nand-to-raytracer/.

Nitpicker's corner

Yes, technically the author runs the code in the VM emulator, not directly on the Hack CPU. The assembled code might not even fit in the ROM.

But, the code still manages to run with the platform's limited RAM and arithmetic capabilities.

It is a very impressive achievement.

So check out the course, it's pretty good!

There are various implementations of Hack on an FPGA, but wouldn't it be nice to have it on actual silicon? If we're cursing sand to do our bidding, might as well go all the way 😈.

The Plan

We already have a working LFSR in hardware, so naturally the next step is to make it work in software. The goal is to build a Hack implementation that can run an LFSR and output its values through the PCB's output pins. Using the 7-segment display is a bonus. And, the original hardware LFSR should still be present, just in case the CPU doesn't work.

We'll need:

A Hack CPU
RAM
- It mustn't be very large. Just enough to make the LFSR program work.
ROM
- Again, only big enough to hold the LFSR code.
A UART for uploading the program to the ROM
Glue for interfacing the Hack CPU to the output pins
A way to switch between running the CPU and the hardware LFSR.

For the UART, I mostly adapted the code from whitequark's implementation. The CPU itself was more-or-less directly translated from my code for the Nand2Tetris course. Actually, it was the "expanded" version of the CPU, with support for multiplication and bitwise shifting.

And here's the address map (in 16-bit words) I landed on:

Low address	High address	Description
`0`	`RAM_WORDS-1`	RAM
`RAM_WORDS`	`0x3FFF`	A20 😎
`0x4000`	`0x4000`	`io_in` (high 8 bits are always 0 on read)
`0x4001`	`0x4001`	`io_out` (high 8 bits are ignored on write, 0 on read)

Where RAM_WORDS is a compile-time parameter which must be a power of 2. Then, the address space between the RAM and the "I/O space" will just wrap back around to point to RAM. Reading from address 0x4000 would sample the input pins of the PCB. Writing to 0x4001 would drive the PCB's output pins.

Finally, I used io_in[1] and io_in[2] to determine whether the LFSR or the CPU should be active. Recall that these pins are used to reset the LFSR initial state and taps, respectively. Asserting both of them at the same time isn't really valid, so we can use that state to indicate that the CPU should be active instead.

And the LFSR program? Here it is:

lfsr.asm

// IO_OUT   - holds current LFSR state
// R0       - holds loop count
// R1       - temp storage

(lblStart)
    @1          // Initial state
    D=A
    @16385      // IO_OUT
    M=D

(lblLoop)
    // Each instruction takes a cycle, and there are
    // 10 instructions in the busy loop, so we need 625
    // loops to wait a second, with a clock speed
    // of 6250 Hz.
    @R0
    D=M
    @624
    D=D-A
    @lblNext
    D;JEQ

    @R0
    M=M+1
    @lblLoop
    0;JMP

(lblNext)
    @R0
    M=0

    @16385  // IO_OUT
    D=M
    M=M>>
    @1
    D=D&A
    @lblXor
    D;JGT

    @lblLoop
    0;JMP

(lblXor)
    // R1 = ~(IO_OUT & Taps)
    @16385  // IO_OUT
    D=M
    @142    // Taps - 0x8E
    D=D&A
    D=!D
    @R1
    M=D

    // IO_OUT = (IO_OUT | Taps) & R1
    @16385  // IO_OUT
    D=M
    @142    // Taps - 0x8E
    D=D|A
    @R1
    D=D&M
    @16385  // IO_OUT
    M=D

    @lblLoop
    0;JMP

The program is an 8-bit LFSR, and outputs its state once a second (approximately) directly to the PCB's io_out pins. There's no 7-segment logic here. After assembling, the whole thing comes down to 42 instructions.

You can see all the code from this stage here.

Okay then. The design is done, the tests are passing, it's time to run synthesis.

We'll fit

Attempt #1

Code, GDS run

[INFO GPL-0019] Util(%): 390.08
...
[ERROR GPL-0301] Utilization exceeds 100%.

That's, umm... Less than ideal. We're basically using 4 times the area we have for the design.

Low address	High address	Description
`0`	`0x3FFF`	Zeroes
`0x4000`	`0x4000`	`io_in` (high 8 bits are always 0 on read)
`0x4001`	`0x4001`	`io_out` (high 8 bits are ignored on write, 0 on read)

Biko's House of Horrors blog writing talks misc about

Shift into high gear

There's no more time

Hack

The Plan

We'll fit

Attempt #1

Attempt #2 - Reduce RAM

Attempt #3 - Disable multiplication

Attempt #4 - Reduce ROM

Attempt #5 - Absolutely disable multiplication

Attempt #6 - Streamline PROM

Attempt #7 - Simplify 7-segment somewhat

Attempt #8 - Disable multiplication (again)

Attempt #9 - Optimize LFSR assembly, reduce ROM size

Attempt #10 - Implement XOR instruction

Attempt #11 - Further optimize LFSR assembly

Attempt #12 - Downclock

Attempt #13 - Remove RAM cell

Attempt #14 - Get rid of loop in LFSR assembly

Attempt #15 - Get rid of RAM entirely

Attempt #16 - Cut ROM in half

Attempt #17 - Further reduce memory

Attempt #18 - Cut ROM in half

Appendix: Hack ISA

A-Instruction

C-Instruction

Biko's House of Horrors
blog writing talks misc about