Introduction

Another article about my Disintegrated Machine project, which will be (the Gods of electricity helping) a 16-bit computer, built from discrete transistors. In the previous chapters, I’ve talked about individual gates and register designs, detailing how I intend to translate a logic design into a bag of transistors.

In this installment I will talk about how the ALU of the process will work and how I intend to go about implementing it. This is a long topic, so strap in and let’s get going!

ALU for a processor: more than an adder

My processor has a complex ALU tasked with calculating all manner of results. The supported set of operations are all that are needed by the instruction set of course but there are a few extras. The ALU – as most in the wild – has two inputs and a single output and a sortie of control signals. The two main inputs are called ‘A’ and ‘B’ and the result is called ‘S’. These are of course 16-bits wide each. One of the important control signals is the single-bit ‘carry-in’ signal. I called it C_IN. The required operations are:

1. S = A + B + C_IN
2. S = A – B
3. S = B – A
4. S = A & B
5. S = A | B
6. S = A ^ B
7. S = ROL(A)
8. S = ROR(B)

As we will see adding C_IN to the sum comes for free.

A single-bit full adder is usually implemented as follows (this is from the Wikipedia page on adders, which I highly recommend if you are not familiar with the subject):

If one wants to build a multi-bit adder, the above logic can be daisy-chained: their C_OUT signals connected to the C_IN input of the following bit. The rest if their inputs and outputs are in parallel:

This is pretty much the simplest adder one can build, but it’s the slowest as well: the carry has to ‘ripple’ through the whole chain (16 instances in our case). Thus the name: a ripple-carry adder.

Of course the ALU I need will have to do a lot more than simple addition, but those functions don’t change the fact that the latency will be determined (and dominated) by the delay of this carry chain.

If this architecture is too slow, there are other, quicker methods, such as the carry-lookahead adder:

This partitions the adders a little differently (only the first AND gate of the carry generation is included in the blue blocks) and the carries for all (4) bits are generated in parallel. The logic in the purple block is rather large, but much faster then the ripple-carry approach.

The question of time

But how much time do we have? The cycle time of the processor at 2MHz of course is 500ns. We certainly need to be able to get through the carry chain in that much time. However, if you look at the block diagram of the processor, you’ll see that that’s not enough:

We need to reserve some time to get through the ALU_A and ALU_B muxes and wind our way to the result registers (ALU_R/BUS_A/BUS_D) in time to capture the result. Furthermore – something that’s not shown here – is that the ALU results feed into the decision-making process of the control path for predicate instructions. We have to be able to get through all of that as well.

Overall, I budgeted 400ns for the ALU and 100ns for all the rest. Can we do that? If we have to get through the ripple-carry chain in that much time (which is very optimistic, there’s other things inside the ALU then the carry-chain), that would leave only 25ns per stage. That is not out of the realms of possibility, but certainly tight.

There’s just one way to know, let’s get cranking!

Making the ALU

Previously, I’ve introduced the basic circuit elements, I’m going to use: inverters, NAND and NOR gates, even an AND-OR-INVERTER (AOI) gate. There was no XOR gate there though. Let’s correct that oversight! One can create XOR gates in many many ways, my approach is the following (I’m using the CircuitVerse online simulator for these examples):

The right-most two gates can be merged into an AOI instance, saving some transistors. A transistorized implementation looks like this:

That’s eight transistors for a measly XOR gate… At any rate, this is the best I could come up with.

Using this XOR structure we can implement our full adder:

This is the very same circuit as the you’ve seen on the top, just the XOR gates replaced by my contraption. Notice how two AND gates are actually redundant and could be removed. I didn’t do that (at least at the moment) for reasons that we will come to shortly.

An ALU is more than just an adder. For one, it needs to support subtraction as well. The normal way of implementing that comes from the following realizations:

First, A-B = A+(-B). So one can still just do addition if we can support negation. Second, -B=~B+1 in two’s complement encoding (here the ‘~’ sign means bit-wise inversion as in C or Python). Putting this together: A-B = A + ~B + 1. The ‘1’ can be added on the ‘C_IN’ input, so really what we need is to be able to invert the B input on command. An XOR gate on each input bit can do that. Of course we need to support B-A as well, which, through the same logic means we need XOR gates on the A input as well:

We also need to support logical operations. For that, we need to do two things: we need to interrupt the carry-chain so we can control whether C_IN is ‘1’ or ‘0’ for all the bit-cells of the ALU. Second, we need to put enough enable signals into this mess to get an effective AND, OR and XOR logic out of it. This needs a few more control lines:

This is getting complicated, so let me give you a decoder ring:

Here you see why I didn’t merge the AND gates before: the bottom one needed an enable signal.

This is getting there, but we need to also support ROL and ROR operations. Those are just swapping bits around. The existing logic is not terribly useful for that purpose. Instead, we can simply implement a 3-way multiplexer on the output to select between those rotate operations or one of the ALU functions above:

This is a single bit of my ALU. There are sixteen of these that make the whole thing up.

There is one NAND2 gate that can be removed as its functionality is duplicated. However, that only works for a ripple-carry implementation. So I’m not going to do that right away. Instead, I will split the logic in two: one responsible for generating the ‘S’ and one responsible for generating ‘C_OUT’:

The two extra signals that need to go between the two blocks are called ‘P’ for ‘propagate’ and ‘G’ for ‘generate’. They refer to how carry is handled: whether this digit generates a carry or propagates one from the previous bit.

With all that, we can look at the eye-chart of the transistorized version of the circuit:

Signals occasionally named slightly differently here, hopefully that’s not too confusing. I have to stress again: this is just one bit. You have to imagine this logic replicated sixteen times to have an idea of the full ALU.

Still, copy-paste is a friend, so one can relatively quickly wire together the whole ALU, fire up a simulation and have a coffee.

Results

Actually, before we get into the results, this is the point where I transitioned from ltspice to KiCAD (and ngspice). The reason for this is that if I go through the trouble of creating all this circuitry, I want to be able to use that for layout work and not to go through the error-prone process of copying the design between the tools.

KiCAD doesn’t support temperature ramps, which was the reasons for sticking with ltspice in the past, but that’s OK. From those investigations, I know that the -25C case is the slowest. So, I can simply set the simulator to that temperature and hit run. So, drum-roll, please, I present you the result:

Another eye-chart… What you see here is me trying to add 0, 0xffff and 1 (this later being C_IN) together. This is the worst-case as far as the carry chain is concerned: the carry has to ripple through every bit. That’s what the colorful rising edges show: each carry-out signal from each bit. The two cursors are set at the beginning – where C_IN changes from 0 to 1 and the last transition, which is V and Z flags change. Oh yeah, we have to talk about the flags. But first, the numbers: this whole thing takes 330ns.

So, success? If I believe these numbers, yes: the ripple-carry ALU neatly fits within the 400ns allocated time, with some time to spare.

Flags

Now, let’s get back to the flags for a moment: these are the signals that the control logic will use to decide if a predicate is satisfied or not. To implement the various magnitude tests, we need the following flags:

• C – which stands for carry
• S – which stands for sign
• Z – which stands for zero
• V – which stands for overflow

Instead of showing you circuit diagrams, I will put here the logic that is in my RTL to generate these flags:

As the comment says, I cheated a little and the V flag is only valid for A – B. However, the flags are not exposed to SW (unlike other CPUs, such as the 6502, the Z80 or even the x86). The only case where this flag is important is for predicate instructions, and they only use the A – B operation.

I’m sure you can visualize the implementation for these after going through all the circuit diagrams together. One thing to note is that o_out here is a 16-bit bus, so the Z flag generation is a 16-input OR gate.

Summary

So how big is this thing? It’s 377 transistors, 234 diodes and about 700 resistors. Not … small. But also, not that big. If I were to buy a whole reel of transistors, that’s 3000 pieces. I would also need PNP and NPN variants, so I would end up with 6000 transistors. This is about 6% of that pile.

I’m also pleasantly surprised how fast the logic is. I didn’t expect the ripple-carry solution to be sufficiently fast to be honest. I’m still thinking in the back of my mind that this is too good to be true. At the same time, if I believed the simulator before, I have no basis to start doubting it now.

Finally, power consumption: this monster consumes on the order of 6A from the 3.3V supply. That’s about 20W. Not exactly low-power. But roughly inline with expectations.

Where will the story go from here? I’m not quite sure. This was the biggest open question in my mind. Now that I have the ALU under control, I think I will look into tools to automatically convert my RTL into a transistor netlist. That should allow me to verify the logic at much higher level and at the same time guarantee that the transistor implementation matches.

The project – as always – is checked in to GitHUB, if you want to check it out.

I’m also adding the CircuitVerse project here, so you can play around with the logic circuits yourselves.