Forum: FPGA, VHDL & Co. RAM basierter Bubble Sort in VHDL


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Bubble (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Zusammen,

ich versuche nun schon seit fast einer Woche, den Bubble Sort 
Algorithmus von Lothar Miller:

http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html

auf ein Dual-Port-RAM anzuwenden. Das Größte Element wird zwar erkannt 
aber eben nicht (wie bei bubble üblich) nach hinten durchgeschoben. 
Irgendwas läuft hier grundsätzlic schief.

Irgendwie will der Knoten in meinem Kopf nicht platzen. Deshalb wende 
ich mich nun verzweifelt an dieses Forum und hoffe Jemand gibt mir den 
entscheidenden Ratschlag, wie ich das mit den RAM-Adressen handhabe.

Vielen vielen Dank schon mal im Vorraus sowie ein tolles Wochenende!

Beste Grüße,
Bubble

Hier der Code:
Library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;

entity Bubblesort is
end Bubblesort;

architecture Behavioral of Bubblesort is

-- Signals RAM
signal addra         : std_logic_vector(5 downto 0)  := (others => '0');    
signal addrb         : std_logic_vector(5 downto 0)  := (others => '0');  
signal addrb_d1      : std_logic_vector(5 downto 0)  := (others => '0');  
signal addrb_d2      : std_logic_vector(5 downto 0)  := (others => '0');  
signal addrb_d3      : std_logic_vector(5 downto 0)  := (others => '0');  
signal addrb_d4      : std_logic_vector(5 downto 0)  := (others => '0');  
signal dout_a        : std_logic_vector(15 downto 0)  := (others => '0');
signal din_a         : std_logic_vector(15 downto 0)  := (others => '0');  
signal din_b         : std_logic_vector(15 downto 0)  := (others => '0');  
signal we_a          : std_logic_vector(0 downto 0)  := (others => '0');
signal we_b          : std_logic_vector(0 downto 0)  := (others => '0');

-- Signals Bubble
signal busy         : std_logic           := '0';
signal value1       : std_logic_vector(15 downto 0)  := (others => '0');
signal value2       : std_logic_vector(15 downto 0)  := (others => '0');
signal temp         : std_logic_vector(15 downto 0)  := (others => '0');
signal n            : integer range 0 to 64;
signal start        : std_logic           := '0';
signal clk          : std_logic           := '0';
signal enable       : std_logic           := '0';     
signal done         : std_logic           := '0';       
signal reset        : std_logic           := '0';       
signal reset_count  : std_logic_vector(1 downto 0)  := (others => '0'); 
signal i            : std_logic_vector(5 downto 0)  := (others => '0');  


begin


-------------------------------------------------------------------
-- TESTBENCH
-------------------------------------------------------------------
clk     <= not clk  after 20 ns;  -- 25 MHz Taktfrequenz
enable  <= '1';
start   <= '1';

-------------------------------------------------------------------
-- INSTANTIATE BUBBLE_RAM
-------------------------------------------------------------------
BUBBLE : entity work.BUBBLE
port map
(
    clka   => clk,
    wea   => "0",
    addra   => i,
    dina   => din_a,
    douta   => value2,
    clkb   => clk,
    web   => we_b,
    addrb   => addrb_d4,
    dinb   => din_b,
    doutb   => open
  );
  
-------------------------------------------------------------------
-- DELAYS
-------------------------------------------------------------------
p_del: process(clk) is
begin
  if rising_edge(clk) then
    value1 <= value2;
  end if;
end process;

p_adrb_del1: process(clk) is 
begin
  if rising_edge(clk) then
    addrb_d1 <= addrb;
  end if;
end process;

p_adrb_del2: process(clk) is 
begin
  if rising_edge(clk) then
    addrb_d2 <= addrb_d1;
  end if;
end process;

p_adrb_del3: process(clk) is 
begin
  if rising_edge(clk) then
    addrb_d3 <= addrb_d2;
  end if;
end process;


p_adrb_del4: process(clk) is 
begin
  if rising_edge(clk) then
    addrb_d4 <= addrb_d3;
  end if;
end process;
 
-------------------------------------------------------------------
-- GENERATE RESET
-------------------------------------------------------------------
p_reset_count: process(clk) is
begin
  if rising_edge(clk) then
    if (reset_count < "10") then
      reset <= '1';
      reset_count <= reset_count + 1;
    else
      reset <= '0';
      reset_count <= "11";
    end if;
  end if;
end process;

-------------------------------------------------------------------
-- BUBBLE ALGORITHM
-------------------------------------------------------------------
p_bubble: process(clk) is 
begin
    if rising_edge(clk) then
    if (busy = '0') then
      if (start = '1') then
            busy <= '1';
            n    <= 0;
            i    <= "000000";
      end if;
    else
      if (n < 64) then
        if (i < "111111") then  -- (n -1) = 63
          if value1 > value2 then
            TEMP <= value2;

            we_b <= "1";
            addrb <= addra + 1;
            din_b <= TEMP;
          else
            we_b <= "0";
            addrb <= addra + 1;
          end if;
          i <= i+1; -- addra
        else
          i <= (others => '0');
          n <= n + 1;
        end if;
      else
        busy <= '0';       
        --do   <= din;
      end if;
    end if;
  end if;
end process;
   
   done <= '1' when start = '0' and busy = '0' else '0';

end Behavioral;


von Philip (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo,

1. Was sagt die Simulation?
2. Ich kriege immer schlechte Laune, wenn ich mich in der Arbeit durch 
fremdcode arbeiten muss, in dem jede kleine Signalzuweisung in einem 
eigenen Prozess steht. Total schlecht lesbar. Warum macht man sowas?

Gruß

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Bubble schrieb:
> auf ein Dual-Port-RAM anzuwenden.
Wie sollen denn die Daten ins RAM kommen, wenn der Sortierer beide Ports 
braucht?

Philip schrieb:
> 2. Ich kriege immer schlechte Laune, wenn ich mich in der Arbeit durch
> fremdcode arbeiten muss, in dem jede kleine Signalzuweisung in einem
> eigenen Prozess steht. Total schlecht lesbar. Warum macht man sowas?
Richtig, diese Orgie ließe sich abkürzen:
p_adrb_del1: process(clk) is 
begin
  if rising_edge(clk) then
    addrb_d1 <= addrb;
    addrb_d2 <= addrb_d1;
    addrb_d3 <= addrb_d2;
    addrb_d4 <= addrb_d3;
  end if;
end process;
Und nein, der Wert von adddrb "flutscht" da nicht einfach so in einem 
Takt auf addrb_d4 durch, sondern er wird brav jeden Takt 
weitergeschoben.

Ich würde hier auch einfach mal eine "richtige" Testbench aufsetzen, ist 
ja nicht sooooo kompliziert. Hoppala, ich seh gerade: das ganze Ding ist 
eine Testbench...  :-o

Wenn der Wert nicht wandert, dann wird einfach mit dem Dreieckstausch 
was nicht stimmen.

: Bearbeitet durch Moderator

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.