Do ALUs perform all/most N operations before running through the multiplexer?

Question

I'm doing some self-study on hardware and currently implementing an ALU. The way I'm designing it is such that I have an N:1 MUX (N inputs yield a single output (16 bit number) based on selector bits). I feed in 2 16-bit numbers with a series of control bits to get my output.

My question is that I have a bunch of gates that execute before they hit the MUX and then the MUX says "based on these control bits I'll output this calculation". Just wondering if it is inefficient to execute all these operations even if they aren't used/outputted.

For example, if I simply want to negate A, the circuit will still perform other arithmetic operations despite not using them at all in the final result. It seems like it would increase the time to get the desired result since you're running through more gates.

Answer 1

Using any modern synthesis tool you can be reasonably sure it'll optimise away any redundancy it possibly can, to the point of sometimes eliminating the entire design if it wasn't tested properly in simulation first.

So, yes this is inefficient; but synth will fix that.

Better to keep what you write simple, clean and clear. 16 ops and a 16:1 MUX fills that bill.

Answer 2

In case all arithmetic operations are performed in the same number of clock cycles, some operations (e.g multiplication) will limit the maximum clock frequency achievable.

I can tell two similar solutions. I will assume multiplication is the bottleneck, as an example.

1. Pipelining bottleneck operations

Say all other operations are performed in one clock cycle, still we can split multiplication into several clock cycles, 2 cycles for example. The CPU needs to stall for one cycle when multiplication is performed. This brings some extra control logic, but roughly doubles the maximum clock frequency.

There are two challenges for this solution. First, pipelining is not easy for some arithmetic operations, however this can be done by the synthesis tool using some retiming (register balancing) commands. Second, the area will increase by about 16 flip-flops.

2. Defining multi-cycle paths

This is a better solution I think. Again extra control logic is required to stall the CPU, but we don't need to pipeline and put additional flip-flops. We should just tell the synthesis tool that multiplication logic is a multi-cycle path. For example, the set_multicycle_path command can be used in Synopsys Design Compiler.

Answer 3

You may be interested in the old TI 74181 4bits ALU which was used in many mincomputers in the 70's:

https://en.wikipedia.org/wiki/74181

A clever arrangement of gates to generate many different operations.

• Additions and subtractions can be combined by conditionally inverting an input and using the carry-in (for two's complement)
• Logical operations can be merged with some arithmetical by removing carry propagation.
• Not / Neg likewise is using the subtraction inverter and a carry-in. Or Inc/Dec using the adder.
• Shift left as an addition... etc.

Depending on the amount of optimisation you want to achieve, you may let a logic synthesis tool do all the optimisations from an high level description, or manually tune it. Sometimes with RISCs some bits in CPU opcodes can be used to control multiplexers or drive constants in the ALU without further decoding.

Answer 4

MUX selecting gates is inefficient. Select from a Karnaugh map gives all 16 possible gates while omitting those gates. Let A vs B drive select lines, while T00,T01,T10,T11 describe the function. Sideways to your prior plan...

Assuming MUX are 4way and offer a twin, you may also omit the adder! Let spare MUX compare magnitudes EQn+1=AvsB(EQ,LT,GT,EQ). Real XOR a Karnaugh mapped XOR against prior EQ for full subtraction. LT=1 GT=0 for A-B, or LT=0 GT=1 for B-A. XORvert B to ADD.

74CBT3253 with 74LVC2G86 on a generic SSOP to DIP28 does every primitive but rotate right. Don't bother to wire a barrel, but store a few tables in ROM: Rotations, Multiply High, Low, Divide, Remainder, etc. You only need enough ALU function to lookup the rest.

If transmission gates are used for the chain, there is no ripple. Series current solves switches prefixed by A vs B. Generate, Propagate, Annihilate are transmission gate drive signals decoded internally by the MUX.