Forum: FPGA, VHDL & Co. RAM Inhalt sortieren


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 Spartan (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich schreibe an einem Algorithmus, der den Inhalt eines Dual-Port-RAM 
von klein nach groß sortieren soll. Dabei versuche ich mich am Bubble 
Sort Algorithmus. Die Beispiele von Lothar Miller habe ich mir bereits 
angesehen.

Wenn man ein Array zur Verfügung hat, ist das Vertauschen der Positionen 
kein Problem.

Nur wie wende ich sowas:
if din(i) > din(i+1) then
  temp     := din(i);   -- Dreieckstausch
  din(i)   <= din(i+1);
  din(i+1) <= temp;
end if;
auf ein RAM an?

Weiß Jemand, wo man da Beispiele findet?
Bei Google war ich bisher nur wenig erfolgreich.

Viele Grüße

von Duke Scarring (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Spartan schrieb:
> Nur wie wende ich sowas:if din(i) > din(i+1) then
>   temp     := din(i);   -- Dreieckstausch
>   din(i)   <= din(i+1);
>   din(i+1) <= temp;
> end if;
> auf ein RAM an?
Da braucht man eine State Machine (FSM).
Für einen Dualport-RAM, muß die dann ungefähr sowas machen:
state_read  => Port A: Wert A lesen,     Port B: Wert B lesen
state_write => Port A: Wert B schreiben, Port B: Wert A schreiben

Duke

von Spartan (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo,

zunächst ein mal vielen Dank für den hilfreichen Tipp! Ich habe mich 
gleich daran gemacht und habe eine FSM geschrieben:
-------------------------------------------------------------------
--State Machine
-------------------------------------------------------------------
process (clk,reset) is
begin
  if (reset='1') then
    addra <= (others => '0');
    state <= stat_READ;  
  elsif rising_edge(clk) then
    case state is
    
    --CASE: IDLE
    when stat_READ =>   
    addra <= addra + 1;
    
    if(value1 > value2) then
      state <= stat_WRITE;
    else
      state <= stat_READ;
    end if;
                    
    --CASE: WRITE_DPRAM  
    when stat_WRITE =>
    addra <= addra;
    
    -- Dreieckstausch, aber wie?
    
    if(value1 > value2) then
      state <= stat_WRITE;
    else
      state <= stat_READ;
    end if;
      
    --CASE: OTHERS
    when others =>
        addra <= (others => '0');
        state <= stat_READ;        
    end case;
  end if;
end process;


Fragen:
- Macht es Sinn den Adresszähler jedes Mal anzuhalten, wenn zwei Werte 
vertauscht werden müssen?

- Wie führen ich den Tausch durch, also wie erreiche ich das sequentiell 
zunächst an die eine und danach an die andere Adresse geschrieben wird?

Da stehe ich total auf dem Schlauch ... :-(

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@ Spartan (Gast)

>zunächst ein mal vielen Dank für den hilfreichen Tipp! Ich habe mich
>gleich daran gemacht und habe eine FSM geschrieben:

Deine Einrückung ist schlecht, man sieht die einzelnen States nicht gut.

>- Macht es Sinn den Adresszähler jedes Mal anzuhalten, wenn zwei Werte
>vertauscht werden müssen?

Sinn wird nicht gemacht. Er ist da oder auch nicht.
Wie lautet deine Antwort auf die Frage und warum?

>- Wie führen ich den Tausch durch, also wie erreiche ich das sequentiell
>zunächst an die eine und danach an die andere Adresse geschrieben wird?

Du musst die Datensätze in zwei Registern zwischenspeichern (sie werden 
sowieso gelesen), dann vertauscht in den RAM zurück schreiben.

von Spartan (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Sorry,

wer lesen kann ist klar im Vorteil! Man nutzt beide Ports zum lesen und 
zum schreiben.

Ich wollte die Ganze Zeit einen Lese und einen Schreibport haben, das 
ist natürlich Quatsch.

Super, vielen vielen Dank für den genialen Tipp!!

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@ Spartan (Gast)

>wer lesen kann ist klar im Vorteil! Man nutzt beide Ports zum lesen und
>zum schreiben.

Kann man machen, für die reine Übung ist das auch OK. Aber in einer 
REALEN Anwendung müssen die Daten ja auch anderweitig in den RAM 
geschrieben/gelesen werden. Dann ist es meist besser, einen PORT für den 
Normalzugriff zu lassen und einen für den Sortiervorgang.

>Ich wollte die Ganze Zeit einen Lese und einen Schreibport haben, das
>ist natürlich Quatsch.

Nö, das ist auch möglich und sinnvoll.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Falk Brunner schrieb:
> Sinn wird nicht gemacht.
Aber Unsinn und Blödsinn kann man machen? Skurrile Welt... :-/

Das mit dem Dreickstausch und dem Problem mit dem "Daten hineinbekommen" 
hatte ich schon mal woanders erwähnt:
Beitrag "RAM basierter Bubble Sort in VHDL"

: Bearbeitet durch Moderator
von Spartan (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

in dem verlinkten Beitrag wird zwar keine FSM benutzt, aber die Idee ist 
sehr ähnlich zu meiner.

Ich lese Port A des RAMs seriell aus (geht ja auch nicht anders) und 
schreibe den Wert (n) und (n+1) jeweils in ein Register.

Die beiden Register vergleiche ich miteinander. Je nach Ergebniss muss 
ich die Werte vertauschen oder eben nicht.

Bis hierhin ist das kein Problem.

Sind die Werte vertauscht schreibe ich Sie über Port B wieder zurück. 
Und genau hier liegt das Problem.

Ich benötige einen Takt zum vergleichen und einen weiteren zum zurück 
schreiben. Danach ist mein Adresszähler bei Port A scon bei (n+3). Das 
ist alles nur kein Bubble was ich da betreibe.

Ich möchte einen Prozess, der wie ein Uhrwerk durchläuft, wie löst man 
das am Besten?

Da denkt man immer sortieren ist sooo einfach :-D

Grüße,
Spartan

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@ Spartan (Gast)

>Ich benötige einen Takt zum vergleichen und einen weiteren zum zurück
>schreiben.

Nicht unbedingt, das kann man ggf. in EINEM Takt machen. Das hat aber 
den Nachteil, dass die Logiktiefe größer wird und dadurch die maximal 
erreichbare Taktrequenz sinkt.

> Danach ist mein Adresszähler bei Port A scon bei (n+3). Das
>ist alles nur kein Bubble was ich da betreibe.

Genau.

>Ich möchte einen Prozess, der wie ein Uhrwerk durchläuft, wie löst man
>das am Besten?

Mit einer FSM. Im Falle der Vertauschung muss der Zähler zurück 
springen.

von MJF (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo,

eine kleine Idee, wie es vielleicht schneller geht. Die beiden 
benachbarten Adressen immer lesen und schreiben. Die gelesenen Werte 
tauschen oder nicht tauschen und beide zurückschreiben. Durch die Latenz 
"verschieben" sich die Daten im Speicher, dies kann aber wieder 
rückgerechnet werden. Da die Lese-Adresse immer um eins weitergeht, muss 
einer der gelesenen Werte nicht aus dem Speicher genommen werden, 
sondern von der vorhergehenden Vergleichsoperation abgeleitet werden.

Ist spät (Schlaflosigkeit), aber ich glaube es geht.

Gruß

Markus

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.