Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
13 years ago

Funtion or something that finds the smaller integer

Hi, I'm looking for a simple way to find the smallest of a large number of integer signals (About 256)

All I have right now is just 4 and I do as the code below, but it will grow up to 256 and I think that it will not be sane to do it by this way... 


process (clkwork,reset)
  begin
  if reset='0' then
    if (clkwork'event and clkwork='1') then
      if ((TaoA<TaoB) and(TaoA<TaoC)and(TaoA<TaoD))then
        DataOut<=decodedBitA;
      elsif ((TaoB<TaoA)and(TaoB<TaoC)and(TaoB<TaoD))then
        DataOut<=decodedBitB;
      elsif ((TaoC<TaoA)and(TaoC<TaoB)and(TaoC<TaoD))then
        DataOut<=decodedBitC;
      elsif ((TaoD<TaoA)and(TaoD<TaoB)and(TaoD<TaoC))then
        DataOut<=decodedBitD;
      end if;
    end if;
  end if;
  if reset='1' then
    DataOut<='0';
  end if;
  end process;

TaoA,TaoB,TaoC,TaoD... are the integer signal

and basically the code is

if TaoA is the smaller do 'A' thing

Thanks

7 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    How fast must the decision be made to do the 'A' thing? Can you have a few cycles of delay? Is the design allowed to be pipelined? Have you considered using a RAM instead of signals?

    Sorry for the large number of questions. If possible, I would end up putting the signals into a RAM and running thru the address space to determine the lowest one. (compare, remember, move on to next address)

    If a result is needed every clock, perhaps pipelining the design so you have a result every clock with roughly 8 clocks of delay from input to output.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Ok, maybe my post has a lack of information...

    The decision has to be taken at each clock cicle because those Integers change at every clock cicle, there is no problem in take a little delay but would not like to take it if I don't have to.

    I'm not familiar with the use of a RAM in the FPGA...

    How to pipeline this? I'm not familiar with that either...

    Thanks
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    --- Quote Start ---

    Ok, maybe my post has a lack of information...

    The decision has to be taken at each clock cicle because those Integers change at every clock cicle, there is no problem in take a little delay but would not like to take it if I don't have to.

    I'm not familiar with the use of a RAM in the FPGA...

    How to pipeline this? I'm not familiar with that either...

    Thanks

    --- Quote End ---

    If your data is slow then a practical way is to run at 256 times the data rate then streamline the data and apply the algorithm:

    -- clked process

    if data < data_min then

    data_min <= data;

    end if;

    at the end of stream the value will be in data_min

    You need also to take care of signed/unsigned issues.

    edit: from where do you get 256 data at same time? Certainly not from pins. If they are generated internal to fpga then I will assume they might be streamlined already

    and you can then insert above algorithm at that point.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Try something like this: 

    process(clkwork,reset)
  begin
--first pipeline stage
  if(reset = '1') then
    pipeline1_0_result <= "0000";
  elsif (rising_edge(clkwork)) then
    if (TaoA< TaoB) then
      pipeline0_0_result <= decodedBitA;
      pipeline0_0_int <= TaoA;
    else
      pipeline0_0_result <= decodedBitB;
      pipeline0_0_int <= TaoB;
    end if;
    if (TaoC < TaoD) then
      pipeline0_1_result <= decodedBitC;
      pipeline0_1_int <= TaoC;
    else
      pipeline0_1_result <= decodedBitD;
      pipeline0_1_int <= TaoD;
    end if;
  --second pipeline stage
    if (pipeline0_0_result < pipeline0_1_result ) then
      pipeline1_0_result <= pipeline0_0_result ;
      pipeline1_0_int <= pipeline0_0_int ;
    else
      pipeline1_0_result <= pipeline0_1_result ;
      pipeline1_0_int <= pipeline0_1_int;
    end if;
  end if;
end process;

    The result is updated in pipeline1_0_result every clock with a delay.

    This is a 2 pipeline stage example using 4 inputs. I have written this long-hand to make it readable. It may be a good idea to wrap this into a for loop for ease of coding.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Apologies Kosh271 but it looks you misunderstood the problem. The issue raised was about the huge logic and coding needed for checking 256 words and it was not about timing (yet). Your solution comes with even more registers amounting to several thousands for a simple job let alone the amount of coding and logic involved.

    If the 256 data words can be streamlined (and they should be) then you don't need anything like memory or logic apart from the simple algorithm that I mentioned. Run the stream through one comparator and update final result to contain the smallest integer. Then apply reset and restart for a new stream.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Whoops, my mistake. Kaz's idea seems to fit your needs quite well. Ignore me, I'm just brain dead today.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    13 years ago

    Well... all the data is generated at 10MHz in a cyclon II FPGA, not sure if it will be available to do it at 256 times... but I think that I can implement paralel pipelines in a kind of trade-off between delay and registers for optimization, so... I think that it sounds kind of the idea of Kosh271 after all.