2.1 ALU Design (Circuits)

1. Overview of ALU and Datapath Organization

Within the CPU, the Arithmetic Logic Unit (ALU) executes all arithmetic and logical microoperations on data. The ALU does not store data itself; rather, it is connected to a shared internal CPU bus. Operands are routed from the internal register file (or temporary registers) into the ALU inputs, and the resulting computation is placed on the bus to be written back to a destination register.

2. Design of Arithmetic Circuit

A multi-bit arithmetic circuit is constructed by cascading $N$ identical 1-bit stages. Each stage consists of a **Full Adder (FA)** and an input multiplexer that controls the second operand.

Let $A_i$ and $B_i$ be the $i$-th bits of the two input words, and $S_1, S_0$ be the operation select lines. The Full Adder receives three inputs:

• The first input, $X_i$, is wired directly to the operand bit $A_i$: $$X_i = A_i$$
• The second input, $Y_i$, is controlled by the multiplexer select lines $S_1, S_0$ to route different variations of the operand $B_i$:
  • When $S_1 S_0 = 00$, $Y_i = B_i$ (yielding Addition).
  • When $S_1 S_0 = 01$, $Y_i = \bar{B}_i$ (yielding Subtraction).
  • When $S_1 S_0 = 10$, $Y_i = 0$ (yielding Transfer or Increment).
  • When $S_1 S_0 = 11$, $Y_i = 1$ (yielding Decrement).
• The third input is the Carry-In ($C_i$) from the previous stage.

2.1 Deriving the $Y_i$ Boolean Equation

To construct the input multiplexer stage using standard logic gates, we map the MUX output $Y_i$ in a truth table and derive its Boolean equation: $$Y_i = B_i S_0 + \bar{B}_i S_1$$ This simple logic slice (implemented with two AND gates, one OR gate, and one NOT gate per bit stage) routes the correct operand value to the adder.

  A_i ─────────────────────────────► [ X_i ]
                                     │
  S_1 ───────┐                       │
             ├──► [ Y_i Multiplexer ]├──► [ Full Adder ] ──► Sum (D_i)
  S_0 ───────┤                       │                  
  B_i ───────┘                       │                  
                                     │
  C_i ──────────────────────────────►[ C_in ] ──► Carry-Out (C_i+1)
                                

3. Design of Logic Circuit

A logic circuit executes bitwise operations (AND, OR, XOR, NOT) on the input words $A_i$ and $B_i$. Because logic operations do not generate carries, no Full Adders are required.

A 1-bit logic stage consists of four gates generating the four basic operations in parallel, connected to a $4 \times 1$ multiplexer. The select lines $S_1, S_0$ select the active output:

• $S_1 S_0 = 00 \Rightarrow \text{AND}$ ($A_i \wedge B_i$)
• $S_1 S_0 = 01 \Rightarrow \text{OR}$ ($A_i \vee B_i$)
• $S_1 S_0 = 10 \Rightarrow \text{XOR}$ ($A_i \oplus B_i$)
• $S_1 S_0 = 11 \Rightarrow \text{NOT}$ ($\bar{A}_i$)

During logic operations, the ALU disables all carry propagation lines to prevent arithmetic carry interference.

4. Consolidated Arithmetic Logic Shift Unit (ALSU)

Rather than deploying separate arithmetic, logic, and shifter units, computer designers combine these stages into a single, consolidated Arithmetic Logic Shift Unit (ALSU).

A consolidated ALSU stage uses an output multiplexer to select among the arithmetic sum ($D_i$), the logic output ($H_i$), or shift-left/shift-right lines. A typical 1-bit ALSU stage uses 3 select lines ($S_2, S_1, S_0$):

• $S_2 = 0 \Rightarrow$ Selects the Arithmetic Circuit output.
• $S_2 = 1, S_1 = 0 \Rightarrow$ Selects the Logic Circuit output.
• $S_2 = 1, S_1 = 1, S_0 = 0 \Rightarrow$ Selects Shift Right (shf-rt).
• $S_2 = 1, S_1 = 1, S_0 = 1 \Rightarrow$ Selects Shift Left (shf-lt).

5. Timing Delays: Ripple Carry vs. Carry Lookahead Adders

The speed of the ALU is heavily limited by the carry propagation delay of its adder circuit.

5.1 Ripple Carry Adder (RCA)

In an $N$-bit Ripple Carry Adder, the carry-out $C_{i+1}$ of stage $i$ must propagate to the carry-in of stage $i+1$. Let $t_{gate}$ be the propagation delay of a single logic gate:

• Each Full Adder requires 2 gate delays to generate $C_{out}$ from $C_{in}$.
• For an $N$-bit adder, the total carry propagation delay is:
  $$t_{RCA} = 2N \times t_{gate}$$
• For $N = 32$ bits, the delay is $64\ t_{gate}$, creating a severe speed bottleneck.

5.2 Carry Lookahead Adder (CLA)

To eliminate this serial carry delay, a Carry Lookahead Adder computes the carry signals for all stages simultaneously. It defines two terms for each stage:

• **Carry Generate ($G_i$)**: The stage generates a carry if both inputs are $1$: $$G_i = A_i B_i$$
• **Carry Propagate ($P_i$)**: The stage propagates a carry if at least one input is $1$: $$P_i = A_i + B_i$$

Using these terms, the carries are calculated in parallel:

Because all $G_i$ and $P_i$ are generated in 1 gate delay, and the carries are generated through a two-level sum-of-products gate array, the total carry propagation delay is reduced to: $$t_{CLA} = 3 \times t_{gate}$$ Regardless of $N$, the CLA computes carries in $O(1)$ constant time. However, as $N$ grows beyond 4, the fan-in (number of inputs per gate) of the logic gates becomes physically unmanageable, requiring hierarchical CLA groupings (e.g. 4-bit CLA blocks).

6. Worked Examples & Numerical Problems

7. Core Comparison Tables

Table 2.1.3: 4-Bit Arithmetic Unit Operations

8. Common Mistakes Students Make

9. Assessment Bank

9.1 Multiple Choice Questions

9.2 Short Answer Questions

1. Trace why the carry propagation of Ripple Carry Adders creates an execution bottleneck. State the complexity class.
2. Derive the Boolean logic equation for the input multiplexer stage ($Y_i$) of the ALU.
3. Why do logic operations (AND, OR) ignore the carry-in ($C_{in}$) line?

9.3 Long Answer / Exam Questions

1. Design a 1-bit ALU slice that performs Addition, Subtraction, AND, and XOR operations. Sketch the logic diagram showing the Full Adder, input logic gates, multiplexers, and select line routing.
2. Explain the working of a Carry Lookahead Adder. Derive the carry equations for $C_1, C_2, C_3,$ and $C_4$ using the generate ($G_i$) and propagate ($P_i$) terms. Discuss the physical fan-in limitations that restrict CLA scaling beyond 4 bits.

9.4 Viva Voce Questions

1. "What is gate fan-in, and how does it limit the speed of Carry Lookahead Adders?" Model Answer: Fan-in is the number of input lines connected to a single logic gate. As the CLA size ($N$) increases, the Boolean equations for higher-order carries require gates with more inputs. Physically, adding inputs to a gate increases transistor capacitance and resistance, slowing down the gate and negating the CLA's speed advantages.
2. "How does a consolidated ALSU handle logical shift operations?" Model Answer: The ALSU contains multiplexer pathways connected to adjacent bits (bit $i-1$ for shift left, bit $i+1$ for shift right). When shift select lines are activated, the output multiplexer routes the shifted inputs directly to the bus, bypassing the arithmetic adder.