Tran Nguyen Minh Tuan
Reputation: 9
Sorting network in VHDL
I am writing a basic program to realize the sorting algorithm in this link Network for N=5, using Bose-Nelson Algorithm.
I compare two numbers by using comb.vhd component, the top entity of my program is in the code below.
I have no problem when I compile using Quartus, but when I use modelsim to simulate RTL, the output is always 0000, no matter what the inputs are.
I think that I misunderstood the use of signals, but I have no clue where it goes wrong.
Following is the main section of my program, the signals I am using are:
SIGNAL out0_temp, out1_temp, out3_temp, out4_temp : bit_vector (3 downto 0); --comp1(0,1),comp2(3,4)
SIGNAL out2_temp, out4_1_temp : bit_vector (3 downto 0); --comp3(2,4)
SIGNAL out2_1_temp, out3_1_temp, out1_1_temp, out4_2_temp : bit_vector (3 downto 0); --comp4(2,3),comp5(1,4)
SIGNAL out0_1_temp, out3_2_temp : bit_vector (3 downto 0); --comp6(0,3)
SIGNAL out0_2_temp, out2_2_temp, out1_2_temp, out3_3_temp : bit_vector (3 downto 0); --comp7(0,2),comp8(1,3)
SIGNAL out1_3_temp, out2_3_temp : bit_vector (3 downto 0); --comp9(1,2)
As showing in the algorithm, I am using 9 comparisons to sort inputs from the largest to smallest as below:
BEGIN
comp1:comp -- (0,1)
PORT MAP (clk,reset, in0, in1, out0_temp, out1_temp);
comp2:comp -- (3,4)
PORT MAP (clk,reset, in3, in4, out3_temp, out4_temp);
comp3:comp -- (2,4)
PORT MAP (clk,reset, in2, out4_temp, out2_temp, out4_1_temp);
comp4:comp -- (2,3)
PORT MAP (clk,reset, out2_temp, out3_temp, out2_1_temp, out3_1_temp);
comp5:comp -- (1,4)
PORT MAP (clk,reset, out1_temp, out4_1_temp, out1_1_temp, out4_2_temp);
comp6:comp -- (0,3)
PORT MAP (clk,reset, out0_temp, out3_1_temp, out0_1_temp, out3_2_temp);
comp7:comp -- (0,2)
PORT MAP ( clk,reset, out0_1_temp, out2_1_temp, out0_2_temp, out2_2_temp);
comp8:comp -- (1,3)
PORT MAP ( clk,reset, out1_1_temp, out3_2_temp, out1_2_temp, out3_3_temp);
comp9:comp -- (1,2)
PORT MAP ( clk,reset, out1_2_temp, out2_2_temp, out1_3_temp, out2_3_temp);
out0 <= out0_2_temp;
out1 <= out1_3_temp;
out2 <= out2_3_temp;
out3 <= out3_3_temp;
out4 <= out4_2_temp;
END ARCHITECTURE behav;
Comp.vhd module
--Comp.vhd module is used to compare 2 numbers and switch them if th
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
ENTITY comp IS
PORT (
clk : IN std_logic;
reset : IN bit;
num0_in : IN bit_vector (3 DOWNTO 0);
num1_in : IN bit_vector (3 DOWNTO 0);
num0_out : OUT bit_vector (3 DOWNTO 0);
num1_out : OUT bit_vector (3 DOWNTO 0)
);
END ENTITY comp;
ARCHITECTURE compare OF comp IS
BEGIN
PROCESS (clk, reset)
BEGIN
-- reset everything to '0' when reset is asserted
IF (reset = '1') THEN
-- num0_out <= (OTHERS => '0');
--num1_out <= (OTHERS => '0');
ELSIF (rising_edge (clk)) THEN
-- num0_in is smaller than num1_in, so switch them
IF (num0_in < num1_in) THEN
num0_out <= num1_in;
num1_out <= num0_in;
-- num0_in and num1_in are in order
ELSE
num0_out <= num0_in;
num1_out <= num1_in;
END IF;
END IF;
END PROCESS;
END ARCHITECTURE compare;
Upvotes: 0
Views: 1417
Answers (2)
user1155120
Reputation:
Well, see here is the rub. I used your declarations and created the missing bits, and started before you posted your COMP.vhd:
entity comp is
port (
clk: in bit;
reset: in bit;
in0: in bit_vector (3 downto 0);
in1: in bit_vector (3 downto 0);
out0: out bit_vector (3 downto 0);
out1: out bit_vector (3 downto 0)
);
end entity;
architecture foo of comp is
begin
comparison:
process (clk, reset)
variable GT: bit;
begin
if in0 > in1 then
GT := '1';
else
GT := '0';
end if;
if reset = '1' then
out0 <= (others => '0');
out1 <= (others => '0');
elsif clk'event and clk = '1' then
if GT = '1' then
out0 <= in0;
out1 <= in1;
else
out0 <= in1;
out1 <= in0;
end if;
end if;
end process;
end architecture;
entity bose is
port (
clk: in bit;
reset: in bit;
in0: in bit_vector (3 downto 0);
in1: in bit_vector (3 downto 0);
in2: in bit_vector (3 downto 0);
in3: in bit_vector (3 downto 0);
in4: in bit_vector (3 downto 0);
out0: out bit_vector (3 downto 0);
out1: out bit_vector (3 downto 0);
out2: out bit_vector (3 downto 0);
out3: out bit_vector (3 downto 0);
out4: out bit_vector (3 downto 0)
);
end entity;
architecture foo of bose is
signal out0_temp, out1_temp, out3_temp, out4_temp:
bit_vector (3 downto 0); --comp1(0,1),comp2(3,4)
signal out2_temp, out4_1_temp:
bit_vector (3 downto 0); --comp3(2,4)
signal out2_1_temp, out3_1_temp, out1_1_temp, out4_2_temp:
bit_vector (3 downto 0); --comp4(2,3),comp5(1,4)
signal out0_1_temp, out3_2_temp:
bit_vector (3 downto 0); --comp6(0,3)
signal out0_2_temp, out2_2_temp, out1_2_temp, out3_3_temp:
bit_vector (3 downto 0); --comp7(0,2),comp8(1,3)
signal out1_3_temp, out2_3_temp:
bit_vector (3 downto 0); --comp9(1,2)
component comp is
port (
clk: in bit;
reset: in bit;
in0: in bit_vector (3 downto 0);
in1: in bit_vector (3 downto 0);
out0: out bit_vector (3 downto 0);
out1: out bit_vector (3 downto 0)
);
end component;
begin
comp1:
comp -- (0,1)
port map (clk,reset, in0, in1, out0_temp, out1_temp);
comp2:
comp -- (3,4)
port map (clk,reset, in3, in4, out3_temp, out4_temp);
comp3:
comp -- (2,4)
port map (clk,reset, in2, out4_temp, out2_temp, out4_1_temp);
comp4:
comp -- (2,3)
port map (clk,reset, out2_temp, out3_temp, out2_1_temp, out3_1_temp);
comp5:
comp -- (1,4)
port map (clk,reset, out1_temp, out4_1_temp, out1_1_temp, out4_2_temp);
comp6:
comp -- (0,3)
port map (clk,reset, out0_temp, out3_1_temp, out0_1_temp, out3_2_temp);
comp7:
comp -- (0,2)
port map ( clk,reset, out0_1_temp, out2_1_temp, out0_2_temp, out2_2_temp);
comp8:
comp -- (1,3)
port map ( clk,reset, out1_1_temp, out3_2_temp, out1_2_temp, out3_3_temp);
comp9:
comp -- (1,2)
port map ( clk,reset, out1_2_temp, out2_2_temp, out1_3_temp, out2_3_temp);
out0 <= out0_2_temp;
out1 <= out1_3_temp;
out2 <= out2_3_temp;
out3 <= out3_3_temp;
out4 <= out4_2_temp;
end architecture;
entity bose_tb is
end entity;
architecture foo of bose_tb is
signal clk: bit := '0';
signal reset: bit := '0';
signal in0: bit_vector (3 downto 0) := x"A";
signal in1: bit_vector (3 downto 0) := x"5";
signal in2: bit_vector (3 downto 0) := x"9";
signal in3: bit_vector (3 downto 0) := x"4";
signal in4: bit_vector (3 downto 0) := x"7";
signal out0: bit_vector (3 downto 0);
signal out1: bit_vector (3 downto 0);
signal out2: bit_vector (3 downto 0);
signal out3: bit_vector (3 downto 0);
signal out4: bit_vector (3 downto 0);
begin
DUT:
entity work.bose
port map (
clk => clk,
reset => reset,
in0 => in0,
in1 => in1,
in2 => in2,
in3 => in3,
in4 => in4,
out0 => out0,
out1 => out1,
out2 => out2,
out3 => out3,
out4 => out4
);
CLOCK:
process
begin
wait for 5 ns;
clk <= not clk;
if Now > 120 ns then
wait;
end if;
end process;
STIMULIS:
process
begin
reset <= '1';
wait for 11 ns;
reset <= not reset;
wait;
end process;
end architecture;
-- Network for N=5, using Bose-Nelson Algorithm.
--
-- o--^--------^--^-----------o
-- | | |
-- o--v--------|--|--^--^--^--o
-- | | | | |
-- o-----^--^--|--v--|--|--v--o
-- | | | | |
-- o--^--|--v--v-----|--v-----o
-- | | |
-- o--v--v-----------v--------o
--
-- There are 9 comparators in this network,
-- grouped into 6 parallel operations.
--
-- [[0,1],[3,4]]
-- [[2,4]]
-- [[2,3],[1,4]]
-- [[0,3]]
-- [[0,2],[1,3]]
-- [[1,2]]
--
-- This is graphed in 8 columns.
And ended up with a working simulation:
(clickable)
The only way I found you could get all '0's out was either by an error in comp, or an error in the test bench.
And notice I picked the same comparison order you used, although using ">" and opposite comparison order.
I though the reset didn't make sense, but actually used it. And the reason it doesn't make sense is that you have to wait those 5 clocks anyway before the correct answer is guaranteed to be present.
This was done with ghdl and gtkwave.
Upvotes: 0
pwolfsberger
Reputation: 366
Since you did not provide a complete example of the code you are using to simulate, I created my own test bench using the comp entity you provided. Take a look to see if it is similar to your own:
library ieee;
use ieee.std_logic_1164.all;
entity vhdl_tb is
end vhdl_tb;
architecture testbench of vhdl_tb is
constant PERIOD : time := 100 ps;
constant TOTAL_CYCLES : natural := 400;
signal clk : std_logic := '1';
signal cycle : natural := 0 ;
signal done : boolean := false;
signal reset : std_logic := '1';
signal simclk : std_logic := '0';
SIGNAL out0_temp, out1_temp, out3_temp, out4_temp : bit_vector (3 downto 0); --comp1(0,1),comp2(3,4)
SIGNAL out2_temp, out4_1_temp : bit_vector (3 downto 0); --comp3(2,4)
SIGNAL out2_1_temp, out3_1_temp, out1_1_temp, out4_2_temp : bit_vector (3 downto 0); --comp4(2,3),comp5(1,4)
SIGNAL out0_1_temp, out3_2_temp : bit_vector (3 downto 0); --comp6(0,3)
SIGNAL out0_2_temp, out2_2_temp, out1_2_temp, out3_3_temp : bit_vector (3 downto 0); --comp7(0,2),comp8(1,3)
SIGNAL out1_3_temp, out2_3_temp : bit_vector (3 downto 0); --comp9(1,2)
signal in0 : bit_vector(3 downto 0) := "0001";
signal in1 : bit_vector(3 downto 0) := "0010";
signal in2 : bit_vector(3 downto 0) := "0011";
signal in3 : bit_vector(3 downto 0) := "0100";
signal in4 : bit_vector(3 downto 0) := "0101";
signal out0 : bit_vector(3 downto 0);
signal out1 : bit_vector(3 downto 0);
signal out2 : bit_vector(3 downto 0);
signal out3 : bit_vector(3 downto 0);
signal out4 : bit_vector(3 downto 0);
signal reset_bit : bit;
component comp is
port (
clk : IN std_logic;
reset : IN bit;
num0_in : IN bit_vector (3 DOWNTO 0);
num1_in : IN bit_vector (3 DOWNTO 0);
num0_out : OUT bit_vector (3 DOWNTO 0);
num1_out : OUT bit_vector (3 DOWNTO 0)
);
end component comp;
begin
-- The following is a process which generates a clock
-- while the unit is still under test
ClkProcess: process(done,simclk)
begin
if (not done) then
if (clk = '1') then
cycle <= cycle + 1 ;
end if ;
simclk <= not simclk after PERIOD / 2 ;
end if;
end process;
DoneProcess: process
begin
wait until (clk = '0');
wait for PERIOD * 3;
reset <= '0';
wait for PERIOD * TOTAL_CYCLES; -- Numder of cycles to execute
done <= true; -- Force the clock process to shutdown
wait; -- This waits forever
end process ;
clk <= not simclk;
-----------------------------------------------------------------
-- Test section
-----------------------------------------------------------------
reset_bit <= to_bit(reset);
comp1:comp -- (0,1)
PORT MAP (clk,reset_bit, in0, in1, out0_temp, out1_temp);
comp2:comp -- (3,4)
PORT MAP (clk,reset_bit, in3, in4, out3_temp, out4_temp);
comp3:comp -- (2,4)
PORT MAP (clk,reset_bit, in2, out4_temp, out2_temp, out4_1_temp);
comp4:comp -- (2,3)
PORT MAP (clk,reset_bit, out2_temp, out3_temp, out2_1_temp, out3_1_temp);
comp5:comp -- (1,4)
PORT MAP (clk,reset_bit, out1_temp, out4_1_temp, out1_1_temp, out4_2_temp);
comp6:comp -- (0,3)
PORT MAP (clk,reset_bit, out0_temp, out3_1_temp, out0_1_temp, out3_2_temp);
comp7:comp -- (0,2)
PORT MAP ( clk,reset_bit, out0_1_temp, out2_1_temp, out0_2_temp, out2_2_temp);
comp8:comp -- (1,3)
PORT MAP ( clk,reset_bit, out1_1_temp, out3_2_temp, out1_2_temp, out3_3_temp);
comp9:comp -- (1,2)
PORT MAP ( clk,reset_bit, out1_2_temp, out2_2_temp, out1_3_temp, out2_3_temp);
out0 <= out0_2_temp;
out1 <= out1_3_temp;
out2 <= out2_3_temp;
out3 <= out3_3_temp;
out4 <= out4_2_temp;
end testbench;
These are the results I got using modelsim:
The code you've provided appears to work. So I would conclude your issue is with your simulation test bench.
Things to look out for:
- Make sure
clkis defined in your test bench and it actually transitions...duh. - Make sure your inputs (
in0-in4) are defined and not all 0. - Ensure your
resetsignal going into your comp blocks is defined. If it is not, the outputs of your comp blocks will be remain undefined.
Upvotes: 0
Related Questions
- Fast, small area and low latency partial sorting algorithm
- Topological Graph Sorting
- Topological Sorting using Kahn's Algorithm
- Sorting a vector in VHDL
- sorting network for binary values
- bubble sort in vhdl
- Parallelized Small Network sort
- List of Comparators in Sorting Networks
- butterfly network in sorting
- Topological sorting of C++ data structures