HDL problem: find the first bit equal to zero, and set it to one

[legacy]

so, you have a vector of 1024 bit (it might be 4x bigger), they are initially all zero, and sometimes, inside a process, you need to find the lower bit set to zero, and once found you need to set it to one.

It's like find the first bit equal to zero, and set it to one so it will be skipped on future searches.

it's 1024 bit, how could you implement it in a decent way?
As a giant circuit made on the cascade of "IF" vector(x) branches ? 


edit:
OT but interesting: some ISA supports ffs, even if their implementation is 32bit/64bit. Here I need the circuit for a different purpose. Happy to know that also MIPS comes with something similar.

Code: [Select]

MIPS clz Count Leading Zeros in Word 32, 64 clz input size
MIPS clo Count Leading Ones in Word 32, 64 clo input size


[filssavi]

You need to provide more informations if you want more precise answers.

That said assuming that by hdl you mean hardware description language, and thus FPGA there is more than One way to skin this Digital cat  if resource usage is a problem you can do this by setting up a pipeline that fetches data from a dual porta ram,  lsb to msb, compares It and makes necessary changes and if necessary writes them back

If speed Is the focus i'd divide and conquer, so split the Vector in smaller chunks, do as above on the chunks once you are Shure you found the lowest 0 bit in the lowest chunks stop the process

[legacy]

Usually I prefer vhdl. I am planning a design for a small fpga.

Code: [Select]

procedure find_first_set
(
   v              : in bit_vector;
   found          : out boolean;
   first_set_index: out natural
)
     is
begin
  for index in v'range
    loop
      if v(index)
         then
           found           := true;
           first_set_index := index;
           return;
         end if;
    end loop
  found := false;
end procedure;

Something like this works on the paper as well as on simulators, I have some doubt about the implementation.

I have to use it in a clocked process

Code: [Select]

process(clk)
begin
  if rising_edge(clk) then
    find_first_set(...
  end if;
end process;

Where clk needs to be around 100MHz (it's 33Mhz x3, using a PLL) on a Spartan3E-250 device.

[legacy]

I can relax a constraint: "find_first_set" can use a first clock's edge, and bit_set can stay on a second one.

[NorthGuy]

If speed Is the focus i'd divide and conquer

Divide is certainly the way to go. If you split the vector in half and do the analysis for each half separately you'll get:

found1, first_set_index1 - for the LS half
found2, first_set_index2 - for the MS half.

Now:

Code: [Select]

if found1 = '1' then
  found <= '1';
  first_set_index(first_set_index'left) <= '0';
  first_set_index(first_set_index'left-1 downto 0) <= first_set_index1;
else
  found <= found2;
  first_set_index(first_set_index'left) <= '1';
  first_set_index(first_set_index'left-1 downto 0) <= first_set_index2;
end if

And so you continue dividing until you get to the array of size 1 which is trivial.

This will give you 10 logic levels which is Ok for 100 MHz. It'll be quite big though.

[marshallh]

If you need single cycle it will require a lot of combinational logic. Otherwise you can just usea counter and shift by 1 bit every clock, until you find hte bit, modify, it and shift everything back until the counter resets.

[hamster_nz]

Isn't what you are describing a long shift register, initially set to all zero, and then ones shifted in from one end (or you can look at it as the lowest zero bit being set)

Or am I missing something?

[legacy]

If you need single cycle

constraint: find and set has be within two clock edges.

[legacy]

Isn't what you are describing a long shift register

Well, it looks more like a giant priority encoder than a shift register.
And I cannot shift one bit per clock edge 

[legacy]

it will require a lot of combinational logic

exactly the feeling I had 

[NorthGuy]

Isn't what you are describing a long shift register, initially set to all zero, and then ones shifted in from one end (or you can look at it as the lowest zero bit being set)

Or am I missing something?

As I understand, there's a 1024-bit register. You scan it from one end. When (if) you find '1', you replace it with '0' and stop.

[legacy]

This will give you 10 logic levels which is Ok for 100 MHz. It'll be quite big though.

Thanks, good idea

Perhaps I'd better switch to a bigger fpga, like S3-500. I have to check the whole project utilization, currently it's just a proof, I mean the project is composed by different modules, a lot of them haven't yet been analyzed, therefore I don't know the current logic utilization, but now I know the "find the first" module will consume a lot of logic.

[legacy]

As I understand, there's a 1024-bit register. You scan it from one end. When (if) you find '1', you replace it with '0' and stop.

yes, but you cannot "scan"

Scanning implies that you check one bit per rising clock edge: it can't be applied to my problem, since I need to find the first bit equal to zero in a vector of 1024-bit  ... within one clock rising edge. As constraint the search mustn't take more than one clock, and the bit-set to 1 mustn't take more than one clock, in other words the whole mustn't take more than two clock rising edges.

[hamster_nz]

Isn't what you are describing a long shift register, initially set to all zero, and then ones shifted in from one end (or you can look at it as the lowest zero bit being set)

Or am I missing something?

As I understand, there's a 1024-bit register. You scan it from one end. When (if) you find '1', you replace it with '0' and stop.

so, you have a vector of 1024 bit (it might be 4x bigger), they are initially all zero,

0000... ...0000

and sometimes, inside a process, you need to find the lower bit set to zero, and once found you need to set it to one.

After each sometimes:

0000... ...0001
0000... ...0011
0000... ...0111
0000... ...1111
...
0001... ...1111
0011... ...1111
0111... ...1111
1111... ...1111

Looks like a shift register to me. 

Either that or we are not being told the whole story

[NorthGuy]

Looks like a shift register to me. 

I assumed the register is modified by other means too, so the regular shift pattern will eventually dissipate.

[legacy]

Either that or we are not being told the whole story

ummm, yup 

Forgot to say that sometimes another process needs to reset the bit in the vector to zero, and since you can't assume any predefined scheme it's like it was a random process which re-sets bit to zero randomly, therefore the shift-register-scheme is broken.

[hamster_nz]

Smallest/slowest answer is something like

Set up a chain from high to low, checking for when the first zero is seen.

   all_zeros(1023) <= NOT vector(n);
   for n in 0 to 1022 loop;
       all_zeros(n) <= all_zeros(n+1) AND NOT vector(n);
   end loop;

...and then leave the tools to optimize it for the underlying architecture (they will most likely do a poor job )
   
During the update just set the bit
   if rising_edge(clk) and something = '1' then
     vector(0) <= '1';
     for n in 1 to 1023 loop
        vector(n) <= vector(n) OR (all_zeros(n) AND vector(n-1));
     end loop;
   end;

There is no way getting around it, that the new state for bit one depends on the state of all other bits in the vector. Somehow the state from the 1023 other bits must fan in to allow it to be updated.

If you need to do that in one cycle the best you can do is celling(log(1024)/log(LUT width)) levels of LUTs...

...unless you also maintain a vector of "this block of n bits is all zeros" alongside the main one, allowing you to move some of the work a cycle earlier.

[Flip-Flop]

Try something like this:

Code: [Select]

Process(clk)
Variable a, b, c : unsigned(1024 downto 0);
Begin
   If rising_edge(clk) then
      a := unsigned('0' & vector);
      b := a + 1;
      c := not a and b; -- contains a one at the position of the first zero
      vector_out <= vector xor c(1023 downto 0); -- Toggle first zero
   End if;
End process;


[kmike]

You clould shift the register to the right with 0s and to the left with 1s.

edit:
Like this: (may contain errors  )
shift_reg <= shift_reg(REGSIZE-1 downto 0) & '1'
shift_reg <= '0' & shift_reg(REGSIZE downto 1)

Br,
mike

[Gribo]

Is that 1024 bit vector a status register for lots of other processes?

[Kalvin]

You might be able to reduce the complexity by creating for example 32  identical macroblocks with 32 bits each. Each block will output 1 if any of its input bits are zero, and the bit position of the zero value bit (5 bits). With some simple decoding you should be able to do the tricks you want to perform with decent propagation delay.

[legacy]

@Kalvin
good trick, I think I will follow your idea 

[legacy]

Is that 1024 bit vector a status register for lots of other processes?

yes it's a status register, but only two processes are involved with it.

[Gribo]

So, let me understand it, one process is filling the vector with bits at an unknown rate, the other is emptying it, again, at an unknown rate?

[JacobPilsen]

It sounds (very similar) like "Flash ADC" to me.
Don't you know how "highest 1 of 1024" to "binary number" is implemented: