cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
Visitor
Visitor
19,635 Views
Registered: ‎08-04-2010

Efficiently compare set of numbers to find the greatest one

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?

0 Kudos
Reply
12 Replies
Instructor
Instructor
19,627 Views
Registered: ‎07-21-2009

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

SIGNATURE:
README for newbies is here: http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

Summary:
1. Read the manual or user guide. Have you read the manual? Can you find the manual?
2. Search the forums (and search the web) for similar topics.
3. Do not post the same question on multiple forums.
4. Do not post a new topic or question on someone else's thread, start a new thread!
5. Students: Copying code is not the same as learning to design.
6 "It does not work" is not a question which can be answered. Provide useful details (with webpage, datasheet links, please).
7. You are not charged extra fees for comments in your code.
8. I am not paid for forum posts. If I write a good post, then I have been good for nothing.
0 Kudos
Reply
Mentor
Mentor
19,610 Views
Registered: ‎11-29-2007

  • 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



Please google your question before asking it.
If someone answers your question, mark the post with "Accept as solution". If you see a particularly good and informative post, consider giving it Kudos (the star on the left).
0 Kudos
Reply
Teacher
Teacher
19,607 Views
Registered: ‎08-14-2007

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

 

Visitor
Visitor
19,548 Views
Registered: ‎08-04-2010

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.

 

0 Kudos
Reply
Teacher
Teacher
19,527 Views
Registered: ‎08-14-2007

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

 

 

Visitor
Visitor
19,516 Views
Registered: ‎08-04-2010

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?

 

 

Teacher
Teacher
19,491 Views
Registered: ‎08-14-2007

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

 

 

 

 

 

 

 

 

 

 

 

 

 

7,147 Views
Registered: ‎04-11-2016

test

0 Kudos
Reply
7,146 Views
Registered: ‎04-11-2016

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;

 

0 Kudos
Reply
4,903 Views
Registered: ‎04-11-2016

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!

0 Kudos
Reply
4,899 Views
Registered: ‎04-11-2016

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!

0 Kudos
Reply
Explorer
Explorer
4,874 Views
Registered: ‎09-07-2011

Missing "end if"?

0 Kudos
Reply