Codiode

Parameterized Pipelined Reduction OR

HardVerilog / SystemVerilogBuild

ORing a 256-bit bus in one cycle makes a deep chain of logic. A tree of 2-input ORs with a register after each level keeps it to one gate between flip-flops.

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, counted the way the trace below counts them: in_data and in_valid are registered first, then each OR level has its own register, so WIDTH = 8 uses four registers in a row and the result of cycle 2 appears in cycle 5. 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 WIDTH parameter will always be greater than or equal to 2.
  • The exact latency from input to output must be $clog2(WIDTH) clock cycles.
  • Both out_valid and out_data must be registered outputs; no combinational logic may follow the final register.
  • When in_valid is 0, the pipeline must still shift the data forward.

Topics

ParameterizedPipeliningReduction Tree

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 Pipelining

Problem 11 of 20 in the Pipelining track.

Related problems

Browse all problems · Verilog practice problems · Learning tracks

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