Coding for synthesis best practices in Verilog - Time & Space Complexity

Time Complexity: Coding for synthesis best practices

O(N)

Understanding Time Complexity

When writing Verilog code for synthesis, it is important to understand how the code's execution time grows as input size changes.

We want to see how the main operations in the code repeat and affect performance.

Scenario Under Consideration

Analyze the time complexity of the following Verilog code snippet.

module sum_array #(parameter N = 8) (
  input wire [7:0] data [0:N-1],
  output reg [15:0] sum
);
  integer i;
  always @* begin
    sum = 0;
    for (i = 0; i < N; i = i + 1) begin
      sum = sum + data[i];
    end
  end
endmodule

This code sums all elements of an input array of size N and outputs the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that adds each array element to the sum.
• How many times: The loop runs exactly N times, once per array element.

How Execution Grows With Input

As the array size N grows, the number of additions grows linearly.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: Doubling the input size doubles the number of operations.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete the sum grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "The loop runs in constant time because hardware runs in parallel."

[OK] Correct: While hardware can do many things at once, this loop describes a sequential addition that depends on previous results, so it takes time proportional to N.

Interview Connect

Understanding how loops and operations scale in hardware description languages shows your grasp of efficient hardware design and synthesis constraints.

Self-Check

"What if we replaced the for-loop with a tree-based adder structure? How would the time complexity change?"

Practice

1. Which of the following is a best practice for writing combinational logic in Verilog for synthesis?

easy

A. Leave some outputs unassigned to infer latches.

B. Use non-blocking assignments (<=) inside an always @(*) block.

C. Use delays like #5 to model timing.

D. Use blocking assignments (=) inside an always @(*) block.

Solution

1. Step 1: Understand combinational logic coding

   Combinational logic should be written using blocking assignments (=) to ensure correct immediate updates within the always @(*) block.

2. Step 2: Identify synthesis best practices

   Using non-blocking assignments or delays in combinational blocks can cause unintended behavior or non-synthesizable code.

3. Final Answer:

   Use blocking assignments (=) inside an always @(*) block. -> Option D

4. Quick Check:

   Combinational logic = blocking assignments [OK]

Hint: Use blocking (=) for combinational, non-blocking (<=) for sequential [OK]

Common Mistakes:

• Using non-blocking assignments in combinational blocks
• Adding delays (#) which are not synthesizable
• Leaving outputs unassigned causing inferred latches

2. Which of the following is the correct sensitivity list for a combinational always block in Verilog?

easy

A. always @(*)

B. always @(negedge reset)

C. always @(posedge clk)

D. always @(clk or reset)

Solution

1. Step 1: Identify combinational block sensitivity

   Combinational logic should react to all input changes, so always @(*) automatically includes all signals read inside the block.

2. Step 2: Compare other options

   Options with clock edges or specific signals are used for sequential logic, not combinational.

3. Final Answer:

   always @(*) -> Option A

4. Quick Check:

   Combinational sensitivity = always @(*) [OK]

Hint: Use always @(*) for combinational blocks to cover all inputs [OK]

Common Mistakes:

• Using clock edges in combinational blocks
• Listing incomplete sensitivity signals manually
• Forgetting to include all inputs causing latches

3. What is the output of the following Verilog code snippet when clk rises?

reg q;
always @(posedge clk) begin
  q = d;
end

medium

A. q updates but may cause simulation vs synthesis mismatch

B. Syntax error due to blocking assignment in sequential block

C. q updates correctly on clock edge

D. q never updates

Solution

1. Step 1: Analyze assignment type in sequential block

   The code uses blocking assignment (=) inside a clocked always block, which is not recommended for registers.

2. Step 2: Understand synthesis vs simulation behavior

   While synthesis tools may infer the register correctly, simulation can show unexpected behavior due to immediate assignment instead of scheduled update.

3. Final Answer:

   q updates but may cause simulation vs synthesis mismatch -> Option A

4. Quick Check:

   Sequential block + blocking assignment = mismatch risk [OK]

Hint: Use non-blocking (<=) in sequential blocks to avoid mismatches [OK]

Common Mistakes:

• Using blocking (=) in clocked always blocks
• Expecting immediate update in sequential logic
• Confusing simulation behavior with synthesis

4. Identify the error in the following Verilog code snippet intended for synthesis:

always @(posedge clk) begin
  if (enable)
    q <= d;
  else
    ; // missing else assignment
end

medium

A. Sensitivity list is incomplete

B. Using non-blocking assignment in sequential block is wrong

C. Missing non-blocking assignment in else branch causes inferred latch

D. Syntax error due to empty else statement

Solution

1. Step 1: Check assignments in all branches

   The else branch has no assignment to q, so q retains its previous value, causing a latch to be inferred.

2. Step 2: Understand synthesis best practice

   To avoid latches, all outputs must be assigned in every branch of a sequential block.

3. Final Answer:

   Missing non-blocking assignment in else branch causes inferred latch -> Option C

4. Quick Check:

   All branches assign outputs to avoid latches [OK]

Hint: Assign outputs in all if-else branches to prevent latches [OK]

Common Mistakes:

• Leaving else branch empty causing inferred latch
• Confusing blocking and non-blocking assignments
• Ignoring sensitivity list completeness in sequential blocks

5. You want to design a 4-bit counter with synchronous reset using best synthesis practices. Which code snippet correctly implements this?

hard

A. always @(posedge clk or posedge reset) begin
if (reset)
count <= 0;
else
count = count + 1;
end

B. always @(posedge clk) begin
if (reset)
count <= 0;
else
count <= count + 1;
end

C. always @(posedge clk) begin
if (reset == 1'b1)
count = 0;
else
count <= count + 1;
end

D. always @(posedge clk) begin
if (reset)
count <= 0;
else
count = count + 1;
end

Solution

1. Step 1: Identify synchronous reset and non-blocking assignments

   Synchronous reset means reset is checked only on clock edge, so sensitivity list should only have posedge clk. Non-blocking assignments (<=) must be used for registers.

2. Step 2: Evaluate each option

   always @(posedge clk or posedge reset) begin if (reset) count <= 0; else count = count + 1; end uses asynchronous reset (posedge reset) and blocking assignment in else branch, which is not best practice. always @(posedge clk) begin if (reset == 1'b1) count = 0; else count <= count + 1; end mixes blocking and non-blocking assignments. always @(posedge clk) begin if (reset) count <= 0; else count = count + 1; end uses blocking assignment in else branch. Only always @(posedge clk) begin if (reset) count <= 0; else count <= count + 1; end uses synchronous reset and non-blocking assignments consistently.

3. Final Answer:

   Option B correctly implements a 4-bit counter with synchronous reset and proper assignments. -> Option B

4. Quick Check:

   Synchronous reset + non-blocking assignments = always @(posedge clk) begin if (reset) count <= 0; else count <= count + 1; end [OK]

Hint: Use only posedge clk and non-blocking (<=) for synchronous reset counters [OK]

Common Mistakes:

• Mixing blocking and non-blocking assignments in sequential logic
• Using asynchronous reset when synchronous is required
• Including reset in sensitivity list for synchronous reset