Codiode

Recursive Generate Reduction Tree

HardVerilog / SystemVerilogBuild

ORing 64 bits in one expression makes a deep chain of logic. A tree of 2-input ORs with a register after each level keeps the depth at one gate per clock.

You will design a parameterized, fully pipelined OR reduction tree. The module must compute the logical OR of all bits in data_in. Instead of using a flat unary operator (|data_in), the module must recursively instantiate itself. At each recursive step, split the input vector in half using a generate for loop, instantiate two smaller versions of the module, and OR their outputs. Every module in the hierarchy (including the base case WIDTH == 1) must register its result on the positive edge of clk.

Timing and Reset Rules:

  • Clock edge: posedge clk
  • Reset type: Asynchronous, active-low (negedge rst_n)
  • Output values on reset: All registers in the hierarchy must reset to 0
  • Priority rules: Reset has highest priority and immediately drives outputs to 0
  • Latency: Because every level of the tree registers its output, a tree with WIDTH=16 will have a latency of exactly 5 clock cycles (\log_2(16) + 1).

Worked Trace (WIDTH=4):
Cycle 1: rst_n=0 → All intermediate registers and final out reset to 0.
Cycle 2: rst_n=1, data_in=4'b0010. Leaf nodes (WIDTH=1) evaluate data_in[i].
Cycle 3: clk posedge. Leaf nodes register inputs. Their outputs become 0, 0, 1, 0.
Cycle 4: clk posedge. Intermediate nodes (WIDTH=2) register the OR of leaf outputs. Their outputs become 0, 1.
Cycle 5: clk posedge. Root node (WIDTH=4) registers the OR of intermediate outputs. Final out=1.

Signal Direction Width Description
clk input 1 Positive-edge triggered clock
rst_n input 1 Asynchronous active-low reset; drives output to 0
data_in input WIDTH Input data vector to be reduced
out output 1 Registered logical OR of all bits in data_in

Constraints

  • The WIDTH parameter must default to 16.
  • You may assume WIDTH is always a power of 2 (e.g., 1, 2, 4, 8, 16).
  • You must use generate if to handle the base case (WIDTH == 1).
  • You must use a generate for loop to recursively instantiate the left and right halves of the tree when WIDTH > 1.
  • You cannot use the built-in unary reduction operator (|data_in).
  • Every level of the tree must register its output on posedge clk.

Topics

PipeliningSystemVerilogGenerate ConstructsRecursion

Solve this problem

Write the module in Verilog, SystemVerilog or VHDL. Your submission is compiled and simulated against the problem's testbench. You get the waveform back, not a stored answer.

This problem is part of Codiode Pro. The statement above is free to read.

The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.

Part of SystemVerilog RTL

Problem 12 of 15 in the SystemVerilog RTL track.

Related problems

Browse all problems · Verilog practice problems · Learning tracks

Solve this on a laptopSend yourself the link and continue there.