Author Topic: Determine whether a binary number is of power of two in verilog code  (Read 1370 times)

0 Members and 1 Guest are viewing this topic.

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #50 on: October 02, 2019, 11:17:31 pm »
Regarding if's (even though I use VHDL, but I'm sure this yields the same results), there are interesting things to realize.

Talking about how "dumb" synthesis tools can be...
Even with Synplify (which is not half bad), you'll run into this. You'll find out that in MOST cases where you use a "if", synthesis will yield a priority encoder, even when it's obvious by design that the if sequence could be perfectly replaced with a simple logic equation instead (without any priority needed). Which is sometimes pretty inefficient.

Long story short: avoid "if" when you can. Sure it may look elegant. But tools are dumb. Yeah definitely. ;D

One simple example: implementing look-up for the above test.

Here are two examples I tested. They are, from a logic POV, strictly identical. One will yield a structure with a priority encoder though, for no useful reason, and take almost twice as many LUTs. ::)

Code: [Select]
if rising_edge(Clk) then
bIsPowerOfTwo <= false;

for i in 0 to (DataWidth - 1) loop
if nWordIn = to_unsigned(2**i, nWordIn'length) then
bIsPowerOfTwo <= true;
exit;
end if;
end loop;
end if;

and:

Code: [Select]
if rising_edge(FPGA_Clk) then
bIsPowerOfTwo <= false;

for i in 0 to (DataWidth - 1) loop
bIsPowerOfTwo <= bIsPowerOfTwo or (nWordIn = to_unsigned(2**i, nWordIn'length));
end loop;
end if;

The last one, you figured it, is the one that yields the better implementation, although again, I don't think it formally should make a difference.
And this last one, actually, as simple as it is (one of the simplest approaches!), yields a rather compact structure, almost as fast as the adder tree one.

 
The following users thanked this post: promach

Offline BrianHG

  • Super Contributor
  • ***
  • Posts: 2959
  • Country: ca
Re: Determine whether a binary number is of power of two in verilog code
« Reply #51 on: October 03, 2019, 12:37:08 am »
Yes, using those loops would yield the same results and are far superior for large numbers of bits.  Note that I write things out the way I do so I may insert exceptions or alternate conditions as I work since a routine like this I may use in first to arrive style interrupt controller where I may have specific priority conditions to add.

As for using the IF, within there I may also clear or increment a timer/position counter or add additional flags.

I tend to operate best at a low level, near the silicon and how my compiler tool likes to partition logic & unfortunately I started with a very early 2000s Quartus 1 which I had to learn to tease every little FMax out of it as working with things like video image processing and ram controller on an APEX FPGA, or Cyclone 1 at 150MHz speeds took quite a little miracle touch.  (Yes, I started out with AHDL which couldn't synth loops, yet had some quick tricks when comparing addresses like using 'x's inside the compared bit-fields as 'don't care' bits.)  (Talk about system crashes when your code became too elegant as well.)

Today, this is obsolete as higher level programming will synthesize just fine and my techniques now only may serve as beginner teaching aids or for special circumstances like forcing a FPGA suite to implement a node literally with a degree of certainty.
« Last Edit: October 03, 2019, 12:43:07 am by BrianHG »
__________
BrianHG.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #52 on: October 03, 2019, 04:24:10 pm »
Today, this is obsolete as higher level programming will synthesize just fine and my techniques now only may serve as beginner teaching aids or for special circumstances like forcing a FPGA suite to implement a node literally with a degree of certainty.

Yup, and it makes the overall code much more readable and easier to maintain.
But, as I just showed above, there can be some pitfalls that are not necessarily obvious (those cases that make you think "why is the tool soo dumb?").
That said, and as I mentioned earlier, as long as the end-result meets your requirements, there's no need to really bother. Over-optimizing is a waste of time, and can be risky.
 

Offline MorgothCreator

  • Contributor
  • Posts: 13
  • Country: ro
Re: Determine whether a binary number is of power of two in verilog code
« Reply #53 on: October 06, 2019, 10:33:16 am »
Use LUT's like asynchronous memory, for 5 input LUT you be able to feed 5 bits from the word, on two LUT you feed 10 bit, from 2 LUT up you use a second stage LUT so you can feed up to 25 bit, 5 LUT first stage, 1 second stage, and so on, from 26 bit up you need 3 stage LUT cascaded and you can go up to 125 bit with 3 stage LUT cascaded.
Is the fastest way, because you are limited on LUT inputs number, if you want to work on very high frequency you can pipeline these stages that is very simple, because is a simple logic you can compose it at low level.
If you use high level formulas you will end up with some monster schematic :)
« Last Edit: October 06, 2019, 10:34:54 am by MorgothCreator »
 

Offline promach

  • Frequent Contributor
  • **
  • Posts: 272
  • Country: us
Re: Determine whether a binary number is of power of two in verilog code
« Reply #54 on: October 07, 2019, 04:38:48 am »
Quote
if rising_edge(FPGA_Clk) then
   bIsPowerOfTwo <= false;
   
   for i in 0 to (DataWidth - 1) loop
      bIsPowerOfTwo <= bIsPowerOfTwo or (nWordIn = to_unsigned(2**i, nWordIn'length));
   end loop;
end if;

@SiliconWizard

I understand DataWidth , but what are nWordIn and length ?

Could you post the code for signals declaration ?
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #55 on: October 07, 2019, 12:35:15 pm »
Quote
if rising_edge(FPGA_Clk) then
   bIsPowerOfTwo <= false;
   
   for i in 0 to (DataWidth - 1) loop
      bIsPowerOfTwo <= bIsPowerOfTwo or (nWordIn = to_unsigned(2**i, nWordIn'length));
   end loop;
end if;

@SiliconWizard

I understand DataWidth , but what are nWordIn and length ?

Could you post the code for signals declaration ?

DataWidth was a generic (constant) to define the register width in bits (probably obvious).
nWordIn is of type unsigned here (typically: 'unsigned(DataWidth -1 downto 0);' )

If the input "Word" is a std_logic_vector and you want to directly use that, you could also write the following instead:

"Word = std_logic_vector(to_unsigned(2**i, nWordIn'length))"

(I just prefer to use the "numeric" types in VHDL if there's going to be any kind of operation on them, and cast from/to std_logic only when required.)

'length is a VHDL attribute that gives the "length" of the corresponding object (unsigned are arrays, so that's the number of bits here). It's handy to write reusable code. Here, it would be equivalent to DataWidth.

"to_unsigned(2**i, nWordIn'length)"  is a handy way of expressing a power of two constant (2^i) of the width of nWordIn in a generic way. It's entirely processed at compile time. Dunno how to write this in Verilog. It may be possible; or you may have to write hard-coded constants instead? (Don't know...)

Likewise, the "for" loop here is entirely processed at compile time. It's the equivalent of hand-writing "xxx or yyy or zzz or..." but in a more compact, and generic way. No need to rewrite anything if you just change the bit width.
 

Offline NorthGuy

  • Super Contributor
  • ***
  • Posts: 1774
  • Country: ca
Re: Determine whether a binary number is of power of two in verilog code
« Reply #56 on: October 07, 2019, 01:25:25 pm »
Quote
if rising_edge(FPGA_Clk) then
   bIsPowerOfTwo <= false;
   
   for i in 0 to (DataWidth - 1) loop
      bIsPowerOfTwo <= bIsPowerOfTwo or (nWordIn = to_unsigned(2**i, nWordIn'length));
   end loop;
end if;

I see you're switching to VHDL :)

This code will not work. When you assign multiple times within the same block, only the last assignment survives.

You need to create a variable and then use ":=" instead of "<=" to do the accumulation. Once you've done this, you assign the variable to the signal.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #57 on: October 07, 2019, 02:01:44 pm »
Quote
if rising_edge(FPGA_Clk) then
   bIsPowerOfTwo <= false;
   
   for i in 0 to (DataWidth - 1) loop
      bIsPowerOfTwo <= bIsPowerOfTwo or (nWordIn = to_unsigned(2**i, nWordIn'length));
   end loop;
end if;

I see you're switching to VHDL :)

This code will not work. When you assign multiple times within the same block, only the last assignment survives.

You need to create a variable and then use ":=" instead of "<=" to do the accumulation. Once you've done this, you assign the variable to the signal.

Sorry about that. The "if" version worked though - due to the if structure in the for loop.
I just copied it to write this "or" version, a bit too fast. Sorry about the fuckup. (For my tests, I actually wrote functions instead of putting the code directly in the process, so that was indeed correct. Moral: avoid posting illustrative code you haven't tested, or be prepared to apologize. ::) )

Due to the assignment using the previous value of bIsPowerOfTwo in the OR operation, it could actually lead to a pretty nasty behavior.
SORRY again.  :horse:

The right version would be:

Code: [Select]
PowerOfTwo: process (Reset, Clk)
variable b : boolean;
begin
if rising_edge(Clk) then
if Reset = '1' then
bIsPowerOfTwo <= false;
else
b := false;

for i in 0 to (DataWidth - 1) loop
b := b or (nWordIn = to_unsigned(2**i, nWordIn'length));
end loop;

bIsPowerOfTwo <= b;
end if;
end if;
end process;
« Last Edit: October 07, 2019, 02:14:21 pm by SiliconWizard »
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #58 on: October 07, 2019, 02:28:25 pm »
As a bonus, I'll post the function I used to implement my "dedicated adder" structure. So far, it's the fastest approach I tested while being the smallest in LUTs (for a 100% generic HDL approach - of course you can do better with more hand-tweaking). It reaches ~262MHz.

Note that it's a recursive function, which will naturally yield a tree structure.

Code: [Select]
type PowerOfTwo_t is
record
bPowerOfTwo, bCarry : boolean;
end record;

(...)

function IsPowerOfTwo(w : unsigned) return PowerOfTwo_t is
variable iMid : integer;
variable sPowerOfTwo, sPowerOfTwo1, sPowerOfTwo2 : PowerOfTwo_t;
variable bCarry : boolean;
begin
if w'length > 2 then
iMid := w'low + w'length / 2;

sPowerOfTwo1 := IsPowerOfTwo(w(w'high downto iMid));
sPowerOfTwo2 := IsPowerOfTwo(w((iMid - 1) downto w'low));

bCarry := sPowerOfTwo1.bCarry or sPowerOfTwo2.bCarry;

sPowerOfTwo.bPowerOfTwo := (not bCarry) and (sPowerOfTwo1.bPowerOfTwo xor sPowerOfTwo2.bPowerOfTwo);
sPowerOfTwo.bCarry := bCarry or (sPowerOfTwo1.bPowerOfTwo and sPowerOfTwo2.bPowerOfTwo);
else
sPowerOfTwo.bPowerOfTwo := ((w(w'low) xor w(w'high)) = '1');
sPowerOfTwo.bCarry := ((w(w'low) and w(w'high)) = '1');
end if;

return sPowerOfTwo;
end IsPowerOfTwo;

-- Can be used like so: bIsPowerOfTwo <= IsPowerOfTwo(nWordIn).bPowerOfTwo;

It shows: how you can use functions (even recursive here), and how you can use records to, for instance, return compound values from functions.

Disclaimer: from my tests and design, it should be correct. Don't hesitate to state if you can find bad corner cases.

 

Offline promach

  • Frequent Contributor
  • **
  • Posts: 272
  • Country: us
Re: Determine whether a binary number is of power of two in verilog code
« Reply #59 on: October 07, 2019, 02:57:00 pm »
Quote
         for i in 0 to (DataWidth - 1) loop
            b := b or (nWordIn = to_unsigned(2**i, nWordIn'length));
         end loop;

Just a moment, variable b is 1-bit , but nWordIn is not 1-bit.

How can you perform an OR operation between two of them ?
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 3189
  • Country: fr
Re: Determine whether a binary number is of power of two in verilog code
« Reply #60 on: October 07, 2019, 06:20:59 pm »
Quote
         for i in 0 to (DataWidth - 1) loop
            b := b or (nWordIn = to_unsigned(2**i, nWordIn'length));
         end loop;

Just a moment, variable b is 1-bit , but nWordIn is not 1-bit.

How can you perform an OR operation between two of them ?

It's actually a boolean OR between two booleans here (and not between 'b' and 'nWordIn'!): 'b', and the equality test 'xx = yy', the result of which is a boolean. ('xx' and 'yy' do have the same type.)
 

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2031
  • Country: nz
Re: Determine whether a binary number is of power of two in verilog code
« Reply #61 on: October 07, 2019, 08:52:30 pm »
I would have thought that the optimal way would be to look at the underlying FPGA architecture, find the biggest width LUT that it supports in a single slice (8 bits on Xilinx 7-series logic), then just compress 8 bits  down to two (00 = no bits, 01 = one bit, 11 = more than one bit, apologies for the VHDL):

case testvalue_8_bits is
 when "00000000" => result <= "00";
 when "00000001" => result <= "01";
 when "00000010" => result <= "01";
 when "00000100" => result <= "01";
 when "00001000" => result <= "01";
 when "00010000" => result <= "01";
 when "00100000" => result <= "01";
 when "01000000" => result <= "01";
 when "10000000" => result <= "01";
 when others         => result <= "11";
end case;

Have as many of these as you need for the width of your input, concatenate the "result" outputs together and repeat, until you get down to two bits. A bit like numerology to find your birth number  ::)


That would be one slice and level of logic for values up to 8 bits, two levels of logic and 18 slices for 32-bit values, and three levels of logic for values up to 256 bits.

I would have guessed it to be about the same resource usage but much faster as the original (x &(x-1)==0), and without the corner-cases for 0 and 1.
« Last Edit: October 07, 2019, 08:54:33 pm by hamster_nz »
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Offline NorthGuy

  • Super Contributor
  • ***
  • Posts: 1774
  • Country: ca
Re: Determine whether a binary number is of power of two in verilog code
« Reply #62 on: October 08, 2019, 03:04:32 pm »
... find the biggest width LUT that it supports in a single slice (8 bits on Xilinx 7-series logic)

The muxes which make the 8-input LUT out of the slice are slow. Using them may be slower than using LUTs from other slices.
 
The following users thanked this post: SiliconWizard

Offline TomS_

  • Frequent Contributor
  • **
  • Posts: 326
  • Country: gb
Re: Determine whether a binary number is of power of two in verilog code
« Reply #63 on: October 09, 2019, 12:46:30 pm »
right shift the number and check the LSB
count the "1" bits
check the count if it is not One the number is not power of two.

There are more elegant ways to count 1's that dont involve testing every single bit. Thats how I used to do it, but then I thought there has to be a better way and did some searching around...

For example, you can use a lookup table if you have the storage to hold that table, or something like Brian Kernighan’s Algorithm which will only loop n times, where n is the number of set bits - its quite ingenious really, if its worthwhile to implement in an FPGA.
 
The following users thanked this post: promach, ucanel

Offline Someone

  • Super Contributor
  • ***
  • Posts: 2103
  • Country: au
Re: Determine whether a binary number is of power of two in verilog code
« Reply #64 on: October 09, 2019, 08:44:54 pm »
right shift the number and check the LSB
count the "1" bits
check the count if it is not One the number is not power of two.
There are more elegant ways to count 1's that dont involve testing every single bit. Thats how I used to do it, but then I thought there has to be a better way and did some searching around...
You do have to test every single bit, there is no way around that. It only comes down to a speed vs size vs code readability/reusability trade off as is common in most FPGA algorithms. Higher end tools can help make those more automatic/directed but it is still testing all bits.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf