Two files

Excluding the warmup puzzle -- which you should for sure try -- the puzzle consists of just two files: puzzle.gds and example_inputs.vcd. The puzzle centres on the Graphic Data System, or GDS file. The example inputs are there as a simple test case: one input, and the output the chip should produce for it.

Layers

Opening the GDS file in a dedicated program like KLayout, we can immediately see some of its structure. It describes a layout: polygons of different types, indicated by their layer. It also contains annotations, which make the entire file look like a mess when you first open it.

Cells

The GDS file format allows you to group polygons into cells. Such cells can be defined once and placed many times. They typically define logic gates, which in turn make up registers, computational units and so forth. Such a hierarchy makes it more manageable to design a chip. Though again, this hierarchy is typically the result of a higher-level description in Verilog, which is ultimately translated into this layout. The cell boundaries give us some of that structure to work with, even though we don't have the original Verilog.

Just a layout

Whilst a GDS defines a layout, on its own it says very little about what that layout actually means. Even the depiction on the right is somewhat suggestive, since we've already given the layers colours and thicknesses. Looking at the file alone, we wouldn't know which of those layers were metal, which were silicon, or how a fab would turn them into a working chip.

To make sense of them, we need to know the manufacturing process the chip was designed for. Each process has its own conventions for what the layer numbers mean. These are documented in a process design kit, or PDK, along with the rules for how the different materials can be used. So before we can read much of the circuit, we need to find out which process we're looking at.

Finding the process

Fortunately, the names of the logic cells give us a fairly direct clue. They start with sky130_fd_sc_hd__, which identifies a standard-cell library for the SkyWater 130 nm process. A standard-cell library is a collection of ready-made components, such as logic gates and flip-flops, that a chip designer can use without having to draw each one from transistors.

The documentation for this process and library is public, so we can look up both what the layers mean and what the cells are supposed to do. Which is quite a bit more convenient than having to work all of that out from the polygons ourselves.

The layers

With that documentation, we can start putting names to the layers. Near the bottom, nwell, diff and poly define the parts of the transistors. We'll look at those in a moment. Just above them is li1, short for local interconnect, which joins transistors together within a cell.

Above that are five metal layers, met1 through met5, for wiring the cells together and carrying signals across the chip. Having several layers lets wires cross without touching. To connect a wire on one layer to a wire on the next, there has to be a connection through the insulating material between them, called a via. The cut layers, the ones ending in /44, specify where those connections go.

This distinction will matter when we try to follow the wires. Two polygons can overlap in the top-down view without being electrically connected, so we need to keep track of their layers as well as their shapes.

Inputs and outputs

The file also contains text labels on some of its layers. At the top level, these name the inputs and outputs of the chip, so we can already get some idea of how we're supposed to interact with it.

On the left we have clk, the clock, along with rst_n, enable and I. On the right are the eight bits of O and a separate success output. The puzzle asks us to find an input that makes success go high. We don't yet know what that input should be, but at least we know where to send it and where to check the result.

The pins of a cell

If we zoom into one of the logic cells, we find another set of labels. These tell us where the cell's own inputs and outputs connect to the wiring around it. The cell we're looking at is an XOR gate, with two inputs, A and B, and an output, X.

There are also VPWR and VGND, the power and ground connections. These run along the top and bottom of the cell, so neighbouring cells can share them. The labels themselves are just annotations. It's the conducting material underneath each label that forms the connection. Later, we can use those positions to work out how the gates are wired together.

A transistor

The logic gates we've been looking at are made from transistors. For our purposes, we can think of a transistor as an electrically controlled switch: the voltage on one terminal, called the gate, determines whether current can flow between the other two, the source and drain.

In the layout, we can recognise one where a strip of polysilicon crosses a diffusion region. The polysilicon forms the gate, separated from the silicon underneath by a thin insulating layer. The diffusion on either side forms the source and drain. So although these shapes overlap in the drawing, the gate isn't directly connected to the material underneath it.

There are two kinds of transistor in these cells, nMOS and pMOS. Roughly speaking, an nMOS conducts when its gate is high, while a pMOS conducts when its gate is low. This is again a simplification, but it's enough to follow how they're used here. By combining the two, we can make a circuit that connects its output to either power or ground depending on its inputs.

The example on the right picks out one transistor from the cell. This helps us understand what the shapes in the GDS represent. For the analysis, though, we can work with the logic gates those transistors form.

XOR gate

An XOR gate is a simple example.2 It has two inputs, A and B, and one output, X. If the inputs differ, the output is one. If they're the same, it's zero. We can treat the whole cell as this one operation, regardless of how it's implemented internally.

In the layout, the labels A, B and X mark its input and output connections on li1. So we know what the gate does and where it connects. Given the values on the two input wires, we can calculate the value on the output wire and pass it on to whichever gates it connects to. That's how we'll use these cells to simulate the chip.

Flip-flops

Most cells are more or less immediate: their output is some function of whatever happens to be on their inputs right now. A flip-flop is slightly different, since it lets the circuit remember a value instead.

It has a data input D, an output Q, and, importantly, a clock input CLK. On the edge where the clock goes from low to high, whatever value is on D becomes the new value of Q, and it then stays there until the next rising edge, regardless of what happens to D in between.

This is throwing quite a bit of nuance out of the window. Real flip-flops have setup and hold times, the clock does not arrive everywhere at exactly the same instant, and none of these transitions are really instantaneous. Though for what we're trying to do, none of that matters very much. We only care about the logical behaviour of the chip, so we can treat a rising clock edge as one precise moment where every flip-flop updates.

The flip-flop shown here also has RESET_B, an active-low reset. Pulling it low forces Q to zero without waiting for a clock edge.

There are 92 flip-flops on the chip. So instead of thinking about the circuit continuously changing over time, we can think of it as having 92 bits of state, with the clock deciding when those bits update during normal operation.

Clock buffers

Buffers are much less interesting. They are simply there to transmit the clock signal over large distances. Physically, they are necessary, since a small gate cannot necessarily drive a long wire or many other gates quickly enough, so buffers are placed in between to help drive the signal.

For us, this means they can mostly be ignored. We just need to keep track of the clock.

Back to the whole chip

If we colour the cells by the kind of component they implement, we can see how much of the chip is made from the same few building blocks. The layout is still fairly overwhelming, but we now have some idea of what we're looking at.

To work out what the whole chip does, we need to know how those components are connected. That means following the wires between them, which is what we'll do in part two.

Abstract the cells

For the purposes of the puzzle, we actually don't need to simulate individual transistors. Just as we identified the sky130 process from the cell names, we can also infer the cells' functions from their names. Each cell name describes a component: xor2 is an XOR gate, and4bb is a four-input AND gate with two inputs inverted, and so on.

Knowing this, we can treat each cell on the chip as the logical component it represents. The only problem is, we don't directly know which components connect to each other and how.

Where a cell connects

To connect components, we need to know two things: which part of the cell corresponds, logically, to which part of the gate? And which conducting wires connect two cells?

The first is answered by the 67/5 layer, otherwise known as li1 label. There we see where the inputs and outputs attach on the cell. For the XOR gate, these are A and B for the inputs and X for the output. Its power and ground labels, VPWR and VGND, are on 68/5, the met1 label layer.

These labels themselves don't conduct. The signal labels refer to the conducting material underneath them, on layer 67/20, the li1 drawing, the lowest wiring layer we use for tracing between cells. Each signal-pin label identifies the li1 conductor beneath it. Shapes touching on the same conductor layer are connected. Connections to another layer require the appropriate contact or via.

Connecting components

Naturally, two cells connect if there is a conducting path between them, and what counts as a conductor is defined by the technology we're using to fabricate the chip. For sky130, we again refer to the diagram. The met -- as well as the li1 -- layers conduct over distances. These layers are connected by vias, which conduct from layer to layer.

Following the wires

Then we simply follow the connected conductors to trace each wire.

Putting everything together and keeping track of the components gives us the netlist.

Deriving the netlist

Following these connections gives us a list of the gates and which pins share a wire. This is the netlist. For each gate, we keep its cell type so we know what it does, and for each of its pins, we record which wire it connects to.

One wire can connect to several gates, and we need to keep track of the particular pins it reaches. Connecting to a flip-flop's data input D means something quite different from connecting to its clock input CLK, even though both connections reach the same component.

With that information, we can draw the circuit as a graph. The components no longer need to sit where they were placed on the die. We can arrange them to make their connections easier to follow. We've also left the power lines out of this view, since we'll treat the supply as fixed when calculating the gates' logical behaviour.

Ignoring the buffers

We can simplify the clock wiring too. The clock buffers repeat the same logical signal, so we can follow them back to check which clock drives each flip-flop. In this chip, they all update on the same rising edge. For the simulation, we can treat that as one moment when all the stored bits update.

Between those updates, the flip-flops hold their current values on Q. Together with the chip inputs, these give us the values we need to start calculating. Whenever we know all the inputs to a gate, we can calculate its output and use that value in the gates connected to it. We keep going until we have the chip outputs and the values on every flip-flop's D input.

Then we update all the flip-flops at once, copying each D value to its corresponding Q, unless reset or set is asserted. Doing this together matters, since every new value should have been calculated from the state before the clock tick. We now have the next set of 92 stored bits, and can repeat the calculation for the next cycle. That's enough to run the circuit.

Testing the circuit

We can now go back to the other file we were given, example_inputs.vcd, and check whether our simulator actually works. A VCD file records how signals change over time: it starts by listing their names, then gives timestamps and the values that change at each one. In this case, it contains both the inputs sent to the chip and the outputs it produced, so we have something to compare against.

The example starts by holding rst_n low for three clock cycles to reset the chip. It then sets enable high and sends 121 bits through I, one per cycle. Once those are sent, enable goes low and we can read the output on O. We can follow exactly the same sequence in our simulator and check whether O and success agree with the recording. Across the whole recording, all 730 output-bit values we can compare match. This doesn't prove we've recovered every connection correctly, but it gives us some confidence that the circuit we're simulating behaves as it should.

The output on O is eight bits wide, and interpreting those bytes as ASCII gives us TRY AGAIN. Which is reassuring as far as the simulator goes, though it doesn't tell us very much about what the chip wants us to give it. To find that out, we'll need to look at what the circuit actually does.

Look at the layout

We follow the hint and group components by their location. Splitting the output writer from the tip of the long region on the right gives us eleven regions in all. We call the output writer R11, following the hint that it can be considered separately.

Among the cells that carry signals, the ones outside these regions are clock buffers. We leave them out of the region diagram, while keeping track of which clock drives the flip-flops.

Drawing these boundaries allows us to separate the logic of each region and treat it as its own subcomponent, with its own inputs and outputs.

Our analysis can then simply look at the behaviour of each component, possibly looking at its memory bits under different inputs, or perhaps how it's structured within the region.

So which region to pick?

How the regions connect

To answer this, we should check how regions connect to one another using the netlist. It might be easier to figure out the function of a particular region if we know the meaning of the information travelling to it.

Some regions are near the outputs, such as R10, which gives us the success bit, and R11, which writes O. Some have many inputs, outputs, and memory bits, such as R5 and R7, and others have very few inputs, like R1.

Ordering the regions

We can now draw the regions as a graph and arrange them according to how information passes between them.

Next, to see where a region sits in the flow of information, we can look at the trophic level of each component. It's a measure from ecology that roughly defines a position in a food web, from prey to predator. For us, that would mean from input to output.

The regions, now drawn with their trophic level in mind, give us an indication of where to start. We see that region 1 is at the bottom of the food chain and tends to feed downstream.

We go through the regions in this order, R1 to R11. It gives us a useful direction to follow, even though feedback means some later regions feed earlier ones.

Along the way, we will then label the regions more descriptively once we have figured out their function.

R1

The first region, region 1, is not only at the bottom. It's also (not quite) coincidentally the simplest. Other than the clock and reset, it has only one input bit, which comes from region 3.

In this case, we can simply check the behaviour of the internal memory and output as we advance the clock, both when its input bit is on and when it's off.

The result is simple: the memory bits don't do anything if the input is off. When it's on, we see a transition every tick: 0001, 1000, 1001, 0010, 0011, 1010, 1011, 0100, 0101, 1100, 0000, and back to 0001. Eleven distinct values and then it repeats. Although these values are not exactly counting in binary, that doesn't matter.

We also know from the previous section that the input is a total of 121 bits, which is already quite suggestive, so we can visualise the counter's value for each of the 121 bits on an 11 by 11 grid.

Because it has a unique value for each column of the grid, we'll just call this the column counter.

We should also check the output wires. Four of them simply pass on the information stored in the memory. There is also one additional bit that pulses on the tick that completes each round of eleven counts. Three regions read that wire. One of them is R2, up next.

R2

The second region has the same inputs as the column counter, with just the extra bit signalling the end of a round of eleven counts.

Again, we observe that if the bit from region 3 is off, nothing happens to the internal state. Equally, we notice that nothing happens as long as the pulse from the column counter is off. It goes on at the end of each round of eleven counts.

If both are on, we see that our internal memory state changes, again cycling through 11 different values.

Visualising this on the grid again, we see the rotated version of the column counter: we've got rows, giving us a row counter. Together, these two give us coordinates to locate a point on the 11x11 grid.

Here, the output wires are the same: four bits that pass on the counter's value, and one more bit that goes on when this counter completes its round, at which point we've finished the 121-bit input.

R3

Next comes the small box that feeds both counters. It has a single memory bit. Its inputs are the enable port and the two round pulses, one from each counter, and it has two outputs. One controls whether input bits are accepted. The other tells R10 that the input is complete.

The input gate is on while enable is high and fewer than 121 bits have been accepted. The memory bit records when both counters complete the input. After that, another attempt requires a reset.

So this wire tells the boxes reading the input whether the bit on I counts right now.

R4

The next box has no memory bits at all. It reads the four bits of the column counter and the four of the row counter, and writes four wires onward.

Without memory, the output is a fixed function of the two counters, so we don't even need the clock. We set the counters to each of the 121 positions and read the four wires.

They take eleven different values. When we colour the grid by these values, the cells that share a value form a patch, and we get eleven patches of quite different sizes, from four cells to twenty-eight, with rather odd outlines.

We can describe the result as a lookup table from grid position to patch number. This implementation uses 147 gates. So this box answers one question: which patch is the current cell in? We'll call it the patch map.

R5

Now the first big one, with twenty-two memory bits. Before running anything, we look at how it is wired. If we follow only the wires that stay inside the box, we find that, after leaving out the buffers, its 96 remaining cells fall apart into eleven separate pieces, each with two memory bits and one output wire, and the pieces don't talk to each other at all. So this is eleven copies of one small machine, and we only need to understand one.

Each piece reads the column counter, the input gate, and I. Nothing from the row counter, so it must behave the same in every row.

We take one piece and run it. Two bits, four states. It only changes while the input gate is on, I is one, and the column counter is at one particular value, and then it goes 00, 01, 10, 11 and stays at 11. Its output wire is on in state 10 only.

So each piece counts the ones in one column, stops counting at three, and says yes at exactly two. On the given input the first piece ends at 11, because that column has four ones. Eleven columns, eleven pieces. The eleven yes wires go on together to the big box after next.

We'll call this the column count.

R6

The next box is small again, three memory bits. It reads the column counter and its round pulse, the input gate, and I. Two wires go to R8, and one goes to R10.

Its cells make four pieces, but three of them are single cells: two OR gates that tell R8 whether the current column is at either edge of the grid, and a tie cell that supplies a constant. The piece that matters has fifteen cells and all three memory bits.

Two of the bits count the ones in the current row, stopping at three. The count resets at the end of each row.

The third bit is a flag: once on, it stays on. Running it on the given input, it goes on at the last cell of the first row, and that row has three ones. It reads the column counter, so it knows where a row ends. The flag means "a row ended with the wrong number of ones".

We'll call this the row check.

R7

This box is the column count once more, with one input swapped: instead of the column counter, it reads the four wires of the patch map. Again eleven pieces that don't talk to each other.

Running one of them gives the same four states and the same rule, but it moves on the ones in one patch. Eleven patches, eleven pieces, each saying yes at exactly two. The eleven yes wires go on together to the box after next.

We'll call this the patch count.

R8

We can look at this box one piece at a time. It has thirteen memory bits. Following the inner wires gives us two pieces: a small one of four gates with no memory, and a large one of twenty-nine cells holding all thirteen bits. We treat them separately.

The small piece is easy. The eleven yes wires of the column count go in, one wire comes out, and the four gates are an AND tree: the output is on only when all eleven are. It means "every column has two", and it goes straight to the second-to-last box.

The large piece takes more care. Twelve of its memory bits form a shift register. While the input gate is on, the first stores I and each following bit copies the one before it. They hold the previous twelve accepted input bits.

Since the input is an 11 by 11 grid arriving one row at a time, we can give those delays a position. The previous input bit is the cell immediately to the left. Eleven bits back is the cell directly above, whilst ten and twelve bits back are above-right and above-left. These four delays identify the earlier neighbours where they exist. The two signals from R6 mask out comparisons that would cross the left or right edge of the grid.

The remaining gates combine those four bits with the arriving I: while the input gate is on, if the new bit is one and any valid earlier neighbour is also one, the thirteenth memory bit is set. It then feeds back into itself, so once this has happened it remains set for the rest of the input.

Those four comparisons are also enough. The other four neighbours of a cell are to its right or below it and haven't arrived yet. When they do arrive, the current cell will instead be one of their four previous neighbours. So every adjacent pair only needs to be checked once.

The chain is therefore turning our one-dimensional stream back into just enough of a two-dimensional neighbourhood to test whether two ones touch, either by an edge or a corner. We'll call the whole thing the neighbor check.

R9

The next box has eight memory bits and, like the last one, two pieces: four gates with no memory, and thirty-five cells with all eight bits.

The four gates are the same AND tree as before, this time over the eleven yes wires of the patch count. "Every patch has two."

The other piece counts I while the input gate is on. When we run it, the bits hold on a zero and change on a one. As we follow the changes, no value comes back until 256 ones have gone by. So the eight bits count every one that arrives, in a code that isn't plain binary. One of its output wires is on at a single value only, the one that 22 ones reach. The given input has 38 ones, so this wire is off when the input ends.

We'll call this the total count.

R10

Almost at the end, the box that drives the success port. Six wires in, and by now every one of them has a name: the input-complete flag, the row check, the neighbor check, "every column has two", "every patch has two", and the total count. Three signals go to the output writer. One of them also drives the success port.

Walking back from the port, we find a memory bit driven by a small network of gates. On the tick after the input is complete, it records whether all the checks passed. It then holds that result until reset. On the given input it stays at zero.

So the chip says yes to a grid with two ones in every row, two in every column, two in every patch, no two touching, and 22 in all. This is the success bit.

The rectangle also holds two more memory bits. One starts the readout after the input ends. The other records the case where all the counts pass but the neighbour check fails, so the output writer can choose a different message.

The rules

Taking a step back, we've mapped out every region and its function. In sum, the success conditions are:

- two per row - two per column - two per region - none touching - 22 in all

If you were any more attentive than me, you might already have realised that these are the rules of the two stars game. This is a Star Battle. The chip is a Star Battle validator, and the eleven patches decoded by R4 divide up its board.

Solution

R11

This is the output writer, the box we were told we could ignore, and it's the biggest of all: twelve memory bits and over two hundred cells. It reads three wires from R10, two from the total count, the input gate and I, and it writes the eight O wires.

Here, we can simply check its behaviour under different inputs and see what output it prints.

Acknowledgements

Through sand to the stars.

Thanks to Leander Post for solving the puzzle with me and helping with the visuals, to Jane Street for the puzzle, and to Fabio Crameri for the colour maps.5

My thanks also to Claude and Astra for their help.