Silicon From Scratch

    The 32-bit ALU Slice

    A single ALU slice handles just one bit — a couple of logic gates, an adder, and a multiplexer that picks which result to keep. Stack thirty-two slices side by side, chain each carry into the next, and you have a complete 32-bit ALU.

    Think you got this already? Skip to Check Yourself
    A one-bit ALU slice: inputs a and b each pass through a 2-to-1 invert mux (controlled by Ainvert and Binvert), then feed an AND gate, an OR gate, and an adder; a 4-to-1 Operation multiplexer selects AND, OR, the adder sum, or a 'less' input as the Result, with a carry-in Cin and carry-out Cout on the adder.

    Ground Zero

    The simple 1-bit ALU from the Logic Gates lesson: inputs a and b feed an AND gate and an OR gate, whose outputs enter a 2-to-1 multiplexer selected by an Operation bit to produce the Result. The same ALU upgraded: each of a and b now passes through a 2-to-1 mux, controlled by Ainvert and Binvert, that selects the input or its inverted version before it reaches the AND and OR gates; the rest of the ALU is unchanged.
    Swap between the simple ALU and its first upgrade.

    Back in the Logic Gates lesson, we built our very first ALU, and it was about as simple as an ALU can get. The two inputs a and b fed an AND gate and an OR gate side by side, and a single 2×1 multiplexer — steered by an operation bit — picked which of those two results to send out as the Result. One control line, two operations, but a real, working ALU nonetheless.

    One of the first upgrades we can make is the ability to invert either input before it reaches the gates — to feed in a or its complement, and likewise for b. Since that's a choice between exactly two things (the input or its inverted version), the most straightforward way to build it is with another 2×1 multiplexer on each input. We run each input through a NOT gate to produce its inverted twin, wire both the original and the inverted signal into a 2×1 mux, and add a control line — Ainvert for the a side and Binvert for the b side — to select which one actually enters the AND and OR gates. Set the control to 0 and the input passes straight through; set it to 1 and its inverted version takes its place.

    Addition Incoming

    The next upgrade is the one that finally lets our ALU do arithmetic: we drop a full adder into every slice. A full adder never works alone, though — each bit's sum depends on the carry rippling in from the bit before it. By putting in the full adder, we have introduced another input, Cin, and another output Cout, to each slice.

    You also may notice that we've added an input to our multiplexer. Instead of a 2×1 multiplexer, it is now a … 3×1 multiplexer?

    As soon as we increase the number of inputs in a multiplexer beyond two, a single control bit is no longer enough. We need at least two control bits to select which path is transmitted to the output. With two bits, we technically have the ability to choose from any one of four inputs, and every additional bit we add to the select signal, the amount of inputs we can choose from increases by a power of 2. For simplicity, in our image we've only drawn the three inputs we actually use; the fourth is left out because it could technically be anything, so long as our operation bits never take on the value 11. A situation like this — where an input's value genuinely doesn't matter — is called a don't care, and is usually written as an x.

    The 1-bit ALU slice with a full adder added: a and b pass through invert muxes, then feed an AND gate, an OR gate, and a full adder with a carry-in Cin and carry-out Cout; a 3-input Operation multiplexer selects among the AND, OR, and adder results to produce the Result.

    The Final Upgrade

    We are now just one operation away from our final ALU slice: the set-less-than, or slt, operation. This operation gives a result of 1 (true) if a is less than b, and 0 (false) otherwise. It is important to note that both results are still a full 32-bit number (i.e. 000…01 and 000…00). We can leverage two neat tricks to simplify the hardware needed to compute it:

    1. If a < b, that would mean that a − b < 0. In other words, to test whether a is less than b, we subtract b from a and compare the result with zero.
    2. Recall that in two's complement, the most significant bit is the sign bit of the 32-bit number. If a − b < 0, our result from subtracting b from a is negative, so Result's most significant bit would be 1. We can route that single bit down to the least significant slice to set our result to 1. And in case you were wondering — if a − b ≥ 0, Result is positive, its most significant bit stays 0, and the least significant bit is never set, leaving 000…00.

    Because of these two tricks, our datapath stays quite simple. We have added an input, less, to each slice, and are now making use of the fourth input of the 4×1 mux. Additionally, we have added an output, set, but only to the most significant slice, where a little extra overflow-detection logic produces it. As you can see, the set signal carries the result of adding the most significant bits together. We'll see in the next lesson how this signal is routed together with the other 31 slices to create our fully functioning ALU.

    The finished ALU slice shown two ways side by side: on the left the generic slice, where a and b pass through their invert muxes into an AND gate, an OR gate, and an adder, and a 4-to-1 Operation mux selects among AND, OR, the adder sum, and a 'less' input to produce the Result with a carry-out Cout; on the right the most-significant slice, which adds overflow-detection logic and a 'set' output that is routed back down to the least-significant slice's 'less' input.
    See the code on GitHub The generic 1-bit slice See the code on GitHub The most-significant slice

    One Last Thing…

    Hand-worked arithmetic comparing -7 with 6 in 4-bit two's complement: on the left, -7 - 6 written as 1001 - 0110; on the right, the same computation as -7 + (-6), i.e. 1001 + 1010 = 10011, whose low four bits read 0011 = 3.

    Before we move on, I thought this would be the perfect time to mention one small detail that we must include in our overflow-detection unit. The way we have organized our hardware, the slt operation works by evaluating a − b and comparing that result to 0. One subtlety to this way of doing things is that there is a chance that we could overflow during that subtraction, and our ALU would report a corrupted, flat-out wrong answer — the overflow quietly poisons our result, flipping its sign so the comparison comes out exactly backwards from the truth.

    For example, suppose we are working with a 4-bit word size in two's complement interpretation. If we wanted to compare −7 (1001) with 6 (0110), we would have to perform −7 − 6, or more simply −7 + (−6). After doing this operation, our intuition tells us that something is off; we cannot store the number −13 in a 4-bit, two's complement number — we can only go as low as −8.

    So what will our ALU do? Well, our ALU will take the lowest 4 bits for its result and interpret our result as a 3! Now, if we think back to what we said earlier, the slt operation will output 1 if and only if a − b < 0, but as we see here 3 < 0… How do we handle this? Think about how you would handle this first, and if you need some help, check out the alu_msb.v file on GitHub.

    Check Yourself

    Suppose you wanted to add the operations NAND and NOR to this ALU slice.
    How could you change the ALU to support it?

    The least-significant-bit ALU slice: a and b each pass through an invert mux (Ainvert, Binvert), then feed an AND gate, an OR gate, and an adder; a 4-to-1 Operation mux selects AND, OR, the adder, or a 'less' input as the Result, with a carry-in Cin and carry-out Cout on the adder.
    Continue to the complete 32-bit ALU