RAM Inhalt sortieren

[Spartan (Gast)]

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

[Duke Scarring (Gast)]

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

[Spartan (Gast)]

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 ... :-(

[Falk B. (falk)]

@ 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.

[Spartan (Gast)]

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!!

[Falk B. (falk)]

@ 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.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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"

[Spartan (Gast)]

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

[Falk B. (falk)]

@ 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.

[MJF (Gast)]

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