Subject: Re: recursive instantiations of modules
From: Paul Graham (pgraham@Cadence.COM)
Date: Fri Mar 08 2002 - 15:12:19 PST
Ben,
Your example has infinite recursion. Of course it can't be supported
by any tool:
> module my_not(out, in);
> input in;
> output out;
>
> my_not inst(out, in);
>
> endmodule
But as for recursive modules in general, sure why not?
> From a hardware point of view I am failing to visualize how a module can
> instantiate itself, when it was not completely defined.
A recursive module has to be parameterized and must contain a conditional
generate (if or case). As a parameterized module, it is not a
representation of hardward, but a template for creating new modules based on
the parameter's value. At each level of recursion, the parameter's value is
different, and the post-elaboration structure of the module is different.
So don't think of it as a module instantiating itself. Instead think of a
chain of instantiations of related modules.
Here's an example of module recursion. I don't know if any designer would
knowingly write this stuff, but at least it should be possible to do so:
module count_bits(q, d);
parameter width = 16;
output [7:0] q;
input [width-1:0] d;
generate
if (width == 1)
assign q = d[0];
else
begin : x
wire [7:0] q1, q2;
count_bits #((width)/2) m1(q1, d[width-1:(width-1)/2+1]);
count_bits #((width+1)/2) m2(q2, d[(width-1)/2:0]);
assign q = q1 + q2;
end
endgenerate
endmodule
module top(q, d);
output [7:0] q;
input [31:0] d;
count_bits #(32) m(q, d);
endmodule
It is basically equivalent to the following expanded chain of modules. As
you can see, no hardware module instantiates itself. Instead, a module like
count_bits_4 instantiates a related module, count_bits_2.
module count_bits_1(q, d);
output [7:0] q;
input [0:0] d;
assign q = d[0];
endmodule
module count_bits_2(q, d);
output [7:0] q;
input [1:0] d;
wire [7:0] q1, q2;
count_bits_1 m1(q1, d[1:1]),
m2(q2, d[0:0]);
assign q = q1 + q2;
endmodule
module count_bits_4(q, d);
output [3:0] q;
input [3:0] d;
wire [3:0] q1, q2;
count_bits_2 m1(q1, d[3:2]),
m2(q2, d[1:0]);
assign q = q1 + q2;
endmodule
module count_bits_8(q, d);
output [7:0] q;
input [7:0] d;
wire [7:0] q1, q2;
count_bits_4 m1(q1, d[7:4]),
m2(q2, d[3:0]);
assign q = q1 + q2;
endmodule
module count_bits_16(q, d);
output [7:0] q;
input [15:0] d;
wire [7:0] q1, q2;
count_bits_8 m1(q1, d[15:8]),
m2(q2, d[7:0]);
assign q = q1 + q2;
endmodule
module count_bits_32(q, d);
output [7:0] q;
input [31:0] d;
wire [7:0] q1, q2;
count_bits_16 m1(q1, d[31:16]),
m2(q2, d[15:0]);
assign q = q1 + q2;
endmodule
module top(q, d);
output [7:0] q;
input [31:0] d;
count_bits_32 m(q, d);
endmodule
> 1. There is no STOP. I guess you could instantiate a module where last
> instance is itself with no components ?
> (ambiguous)
As you can see, there is a stop. The lowest level module (count_bits_1) has
no component instances, but does have an assignment (which is missing in all
the higher-level modules).
> 2. Drivers. Multiple drivers would result.
Again, the different levels of recursion all result in physically different
modules, so there are no multiply-driven signals.
> Is there anyone out there who has seen or applied this module recursion
> before?
BuildGates has supported recursive VHDL module instantiation for years. I
don't know if anyone actually *uses* it, but it's there.
Paul
This archive was generated by hypermail 2b28 : Fri Mar 08 2002 - 15:17:16 PST