Design hierarchy for ALU in Verilog - Time & Space Complexity

Time Complexity: Design hierarchy for ALU

O(n)

Understanding Time Complexity

When we build an ALU using design hierarchy, we want to know how the time it takes to run grows as the ALU handles bigger inputs.

We ask: How does the design structure affect the speed when input size changes?

Scenario Under Consideration

Analyze the time complexity of the following Verilog ALU design hierarchy snippet.

module alu(
  input  [3:0] a, b,
  input  [2:0] op,
  output reg [3:0] result
);
  always @(*) begin
    case(op)
      3'b000: result = a + b;
      3'b001: result = a - b;
      3'b010: result = a & b;
      3'b011: result = a | b;
      default: result = 4'b0000;
    endcase
  end
endmodule

This ALU module uses a case statement to select operations on 4-bit inputs.

Identify Repeating Operations

Look for parts that repeat work as input size grows.

• Primary operation: Bitwise and arithmetic operations on 4-bit inputs.
• How many times: Each operation works on all bits in parallel, no loops.

How Execution Grows With Input

As input size (bit width) grows, the ALU does more work on each bit.

Input Size (bits)	Approx. Operations
4	4 operations in parallel
8	8 operations in parallel
16	16 operations in parallel

Pattern observation: The work grows linearly with input size because each bit is processed once.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute grows directly with the number of bits in the inputs.

Common Mistake

[X] Wrong: "The ALU runs in constant time no matter the input size because operations happen in parallel."

[OK] Correct: While operations are parallel, the hardware must handle each bit, so increasing bits means more hardware and longer signal paths, which grows time roughly linearly.

Interview Connect

Understanding how design hierarchy affects time helps you explain hardware speed and scaling clearly, a useful skill in design and system discussions.

Self-Check

What if we changed the ALU to handle 32-bit inputs instead of 4-bit? How would the time complexity change?

Practice

1. What is the main benefit of using a design hierarchy when creating an ALU in Verilog?

easy

A. It removes the need for a top module to connect parts.

B. It makes the ALU run faster without changing the design.

C. It automatically generates testbenches for the ALU.

D. It breaks the ALU into smaller, manageable modules like adders and logic units.

Solution

1. Step 1: Understand design hierarchy concept

   Design hierarchy means dividing a big design into smaller modules for clarity and easier management.

2. Step 2: Apply to ALU design

   Breaking ALU into smaller parts like adders and logic units helps in understanding and fixing the design easily.

3. Final Answer:

   It breaks the ALU into smaller, manageable modules like adders and logic units. -> Option D

4. Quick Check:

   Design hierarchy = smaller modules [OK]

Hint: Think modular: big design = small parts [OK]

Common Mistakes:

• Assuming hierarchy speeds up ALU automatically
• Thinking top module is unnecessary
• Believing hierarchy creates testbenches

2. Which of the following is the correct way to instantiate a 4-bit adder module named adder4 inside a top ALU module in Verilog?

easy

A. adder4 add(.a(a), .b(b), .sum(sum));

B. adder4(a, b, sum);

C. adder4 add = (a, b, sum);

D. adder4 add {a, b, sum};

Solution

1. Step 1: Recall Verilog module instantiation syntax

   Correct syntax uses module name, instance name, and port connections with dot notation and parentheses.

2. Step 2: Check each option

   adder4 add(.a(a), .b(b), .sum(sum)); uses correct dot notation and parentheses. Options B, C, D have syntax errors or wrong format.

3. Final Answer:

   adder4 add(.a(a), .b(b), .sum(sum)); -> Option A

4. Quick Check:

   Correct instantiation = dot notation [OK]

Hint: Use dot and parentheses for ports [OK]

Common Mistakes:

• Omitting dot before port names
• Using equals sign instead of parentheses
• Using braces instead of parentheses

3. Given the following Verilog code snippet for a top ALU module, what will be the output result when op = 2'b01, a = 4'b0011, and b = 4'b0101?

module alu_top(input [3:0] a, b, input [1:0] op, output reg [3:0] result);
  wire [3:0] sum, and_out;
  adder4 add(.a(a), .b(b), .sum(sum));
  logic_unit logicu(.a(a), .b(b), .and_out(and_out));
  always @(*) begin
    case(op)
      2'b00: result = sum;
      2'b01: result = and_out;
      default: result = 4'b0000;
    endcase
  end
endmodule

medium

A. 4'b0110

B. 4'b0011

C. 4'b0001

D. 4'b0000

Solution

1. Step 1: Understand module connections and operations

   When op=2'b01, result is assigned from logic_unit output 'and_out', which is bitwise AND of a and b.

2. Step 2: Calculate bitwise AND of a=0011 and b=0101

   0011 AND 0101 = 0001 in binary.

3. Final Answer:

   4'b0001 -> Option C

4. Quick Check:

   Bitwise AND(0011,0101) = 0001 [OK]

Hint: Match op code to output source [OK]

Common Mistakes:

• Confusing sum with and_out
• Calculating OR instead of AND
• Ignoring op code in case statement

4. Identify the error in this Verilog top module instantiation of submodules for an ALU:

module alu_top(input [3:0] a, b, input [1:0] op, output reg [3:0] result);
  wire [3:0] sum, and_out;
  adder4 add(a, b, .sum(sum));
  logic_unit logicu(.a(a), .b(b), .and_out(and_out));
  always @(*) begin
    case(op)
      2'b00: result = sum;
      2'b01: result = and_out;
      default: result = 4'b0000;
    endcase
  end
endmodule

medium

A. Missing dot notation in adder4 instantiation causes syntax error.

B. logic_unit ports are incorrectly connected.

C. The always block should be replaced with an initial block.

D. The output 'result' should be a wire, not reg.

Solution

1. Step 1: Check module instantiations for syntax

   Adder4 instantiation uses positional ports without dot notation, which is allowed only if order matches exactly and ports are declared in module. But best practice and safer is dot notation.

2. Step 2: Identify error in given code

   Since logic_unit uses dot notation and adder4 does not, and if adder4 module expects named ports, missing dot notation causes syntax or connection error.

3. Final Answer:

   Missing dot notation in adder4 instantiation causes syntax error. -> Option A

4. Quick Check:

   Use dot notation for clarity and correctness [OK]

Hint: Use dot notation for all module ports [OK]

Common Mistakes:

• Thinking initial block is needed for combinational logic
• Changing reg to wire incorrectly
• Ignoring port connection style consistency

5. You want to extend your ALU design hierarchy by adding a subtractor module sub4 alongside the existing adder4 and logic_unit. How should you modify the top ALU module to select between addition and subtraction based on op signal, assuming op=2'b10 means subtraction?

hard

A. Replace adder4 with sub4 and ignore op=2'b10 case.

B. Instantiate sub4 module and add a case for 2'b10 to assign its output to result.

C. Add subtraction logic inside adder4 without new module.

D. Use a separate top module for subtraction and call it only when op=2'b10.

Solution

1. Step 1: Understand design hierarchy extension

   Adding a new subtractor module means instantiating it in the top module alongside existing modules.

2. Step 2: Modify case statement for op signal

   Add a case for op=2'b10 to assign the subtractor output to result, enabling selection between add and subtract.

3. Final Answer:

   Instantiate sub4 module and add a case for 2'b10 to assign its output to result. -> Option B

4. Quick Check:

   New module + case for op = extend hierarchy [OK]

Hint: Add module and case for new operation [OK]

Common Mistakes:

• Replacing adder instead of adding subtractor
• Ignoring op code for subtraction
• Creating separate top module unnecessarily