Recursive instantiation: a synthesis no no?

Hi,

What is expected synthesizability of recursively generated
instantiation (see below for trivial test case)
Is this explicitely prohibited by Verilog 2001 LRM?
(Did not found it)

So far my results are 50/50: Xilinx ISE8.1 XST works,
Synopsys dc_shell (2005.09) dies with "Internal error".

BTW Modelism did not have any issues with this code either.

<rant>
It is really anoying that support level for Verilog 2001 is still
so patchy (5 years on). How anybody is expected to adopt
SystemVerilog if basic V2001 stuff does not work yet.

Do you guys use V2001 or do you stay with V95 for safety
and peace of mind?
</rant>

Cheers,
Przemek



module iee_biton_test (
data_in,
data_out
);

// Global parameters
parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 3;

// Local parameters
parameter DATA_ARRAY_MSB = DATA_WIDTH -1;
parameter DATA_ARRAY_SIZE_EXP_M1 = DATA_ARRAY_SIZE_EXP-1;

input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;


wire [DATA_ARRAY_MSB:0] data_in_p1 = data_in +1'b1;

generate

if(DATA_ARRAY_SIZE_EXP>1) begin: nest

iee_biton_test
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
iee_biton_test_0
(
..data_in(data_in_p1),
..data_out(data_out)
);

end
else begin: last
assign data_out = data_in_p1;
end
endgenerate

endmodule

 

bazarnik@hotmail.com wrote:

Hi,

What is expected synthesizability of recursively generated
instantiation (see below for trivial test case)
Is this explicitely prohibited by Verilog 2001 LRM?
(Did not found it)

The 2001 LRM doesn't say anything about it, but the 2005 LRM states
that generates make recursive module instantiation possible. This was
a clarification that it is indeed allowed.

Synthesizability is up to your synthesis tool implementation. I
believe that our synthesis tools handle it, but I don't work on them so
I can't be certain.

 

Thanks for info!
Looks like a point for Cadence tools here.

Ability to use recursion is a very strong tool combined with generated
instantiation.
I coded and simulated a fully parametrizable bitionic sort
implementation
in a matter of hour just to find out I will have to write it in
iterative form for synthesis.
(looks like it is going to be a very mundane job to manage all the
wiring)

No wonder people go to an effort to develop Confluence
(www.confluent.org), ESL stuff.

Cheers,
Przemek



sharp@cadence.com wrote:

bazarnik@hotmail.com wrote:
Hi,

What is expected synthesizability of recursively generated
instantiation (see below for trivial test case)
Is this explicitely prohibited by Verilog 2001 LRM?
(Did not found it)

The 2001 LRM doesn't say anything about it, but the 2005 LRM states
that generates make recursive module instantiation possible. This was
a clarification that it is indeed allowed.

Synthesizability is up to your synthesis tool implementation. I
believe that our synthesis tools handle it, but I don't work on them so
I can't be certain.

 

[Jonathan Bromley]

On 12 Jul 2006 19:20:44 -0700, bazarnik@hotmail.com wrote:

Looks like a point for Cadence tools here.

In fairness, most synthesis tools can do recursive instantiation
given the right input. When I last looked, the FPGA-native
tools (Quartus, ISE) could not; but that was a while ago, and
things may have changed by now.

Ability to use recursion is a very strong tool combined with generated
instantiation.
I coded and simulated a fully parametrizable bitionic sort
implementation
in a matter of hour just to find out I will have to write it in
iterative form for synthesis.

No wonder people go to an effort to develop Confluence
(www.confluent.org), ESL stuff.

No wonder people go to VHDL, where you can do
this sort of thing very easily (and always could).
All the mainstream synthesis tools I've used are OK with
recursive VHDL function calls, and most of them handle
recursive VHDL generate too.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

Jonathan Bromley wrote:

On 12 Jul 2006 19:20:44 -0700, bazarnik@hotmail.com wrote:

Looks like a point for Cadence tools here.

In fairness, most synthesis tools can do recursive instantiation
given the right input. When I last looked, the FPGA-native
tools (Quartus, ISE) could not; but that was a while ago, and
things may have changed by now.

I can tell you that even newest version of Synopsys Design Compiler
(2006.06)
exits with error (generic VER-27) for the above test code.
Just now I'm preparing a test case and bug report for Synopsys.

As I mentioned Xilinx XST syntheiszed this code correctly.

No wonder people go to VHDL, where you can do
this sort of thing very easily (and always could).
All the mainstream synthesis tools I've used are OK with
recursive VHDL function calls, and most of them handle
recursive VHDL generate too.

Isn't it true? After years of catching up to VHDL Verilog 2001 got
generate just so that for the next 10 years we can play
the same supported/not supported feature lottery as it was the case
with early VHDL

Thanks,
Przemek

 

[Mike Treseler]

bazarnik@hotmail.com wrote:

Just now I'm preparing a test case and bug report for Synopsys.
....
After years of catching up to VHDL Verilog 2001 got
generate just so that for the next 10 years we can play
the same supported/not supported feature lottery as it was the case
with early VHDL

Synopsys *still* lags way behind brands A, X and M
in VHDL language support. Ten years may not be long enough

-- Mike Treseler

 

[ABC]

Hi Groups,
It is because the recursive instantiated module identifier is same as
the module that enclosed it. Resolve the identifier conflict and it
should work in DC 2006.06

Best regards,
ABC

bazarnik@hotmail.com wrote:

Jonathan Bromley wrote:
On 12 Jul 2006 19:20:44 -0700, bazarnik@hotmail.com wrote:

Looks like a point for Cadence tools here.

In fairness, most synthesis tools can do recursive instantiation
given the right input. When I last looked, the FPGA-native
tools (Quartus, ISE) could not; but that was a while ago, and
things may have changed by now.

I can tell you that even newest version of Synopsys Design Compiler
(2006.06)
exits with error (generic VER-27) for the above test code.
Just now I'm preparing a test case and bug report for Synopsys.

As I mentioned Xilinx XST syntheiszed this code correctly.

No wonder people go to VHDL, where you can do
this sort of thing very easily (and always could).
All the mainstream synthesis tools I've used are OK with
recursive VHDL function calls, and most of them handle
recursive VHDL generate too.

Isn't it true? After years of catching up to VHDL Verilog 2001 got
generate just so that for the next 10 years we can play
the same supported/not supported feature lottery as it was the case
with early VHDL

Thanks,
Przemek

 

Well, if the module identifier name "iee_biton_test" would be different
than enclosing module then it would not be a recursive instantiation
(not direct anyway) (?)

The idea behind recursion is that module instantiates itself.
Of course there is condition built in to terminate the recursion.

It just happens that bitonic sort is nicely defined in recursive manner
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

See BitonicMerge definition. It is recursive because it includes
two other BitonicMerge(n/2) instances of itself (plus Bn operation)

BTW the tools resolve the nameing conflict by generating unique names
using begin/end block label and generate variable.

Cheers,
Przemek




ABC wrote:

Hi Groups,
It is because the recursive instantiated module identifier is same as
the module that enclosed it. Resolve the identifier conflict and it
should work in DC 2006.06

Best regards,
ABC

 

[ABC]

Hi Przemek,
Let's simplify the scenario.
module abc (a,b);
input a;
output b;
abc gen1.x1 (.a(a),.b(b));
endmodule
Is it legal?
Any verilog reader tools that doesn't flag me error, I will file it as
a bug immediately.

Best regards,
ABC
bazarnik@hotmail.com wrote:

Well, if the module identifier name "iee_biton_test" would be different
than enclosing module then it would not be a recursive instantiation
(not direct anyway) (?)

The idea behind recursion is that module instantiates itself.
Of course there is condition built in to terminate the recursion.

It just happens that bitonic sort is nicely defined in recursive manner
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

See BitonicMerge definition. It is recursive because it includes
two other BitonicMerge(n/2) instances of itself (plus Bn operation)

BTW the tools resolve the nameing conflict by generating unique names
using begin/end block label and generate variable.

Cheers,
Przemek




ABC wrote:
Hi Groups,
It is because the recursive instantiated module identifier is same as
the module that enclosed it. Resolve the identifier conflict and it
should work in DC 2006.06

Best regards,
ABC

 

[ABC]

Hi Przemek,
An example of the correct usage of recursive instantiation as shown
below.
module gen1 (s,a, b);
parameter SIZE = 2;
output [1:0] s;
input [1:0] a, b;

genvar i;


generate
for(i=0; i<SIZE; i=i+1) begin:bit
xor g1 ( s, a, b);
end
endgenerate
endmodule

Regarding the bitonic sort,I guess you should ask Jonathan how to
convert his C language to verilog. I saw his bitonic sort C code
posting before if not mistaken.Java language is extremely flexible and
didn't touch it for more than 8 years already. Sorry.

Best regards,
ABC



bazarnik@hotmail.com wrote:

Well, if the module identifier name "iee_biton_test" would be different
than enclosing module then it would not be a recursive instantiation
(not direct anyway) (?)

The idea behind recursion is that module instantiates itself.
Of course there is condition built in to terminate the recursion.

It just happens that bitonic sort is nicely defined in recursive manner
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

See BitonicMerge definition. It is recursive because it includes
two other BitonicMerge(n/2) instances of itself (plus Bn operation)

BTW the tools resolve the nameing conflict by generating unique names
using begin/end block label and generate variable.

Cheers,
Przemek




ABC wrote:
Hi Groups,
It is because the recursive instantiated module identifier is same as
the module that enclosed it. Resolve the identifier conflict and it
should work in DC 2006.06

Best regards,
ABC

 

ABC wrote:

Let's simplify the scenario.
module abc (a,b);
input a;
output b;
abc gen1.x1 (.a(a),.b(b));
endmodule
Is it legal?

No. To start with, gen1.x1 is an invalid identifier, so you have a
syntax error. If you fix that, then you have an error because it
contains infinite recursion. The original testcase used a conditional
generate to prevent the infinite recursion, and was legal. In
simplifying it, you have made it illegal.

 

[ABC]

Hi Sharp,
You were right.
It should be
module abc (a,b);
input a;
output b;
abc gen1_x1 (.a(a),.b(b));
endmodule
The character "." is illegal for verilog identifier. Sorry.
Now, is it legal?

Best regards,
ABC

sharp@cadence.com wrote:

ABC wrote:
Let's simplify the scenario.
module abc (a,b);
input a;
output b;
abc gen1.x1 (.a(a),.b(b));
endmodule
Is it legal?

No. To start with, gen1.x1 is an invalid identifier, so you have a
syntax error. If you fix that, then you have an error because it
contains infinite recursion. The original testcase used a conditional
generate to prevent the infinite recursion, and was legal. In
simplifying it, you have made it illegal.

 

[Andy Ray]

ABC wrote:

Hi Sharp,
You were right.
It should be
module abc (a,b);
input a;
output b;
abc gen1_x1 (.a(a),.b(b));
endmodule
The character "." is illegal for verilog identifier. Sorry.
Now, is it legal?

Best regards,
ABC

sharp@cadence.com wrote:
ABC wrote:
Let's simplify the scenario.
module abc (a,b);
input a;
output b;
abc gen1.x1 (.a(a),.b(b));
endmodule
Is it legal?
No. To start with, gen1.x1 is an invalid identifier, so you have a
syntax error. If you fix that, then you have an error because it
contains infinite recursion. The original testcase used a conditional
generate to prevent the infinite recursion, and was legal. In
simplifying it, you have made it illegal.

Hi,

It was briefly mentioned at the beginning of this thread, and somewhat
dismissed, but this sort of thing really is a breeze in confluence (or
better yet in HDCaml).

Fair enough there's a learning curve, but if you want to apply recursive
techniques to hardware design its the place to be. You'll end up with
simple, synthesizable verilog without all the fuss.

Cheers,

Andy.

 

[ABC]

Hi Sharp,
FYI, the recursive function shown in the website is what make Java
language so powerful and user fancy about it when the language was
introduced. It can be done in nonrecursive way as well but definitely
lengthy.
but with a verilog coding of
module abc (a,b);
input a;
output b;
abc gen1_x1 (.a(a),.b(b)); //after rectify my instance identifier
error
endmodule
It is definitely having module name identifier conflict. If any design
tools that I use doesn't flag me that error, I will file a bug case
for sure and including SR. I made this stupid mistakes when I first
started using verilog and wasted whole day to figure out this stupid
coding mistake. I was really piss off with myself at that moment.


Best regards,
ABC

ABC wrote:

Hi Sharp,
You were right.
It should be
module abc (a,b);
input a;
output b;
abc gen1_x1 (.a(a),.b(b));
endmodule
The character "." is illegal for verilog identifier. Sorry.
Now, is it legal?

Best regards,
ABC

sharp@cadence.com wrote:
ABC wrote:
Let's simplify the scenario.
module abc (a,b);
input a;
output b;
abc gen1.x1 (.a(a),.b(b));
endmodule
Is it legal?

No. To start with, gen1.x1 is an invalid identifier, so you have a
syntax error. If you fix that, then you have an error because it
contains infinite recursion. The original testcase used a conditional
generate to prevent the infinite recursion, and was legal. In
simplifying it, you have made it illegal.

 

[ABC]

Hi Andy and group,
You were right. Sorry if my wording is harsh. I mean no hard feeling.
Sorry.
Recursive function and stack is famous to solve the tower of hanoi
puzzle.
Sorry if I offend anyone.

Best regards,
ABC

 

[Andy Ray]

ABC wrote:

Hi Andy and group,
You were right. Sorry if my wording is harsh. I mean no hard feeling.
Sorry.

Your wording wasn't harsh, and I didn't mean to suggest it was. My
apologies if I did.

Recursive function and stack is famous to solve the tower of hanoi
puzzle.

Recursion isn't only useful for simple computational puzzles, but also
to describe regular hardware structures. Both vhdl and verilog support
it but in a rather wordy manner - at least in my opinion.

Confluence and HDcaml are free and are designed for this sort of
problem. They dont replace verilog but rather provide an abstraction
which makes certain problems easier.

Cheers,

Andy

 

Dear All,

FYI this issue was confirmed to be a bug in Design Compiler
(hopefully fixed in a next service pack)

I recoded the bitionic sort in an iterative form.
I would not recommend it unless one feels a need for a some of
the "human compiler" type of brain workout.
Actually doing the b.sort with recursion in Verilog is not really
that complex (see below) One just needs to use modules to avoid
too many nested loops and to keep things neat.

I did try Confluence quite some time earlier. It is a nice tool.
I have found the syntax to be quite "peculiar" but still better
than HDCaml bracket flood.
We do not have that much datapath code which would warrant
adding Confluence to our ASIC flow. This may change though.

Ultimately Confluence type languages are thay way HW design must go.
SystemVerilog interfaces and other stuff are another way to introduce
high level hardware design features.

Thanks,
Przemek


PS For you viewing pleasure:
the bitionic sort implemented in Verilog 2001 with recursive
instantiation.

Module list:
system (top level)
biton_sort
biton_merge
biton_bn
biton_reverse

I leave the iterative version as an excercise for the reader


module biton_bn (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (1<<DATA_ARRAY_SIZE_EXP) * DATA_WIDTH -1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output reg [DATA_ARRAY_MSB:0] data_out;

// ===============


genvar i;

generate for(i=0;i<(DATA_ARRAY_SIZE>>1);i=i+1) begin: comp

always @*
if( data_in[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] > data_in[
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] ) begin
// swap
data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in [
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET];
data_out[ (i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] = data_in [ (i+1)*DATA_WIDTH-1 :
i*DATA_WIDTH];

end
else begin
// keep the same
data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in [
(i+1)*DATA_WIDTH-1 : i*DATA_WIDTH];
data_out[ (i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] = data_in [
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET];

end
end

endgenerate
endmodule


module biton_merge (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;

parameter DATA_ARRAY_SIZE_EXP_M1 = DATA_ARRAY_SIZE_EXP-1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

wire [DATA_ARRAY_MSB:0] data_div;


biton_bn
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_bn_1
(
..data_in(data_in),
..data_out(data_div)
);


generate

if(DATA_ARRAY_SIZE_EXP>1) begin: nest

wire [DATA_UPPER_HALF_OFFSET-1:0] data_merge_1;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_merge_0;


biton_merge
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_merge_0
(
..data_in(data_div[ DATA_UPPER_HALF_OFFSET-1:0]),
..data_out(data_merge_0)
);


biton_merge
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_merge_1
(
..data_in(data_div[ DATA_ARRAY_MSBATA_UPPER_HALF_OFFSET]),
..data_out(data_merge_1)
);

assign data_out = {data_merge_1, data_merge_0};

end
else begin: last

assign data_out = data_div;

end
endgenerate
endmodule


module biton_reverse (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;


input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

genvar i;

generate for(i=0;i<DATA_ARRAY_SIZE;i=i+1) begin: rev
assign data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in[
(DATA_ARRAY_SIZE-i)*DATA_WIDTH-1 : (DATA_ARRAY_SIZE-i-1)*DATA_WIDTH];
end

endgenerate
endmodule




module biton_sort (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;

parameter DATA_ARRAY_SIZE_EXP_M1 = DATA_ARRAY_SIZE_EXP-1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

wire [DATA_ARRAY_MSB:0] data_conq;




generate

if(DATA_ARRAY_SIZE_EXP>1) begin: nest

wire [DATA_UPPER_HALF_OFFSET-1:0] data_sort_1;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_sort_0;

wire [DATA_UPPER_HALF_OFFSET-1:0] data_rev_0;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_rev_1;


biton_sort
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_sort_0
(
..data_in(data_in[ DATA_UPPER_HALF_OFFSET-1:0]),
..data_out(data_sort_0)
);


biton_reverse
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_reverse_1_0
(
..data_in(data_in[ DATA_ARRAY_MSBATA_UPPER_HALF_OFFSET]),
..data_out(data_rev_0)
);


biton_sort
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_sort_1
(
..data_in(data_rev_0),
..data_out(data_rev_1)
);


biton_reverse
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_reverse_1_1
(
..data_in(data_rev_1),
..data_out(data_sort_1)
);



assign data_conq = {data_sort_1, data_sort_0};

end
else begin: last

assign data_conq = data_in;

end

endgenerate


biton_merge
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_merge_1
(
..data_in(data_conq),
..data_out(data_out)
);

endmodule




module system;

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 3; // array is 2^DATA_ARRAY_SIZE_POW
elements

// ==================

// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}

parameter DATA_ARRAY_MSB = (1<<DATA_ARRAY_SIZE_EXP) * DATA_WIDTH -1;

wire [DATA_ARRAY_MSB:0] data_in = {4'h1, 4'h3, 4'h5, 4'h2, 4'hf, 4'hb,
4'h0, 4'ha };
wire [DATA_ARRAY_MSB:0] data_out;



biton_sort
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_sort_1
(
..data_in(data_in),
..data_out(data_out)
);

/*

biton_merge
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_merge_1
(
..data_in(data_in),
..data_out(data_out)
);

biton_bn
#(
..DATA_WIDTH(DATA_WIDTH),
..DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_bn_1
(
..data_in(data_in),
..data_out(data_out)
);
*/

endmodule

 

[Andy Ray]

PS For you viewing pleasure:
the bitionic sort implemented in Verilog 2001 with recursive
instantiation.

I leave the iterative version as an excercise for the reader

I'll take you up on that !

The output is verilog with no recursion (or iteration for that matter).

Cheers,

Andy

(* ocamlc -o bitonic.exe hdcaml.cma bitonic.ml *)

open Hdcaml
open Design
open List

(*
inputs:
sort_fn : (> unsigned sort up; (< unsigned sort down;
(>+) signed sort up; (<+) signed sort down
pipeline: (fun x->x) combinatorial; (reg ena) pipelined
inputs : list of inputs (must be power of two)
vld_in : input valid signal
returns:
list of sorted outputs, output valid signal
*)
let bitonic_sort sort_fn pipeline inputs vld =

let asc = const "1" in
let dsc = const "0" in

(* split list into two halves *)
let halve_list l =
let rec s0 l0 l1 =
if (length l0) = (length l1) then l0, l1
else s0 (l0 @ [hd l1]) (tl l1) in
s0 [] l in

let compare a b dir =
let c = dir ==: (sort_fn a b) in
pipeline (mux2 c b a), pipeline (mux2 c a b) in

let rec merge l dir vld =
if (length l) > 1 then
let l0,l1 = halve_list l in
let l0,l1 = split (map2
(fun a b -> compare a b dir) l0 l1) in
let l0,v0 = merge l0 dir (pipeline vld) in
let l1,_ = merge l1 dir (const "0") in
(l0@l1), v0
else l, vld in

let rec sort l dir vld =
if ((length l) > 1) then
let l0,l1 = halve_list l in
let s0,v0 = (sort l0 asc vld) in
let s1,_ = (sort l1 dsc vld) in
merge (s0@s1) dir v0
else l, vld in

sort inputs asc vld

let _ =
start_circuit "bitonic";
(* let inputs = map (fun x -> input ("i" ^ (string_of_int x)) 4)
[ 0; 1; 2; 3; 4; 5; 6; 7 ] in *)
let inputs = map (fun x -> const x)
[ "0001"; "0011"; "0101"; "0010";
"1111"; "1011"; "0000"; "1010" ] in
let outputs, vld_out = bitonic_sort (> (fun x -> x)
inputs (const "0") in
iter2 (fun x y -> output ("o" ^ (string_of_int y)) x) outputs
[0;1;2;3;4;5;6;7];
let circuit = get_circuit () in
Verilog.output_netlist circuit

 

[ABC]

Hi Przemek,
Which statement of verilog allow recursive instantiation?

Best regards,
ABC

bazarnik@hotmail.com wrote:

Dear All,

FYI this issue was confirmed to be a bug in Design Compiler
(hopefully fixed in a next service pack)

I recoded the bitionic sort in an iterative form.
I would not recommend it unless one feels a need for a some of
the "human compiler" type of brain workout.
Actually doing the b.sort with recursion in Verilog is not really
that complex (see below) One just needs to use modules to avoid
too many nested loops and to keep things neat.

I did try Confluence quite some time earlier. It is a nice tool.
I have found the syntax to be quite "peculiar" but still better
than HDCaml bracket flood.
We do not have that much datapath code which would warrant
adding Confluence to our ASIC flow. This may change though.

Ultimately Confluence type languages are thay way HW design must go.
SystemVerilog interfaces and other stuff are another way to introduce
high level hardware design features.

Thanks,
Przemek


PS For you viewing pleasure:
the bitionic sort implemented in Verilog 2001 with recursive
instantiation.

Module list:
system (top level)
biton_sort
biton_merge
biton_bn
biton_reverse

I leave the iterative version as an excercise for the reader


module biton_bn (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (1<<DATA_ARRAY_SIZE_EXP) * DATA_WIDTH -1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output reg [DATA_ARRAY_MSB:0] data_out;

// ===============


genvar i;

generate for(i=0;i<(DATA_ARRAY_SIZE>>1);i=i+1) begin: comp

always @*
if( data_in[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] > data_in[
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] ) begin
// swap
data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in [
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET];
data_out[ (i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] = data_in [ (i+1)*DATA_WIDTH-1 :
i*DATA_WIDTH];

end
else begin
// keep the same
data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in [
(i+1)*DATA_WIDTH-1 : i*DATA_WIDTH];
data_out[ (i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET] = data_in [
(i+1)*DATA_WIDTH-1+DATA_UPPER_HALF_OFFSET :
i*DATA_WIDTH+DATA_UPPER_HALF_OFFSET];

end
end

endgenerate
endmodule


module biton_merge (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;

parameter DATA_ARRAY_SIZE_EXP_M1 = DATA_ARRAY_SIZE_EXP-1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

wire [DATA_ARRAY_MSB:0] data_div;


biton_bn
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_bn_1
(
.data_in(data_in),
.data_out(data_div)
);


generate

if(DATA_ARRAY_SIZE_EXP>1) begin: nest

wire [DATA_UPPER_HALF_OFFSET-1:0] data_merge_1;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_merge_0;


biton_merge
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_merge_0
(
.data_in(data_div[ DATA_UPPER_HALF_OFFSET-1:0]),
.data_out(data_merge_0)
);


biton_merge
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_merge_1
(
.data_in(data_div[ DATA_ARRAY_MSBATA_UPPER_HALF_OFFSET]),
.data_out(data_merge_1)
);

assign data_out = {data_merge_1, data_merge_0};

end
else begin: last

assign data_out = data_div;

end
endgenerate
endmodule


module biton_reverse (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;


input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

genvar i;

generate for(i=0;i<DATA_ARRAY_SIZE;i=i+1) begin: rev
assign data_out[ (i+1)*DATA_WIDTH-1 : i*DATA_WIDTH] = data_in[
(DATA_ARRAY_SIZE-i)*DATA_WIDTH-1 : (DATA_ARRAY_SIZE-i-1)*DATA_WIDTH];
end

endgenerate
endmodule




module biton_sort (
data_in,
data_out
);

// Global parameters

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 2; // array is 2^DATA_ARRAY_SIZE_POW
elements this is equal to N for B bitonic sort operator


// Local parameters
// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}
parameter DATA_ARRAY_SIZE = (1<<DATA_ARRAY_SIZE_EXP); // array is
2^DATA_ARRAY_SIZE_POW elements
parameter DATA_ARRAY_MSB = (DATA_ARRAY_SIZE * DATA_WIDTH) -1;

parameter DATA_ARRAY_SIZE_EXP_M1 = DATA_ARRAY_SIZE_EXP-1;


parameter DATA_UPPER_HALF_OFFSET = DATA_WIDTH * (DATA_ARRAY_SIZE>>1);

input [DATA_ARRAY_MSB:0] data_in;
output [DATA_ARRAY_MSB:0] data_out;

// ===============

wire [DATA_ARRAY_MSB:0] data_conq;




generate

if(DATA_ARRAY_SIZE_EXP>1) begin: nest

wire [DATA_UPPER_HALF_OFFSET-1:0] data_sort_1;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_sort_0;

wire [DATA_UPPER_HALF_OFFSET-1:0] data_rev_0;
wire [DATA_UPPER_HALF_OFFSET-1:0] data_rev_1;


biton_sort
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_sort_0
(
.data_in(data_in[ DATA_UPPER_HALF_OFFSET-1:0]),
.data_out(data_sort_0)
);


biton_reverse
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_reverse_1_0
(
.data_in(data_in[ DATA_ARRAY_MSBATA_UPPER_HALF_OFFSET]),
.data_out(data_rev_0)
);


biton_sort
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_sort_1
(
.data_in(data_rev_0),
.data_out(data_rev_1)
);


biton_reverse
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP_M1)
)
biton_reverse_1_1
(
.data_in(data_rev_1),
.data_out(data_sort_1)
);



assign data_conq = {data_sort_1, data_sort_0};

end
else begin: last

assign data_conq = data_in;

end

endgenerate


biton_merge
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_merge_1
(
.data_in(data_conq),
.data_out(data_out)
);

endmodule




module system;

parameter DATA_WIDTH = 4;
parameter DATA_ARRAY_SIZE_EXP = 3; // array is 2^DATA_ARRAY_SIZE_POW
elements

// ==================

// data organized in following way:
// single long vector: { data3[3:0], data2[3:0], data1[3:0],
data0[3:0]}

parameter DATA_ARRAY_MSB = (1<<DATA_ARRAY_SIZE_EXP) * DATA_WIDTH -1;

wire [DATA_ARRAY_MSB:0] data_in = {4'h1, 4'h3, 4'h5, 4'h2, 4'hf, 4'hb,
4'h0, 4'ha };
wire [DATA_ARRAY_MSB:0] data_out;



biton_sort
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_sort_1
(
.data_in(data_in),
.data_out(data_out)
);

/*

biton_merge
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_merge_1
(
.data_in(data_in),
.data_out(data_out)
);

biton_bn
#(
.DATA_WIDTH(DATA_WIDTH),
.DATA_ARRAY_SIZE_EXP(DATA_ARRAY_SIZE_EXP)
)
biton_bn_1
(
.data_in(data_in),
.data_out(data_out)
);
*/

endmodule

 

Andy,

Thanks for hdcaml version!
I guess you win - yours is definitely shorter

To my defense I have to say that I deliberatly did not use +: notation
(we have found those breaking the Xilinx synthesis).
Array ports would also help with tersness (but that's SystemVerilog)

Also I could dispute that hdcaml verison is still recursive
(merge calls itself) but then iterative verison was for masochists
anyway .

Thanks,
Przemek



Andy Ray wrote:

PS For you viewing pleasure:
the bitionic sort implemented in Verilog 2001 with recursive
instantiation.

I leave the iterative version as an excercise for the reader



I'll take you up on that !

The output is verilog with no recursion (or iteration for that matter).

Cheers,

Andy

(* ocamlc -o bitonic.exe hdcaml.cma bitonic.ml *)

open Hdcaml
open Design
open List

(*
inputs:
sort_fn : (> unsigned sort up; (< unsigned sort down;
(>+) signed sort up; (<+) signed sort down
pipeline: (fun x->x) combinatorial; (reg ena) pipelined
inputs : list of inputs (must be power of two)
vld_in : input valid signal
returns:
list of sorted outputs, output valid signal
*)
let bitonic_sort sort_fn pipeline inputs vld =

let asc = const "1" in
let dsc = const "0" in

(* split list into two halves *)
let halve_list l =
let rec s0 l0 l1 =
if (length l0) = (length l1) then l0, l1
else s0 (l0 @ [hd l1]) (tl l1) in
s0 [] l in

let compare a b dir =
let c = dir ==: (sort_fn a b) in
pipeline (mux2 c b a), pipeline (mux2 c a b) in

let rec merge l dir vld =
if (length l) > 1 then
let l0,l1 = halve_list l in
let l0,l1 = split (map2
(fun a b -> compare a b dir) l0 l1) in
let l0,v0 = merge l0 dir (pipeline vld) in
let l1,_ = merge l1 dir (const "0") in
(l0@l1), v0
else l, vld in

let rec sort l dir vld =
if ((length l) > 1) then
let l0,l1 = halve_list l in
let s0,v0 = (sort l0 asc vld) in
let s1,_ = (sort l1 dsc vld) in
merge (s0@s1) dir v0
else l, vld in

sort inputs asc vld

let _ =
start_circuit "bitonic";
(* let inputs = map (fun x -> input ("i" ^ (string_of_int x)) 4)
[ 0; 1; 2; 3; 4; 5; 6; 7 ] in *)
let inputs = map (fun x -> const x)
[ "0001"; "0011"; "0101"; "0010";
"1111"; "1011"; "0000"; "1010" ] in
let outputs, vld_out = bitonic_sort (> (fun x -> x)
inputs (const "0") in
iter2 (fun x y -> output ("o" ^ (string_of_int y)) x) outputs
[0;1;2;3;4;5;6;7];
let circuit = get_circuit () in
Verilog.output_netlist circuit