VHDL Code for Bitonic Sorter

Bitonic Sorter is one kind of Sorting Algorithm. This algorithm invented by Ken Batcher. You can find more detail about this algorithm over here.

Bitonic Sorter

Above figure tells you about algorithm of Bitonic Sorter. In this each coloured block is kind of sorter and sorts two values. Arrow shows towards high value. In this it is given for sixteen inputs.

Simplified Bitonic Sorter

Above figure is a simplified version of Bitonic Sorter. In this dark yellow colored and light red colored box are sorters, those are either sorting down or sorting up.

In our design we will use sorting down sorter means higher values will be at low place and lower values will be at high place. Output of each sorter assign as stage1_op, stage2_op etc. Output of each sorter block will act as a input to second sorter block.

• Simple Sorter Design Code

library ieee;
use ieee.std_logic_1164.all;
use IEEE.STD_LOGIC_ARITH.ALL; 
use IEEE.STD_LOGIC_UNSIGNED.ALL;

entity sort is
port (a : in signed (7 downto 0);
   b : in signed (7 downto 0);
   sort_op_up : out signed (7 downto 0);
   sort_op_down : out signed (7 downto 0));
end sort;

architecture beh of sort is
begin

process(a,b)
begin
 if (a > b) then
  sort_op_up <= b;
  sort_op_down <= a;
 else
  sort_op_down <= b;
  sort_op_up <= a;
 end if;
end process;

end beh;

• Bitonic Sorter Design Code using Above Sorter Code

library ieee;
use ieee.std_logic_1164.all;
use IEEE.STD_LOGIC_ARITH.ALL; 
use IEEE.STD_LOGIC_UNSIGNED.ALL;

package bus_input_pkg is
        type bus_array is array(15 downto 0) of signed (7 downto 0);
end package;

library ieee;
use ieee.std_logic_1164.all;
use IEEE.STD_LOGIC_ARITH.ALL; 
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use work.bus_input_pkg.all;

entity top_sort is
port (input : in bus_array;
   output : out bus_array);
end top_sort;

architecture structural of top_sort is
component sort is
port (a : in signed (7 downto 0);
   b : in signed (7 downto 0);
   sort_op_up : out signed (7 downto 0);
   sort_op_down : out signed (7 downto 0));
end component;

signal stage1_op,stage2_op,stage3_op,stage4_op,stage5_op,stage6_op,stage7_op,stage8_op,stage9_op : bus_array;

begin
-------------------------------------------------------------------------------------------
gen_reg0: for i in 0 to 7 generate
 sort1 : sort port map (input(2*i),input((2*i)+1),stage1_op(2*i),stage1_op((2*i)+1));
end generate gen_reg0;
-------------------------------------------------------------------------------------------
gen_reg1: for i in 0 to 3 generate
 sort2 : sort port map (stage1_op(4*i),stage1_op((4*i)+3),stage2_op(4*i),stage2_op((4*i)+3));
 sort3 : sort port map (stage1_op((4*i)+1), stage1_op((4*i)+2), stage2_op((4*i)+1), stage2_op((4*i)+2));
end generate gen_reg1;

gen_reg2: for i in 0 to 7 generate
 sort4 : sort port map (stage2_op(2*i),stage2_op((2*i)+1),stage3_op(2*i),stage3_op((2*i)+1));
end generate gen_reg2;
-------------------------------------------------------------------------------------------
gen_reg3: for i in 0 to 1 generate
 sort5 : sort port map (stage3_op(8*i), stage3_op((8*i)+7),stage4_op(8*i), stage4_op((8*i)+7));
 sort6 : sort port map (stage3_op((8*i)+1), stage3_op((8*i)+6),stage4_op((8*i)+1), stage4_op((8*i)+6));
 sort7 : sort port map (stage3_op((8*i)+2), stage3_op((8*i)+5),stage4_op((8*i)+2), stage4_op((8*i)+5)); 
 sort8 : sort port map (stage3_op((8*i)+3), stage3_op((8*i)+4),stage4_op((8*i)+3), stage4_op((8*i)+4));
end generate gen_reg3;

gen_reg4:for i in 0 to 3 generate
 sort9 : sort port map (stage4_op(4*i), stage4_op((4*i)+2),stage5_op(4*i), stage5_op((4*i)+2));
 sort10 : sort port map (stage4_op((4*i)+1), stage4_op((4*i)+3),stage5_op((4*i)+1), stage5_op((4*i)+3));
end generate gen_reg4;

gen_reg5:for i in 0 to 7 generate
 sort11 : sort port map (stage5_op(2*i), stage5_op((2*i)+1),stage6_op(2*i), stage6_op((2*i)+1));
end generate gen_reg5;
-------------------------------------------------------------------------------------------
gen_reg6: for i in 0 to 7 generate
 sort12 : sort port map (stage6_op(i), stage6_op((i+15)-(2*i)),stage7_op(i), stage7_op((i+15)-(2*i)));
end generate gen_reg6;

gen_reg7: for i in 0 to 3 generate
 sort13 : sort port map (stage7_op(i), stage7_op(i+4),stage8_op(i), stage8_op(i+4));
 sort14 : sort port map (stage7_op(i+8), stage7_op(i+12),stage8_op(i+8), stage8_op(i+12));
end generate gen_reg7;

gen_reg8:for i in 0 to 7 generate
 even_generate :if (i=0 or i=2 or i=4 or i=6) generate
  sort15 : sort port map (stage8_op(2*i), stage8_op((2*i)+2),stage9_op(2*i), stage9_op((2*i)+2));
 end generate even_generate;
 
 odd_generate :if (i=1 or i=3 or i=5 or i=7) generate
  sort16 : sort port map (stage8_op((2*i)-1), stage8_op((2*i)+1),stage9_op((2*i)-1), stage9_op((2*i)+1));
 end generate odd_generate;
end generate gen_reg8;

gen_reg9:for i in 0 to 7 generate
 sort17 : sort port map (stage9_op(2*i), stage9_op((2*i)+1), output(2*i), output((2*i)+1));
end generate gen_reg9;
-------------------------------------------------------------------------------------------
end structural;