implementing even-odd merge sort in fpga using vhdl

[Dave Fontes]

hi guys,

i want to implement the even-odd merge sort in a fpga using vhdl, 16 numbers of 32 bits each, as input, but the problem is, i really down understand how does this sorting algorithm works, or it's suppose to work, can anyone help me ?

 

[TrickyDicky]

A quick google can be very helpfull:
https://www.google.co.uk/search?q=e...j7&sourceid=chrome&espv=210&es_sm=93&ie=UTF-8

 

[Dave Fontes]

i already have done that, i'm getting a strange warning on my code

WARNING:Xst:1290 - Hierarchical block <stage3[3].group1_stage3> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[3].check1_stage3.group2stage3> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check2stage3.finalComp> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].check2stage3.finalComp> is unconnected in block <sort8items>.
It will be removed from the design.

and i dont understand why, i made my code for 8 inputs of 4 bits each, and i run with no problem, but when i changed to 32 bits, i got this warnings, and the program doesn't work :S

 

[ads-ee]

Then instead of saying:

but the problem is, i really down understand how does this sorting algorithm works, or it's suppose to work, can anyone help me ?

You should ask an appropriate question about the errors you are experiencing and POST the CODE. We aren't a group of psychics that can read your mind. Go to the "Psychics EDA forum" for that. ;-)

WARNING:Xst:1290 - Hierarchical block <stage3[3].group1_stage3> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[3].check1_stage3.group2stage3> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check2stage3.finalComp> is unconnected in block <sort8items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].check2stage3.finalComp> is unconnected in block <sort8items>.
It will be removed from the design.

Giving us a bunch of warnings from XST isn't going to allow us to help as we don't know what is in sort8items, do you expect us to guess?
Uhhh, concentrating really hard I see your problem is on line 456, now go fix it. ;-)

Maybe you should do a search on "How to ask questions". It might make things go smoother next time.

Regards

 

[Dave Fontes]

sorry, i really didnt think it through.

i have change the code a little bit but i keep getting the same warnings (in a greater scale) ,

my top level program :

---

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use std.textio.all;                 -- this library has to be used
use ieee.std_logic_textio.all;  -- this library has to be used
 
use work.set_of_data_items.all; 
 
entity teste is
--generic ( M                   : integer := 4;
--              N                   : integer := 16 );
  Port (        seg: out STD_LOGIC_VECTOR(6 downto 0);
                an: out STD_LOGIC_VECTOR(7 downto 0);
                clk: in STD_LOGIC   );
end teste;
 
architecture Behavioral of teste is
    
    --metodo para ler valores de um ficheiro
        impure function read_array (input_data : in string) return set_of_16items is    --metodo para ler do ficheiro                                               
            file        my_file     : text is in input_data;                       
            variable    line_name   : line;                                 
            variable    a_name    : set_of_16items;                                      
            begin                                                        
                for i in set_of_8items'range loop                                  
                    readline (my_file, line_name);                             
                    read (line_name, a_name(i));                                  
                end loop;                                                     
                return a_name;                                                  
            end function; 
 
signal array_name   :  set_of_16items := read_array("data.txt");     --nome do ficheiro
signal array1           : set_of_16items;
signal first_set,second_set: set_of_8items;
 
signal val1,val2,val3,val4,val5,val6,val7,val8: std_logic_vector(3 downto 0);
begin
 
first_set<=(array_name(0),array_name(1),array_name(2),array_name(3),array_name(4),array_name(5),array_name(6),array_name(7));
second_set<=(array_name(8),array_name(9),array_name(10),array_name(11),array_name(12),array_name(13),array_name(14),array_name(15));
 
val8<=array1(15)(31 downto 28);
val7<=array1(15)(27 downto 24);
val6<=array1(15)(23 downto 20);
val5<=array1(15)(19 downto 16);
val4<=array1(15)(15 downto 12);
val3<=array1(15)(11 downto 8);
val2<=array1(15)(7 downto 4);
val1<=array1(15)(3 downto 0);
 
sort16items:    entity work.merge16to16
                        port map(first_set,second_set,array1);
            
DispCont: entity work.EightDisplayControl
                port map(clk,val1,val2,val3,val4,val5,val6,val7,val8,an,seg);                   
 
end Behavioral;

---

my 8to8merge module:

---

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
 
use work.set_of_data_items.all; 
 
entity merge8to8 is
--generic (     M                   : integer := 4;
--                  N                   : integer := 8 );
  port (        unsorted_items  : in set_of_8items;
                sorted_items    : out set_of_8items);
end merge8to8;
 
architecture Behavioral of merge8to8 is
 
signal out1_in2, out2_in3, out3_in4 : set_of_8items;
signal out4_in5, out5_in6, sorted   : set_of_8items;
 
begin
 
stage1:
        for i in N/2-1 downto 0 generate
            group1stage1:   entity work.Comparator
                                port map(unsorted_items(i*2),unsorted_items(i*2+1),out1_in2(i*2),out1_in2(i*2+1));
        end generate stage1;
 
stage2:
        for i in N/4-1 downto 0 generate
            on_stage2:
                        for j in 0 to N/4-1 generate
                        group1stage2:   entity work.Comparator
                                            port map(out1_in2(i*4+j),out1_in2(i*4+j+2),out2_in3(i*4+j),out2_in3(i*4+j+2));
                        out3_in4(i*4+j*3) <= out2_in3(i*4+j*3);
            end generate on_stage2;
 
            group2stage2:   entity work.Comparator
                                port map(out2_in3(i*4+1),out2_in3(i*4+2),out3_in4(i*4+1),out3_in4(i*4+2));
            end generate stage2;
 
stage3:
        for i in N/2-1 downto 0 generate
            group1_stage3:
                            entity work.Comparator
                                    port map(out3_in4(i),out3_in4(i+4),out4_in5(i),out4_in5(i+4));
            
            check1_stage3:  if(i>=2 and i<=3) generate
                            group2stage3:   entity work.Comparator
                                                port map(out4_in5(i),out4_in5(i+2),out5_in6(i),out5_in6(i+2));
            end generate;
            group3stage3:   if(i<2) generate
                            out5_in6(i)<=out4_in5(i);
                            out5_in6(i+6)<=out4_in5(i+6);
                            sorted_items(i*7)<= out5_in6(i*7);
            end generate;
            check2stage3:   if(i <N /2-1 ) generate
                            finalComp:  entity work.Comparator
                                            port map(out5_in6(i*2+1),out5_in6(i*2+2),sorted_items(i*2+1),sorted_items(i*2+2));
            end generate;
        end generate stage3;
end behavioral;

---

and warnings:

Xst:1290 - Hierarchical block <stage2[1].on_stage2[0].group1stage2> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[0].on_stage2[0].group1stage2> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[0].group1_stage3> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[1].group2stage2> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[0].group2stage2> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check1_stage3.group2stage3> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].group1_stage3> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].group1_stage3> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[3].check1_stage3.group2stage3> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[0].check2stage3.finalComp> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].check2stage3.finalComp> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check2stage3.finalComp> is unconnected in block <sort8items1>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[1].on_stage2[0].group1stage2> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[0].on_stage2[0].group1stage2> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[0].group1_stage3> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[1].group2stage2> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage2[0].group2stage2> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check1_stage3.group2stage3> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].group1_stage3> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].group1_stage3> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[3].check1_stage3.group2stage3> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[0].check2stage3.finalComp> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[1].check2stage3.finalComp> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage3[2].check2stage3.finalComp> is unconnected in block <sort8items2>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[7].step1stage4.group2stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[6].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[6].step1stage4.group2stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[6].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[5].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[5].step1stage4.group2stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[5].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[4].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[4].step1stage4.group2stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[4].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[3].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[3].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[2].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[2].step3stage4.incide_stage4[0].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[2].step3stage4.incide_stage4[1].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[2].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[1].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[1].step3stage4.incide_stage4[0].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[1].step3stage4.incide_stage4[1].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[1].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[0].group1stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[0].step3stage4.incide_stage4[0].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[0].step3stage4.incide_stage4[1].group3stage4> is unconnected in block <sort16items>.
It will be removed from the design.
WARNING:Xst:1290 - Hierarchical block <stage4[0].step5stage4.step5stage4> is unconnected in block <sort16items>.
It will be removed from the design.

if necessary , i will post here the 16to16merge module.
thanks in advance

 

[TrickyDicky]

The main problem appears to be your lack of understanding of VHDL. VHDL is a hardware description language, not a programming language.
You need to realise than instantiating components is like putting chips on a circuit board. You havent shown all the code. Are you using teste as the top level? this has no inputs that connect to the design, just constants - so all the logic can be removed.

I highly suggest starting again after learning about digital logic design. Your design has 0 pipelining, which will be a massive problem.

 

[Dave Fontes]

Thanks for the answer!

Yes im using teste as my top level module, it makes sense, since im reading values from a ".txt" file , you see, when i use 4 bits for the word size, the modules synthesize with no problem, but when i change the word size to 32 bits, all this warnings show up :S

but when the synthesizer remove the blocks (left them unconnected) this affects the logic in my program ..

 

[TrickyDicky]

I suggest taking a step back and drawing out the logic before writing any code. it is a description language after all - if you dont know what you're describing, or what the tool will produce, you should not be writing the VHDL.

 

[Dave Fontes]

Ok im gonna try that, it's the first time i work with vhdl, so sorry for any dumb questions, any way thanks for the support