Comprehensive Notes on 32-Bit ALU Design, Overflow Logic, and Single-Cycle MIPS Datapath Architecture

1-Bit and 32-Bit Arithmetic Logic Unit (ALU) Architecture

  • Single-Bit ALU Capabilities:

    • A single-bit ALU slice computes basic logical and arithmetic operations in parallel: AND, OR, addition, subtraction, NOR, NAND, and Set on Less Than (SLTSLT).
    • All operations are computed concurrently by the underlying logic blocks; multiplexers select the desired result based on control inputs.
  • ALU Inputs and Control Lines:

    • AinvertA_{invert}: A 11-bit control signal that inverts operand AA when asserted (11).
    • BinvertB_{invert}: A 11-bit control signal that inverts operand BB when asserted (11).
    • CarryInCarryIn: A 11-bit carry-in signal routed to the adder unit.
    • OperationOperation (opop): A 22-bit selection field that controls the final multiplexer choosing among four inputs:
      • Input 0000: Result of the logical AND stage.
      • Input 0101: Result of the logical OR stage.
      • Input 1010: Result of the full adder stage.
      • Input 1111: Result of the LessLess input stage.
  • Hardware Unification for Subtraction (BnegateB_{negate}):

    • Subtraction is computed as A−B=A+(−B)=A+B‾+1A - B = A + (-B) = A + \overline{B} + 1 using two's complement arithmetic.
    • Performing a subtraction requires setting Binvert=1B_{invert} = 1 and supplying a carry-in of 11 to the least significant bit (ALU0ALU_0).
    • To streamline control hardware, BinvertB_{invert} and the initial CarryInCarryIn at ALU0ALU_0 are combined into a single control line designated BnegateB_{negate}.
    • When Bnegate=1B_{negate} = 1, operand BB is inverted and CarryIn=1CarryIn = 1 is injected at the least significant bit position.
    • When Bnegate=0B_{negate} = 0, operand BB passes through un-inverted and CarryIn=0CarryIn = 0.
  • Derivation of De Morgan Logic Operations:

    • NOR Generation:
      • Setting Ainvert=1A_{invert} = 1, Bnegate=1B_{negate} = 1 (Binvert=1B_{invert} = 1), and selecting the AND operation (Operation=00Operation = 00) computes:A‾⋅B‾\overline{A} \cdot \overline{B}
      • By De Morgan's Law, A‾⋅B‾=A+B‾\overline{A} \cdot \overline{B} = \overline{A + B}, which is the logical NOR function.
      • ALU control setting for NOR: 11001100.
    • NAND Generation:
      • Setting Ainvert=1A_{invert} = 1, Bnegate=1B_{negate} = 1 (Binvert=1B_{invert} = 1), and selecting the OR operation (Operation=01Operation = 01) computes:A‾+B‾\overline{A} + \overline{B}
      • By De Morgan's Law, A‾+B‾=A⋅B‾\overline{A} + \overline{B} = \overline{A \cdot B}, which is the logical NAND function.
      • ALU control setting for NAND: 11011101.
  • Complete 4-Bit ALU Control Line Table:

    • 00000000: AND (Ainvert=0A_{invert} = 0, Bnegate=0B_{negate} = 0, op=00op = 00)
    • 00010001: OR (Ainvert=0A_{invert} = 0, Bnegate=0B_{negate} = 0, op=01op = 01)
    • 00100010: ADD (Ainvert=0A_{invert} = 0, Bnegate=0B_{negate} = 0, op=10op = 10)
    • 01100110: SUBTRACT (Ainvert=0A_{invert} = 0, Bnegate=1B_{negate} = 1, op=10op = 10)
    • 01110111: Set on Less Than / SLT (Ainvert=0A_{invert} = 0, Bnegate=1B_{negate} = 1, op=11op = 11)
    • 11001100: NOR (Ainvert=1A_{invert} = 1, Bnegate=1B_{negate} = 1, op=00op = 00)
    • 11011101: NAND (Ainvert=1A_{invert} = 1, Bnegate=1B_{negate} = 1, op=01op = 01)
  • Ripple Carry ALU Characteristics:

    • The 32-bit ALU is constructed by cascading 32 individual 1-bit ALU slices from ALU0ALU_0 (least significant bit) to ALU31ALU_{31} (most significant bit).
    • The CarryOutCarryOut of stage ii is wired directly to the CarryInCarryIn of stage i+1i+1.
    • Because the carry ripples serially through all 32 stages, the delay accumulates across the full bit width, making this architecture relatively slow compared to advanced carry-lookahead implementations.
    • Comprehensive reference specifications for the 32-bit ALU architecture are provided in Appendix C.

Set on Less Than (SLT) and Status Flag Logic

  • Operation Definition of SLT:

    • The operation evaluates whether operand AA is strictly less than operand BB (A<BA < B).
    • If A<BA < B, the resulting 32-bit output must be 00000000 00000000 00000000 00000001200000000\,00000000\,00000000\,00000001_2 (11).
    • If A≥BA \ge B, the resulting 32-bit output must be 00000000 00000000 00000000 00000000200000000\,00000000\,00000000\,00000000_2 (00).
  • Mathematical Evaluation via Subtraction:

    • Evaluating A<BA < B is mathematically equivalent to evaluating whether A−B<0A - B < 0.
    • In two's complement binary representation, a number is negative if and only if its sign bit (most significant bit, position 3131) is 11.
    • Subtracting BB from AA produces a sign bit of 11 at the adder output of ALU31ALU_{31} when the difference is negative.
  • Hardware Implementation and Interconnect:

    • The adder output of the most significant bit (ALU31ALU_{31}) is defined as the SetSet signal.
    • The SetSet signal is routed back to the LessLess input of ALU0ALU_0 (multiplexer input 33 / 1111).
    • For all other bit positions (ALU1ALU_1 through ALU31ALU_{31}), the LessLess input is tied to a constant logical 00.
    • When the operation code is set to 01110111 (SLT):
      • If A<BA < B, the sign bit from ALU31ALU_{31} is 11, which is passed to Result0Result_0. All other outputs (Result1Result_1 to Result31Result_{31}) output 00, generating a 32-bit value of 11.
      • If A≥BA \ge B, the sign bit from ALU31ALU_{31} is 00, which is passed to Result0Result_0. All bits output 00, generating a 32-bit value of 00.
  • Zero Flag Detection:

    • The ALU provides a 1-bit status flag, ZeroZero, to detect when all 32 bits of the output are 00, which is essential for evaluating branch instructions such as branch on equal (beqbeq) and branch on not equal (bnebne).
    • Zero output condition:Zero=1  ⟺  (Result0=0∧Result1=0∧⋯∧Result31=0)\text{Zero} = 1 \iff (Result_0 = 0 \land Result_1 = 0 \land \dots \land Result_{31} = 0)
    • Expressed using Boolean logic:Zero=Result0‾⋅Result1‾⋅Result2‾…Result31‾=Result0+Result1+Result2+⋯+Result31‾\text{Zero} = \overline{Result_0} \cdot \overline{Result_1} \cdot \overline{Result_2} \dots \overline{Result_{31}} = \overline{Result_0 + Result_1 + Result_2 + \dots + Result_{31}}
    • Hardware implementation: A 32-input NOR gate that evaluates all 32 output lines of the ALU. The flag outputs 11 when every result bit is 00, and outputs 00 otherwise.

Signed Arithmetic Overflow Detection

  • Scope and Exclusions:

    • Arithmetic overflow occurs when the result of a signed arithmetic operation exceeds the finite representational capacity of a 32-bit two's complement register.
    • Overflow can only occur during addition and subtraction operations; logical operations (AND, OR, NAND, NOR) and comparison operations (SLT) can never produce an overflow.
  • Overflow Conditions for Signed Arithmetic:

    • Addition (A+BA + B):
      • Adding two positive numbers (A≥0A \ge 0, B≥0B \ge 0) yields a negative result (Result<0Result < 0).
      • Adding two negative numbers (A<0A < 0, B<0B < 0) yields a non-negative result (Result≥0Result \ge 0).
      • Adding numbers of opposite signs cannot cause an overflow.
    • Subtraction (A−BA - B):
      • Subtracting a negative number from a non-negative number (A≥0A \ge 0, B<0B < 0) yields a negative result (Result<0Result < 0).
      • Subtracting a non-negative number from a negative number (A<0A < 0, B≥0B \ge 0) yields a non-negative result (Result≥0Result \ge 0).
      • Subtracting numbers of the same sign cannot cause an overflow.
  • Testing Sign Bits (A31A_{31}, B31B_{31}, Result31Result_{31}):

    • A sign bit of 00 represents a non-negative number; a sign bit of 11 represents a negative number.
    • The overflow circuit inspects the four operation control bits, the sign bits of both inputs (A31A_{31}, B31B_{31}), and the sign bit of the output (Result31Result_{31}).
  • Truth Table for Overflow Assertion (Overflow=1Overflow = 1):

    • Row 1 (Addition):
      • Control bits (Ainvert,Bnegate,op1,op0A_{invert}, B_{negate}, op_1, op_0): 00100010
      • Input A31A_{31}: 00
      • Input B31B_{31}: 00
      • Output Result31Result_{31}: 11
      • OverflowOverflow: 11
    • Row 2 (Addition):
      • Control bits (Ainvert,Bnegate,op1,op0A_{invert}, B_{negate}, op_1, op_0): 00100010
      • Input A31A_{31}: 11
      • Input B31B_{31}: 11
      • Output Result31Result_{31}: 00
      • OverflowOverflow: 11
    • Row 3 (Subtraction):
      • Control bits (Ainvert,Bnegate,op1,op0A_{invert}, B_{negate}, op_1, op_0): 01100110
      • Input A31A_{31}: 00
      • Input B31B_{31}: 11
      • Output Result31Result_{31}: 11
      • OverflowOverflow: 11
    • Row 4 (Subtraction):
      • Control bits (Ainvert,Bnegate,op1,op0A_{invert}, B_{negate}, op_1, op_0): 01100110
      • Input A31A_{31}: 11
      • Input B31B_{31}: 00
      • Output Result31Result_{31}: 00
      • OverflowOverflow: 11
  • Sum of Products (SOP) Implementation:

    • An SOP Boolean expression is derived directly from these four specific conditions.
    • For all other input combinations not specified in the four truth table rows, the output OverflowOverflow is defined as 00.

CPU Performance and Architecture Principles

  • CPU Performance Equation:

    • Total CPU execution time is dictated by three primary factors:CPU Execution Time=Instruction Count×CPI×Clock Cycle Time\text{CPU Execution Time} = \text{Instruction Count} \times \text{CPI} \times \text{Clock Cycle Time}
    • Alternatively expressed as:CPU Execution Time=Instruction Count×CPIClock Rate\text{CPU Execution Time} = \frac{\text{Instruction Count} \times \text{CPI}}{\text{Clock Rate}}
  • Determinants of Execution Parameters:

    • Instruction Count: Controlled by the Instruction Set Architecture (ISA) and the efficiency of the compiler. Optimizations applied during compilation (e.g., in Quick Sort or Bubble Sort routines) significantly adjust the instruction count.
    • Clock Cycles Per Instruction (CPI): Dictated by the underlying hardware architecture and implementation of the datapath.
    • Clock Cycle Time / Clock Rate: Determined by the physical circuit design, semiconductor technology, and the critical path delay of the datapath.
  • MIPS Core Instruction Subset (9 Target Instructions):

    • To illustrate datapath and control design without implementing the full 100+ instructions of the MIPS architecture, a representative 9-instruction subset is selected:
      • Memory Reference Instructions: Load Word (lwlw), Store Word (swsw).
      • Arithmetic/Logical Instructions: Add (addadd), Subtract (subsub), Logical AND (andand), Logical OR (oror), Set on Less Than (sltslt).
      • Control Transfer Instructions: Branch on Equal (beqbeq), Jump (jj).
    • Multiplication can be realized as repeated addition, and division can be realized as repeated subtraction.
    • Floating-point operations are excluded; only integer arithmetic is handled.
  • Industry and Embedded Context:

    • Simplified instruction sets containing 12 to 24 instructions are widely used in specialized embedded microprocessors, such as those governing automotive fuel injection systems (monitoring speed, acceleration, and fuel delivery) and robotics controllers.
    • Embedded microprocessors constitute the largest volume of processor deployments in industry, far outnumbering general-purpose desktop computing processors.

Datapath Building Blocks and Execution Phases

  • Instruction Execution Phases:

    • Instruction Fetch: Retrieve the instruction from instruction memory (instruction cache) using the current address stored in the Program Counter (PCPC).
    • Instruction Decode & Register File Read: Parse the instruction fields to extract opcode and register specifiers; read source registers from the Register File.
    • Execution / ALU Operation:
      • Arithmetic/logical instructions compute the designated operation using the ALU.
      • Memory reference instructions (lwlw, swsw) compute the effective memory address by adding the base register contents to the sign-extended offset.
      • Branch instructions (beqbeq) subtract the two register values to test equality (Zero=1Zero = 1) and simultaneously compute the branch target address.
    • Memory Access: Access data memory (data cache) to read data (lwlw) or write data (swsw).
    • Register Write-Back: Write computed ALU results or memory-loaded data into the destination register.
    • Program Counter Update: Advance the PCPC to the next sequential address (PC+4PC + 4) or update it to the target branch/jump address.
  • Byte Addressability and PCPC Incrementing:

    • Memory is byte-addressable, meaning each individual byte has a unique address.
    • MIPS instructions are 32 bits (4 bytes4\text{ bytes}) in width.
    • To step to the next sequential instruction, the program counter must be incremented by 44:PCnext=PC+4PC_{\text{next}} = PC + 4
  • Hardware Implementation of the Sign-Extension Unit:

    • Converts a 16-bit two's complement offset (x0x_0 through x15x_{15}) into a 32-bit two's complement value (y0y_0 through y31y_{31}) to feed the 32-bit ALU.
    • Hardware structure:
      • Lower bits are connected straight through: yi=xiy_i = x_i for i=0,1,…,15i = 0, 1, \dots, 15.
      • The sign bit (x15x_{15}) is replicated across all higher-order bits: yj=x15y_j = x_{15} for all j=16,17,…,31j = 16, 17, \dots, 31.
    • This direct wiring maintains identical numeric value in two's complement representation.
  • Hardware Implementation of the Shift-Left-2 Unit:

    • Branch offsets in MIPS specify displacement in words, but the PCPC operates on byte addresses. Word displacement is converted to byte displacement by multiplying by 44, implemented as a logical shift left by 2 bit positions.
    • Hardware structure (32-bit input x0…x31x_0 \dots x_{31}, 32-bit output y0…y31y_0 \dots y_{31}):
      • The lowest two output bits are tied to ground (logical 00): y0=0y_0 = 0, y1=0y_1 = 0.
      • The inputs are shifted left by two positions: yk+2=xky_{k+2} = x_k for k=0,1,…,29k = 0, 1, \dots, 29.
      • The upper two input bits (x30,x31x_{30}, x_{31}) are discarded.
    • Because word sizes and shift parameters are fixed in MIPS, both sign extension and shifting are achieved purely through hardwired routing without logic gates.

Single-Cycle Datapath Integration

  • Single-Cycle Execution Constraint:

    • In a single-cycle implementation, each instruction must complete all its processing steps within one clock cycle.
    • A functional hardware element cannot perform more than one operation within the same clock cycle.
  • Separation of Instruction and Data Memory:

    • During a single clock cycle, an instruction must be fetched from memory, and a load or store instruction must simultaneously access data memory.
    • A single memory unit cannot support simultaneous read and write operations on distinct addresses in the same cycle.
    • The datapath requires separate memories: an Instruction Memory (Instruction Cache) and a Data Memory (Data Cache).
  • Role of Multiplexers (MUXes):

    • Independent signal lines cannot simply be tied together in hardware; multiplexers must be inserted at junction points to select between alternate data sources based on control signals.
    • ALU Source Multiplexer (ALUSrcALUSrc):
      • Selects between the second register operand (for R-type instructions) and the 32-bit sign-extended offset (for lwlw and swsw).
    • Memory-to-Register Multiplexer (MemtoRegMemtoReg):
      • Selects between the output of the ALU (for R-type instructions) and the output of the Data Memory (for lwlw) to be written back into the Register File.
    • Next PC Multiplexer:
      • Selects between sequential execution (PC+4PC + 4) and the calculated branch target address (PC+4+(SignExtendedOffset≪2)PC + 4 + (\text{SignExtendedOffset} \ll 2)).
  • Datapath Interconnections for Combined R-Type and Load/Store Execution:

    • Instruction Memory outputs the 32-bit instruction.
    • Register File receives read register specifiers and reads source data 1 and source data 2.
    • The ALUSrcALUSrc multiplexer directs either source data 2 or the sign-extended offset into the second ALU input.
    • The ALU computes the arithmetic result or the effective memory address (Base Address+Offset\text{Base Address} + \text{Offset}).
    • Data Memory uses the ALU output as an address; for swsw, it writes source data 2 to that address; for lwlw, it reads data from that address.
    • The MemtoRegMemtoReg multiplexer chooses the data source, which is routed to the write data port of the Register File and written to the destination register when RegWriteRegWrite is asserted.

Questions & Discussion

  • Question: Why can the CarryOutCarryOut of the final ALU slice (ALU31ALU_{31}) not be used directly as the overflow bit?

    • Response: Using the final CarryOutCarryOut directly only detects overflow for unsigned arithmetic. For signed addition and subtraction, overflow must be evaluated based on the sign bits of the operands (A31A_{31}, B31B_{31}) and the sign bit of the result (Result31Result_{31}).
  • Question: Is SRAM or cache memory considered an internal subset of the CPU?

    • Response: Cache memory is physically integrated as a component within the CPU.
  • Question: Does replicating the sign bit (x15x_{15}) across the upper bits change the underlying value of the number?

    • Response: In two's complement representation, replicating the sign bit to higher-order positions does not alter the numeric value; the value remains strictly identical.
  • Question: What control line combination generates a NAND operation?

    • Response: Setting the control lines to 11011101 generates a NAND operation (Ainvert=1A_{invert} = 1, Bnegate=1B_{negate} = 1, Operation=01Operation = 01).