Efficiently compare set of numbers to find the greatest one

[nabla101]

How can I write a vhdl module, which when given a set of numbers (Either unsigned int, or std logic vector), will find the greatest one in the least amount of clock ticks?

[eteam00]

First, design the hardware you need.  You can use a computer, a spreadsheet, a software language, or a pencil and paper.

Next, learn VHDL language and translate your hardware design to VHDL code.

- Bob Elkind

[awillen]

• Is the size of the set of numbers fixed, or does it vary during runtime?
• Is only cycle latency a concern, or do you care about the clock period as well?

Adrian

[eilert]

Hi,

just a hint:

if the Input numbers come in sequentially, you just have to store the greater one and discard the rest.

Such you get the final result one clock after the last number on your input, with minimal logic requirements.

Nice homework idea, maybe I can find a way to "torment" our  students with it as well. :-)

Have a nice synthesis

  Eilert

[nabla101]

Awillen, the number size will be fixed (8-bit std_logic_vector) during runtime, and I'm mainly concerned about cycle latency, but I'm using a 100MHz clock, so I'm not sure if that is high enough for me to need to worry about the clock period as well?

Eilert, thanks, I can easily write an algorithm for this in c...something like:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int array_size;
  printf("Find minimum of array\n");
  printf("Enter array size:");
  scanf("%d", &array_size);
  int array[array_size];

  int i;
  for(i=0;i<array_size;i++){
    printf("Enter array element %d:",i);
    scanf("%d", &array[i]);
  }

  printf("\nArray is:\n");
  for(i=0;i<array_size;i++){
    printf("element %d = %d\n",i, array[i]);
  } 

  int minimum = array[0];
  for(i=0;i<array_size;i++){
    if(array[i]<minimum) minimum = array[i]; 
  }  

  printf("\n\nMinimum value = %d\n", minimum);

  system("PAUSE");	
  return 0;
}

So I understand that it if the next number in the sequence is greater than the current stored value, then it becomes the new stored value (Although the above finds minimum value, the idea is the same), but I'm just finding it very hard to translate this to VHDL, especially where I'm worrying about minimising the time taken to process a calculation.

[eilert]

Hi,

so you already got the idea.  In VHDL it looks almost the same.

Only question is about the interface. In C you can work on an array using an index.

In hardware it's a little different. Your data is either constantly streaming, or stored in a RAM, that needs to be addressed.

The magnitude compare operation in hardware takes some LUTs. But if you are concerned about timing you can use pipelinig to improve fmax. This can be done automatically by adding extra register stages to the process. With the register balancing option enabled, these are absorbed into the logic in order to improve the timing. (remember to set proper clock constraints in your UCF file)

I give you an example for a streaming solution, If you want to use some RAM array you can put that stage in a separate process and feed this process with the RAM values.

find_min: process (reset,clk) is

begin

  if reset = '1' then    -- async. reset for power on (net can be tied to low for synthesis)

   minimum <= (others => '1'); -- initialized with the highest possible value

  -- pipe_reg1 <= (others => '1');

  --  more pipe regs...

  -- pipe_regN <= (others => '1');

  elsif rising_edge(clk) then

  -- pipe_reg1 <= data_in;  -- if you are using the pipeline

   -- ... 

  -- if pipe_reg N < minimum then -- if you are using the pipeline

    if data_in < minimum then

      minimum <= data_in;

    end if;

  end if;

  -- at the beginning of a calculation use "init" to flush the pipeline synchronously

  -- signals are overwritten with init value if neccessary, that's VHDL ;-)

  if init = '1' then

     minimum <= (others => '1');

    -- pipe_reg1 <= (others => '1');

    --  more pipe regs...

    -- pipe_regN <= (others => '1');

 end if

end process find_min;

So, this should give you a starting point to experiment with some simulation and synthesis.

Also: latency and delay are two different things!

A big combinatorical circuit can cause a high delay, thus reducing fmax of the system.

A pipeline with N register stages causes a latency of N clock periods.

But if you have a good balance between combinatorical stuff and pipeline registers the time wasted by latency can be shorter than what's caused by delay without pipelining.

Also, of you have some continuous calculation, (e.g. in filters) you get a new result on every clock cycle after the initial time caused by latency.

Now you have a lot to work on.

Have a nice synthesis.

  Eilert

[nabla101]

Hi Eilert, thanks alot. I tried to write some vhdl for it while I was waiting for a reply. It looks like this:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

-- Uncomment the following library declaration if using
-- arithmetic functions with Signed or Unsigned values
--use IEEE.NUMERIC_STD.ALL;

-- Uncomment the following library declaration if instantiating
-- any Xilinx primitives in this code.
--library UNISIM;
--use UNISIM.VComponents.all;

entity mode_decision is
    Port ( data_in : in  STD_LOGIC_VECTOR (7 downto 0);
           clk : in  STD_LOGIC;
           rst : in  STD_LOGIC;
           en : in  STD_LOGIC;
           decision_out : out  STD_LOGIC_VECTOR (3 downto 0);
           complete : out  STD_LOGIC;
           mode_select : out  STD_LOGIC_VECTOR (3 downto 0));
end mode_decision;

architecture Behavioral of mode_decision is

	constant no_of_modes : integer := 4;

begin

	minimum : process(clk, rst)

		variable minimum : integer := 0;
		variable mode_slct : integer := 0;

	begin
		if rst = '1' then
			minimum := 0;
			mode_slct := 0;
		elsif (clk'event and clk = '1') then
			if en = '1' then
				mode_slct := 0;				
				minimum := data_in;								-- sae of mode 0
				for i in 1 to no_of_modes-1 loop
						mode_slct := i;
						if (data_in < minimum) then
							minimum := data_in;
							decision_out := mode_slct;
						end if;
				end loop;
			end if;
		end if;
	end process minimum;		

end Behavioral;

I just wanted to show you this, so I could compare it with the example you've given, since I'm really struggling getting my head round all the endless different types and operations that can be used in vhdl.

In my code I defined minimum as an integer variable. In your code have you defined it (And all the pipe registers) as vhdl 

signals  (since you use '<=' instead of ':=') of type STD_LOGIC_VECTOR?

I realise my code won't work since I am comparing STD_LOGIC_VECTOR to a type integer, and trying to make assignments with the two different types, so I got error messages when trying to synthesize. My next step was to figure out conversion between STD_LOGIC_VECTOR and integer (in particular unsigned integer) types, because I thought you could only use comparisons such as checking for minimum or maximum of two operands with integer types and not STD_LOGIC_VECTOR, since this type has no concept of greater or lesser to vhdl? i.e. Where you have used:

 -- if pipe_reg N < minimum then -- if you are using the pipeline
    if data_in < minimum then

these must be integer, and cannot be type STD_LOGIC_VECTOR? 

Also I have a question about the pipelining registers you have used. Is the idea that you can read a new value into one register from the input data stream, and compare the values in two other registers (to find their minimum) both in the same clock tick, instead of having to read a value into a register, and then compare values on the next clock tick? So if you have a large set of data which you want to perform the comparison over (e.g. finding the minimum of every 10 consecutive bytes of data from the incoming data stream), you could effectively halve the number of clock ticks needed?

[eilert]

Hi,

you have reviewed my code very well. Good job.

Still you have to learn some fundamental things about VHDL.

First of all: The process shows no type declarations at all. (That's the mean thing with code snippets, they are incomplete)

Your assumption about using std_logic_vector may be right or wrong.

That depends on the libraries used.

In your code you find

 use IEEE.NUMERIC_STD.ALL;

Uncomment this line and read about what's in that line.

Amongst many other nice things it defines the type UNSIGNED.

Signals and variables of this type can be treated (almost) like SLV.

The library provides arithmetic, logic and other functions for unsigned and signed data.

Most of it works also in conjunction with integer signals or variables.

Now about your code.

First: Better avoid the use of bare integers. They are limited to 32 bit datawith, and without restriction always unneccessarily use these, so logic ressources may be wasted.

If you urgently need to use this type (e.g. for indexing purposes) you should define them like this:

e.g.:

signal count : natural range 0 to 255;  -- defines an unsigned integer with 8 bits width.

variable sum: integer range -1000 to + 1000; -- defines a signed integer, 11 bits wide with extra range checking

In numeric_std you also find various conversion functions between integer and signed/unsigned types.

Conversion to SLV can be done with simple casting.

e.g.:

 If you have some result declared as unsigned and want to assign it ot a SLV signal or port just write:

outport <= std_logic_vector(result);

Also: Ports are always assigned like signals so all your output assignments are wrong.

they must be written like this:

mode_selct <= std_logic_vector(to_unsigned(i,4);

And, yes, it is possible to assign variables to signals and vice versa.

BUT: variables and signals behave different in a process.

Now you already have something to work on, I think.

I'm not going to comment your thougths about the pipelining registers yet.

First read (e.g. in this forum) about the concept of pipelining and its benefits and consequences for hardware designs.

Your ideas are not really wrong, but they lead to something completely different.

Have a nice synthesis

  Eilert

[gmortimer@ferrari.it]

test

[gmortimer@ferrari.it]

This is a plea for help, too, From a stupid old man from the world of software, in which iteration is not manufacturing. I am tired, and cannot easily see what is in front of my eyes.

Would somebody please, tell me why this code, intended to create a comparator tree for the purpose of finding the largest of 21 16-bit values, causes a syntax error ate the end loop; statement shown in red?

Sarcasm, scorn and bullying would be most welcome, also concerning the style. As an Engineer, of many years, It has always served me well, as a medium of tuition.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
 
entity RTLTD_SLV_PIPELINE_SEARCH is
--Pipeline search, log(n)+1 clocks, n-1 comparators if data size is power of 2;
--Not to be used until thoroughly tested, it has not been!
 
  generic (
    C_MAX_DATA_SIZE : integer := 64;
    C_DATA_SIZE     : integer := 21
    );
   
  port (
    aclk            : in  std_logic; --usual
    aresetn         : in  std_logic  --culprits
    );
     
end RTLTD_SLV_PIPELINE_SEARCH;
     
architecture arch_imp of RTLTD_SLV_PIPELINE_SEARCH is

  type T_DATA  is array(C_DATA_SIZE-1   downto 0) of integer range 0 to 65535;
  type T_INDEX is array(C_DATA_SIZE / 2 downto 0) of integer range 0 to MAX_DATA_LENGTH - 1;
  type T_STATE is (ST_IDLE, ST_SRCH);
  signal state      : T_STATE;
  signal idx        : T_INDEX;
  signal data_in    : T_DATA;
  signal ps_reset   : std_logic; -- soft reset from, usually, my control register interface
  signal find_min   : std_logic; -- '1' to find smallest
  signal start_f    : std_logic; -- single cycle start pulse
  signal done_f     : std_logic; -- single cycle end pulse
  signal srch_idx   : integer range 0 to C_DATA_SIZE - 1; --result of search
  signal length     : integer range 0 to C_DATA_SIZE / 2; --used in algorithm
 
begin

 
search : process( aclk )
  begin
    if (rising_edge( aclk )) then
      if (( aresetn = '0' ) or ( ps_reset = '1' )) then
        state   <= ST_IDLE;
        done_f  <= '0';
      else
        case state is
          when ST_IDLE =>
            done_f <= '0';
            
            if (start_f = '1') then
              length <= shift_right(data'length, 1); --if odd we lose a value so must check it at the end
              for i in shift_right(data'length ,1) downto 0 loop idx(i) <= i; end loop;
              state <= ST_SRCH;
            end if;
          
          when ST_SRCH =>
            for i in (length - 1) downto 0 loop
              if ((data_in(idx(i + i)) > data_in(idx(i + i + 1))) xor (find_min = '1')) then idx(i) <= idx(i + i); else idx(i) <= idx(i + i + 1);
            end loop;
 
            if (length > 1) then
              length <= shift_right(length, 1);
            else
              srch_idx  <= idx(0);
              --check for odd length
              if ((data_in'length and 1) = 1) then
                if ((data_in(data_in'length-1) > data_in(idx(0))) xor (find_min = '1')) then srch_idx <= data_in'length-1;
              end if;
              done_f    <= '1';
              state     <= ST_IDLE;
            end if;
        
          when others =>
            null;
        
        end case;
      end if;
    end if;
  end process;
 
end arch_imp;

[gmortimer@ferrari.it]

I now think I know. It is difficult to construct a means of comparing things, if it is not known what they are. The indexed comparison, it cannot be done! At least without some considerable wiring! Typical software thinking! An array element would need to have a means of comparing itself with any other. Dear me! I hope my clients don't here about this!

[gmortimer@ferrari.it]

Well, I do at least have the consolation of having seen it for myself. That algorithm would have needed any element of the array to compare itself with any other. A sort of general switching network. Ha ha ha! That which is elegant in software, is quite the opposite, in hardware, in fact it is the dapper exchanges itself with the criminal!

[geoffbarnes]

Missing "end if"?