Introduction

In the previous write-up, I explained the CPU architecture in detail for my new project, the disintegrated machine, a transistor-based computer, using core memory.

In this article I will detail how I intend to implement the CPU. The word 'intend' does some work in that sentence. At this point, I have a working RTL implementation that passes tests in simulation. It is not fully tested though and I certainly haven't built anything real yet. I will link to the repository containing the code at the end for those few who are interested in checking it out.

With all these weasel-words out of the way, let's dig in!

A quick recap

Previously I went on and on about core memory and it's temperament. The short version is that core memory requires reads and writes to come in pairs: a read must be followed by a write and a write must be preceded by a read. Even if the read value is not used, or the value in memory is not modified. These are the rules.

I also mentioned that the access time of my core memory is about 500ns, so I plan on a 2MHz clock speed for the processor.

The instruction set uses 16-bit instructions and usually have one register and one memory operand.

Putting these together the shortest time to execute an instruction is 4 cycles: one needs to read the instruction word, then write it back, then read the memory operand and finally write that (or the modified result) back.

This already means that a pipelined implementation is overkill, even if it were in the cards for a transistor-based machine, which it isn't of course. So I'll have a multi-cycle implementation, trying to stick close to the four clock cycles per instruction as much as possible. Why I couldn't quite get there will be revealed towards the end. Before we get further though, I'll have to discuss one topic in detail. And that is: registers

Registers

Or state in general. A CPU holds its state in things, called flip-flops.

Let's take count of how many bits of 'state' the CPU will have to have. There are the four architectural registers: $PC, $SP, $R0 and $R1. At 16 bits each, this is 64 bits total. Then, there's the instruction register holding the currently executing instruction for an additional 16 bits. There's the INTEN bit that controls if interrupts are enabled. Then there's the current phase of the instruction execution (since every instruction takes multiple clock cycles, the CPU has to keep track of where it is). This is at least 2 bits,, bringing the total to 83 bits. There are others as well that we'll get to in due course, but let's stop here for now.

To get an estimation of how expensive this is, we have to understand how many transistors each storage-bit takes. The minimal RS-flip-flop, the most primitive of storage elements needs two NAND gates and requires 6 transistors.

As a side-note: the fact that each of these NAND gates need three transistors depends on the logic used and I will get back to this in a future post. For now, just take my word for it.

By the time we create a D-latch, things get more complicated:

This would be a whopping 12 transistors.

Modern logic design shies away from latches and for good reason: timing closure. They instead use something called an edge-triggered D-flop:

This monster takes 19 transistors per bit to implement. If I went the traditional route and each state-bit takes 19 transistors, that's more than 1,500 transistors right there. Storage is expensive. State is expensive. This is the primary reason why the instruction set only defines four registers. Fewer than that seems too limiting (even the 6502 had five and you can't get much simpler than that) and more is too expensive.

This is also the reason that my implementation doesn't use D-flops, instead relying on almost exclusively latches. That still is about 1,000 transistors, but a significant saving.

Another side-note: transistors are not expensive, one can have 3,000 of them for about thirty bucks. That's not the problem. The problem is all the work of soldering them in place. The time involved is what makes me want to reduce transistor count to a reasonable minimum.

The block diagram

Every CPU description must have a block diagram going with it and who am I to buck the trend? So this is what my CPU looks like:

The design centers around the ALU. To the left of it, you see the four architectural registers. On the top-right corner you have the instruction register while at the bottom you find the bus interface. Registers are marked with 'REG' in the block diagram and have pointy corners (because I couldn't figure out how to add colors in Svgbob). There are of course extra details not shown and there is the whole control logic omitted, but it still gets us something to talk about.

As I have said, the center of the CPU is the ALU. It has two inputs, each fed by a multiplexer. The A input can be set to any of the architectural registers, constant zero or 1, the address bus register and the combination of INTEN and the INT pin status.

Yet another side-bar: the address bus register contains the result of the effective address calculation. This, in case the second operand was not a memory reference, is what we need to use as our second operand during execution. For this reason we need a path to feed the register output back into the ALU input.

The B input has a much smaller multiplexer that can chose between the data bus register value, zero or the (sign-extended) immediate field of the currently executing instruction.

The ALU result flows through the ALU result register before it can be fed back to any of the architectural registers. The ALU result can be directly fed into the data- or address-bus registers.

The data-bus register (BUS_D) is also used to capture any value read from memory - be instruction or data, which is why an input multiplexer is needed before this register. Capturing the received data during a read operation is needed to support the mandatory write-back to core memory.

The last bus to mention is the data-bus from memory. This can feed two consumers: the instruction register, and (as I mentioned before) the data-bus register.

I've mentioned several new registers here, so let's spend some more time justifying their existence. The easy ones to explain are the address- and data-bus registers. These are needed to present stable address and data values towards the memory during an access cycle. This in turn is needed because the memory is doing a lot of things during the 500ns it takes it to do a read or write; stable control signals are crucial for proper operation. Of course keeping the signals stable could be part of the memory subsystem instead of the CPU, but these registers need to live somewhere.

The register at the back-end of the ALU serves a different purpose and its existence leads us back to the discussion of the complexity of the various register types. As I mentioned, I decided to use latches (sometimes called transparent latches) as much as possible. These have the property that when the latch-enable is asserted, they simply copy their input to their output. They are transparent. When the latch-enable is de-asserted, they hold the value last presented on their input. The consequence of this behavior is that one can't modify a register in one step. Implementing - say - $R0 = $R0+1 is not possible in one clock cycle. You see, in order to store the result in $R0, the latch-enable should be asserted, but if it is, it destroys the previously held value of $R0, which is needed for the addition. An intermediate holding register is needed, which can load and hold the result and be used to write back into $R0 from that in the following cycle. This intermediate register is the one labeled ALU_R on the diagram.

There are a few bits of additional storage that is needed to make the CPU work which I won't detail here. Those are mostly needed for the control circuit to do its job. Instead I'll bring up another topic related to the data-path:

Bit-serial or bit-parallel?

Given the above block diagram, one faces a choice: should we implement all operations in a parallel fashion (such that the buses are 16-bit wide and the ALU just as everything else operates on one word at a time) or should we deal with one bit at a time, shrinking the buses to simple wires and serialize all operation?

Of course, to get to the same compute power, the serial implementation would need a clock rate 16 times as high as the parallel implementation (so 32MHz instead of 2), but the benefit would be a massive reduction in the number of transistors needed, especially in the ALU. Or would it?

In order to make a serial implementation work, the registers would need to turn into shift-registers: they would shift their data out one bit at a time over 16 clock cycles, while consume their results on the other end of the shift register in the same 16 clock cycles. It is a very elegant design and to be frank, I really wanted it to work. There are two problems with it. One, you need a shift register that can work up to 32MHz frequencies. I have not been able to construct such a thing out of discrete transistors. Maybe I'm dumb, maybe I used the wrong kind of transistors or the wrong topology but I couldn't get them past about 10MHz. The second issue is cost: shift registers need D-flops as their storage, they can't be created using latches. This immediately increases the transistor count so high that a bit-serial implementation would not be an obvious win in terms of circuit size over a parallel implementation anymore.

After these realizations, I decided to go back to a bit-parallel implementation. There is some middle-ground though that might be worth exploring: while the registers and the buses are still parallel, the ALU can operate in a bit (or nibble)-serial fashion. This would need some extra multiplexers on the input and a bit- (or nibble-) addressable ALU result (and BUS_A plus BUS_D) registers, but would cut down on ALU complexity. The nibble-serial solution is especially intriguing because the 4x reduction in transistor count can be used to implement a carry-lookahead adder which should give us nice operating frequency gains. As for now, I kept the parallel ALU in the design as it is easier to design the system around, but I might come back to these ideas at a later point.

Control

Let's shift our attention to the control part of things now: given this data-path, the behavior of the memory and the instruction set we want to implement, how should we wiggle the various control signals of the data-path to make the CPU tick?

I've mentioned before that an instruction normally needs four clock cycles to interact with the memory (two read and two write cycles). It also needs to do three calculations:

1. effective address calculation (i.e. compute the address for a [$R0+3]-style reference)
2. execute the instruction
3. increment the instruction pointer

Unfortunately I haven't managed to squeeze all of this into 4 clock cycles. This is due to the following: we need three clock cycles to get to the point where both arguments are available (instruction read, instruction write, data read) and one clock cycle to execute the instruction. This means that the results are only ready to write-back into memory (or registers for that matter, but that potentially could be hidden) in cycle 5. So, for most instructions, we need 5, for SWAP/ISWAP we need 6 cycles. So let's look at what each cycle (I call them phases to make it clear that they belong to executing a single instruction) does in detail:

In phase 0, we load the instruction from memory. This involves putting the address of the instruction on BUS_A (loading the BUS_A register, I call L_BUS_A on the timing diagram), issuing a read operation to the memory and capturing the result in both L_BUS_D and L_INST, that is the data-bus register and the instruction register at the end of the cycle.

However, you have to recall that all of these registers are latches. If they are loaded (their corresponding '_ld' signal is asserted high), they are transparent and their input is the same as their output. In this cycle we load the address-bus register, which means it mirrors its input to its output. Its input is the ALU, which takes a long time to compute a result, yet the output of the address-bus register needs to be stable at the beginning of the cycle. This in turn requires that we repeat the computation (the increment of $PC) twice to ensure that the ALU output is stable for the whole duration of phase 0. This is the reason you see the updating of $PC taking two cycles, both phase 0 and phase 5.

In this phase we also capture the updated $PC in L_ALU_RESULT.

In phase 1, we can start working with the newly arrived instruction. This means starting the effective address computation (this is repeated twice for similar reasons as the $PC update before). We also need to write back the instruction that was just read into core. For this reason, we can't update neither L_BUS_D or L_BUS_A in this cycle. Finally we take the opportunity to update $PC with the updated value from L_ALU_RESULT. Notice that we don't load L_ALU_RESULT at this point. The effective address calculation that occupies the ALU now is purely there to make sure the ALU output is stable at the beginning of phase 2.

In phase 2, we can do the memory read portion of the operand load. We load the effective address into L_BUS_A and issue a read operation (if needed per the instruction of course). Again, the transparent nature of L_BUS_A requires us to keep the ALU continuing the effective address calculation. We also load the read-back value into L_BUS_D so we have it available as the operand as well as for write-back into core. I will skip phase 3 for now as it only plays a part in SWAP/ISWAP operations. All other instructions skip it and move straight to phase 4.

Phase 4 is the execution stage: we received the second operand in phase 2, so we are ready to execute the instruction. The result is captured in L_ALU_RESULT and, if the target is memory - in L_BUS_D.

The last phase of any instruction is phase 5. We do two things here. First, we write back the result to its destination. This could be a register or a memory location. The result itself is captured in both L_ALU_RESULT or L_BUS_D in case we need it, so the write-back can commence. We also prepare the ALU for the two-cycle $PC increment by putting $PC on it's input and '0' on its other input (using the carry-in signal not shown on the block-diagram as the increment input). Of course, if the target of the operation was the $PC itself, we shouldn't increment here, so in those cases the carry-input is held at 0. Notice that it's possible that we both read and write $PC in this cycle (the instructions output is $PC, but we also try to get ready for the next instruction). This is not a problem for the following reason: there isn't a direct path from the ALU output to $PCs input: there is the L_ALU_RESULT register in between and we don't enable that latch for this phase.

For SWAP and ISWAP operations, things commence slightly differently. For one, there is an extra phase (phase 3) inserted into the flow. Second, it needs to write to both memory and the registers and do so without destroying any data along the way. So, what's done is this: In phase 3 we load L_BUS_D (through the ALU) into L_ALU_RESULT. This frees up L_BUS_D such that in phase 4 we can load it (again, though the ALU) with the register operands value. By the end of phase 4, we have the register value in L_BUS_D and the memory value in L_ALU_RESULT. This enables us in phase 5 to issue both the memory and the register write operations.

Could we make it faster?

Maybe. The rough order of operations right now is:

1. Instruction read
2. Instruction write-back
3. Data read
4. Data write-back/execute
5. Data write-back

Here's what could be done to make things go slightly faster:

1. Instruction read / Data write-back to register of previous instruction
2. Instruction write-back / Update of $PC / Effective address calculation
3. Data read / $PC update calculation
4. Execute / Data write-back to memory of previous instruction

The trouble with this setup is we would need to hold on to the results of the previous instruction for much longer. This would need an extra register. It also complicates the updating of $PC: that usually happens twice, in phase 5 and phase 0. Now it somehow would need to happen before phase 0 (as we need the results by then), but can't happen in any other phase as the ALU is busy with something else. It could potentially happen in phase 3, but that requires that we don't repeat the effective address calculation, which in turn would need yet another register to hold on to the result. We would also need to be able to multiplex this register to the input of L_BUS_A, which doesn't have a multiplexer there at this point. So, the total cost is 32 bits of latches and a 16-bit two-way mux. A mux (at the very minimum) is 4 transistors per bit, a latch is 12. So we're looking at around 450 extra transistors. This is for a 20% speed improvement. I voted not to go with this tradeoff, valuing simplicity over performance.

Final words

All of this is checked in to https://github.com/andrastantos/the_d_machine. You can take a look. The implementation is in CPU.PY the test-bench for it is in TB_CPU.PY. These both use my RTL 'language', called Silicon, which I do need to document, but in the meantime you can have it from a different repository: https://github.com/andrastantos/silicon.

The test-bench passes without any problems and although not exhaustive it gives the CPU a pretty decent work-out. The main thing missing is a test for interrupts and resets other then the power-on reset.

In the next installment, I will discuss how to make the various building-blocks out of transistor. I plan to put forth some ideas of how to go about physical implementation, so stay tuned.