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:
Und hier können die Dateien gezippt heruntergeladen werden: Bubblesort.zip
