How to implement an xor tree?

B

blakaxe@gmail.com

Guest
This is a snippet of my code

always @(*)
begin
for(i=ring_length;i>0;i=i-1)
begin
if(i==ring_length) result = connect[ring_length];
else result = result ^ (connect & gen_poly);
end
end


This following statement produces a huge XOR gate with anywhere
between 0-15 inputs depending on my value of i.
result = result ^ (connect & gen_poly);

How do I make sure that it is implemented as an XOR tree with only 2
input XOR gates?

I am using the Altera Quartus synthesis tool.

Thanks
 
blakaxe@gmail.com wrote:
This is a snippet of my code

always @(*)
begin
for(i=ring_length;i>0;i=i-1)
begin
if(i==ring_length) result = connect[ring_length];
else result = result ^ (connect & gen_poly);
end
end


This following statement produces a huge XOR gate with anywhere
between 0-15 inputs depending on my value of i.
result = result ^ (connect & gen_poly);

How do I make sure that it is implemented as an XOR tree with only 2
input XOR gates?

I am using the Altera Quartus synthesis tool.

Thankl
Is this an RS encoder? You can write the same code looplessly using the
Click to expand...

unary XOR:

always@(*) result= ^(connect & gen_poly);

As for using only 2-input XOR gates: the synthesizer will optimize the
code and will surely not use 2-input XORs, which is not something you'd
want anyway because it will result in excess levels of logic. If you
really wanted a nonoptimal solution, you would have to use a 'generate'
loop and instantiate the primitives.
-Kevin
 
On Thu, 26 Jun 2008 09:24:14 -0700 (PDT), "blakaxe@gmail.com"
<blakaxe@gmail.com> wrote:

This is a snippet of my code

always @(*)
begin
for(i=ring_length;i>0;i=i-1)
begin
if(i==ring_length) result = connect[ring_length];
else result = result ^ (connect & gen_poly);
end
end


This following statement produces a huge XOR gate with anywhere
between 0-15 inputs depending on my value of i.
result = result ^ (connect & gen_poly);

How do I make sure that it is implemented as an XOR tree with only 2
input XOR gates?

I am using the Altera Quartus synthesis tool.
Click to expand...

Why do you think you need to make sure such a thing? FPGAs have multi
input lookup tables (currently 4 to 6) and your logic will be mapped
to some implementation suitable for your device. If you could get an
XOR tree made of 2 input gates to be used for your logic, it would
almost definitely be way sub-optimal. Let the synthesis tool do what
it knows how to do and worry about getting your logic right (unless of
course, you have a very specific and well defined reasoned to do
otherwise).
 
On Thu, 26 Jun 2008 09:24:14 -0700 (PDT)
"blakaxe@gmail.com" <blakaxe@gmail.com> wrote:

This following statement produces a huge XOR gate with anywhere
between 0-15 inputs depending on my value of i.
result = result ^ (connect & gen_poly);

How do I make sure that it is implemented as an XOR tree with only 2
input XOR gates?
Click to expand...

Most synthesis tools are incapable of doing exactly what you wish for
without explicit guidance. I suggest you use explicit instantiation of
xor tree structure and use /*synthesis syn_keep*/ on all
inter-connecting nets. Most designs don't need this kind of hands-on
guidance, but if you really want to have total control over the
structure of the logic, there is no other way.

--
In like a dimwit, out like a light.
-- Pogo
 
On Thu, 26 Jun 2008 09:56:43 -0700
Muzaffer Kal <kal@dspia.com> wrote:

Why do you think you need to make sure such a thing? FPGAs have multi
input lookup tables (currently 4 to 6) and your logic will be mapped
to some implementation suitable for your device. If you could get an
XOR tree made of 2 input gates to be used for your logic, it would
almost definitely be way sub-optimal. Let the synthesis tool do what
it knows how to do and worry about getting your logic right (unless of
course, you have a very specific and well defined reasoned to do
otherwise).
Click to expand...
Sometimes, these kind of designs are more desirable. Sure, most of the
time you should trust the logic synthesis tool to do the right thing,
but there are plenty of times when you really want to tight control,
even if such tight control seems "unreasonable" or "suboptimal" in your
eyes.

For example: a 16-bit XOR gate can be written like this:

assign dout = ^din[15:0];

If you pass this piece of code to most FPGA synthesis tools (xst,
synplify), they will be synthesized to cascaded 4-input XOR LUTs.
Applying some tight timing constraints, the synthesis tools might give
you a better structure, but never "optimal". Go ahead, try it yourself.

Even if the structure becomes more optimal as the timing constraint
gets tighter, here's a question: Why should the optimality of the
structure be based on the clock speed?

If the example isn't shocking enough to you, try a 64-input, or
96-input XOR tree. See what kind of logic structure your favorite logic
synthesis tool will produce :).

--
In like a dimwit, out like a light.
-- Pogo
 
blakaxe@gmail.com wrote:
Thanks guys...

I am trying to implement a combinatorial loop.
It is a ring oscillator with a few taps just like an LFSR (replace the
registers with not gates.. )
As it is a combinatorial loop the logic is not certain.
I just know the structure.

I know that the design would be sub optimal.. but I got to do this
this way

And thanks Kevin, I used
always@(*) result= ^(connect & gen_poly); instead of the loop

I guess I'll use the 'generate' statement and will instantiate 2 input
xor gate primitives...

post your comments if you have any more ideas

Thanks
Making ring oscillators is tough because the synthesizer and the mapper
Click to expand...
both really want to optimize away the logic. You can do it with the
right amount of directives. As Jason suggested, maybe you can use
syn_keep attributes instead of instantiating the primitives and this
will create the logic you want. But the mapper (at least in a Xilinx
flow) will also wish to prune this loop so you may need some sort of
"don't remove" constraints.
-Kevin
 
Thanks guys...

I am trying to implement a combinatorial loop.
It is a ring oscillator with a few taps just like an LFSR (replace the
registers with not gates.. )
As it is a combinatorial loop the logic is not certain.
I just know the structure.

I know that the design would be sub optimal.. but I got to do this
this way

And thanks Kevin, I used
always@(*) result= ^(connect & gen_poly); instead of the loop

I guess I'll use the 'generate' statement and will instantiate 2 input
xor gate primitives...

post your comments if you have any more ideas

Thanks
 
blakaxe@gmail.com wrote:
Thanks guys...

I am trying to implement a combinatorial loop.
It is a ring oscillator with a few taps just like an LFSR (replace the
registers with not gates.. )
As it is a combinatorial loop the logic is not certain.
I just know the structure.

I know that the design would be sub optimal.. but I got to do this
this way

And thanks Kevin, I used
always@(*) result= ^(connect & gen_poly); instead of the loop

I guess I'll use the 'generate' statement and will instantiate 2 input
xor gate primitives...

post your comments if you have any more ideas

Thanks
Click to expand...
Keep in mind that "xor" primitives may not map directly to LEs either.
A ring oscillator type structure needs severe control that synthesis
and map tools aren't always ready to allow. If you can instantiate
the Altera atom directly, that might be the better way to go. In
Xilinx I'd use LUT primitives. Even specifying syn_keep attributes in
the Synplify synthesizer left logic that the mapper had problems
keeping in place. In some instances it may have taken even further
convincing the mapper software to keep things from optimizing away at
that level.

Experiment and talk to the Altera apps folks - for something this
specific and extreme, the Altera knowledge on this forum may be
limited.

- John_H
 
On Jun 26, 3:11 pm, John_H <newsgr...@johnhandwork.com> wrote:
blak...@gmail.com wrote:
Thanks guys...

I am trying to implement a combinatorial loop.
It is a ring oscillator with a few taps just like an LFSR (replace the
registers with not gates.. )
As it is a combinatorial loop the logic is not certain.
I just know the structure.

I know that the design would be sub optimal.. but I got to do this
this way

And thanks Kevin, I used
always@(*) result= ^(connect & gen_poly);  instead of the loop

I guess I'll use the 'generate' statement and will instantiate 2 input
xor gate primitives...

post your comments if you have any more ideas

Thanks

Keep in mind that "xor" primitives may not map directly to LEs either.
A ring oscillator type structure needs severe control that synthesis
and map tools aren't always ready to allow.  If you can instantiate
the Altera atom directly, that might be the better way to go.  In
Xilinx I'd use LUT primitives.  Even specifying syn_keep attributes in
the Synplify synthesizer left logic that the mapper had problems
keeping in place.  In some instances it may have taken even further
convincing the mapper software to keep things from optimizing away at
that level.

Experiment and talk to the Altera apps folks - for something this
specific and extreme, the Altera knowledge on this forum may be
limited.

- John_H
Click to expand...

I have implemented simple ring oscillators in Xilinx ISE earlier.
The synthesizer tries to optimize the logic.

To solve this problem use the ISE synthesis attribute
(* keep = "true" *) wire [length-1:0] connect;
This will prevent the wires between not gates from getting optimized

In Quartus its (*keep*) wire [length-1:0] connect;

I have also mapped the not gate logic to LUTs in Xilinx ISE using

LUT1 #(
.INIT(2'b01) // Specify LUT Contents
) LUT1_inst1 (
.O(connect[0]), // LUT general output
.I0(connect_fb) // LUT input
);

But have never done it on Altera FPGAs or using synplify pro systhesis
tools.

Thanks
 
On Jun 26, 5:37 pm, "blak...@gmail.com" <blak...@gmail.com> wrote:
On Jun 26, 3:11 pm, John_H <newsgr...@johnhandwork.com> wrote:



blak...@gmail.com wrote:
Thanks guys...

I am trying to implement a combinatorial loop.
It is a ring oscillator with a few taps just like an LFSR (replace the
registers with not gates.. )
As it is a combinatorial loop the logic is not certain.
I just know the structure.

I know that the design would be sub optimal.. but I got to do this
this way

And thanks Kevin, I used
always@(*) result= ^(connect & gen_poly);  instead of the loop

I guess I'll use the 'generate' statement and will instantiate 2 input
xor gate primitives...

post your comments if you have any more ideas

Thanks

Keep in mind that "xor" primitives may not map directly to LEs either.
A ring oscillator type structure needs severe control that synthesis
and map tools aren't always ready to allow.  If you can instantiate
the Altera atom directly, that might be the better way to go.  In
Xilinx I'd use LUT primitives.  Even specifying syn_keep attributes in
the Synplify synthesizer left logic that the mapper had problems
keeping in place.  In some instances it may have taken even further
convincing the mapper software to keep things from optimizing away at
that level.

Experiment and talk to the Altera apps folks - for something this
specific and extreme, the Altera knowledge on this forum may be
limited.

- John_H

I have implemented simple ring oscillators in Xilinx ISE earlier.
The synthesizer tries to optimize the logic.

To solve this problem use the ISE synthesis attribute
(* keep = "true" *) wire [length-1:0] connect;
This will prevent the wires between not gates from getting optimized

In Quartus its (*keep*) wire [length-1:0] connect;

I have also mapped the not gate logic to LUTs in Xilinx ISE using

LUT1 #(
.INIT(2'b01) // Specify LUT Contents
) LUT1_inst1 (
.O(connect[0]), // LUT general output
.I0(connect_fb) // LUT input
);

But have never done it on Altera FPGAs or using synplify pro systhesis
tools.

Thanks
Click to expand...
I have also kept the gates from getting optimized by using
(*preserve*) in Quartus as shown below

generate
genvar k;
for (k=0; k<ring_length; k=k+1)
begin : ring_0
(*preserve*) not not_00(connect[k+1],connect[k]);
end
endgenerate

John, what is the Altera "atom"?
 
blakaxe@gmail.com wrote:
<snip>
I have also kept the gates from getting optimized by using
(*preserve*) in Quartus as shown below

generate
genvar k;
for (k=0; k<ring_length; k=k+1)
begin : ring_0
(*preserve*) not not_00(connect[k+1],connect[k]);
end
endgenerate
Click to expand...
Oh - so you solved your problem already. Cool.

John, what is the Altera "atom"?
Click to expand...
http://www.altera.com/support/software/nativelink/quartus2/glossary/def_atom.html

It seems my view of logic mapping to Atoms in Quartus as logic maps to
LUTs in ISE may not translate to instantiating Atoms the way one
instantiates LUTs. Atoms might only be generated by Quartus and not
available as input to the tool. That extremely low level of WYSIWG
control has been helpful in ISE. Quartus? Hmmm....

- John_H

- John
 
On Jun 26, 12:20 pm, Jason Zheng <Xin.Zh...@jpl.nasa.gov> wrote:
On Thu, 26 Jun 2008 09:56:43 -0700

Muzaffer Kal <k...@dspia.com> wrote:
Even if the structure becomes more optimal as the timing constraint
gets tighter, here's a question: Why should the optimality of the
structure be based on the clock speed?
Click to expand...

That depends on how you define optimal. In terms of speed, yes, I want
the synthesis tool to quit, and not waste any more of my time when it
has a solution that meets timing (perhaps with some margin). If I make
the timing constraint more difficult to meet, then the synthesis tool
will have to work harder to meet it, but only then. Do you keep
looking for your car keys after you find them?

If there are other constraints, such as resources consumed, and it
fits, then I expect the same behavior as above. Same with power, etc.,
but only if those constraints are given.

Andy
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top