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 ().
- All operations are computed concurrently by the underlying logic blocks; multiplexers select the desired result based on control inputs.
ALU Inputs and Control Lines:
- : A -bit control signal that inverts operand when asserted ().
- : A -bit control signal that inverts operand when asserted ().
- : A -bit carry-in signal routed to the adder unit.
- (): A -bit selection field that controls the final multiplexer choosing among four inputs:
- Input : Result of the logical AND stage.
- Input : Result of the logical OR stage.
- Input : Result of the full adder stage.
- Input : Result of the input stage.
Hardware Unification for Subtraction ():
- Subtraction is computed as using two's complement arithmetic.
- Performing a subtraction requires setting and supplying a carry-in of to the least significant bit ().
- To streamline control hardware, and the initial at are combined into a single control line designated .
- When , operand is inverted and is injected at the least significant bit position.
- When , operand passes through un-inverted and .
Derivation of De Morgan Logic Operations:
- NOR Generation:
- Setting , (), and selecting the AND operation () computes:
- By De Morgan's Law, , which is the logical NOR function.
- ALU control setting for NOR: .
- NAND Generation:
- Setting , (), and selecting the OR operation () computes:
- By De Morgan's Law, , which is the logical NAND function.
- ALU control setting for NAND: .
- NOR Generation:
Complete 4-Bit ALU Control Line Table:
- : AND (, , )
- : OR (, , )
- : ADD (, , )
- : SUBTRACT (, , )
- : Set on Less Than / SLT (, , )
- : NOR (, , )
- : NAND (, , )
Ripple Carry ALU Characteristics:
- The 32-bit ALU is constructed by cascading 32 individual 1-bit ALU slices from (least significant bit) to (most significant bit).
- The of stage is wired directly to the of stage .
- 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 is strictly less than operand ().
- If , the resulting 32-bit output must be ().
- If , the resulting 32-bit output must be ().
Mathematical Evaluation via Subtraction:
- Evaluating is mathematically equivalent to evaluating whether .
- In two's complement binary representation, a number is negative if and only if its sign bit (most significant bit, position ) is .
- Subtracting from produces a sign bit of at the adder output of when the difference is negative.
Hardware Implementation and Interconnect:
- The adder output of the most significant bit () is defined as the signal.
- The signal is routed back to the input of (multiplexer input / ).
- For all other bit positions ( through ), the input is tied to a constant logical .
- When the operation code is set to (SLT):
- If , the sign bit from is , which is passed to . All other outputs ( to ) output , generating a 32-bit value of .
- If , the sign bit from is , which is passed to . All bits output , generating a 32-bit value of .
Zero Flag Detection:
- The ALU provides a 1-bit status flag, , to detect when all 32 bits of the output are , which is essential for evaluating branch instructions such as branch on equal () and branch on not equal ().
- Zero output condition:
- Expressed using Boolean logic:
- Hardware implementation: A 32-input NOR gate that evaluates all 32 output lines of the ALU. The flag outputs when every result bit is , and outputs 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 ():
- Adding two positive numbers (, ) yields a negative result ().
- Adding two negative numbers (, ) yields a non-negative result ().
- Adding numbers of opposite signs cannot cause an overflow.
- Subtraction ():
- Subtracting a negative number from a non-negative number (, ) yields a negative result ().
- Subtracting a non-negative number from a negative number (, ) yields a non-negative result ().
- Subtracting numbers of the same sign cannot cause an overflow.
- Addition ():
Testing Sign Bits (, , ):
- A sign bit of represents a non-negative number; a sign bit of represents a negative number.
- The overflow circuit inspects the four operation control bits, the sign bits of both inputs (, ), and the sign bit of the output ().
Truth Table for Overflow Assertion ():
- Row 1 (Addition):
- Control bits ():
- Input :
- Input :
- Output :
- :
- Row 2 (Addition):
- Control bits ():
- Input :
- Input :
- Output :
- :
- Row 3 (Subtraction):
- Control bits ():
- Input :
- Input :
- Output :
- :
- Row 4 (Subtraction):
- Control bits ():
- Input :
- Input :
- Output :
- :
- Row 1 (Addition):
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 is defined as .
CPU Performance and Architecture Principles
CPU Performance Equation:
- Total CPU execution time is dictated by three primary factors:
- Alternatively expressed as:
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 (), Store Word ().
- Arithmetic/Logical Instructions: Add (), Subtract (), Logical AND (), Logical OR (), Set on Less Than ().
- Control Transfer Instructions: Branch on Equal (), Jump ().
- 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.
- To illustrate datapath and control design without implementing the full 100+ instructions of the MIPS architecture, a representative 9-instruction subset is selected:
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 ().
- 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 (, ) compute the effective memory address by adding the base register contents to the sign-extended offset.
- Branch instructions () subtract the two register values to test equality () and simultaneously compute the branch target address.
- Memory Access: Access data memory (data cache) to read data () or write data ().
- Register Write-Back: Write computed ALU results or memory-loaded data into the destination register.
- Program Counter Update: Advance the to the next sequential address () or update it to the target branch/jump address.
Byte Addressability and Incrementing:
- Memory is byte-addressable, meaning each individual byte has a unique address.
- MIPS instructions are 32 bits () in width.
- To step to the next sequential instruction, the program counter must be incremented by :
Hardware Implementation of the Sign-Extension Unit:
- Converts a 16-bit two's complement offset ( through ) into a 32-bit two's complement value ( through ) to feed the 32-bit ALU.
- Hardware structure:
- Lower bits are connected straight through: for .
- The sign bit () is replicated across all higher-order bits: for all .
- 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 operates on byte addresses. Word displacement is converted to byte displacement by multiplying by , implemented as a logical shift left by 2 bit positions.
- Hardware structure (32-bit input , 32-bit output ):
- The lowest two output bits are tied to ground (logical ): , .
- The inputs are shifted left by two positions: for .
- The upper two input bits () 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 ():
- Selects between the second register operand (for R-type instructions) and the 32-bit sign-extended offset (for and ).
- Memory-to-Register Multiplexer ():
- Selects between the output of the ALU (for R-type instructions) and the output of the Data Memory (for ) to be written back into the Register File.
- Next PC Multiplexer:
- Selects between sequential execution () and the calculated branch target address ().
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 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 ().
- Data Memory uses the ALU output as an address; for , it writes source data 2 to that address; for , it reads data from that address.
- The multiplexer chooses the data source, which is routed to the write data port of the Register File and written to the destination register when is asserted.
Questions & Discussion
Question: Why can the of the final ALU slice () not be used directly as the overflow bit?
- Response: Using the final directly only detects overflow for unsigned arithmetic. For signed addition and subtraction, overflow must be evaluated based on the sign bits of the operands (, ) and the sign bit of the result ().
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 () 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 generates a NAND operation (, , ).