Recursive Instantiation in Verilog

A student asked me whether it was possible to have a recursive function in Verilog. This set me wondering whether it was possible to do recursive instantiation in Verilog. Recursive instantiation is where a module instantiates itself.

Why would you want to do that? Well, some problems lead themselves to a recursive solution. Finding the minimum of a set of numbers is just such a job: basically, the minimum of a set of numbers is the minimum of the minimum of the first half and the minimum of the second half. Run that by me again...

Take a set of numbers. Divide that set in half. Find the minimum of each half. The minimum of the whole set is the lesser of the minimums of each half. How do you find the minimum of each half? Well, each half is a set of numbers, so for each half, go back to the beginning of this paragraph...

See: it's recursive. Eventually, you get a set of one number. The minimum of that set is obviously that number, so the problem becomes trivial, which is the point of working something out recursively. So, how can we do this in hardware using recursive instantiation?

We need a parameterizable module with N inputs. Inside the module, if N is greater than 2, we instantiate 2 copies of the module and route half the inputs to one and half the inputs to the other. The output of the module is then the lesser of the outputs of these 2 submodules.  If N is 1, however, we just connect the input straight to the output. That's it.

To do this in Verilog, we're going to have to use parameters and, given we might instantiate something or we might not, generate statements.

So, here is a Verilog implementation of this algorithm:

module MinN #(parameter N = 8, W=16) (input [(N*W)-1:0] I, output [W-1:0] Min);
 
  wire [W-1:0] Min1, Min2;
   
  generate
    if (N == 1)
      begin : Neq1
        assign Min1 = I;
        assign Min2 = I;
      end
    else
      begin : Ngt1
        MinN #(.N(N-(N/2)), .W(W)) M1 (.I(    I[(N*W)-1:((N/2)*W)]), .Min(Min1));
        MinN #(.N(N/2),     .W(W)) M2 (.I(I[((N/2)*W)-1:        0]), .Min(Min2));
      end
  endgenerate
 
  assign Min = (Min1 < Min2) ? Min1 : Min2;
 
endmodule
  
There are two parameters: N is the number of inputs and W is the width of each. Unfortunately, there is a complication: Verilog does not allow array ports. Instead we have to use a single vector input of width N*W. You can see this in the code. This complicates the code, because calculations then have to be done to index the bits of this input vector.

So, the core of our code is the generate block.  Inside that, we test the parameter N to see how many inputs we are dealing with. If we are dealing with one input, then the job is easy: the minimum value just equal to that one input. Otherwise, we are dealing with more than one input and so send half the inputs to one instance of the MinN module and the rest to the other instance. Outside the generate block we determine the overall minimum by comparing the outputs of each subblock.

Of course, this would be possible in SystemVerilog, because Verilog is a subset of SystemVerilog. But it would actually be easier in SystemVerilog, because you are allowed array ports.

And this is synthesizable.