Bubblesort

Hier jetzt mal eine Umsetzung des allseits bekannten Bubblesort-Algorithmus in VHDL.
Zuerst die rein kombinatorische Variante:

library IEEE;
use IEEE.STD_LOGIC_1164.all;

package BSTypes is
  type BSData_Typ is array (0 to 9) of integer range 0 to 127;
end BSTypes;

package body BSTypes is
end BSTypes;




library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use work.bstypes.all;

entity Bubblesort is
    Port ( di  : in  BSData_Typ;
           do  : out BSData_Typ );
end Bubblesort;

architecture Behavioral of Bubblesort is
begin

   process (di) 
   variable din  : BSData_Typ;
   variable temp : integer;
   variable n    : integer;
   variable oncemore : boolean;
   begin
      din      := di;
      n        := din'length;
      oncemore := TRUE;
      while oncemore = TRUE and n > 1 loop
         oncemore := FALSE;
         for i in 0 to din'length-2 loop
            if din(i) > din(i+1) then 
               temp     := din(i);   -- Dreieckstausch
               din(i)   := din(i+1);
               din(i+1) := temp;
               oncemore := TRUE;
            end if;
         end loop;
         n := n-1;
      end loop;
      do <= din;
   end process;
   
end Behavioral;

In einem Spartan 3 FPGA braucht diese Lösung abhängig vom Abbruch (über die Variable oncemore) unterschiedlich viele Ressourcen:
Mit Abbruch:      Number of Slices  1293         Number of 4 input LUTs 2272
Ohne Abbruch:   Number of Slices  976           Number of 4 input LUTs 1701

Der offensichtlichste Unterschied ist, dass der in der Software effizientere Abbruch (wenn das Array schon vor Ablauf aller Kombinationen schon komplett sortiert ist) in der Hardware nur Nachteile mit sich bringt.

Nachfolgend eine getaktete Lösung, die auf Kosten der Rechenzeit deutlich weniger Ressourcen braucht. Bubblesort.zip
Insbesondere fällt hier der Unterschied zwischen der Variante mit und der ohneAbbruch wesentlich geringer aus:
Mit Abbruch:      Number of Slices  168           Number of 4 input LUTs 250
Ohne Abbruch:   Number of Slices  167           Number of 4 input LUTs 245

-- Typdefinition BSData_Typ s.o.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use work.bstypes.all;

entity Bubblesort is
    Port ( di    : in  BSData_Typ;
           do    : out BSData_Typ;
           start : in  std_logic;
           done  : out std_logic;
           clk   : in  std_logic);
end Bubblesort;

architecture Behavioral of Bubblesort is
signal busy     : boolean := FALSE;
signal din      : BSData_Typ;
signal n,i      : integer range 0 to din'length;
begin

   process 
   variable temp : integer;
   begin
      wait until rising_edge(clk);
      if (busy=FALSE) then
         if (start='1') then
            din  <= di;
            busy <= TRUE;
            n    <= 0;
            i    <= 0;
         end if;
      else
         if (n < din'length) then
            if (i<din'length-1) then
               if din(i) > din(i+1) then
                  temp     := din(i);   -- Dreieckstausch
                  din(i)   <= din(i+1);
                  din(i+1) <= temp;
               end if;
               i <= i+1;
            else
               i <= 0;
               n <= n+1;
            end if;
         else
            busy <= FALSE;       
            do   <= din;
         end if;
      end if;
   end process;
   
   done <= '1' when start='0' and busy=FALSE else '0';

end Behavioral;

Das ist die Testbench für die kombinatorische Variante:

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.numeric_std.ALL;
use ieee.math_real.all;
use work.bstypes.all;
 
ENTITY tb_BubbleSort IS
END tb_BubbleSort;
 
ARCHITECTURE behavior OF tb_BubbleSort IS 
    COMPONENT Bubblesort
    Port ( di  : in  BSData_Typ;
           do  : out BSData_Typ );
    END COMPONENT;

   --Inputs
   signal di : BSData_Typ := (3,6,1,8,7,2,4,5,9,0);
   --Outputs
   signal do : BSData_Typ;
   
BEGIN
  -- Instantiate the Unit Under Test (UUT)
   uut: Bubblesort PORT MAP (
          di => di,
          do => do
        );

   -- Stimulus process
   stim_proc: process
    variable rand  : real;
    variable seed1 : positive := 234;
    variable seed2 : positive := 567;
   begin    
      wait for 100 ns;  
      loop
         for i in 0 to 9 loop
            UNIFORM(seed1, seed2, rand);
            di(i) <= integer(TRUNC(rand*127.999));
         end loop;
         wait for 10 ns;
         for i in 0 to 8 loop
            assert do(i)<=do(i+1) report "Falsche Reihenfolge!" severity failure;
         end loop;
       end loop;
   end process;

END;

Und das kommt dabei heraus:

Waveform der Testbench für den kombinatorischen Sortierer

Und hier können die Dateien gezippt heruntergeladen werden: Bubblesort.zip