Parameterized Pipelined Reduction OR
Wide reduction operations, such as zero-detection across a 256-bit bus or aggregating interrupts from dozens of peripherals, create massive combinational logic depths. If evaluated in a single clock cycle, these wide gates become the critical path and violate timing constraints. Pipelining the reduction tree guarantees timing closure by restricting the combinational depth between registers to a single gate level.
The solution module takes a parameterized WIDTH-bit input in_data and computes its reduction OR. To meet high clock speeds, the reduction must be pipelined. While a simple shift register of the final reduction would pass a cycle-accurate test, a true hardware implementation must distribute the OR gates across the pipeline stages. At each stage, adjacent pairs of bits are logically ORed together and stored in a pipeline register. If a stage has an odd number of bits, the unpaired bit is registered as-is. This process continues until a single bit remains. The module delays the result by exactly $clog2(WIDTH) clock cycles. An accompanying in_valid signal must also be delayed by the same number of cycles to produce out_valid.
All registers are updated on the positive edge of clk. An asynchronous active-low reset rst_n clears all internal pipeline registers and outputs to 0. When in_valid is 0, the pipeline continues to shift, but out_valid will be 0 when that pipeline stage reaches the output.
Cycle-by-cycle trace for WIDTH = 8 (Latency = 3 cycles): • Cycle 1: rst_n=0 → out_valid=0, out_data=0 • Cycle 2: rst_n=1, in_valid=1, in_data=8'h01 → out_valid=0, out_data=0 (Pipeline filling) • Cycle 3: in_valid=1, in_data=8'h80 → out_valid=0, out_data=0 (Pipeline filling) • Cycle 4: in_valid=0, in_data=8'h00 → out_valid=0, out_data=0 (Pipeline filling) • Cycle 5: in_valid=0, in_data=8'h00 → out_valid=1, out_data=1 (Result of Cycle 2 emerges) • Cycle 6: in_valid=0, in_data=8'h00 → out_valid=1, out_data=1 (Result of Cycle 3 emerges) • Cycle 7: in_valid=0, in_data=8'h00 → out_valid=0, out_data=0 (Result of Cycle 4 emerges)
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | clk | input | 1 | Positive-edge triggered clock. | | rst_n | input | 1 | Asynchronous active-low reset; all outputs and internal registers go to 0 when asserted. | | in_valid | input | 1 | Asserted when in_data is valid. | | in_data | input | WIDTH | The input data vector to be reduced. | | out_valid | output | 1 | Delayed version of in_valid matching the pipeline latency. | | out_data | output | 1 | The pipelined reduction OR result. |
Constraints
- The
WIDTHparameter will always be greater than or equal to 2. - The exact latency from input to output must be
$clog2(WIDTH)clock cycles. - Both
out_validandout_datamust be registered outputs; no combinational logic may follow the final register. - When
in_validis 0, the pipeline must still shift the data forward.
Topics
Solve this problem
Write the module in Verilog, SystemVerilog or VHDL. Your submission is compiled and simulated against a real 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.