Recursive Generate Reduction Tree

Flat reduction operations—like ORing 64 bits together in a single combinational statement—create long critical paths that severely limit the maximum achievable clock frequency in high-performance hardware. By restructuring the logic into a balanced tree and pipelining each stage, we reduce the maximum combinational delay to a single gate per clock cycle, vastly increasing throughput.

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

Related problems

• Basic D Flip FlopEasy
• Debug: Missing Edge in Sensitivity ListMedium
• Phase Aligned Clock Domain CrossingHard
• Struct Array PipelineHard
• T Flip Flop from D Flip Flop TemplateEasy
• Read After Write Hazard DetectionEasy
• Parameterized Interface with ModportsHard
• Four Stage Shift RegisterEasy