Sortieralgorithmus in VHDL

Sortieralgorithmus in VHDL? "Bubblesort"? Bezweifle, dass das zu 
schaffen ist. Es sei denn, du programmierst eine CPU in VHDL und 
schreibst ein Programm in irgendeiner "höherer" Sprache dafür, das die 
Daten irgendwie sortiert.

Gruß,
Alex

was die geschwindigkeit angeht ist es nicht so wichtig, einfach wär mir 
lieber ;). ich weiß allerdings auch nicht, was fsm ist. versuche gerade 
bubblesort umzusetzen, aber will noch nicht wirklich...find halt leider 
keine beispiele für die vhdl-syntax. desweiteren müssen werte aus dem 
alten array erhalten bleiben und der neue array müsste noch eine 
laufvariable besitzen.

danke für das interesse!

FSM steht für Finite State Machine. Man erzeugt eine Maschine mit 
mehreren Zustände. In Abhängigkeit vom Zustand werden dann Aktionen 
ausgeführt.
Wenn Du die VHDL-Syntax nicht kennst, empfiehlt sich ein Buch.
Für bubble-sort brauchst Du aber keine zwei Arrays.

Hallo,

ok, so könnte man es machen, allerdings ist der Wunsch

>benötige ich einen Sortieralgorithmus, welcher mir einen Ausgangsvektor
>mit unterschiedlichen (Integer-)Werten nach Größe sortiert in einen
>zweiten Vektor ausgibt. Ich suche Anregungen und Lösungen, wie man

ich habe mir hier irgendwie eine entity vorgestellt, die n 
Interger-Eingänge und n Interger-Ausgänge hat und die dann 
wahrscheinlich auf ein Enable-Pin triggert... also irgendwie so ähnlich.

Wenn es da aber einen Speicher gibt und die Daten von jemandem da 
geschrieben werden, könnte man einen Zustandsautomaten realisieren. Man 
muss dann bloss genau steuern, wer, wie und wann auf den Speicher 
zugreifen darf.

Gruß,
Alex

danke an alle!!! hab's geschafft... das nächste problem wird wohl, wie 
ich aus meinem eindimensionalen array einen mehrdimensionalen mache und 
vor der Sortierung bereits eine kennung hinzufüge, welche mich danach 
noch die ursprünglichen character'pos aus der ascii-tafel bestimmen 
lässt, denke aber das wird schon. für ideen bin ich gerne offen.

>@ Philip Kirchhoff (plip)

>>> muss dann bloss genau steuern, wer, wie und wann auf den Speicher
>>> zugreifen darf.

>>Ja, das ist doch immer so, oder?! ;-)

>Apfelmus ist Mus aus Äpfeln . . . ;-)

ich habe doch bloss laut gedacht, und so trivial ist das doch gar nicht 
- oder vielleicht habe ich nicht so viel Erfahrung in VHDL oder denke 
ich hier zu kompliziert?

Sortieren ist natürlich sicher möglich. Die Frage ist jedoch, ob du 
einen eher hardware geeigneten Ansatz verwenden willst. Sprich eine 
Sortierung je Taktzyklus und konstante Durchlaufzeit. Das erfordert eine 
durchdachte Pipeline-Struktur und einen geeigneten Algorithmus. 
Merge-Sort sollte dafür gut geeignet sein. Einfach ist aber was anderes.

Oder eben ein Softwareansatz, wo in jedem Taktzyklus eine ein paar 
Elemente sortiert werden. Da kann man im wesentlichen alle Software 
Algorithmen sequentiell ausführen.

Wenn man den Bereich der Eingangsdaten kennt (also zb dass alle 7bit 
sind) und auch eine sinnvolle Beschränkung für die Häufigkeit des 
Auftretens annehmen kann (zb maximal 255 mal), kann man auch einfach ein 
großes Array nehmen, in dem für jeden Wert, der auftreten kann, ein oder 
mehrere Bits sind (mehrere wenn man mitzählen möchte) und dann bei 
auftreten des Wertes entweder das Bit setzen oder den Wert in dem 
Register inkrementieren.

Am Schluss dann über das Array iterieren und die Werte ausgeben, bei 
denen das Bit gesetzt ist.

Ist sicher HW-intensiver als andere Lösungen aber dafür einfach und 
schnell.

p.s.: Ich bin übrigens nicht der Threadersteller. Ich muss mich wohl 
langsam hier mal registrieren, ist nicht das erste Mal dass hier zwei 
Gast Matthiasse im selben Thread unterwegs sind.

Hallo  Matthias,

wie Sym es schon angemerkt hat, ist Merge-Sort eine Möglichkeit. Ich 
persöhnlich würde Dir auch MergeSort empfehlen weil es in VHDL relativ 
einfach implementierbar ist. Zum Algorithmus selbst siehe vieleicht ein 
Buch über Algorithmentechnik wie z.B. T. Cormen, C. Leiserson and R. 
Riverst, "Introduction to Algorithms" empfehlen, ist sehr gut zu 
verstehen!

Grundelement der Verfahrens ist der Vergleich zweier Elemente bzgl. 
GrösserGleich-Relation (sollte wohl kein Problem darstellen loool).
Hauptaufgabe ist die Sortierung zweier Arrays in ein neues Array, so 
dass aus beiden sortierten Arrays ein neues, sortiertes Array entsteht. 
Fange dazu bei Arrays der jeweiligen Länge 1 (Schritt 1) an 
(trivialerweise sortiert!) und erhalte daraus Arrays von jeweils 2 
Elementen. Dann (Schritt 2) werden jeweils zwei Arrays der Länge 2 zu 
einem Array der Länge 4 erzeugt. Im Schritt 3 dann Arrays der Lange 4 zu 
Arrays der Länge 8 etc..
Ist die Länge deines ElementeArray keine zweierpotenz, fülle einfach 
mich maximalen Werten auf!

Hauptproblem ist also das Mergen zweier Arrays zu einem sortierten Array 
der doppelten Länge. Ist aber nicht so schwer wie es sich anhört, schaue 
einfach im Buch nach. Auch die Logik für die einzelnen Schritte etc. ist 
mit einfacher Zählerlogik implementierbar.

Nachteil der Verfahrens ist, das der Algorithmus die einzelnen Schritte 
und Mergevorgänge nur sequentiell erledigt. Dafür kann der gesamte 
Algorithmus aber so gestalltet werden, das er vollständig pipeline-fähig 
ist.

Falls Du aber nach einem parallelen Sortierverfahren suchst, schaue mal 
in Joseph Jaja "An Introduction to Parallel Algorithms", insbesondere 
Bitonic-Sorting. Diese Verfahren sind aber deutlich schwerer in VHDL 
implementierbar.

Gruss,

Jörg

Hallo Falk,

MergeSort ist nicht nur einer der schnellsten, er ist sogar der 
schnellste bzgl. Berechnungskomplexität. Quicksort und andere sind 
meistens nur im Schnitt (!!) die Schnellsten, aber nur mit grossen 
Hürden in Hardware giesbar. MergeSort ist ausserdem extrem einfach in 
Software realisierbar und (aber das ist nur meine persöhnliche Meinung) 
auch der am einfachsten zu implementierende unter den schnellen 
Algorithmen. Aber das nur nebenbei bemerkt.

MergeSort ist definitiv nicht rekursiv in seiner Grundform, kann aber 
natürlich wie viele andere Algorithmen rekuriv programmiert werden, was 
dann aber in VHDL wohl nicht so einfach realisiert werden kann.

Nehme einfach an, Du sortierst n Elemente, n = 2**k. Verwende nun in 
Deiner VHDL-Realisierung k Arrays A_1..A_k der Länge n. In jedem in 
meinem ersten Beitrag erwähnten Schritt werden die Teilarrays aus A_i in 
doppeltsolange,sortierte Teilarrays aus A_(i+1) sortiert (sogenantes 
Mergen). Dies kann rekursivlos (!) implementiert werden. Die einzelnen 
Schritte nacheinander auszuführen ist ebenfalls rekursivlos 
implementierbar, die von mir vorgeschlagene Verwendung der Arrays 
A_1..A_k läst sogar eine einfache Pipeline-Struktur zu, so das 
"gleichzeitig" k Sortiervorgänge gleichzeitig ablaufen können (Bem: 
jeder Schritt bracht aber O(n) Schritte!). Bei geschickter Formulierung 
lassen sich sogar k*n (!!) Arrays gleichzeitig sortieren, was aber 
irrsinnig viele FPGA-Resourcen in Anspruch nehmen dürfte (gleichzeitiges 
Ausführen von Arbeitsschritten hat ja schliesslich idR. auch das 
parallele Vorhandensein von Schaltungen zur Folge). Der einzige grössere 
Nachteil einer VHDL-Implementierung ist die von vornherein festzulegende 
Arraylänge n, aber versuch mal einen Algorithmus mit variabler Länge n 
zu implementieren..geht zwar auch, aber viel Spass dabei.

Bleibt nur die Implementierung des Mergens: Verwende drei Zähler für die 
Position ind Teilarray B_1,B_2 (Länge L) und B_2 (Länge 2*L, als 
Ergebnisteilarray). Zu Beginn sind die Zähler Z_1, Z_2, Z_3 = 0. Dann 
wird in jedem Durchlauf die Elemente B_1(Z_1) und B_2(Z_2) verglichen 
und der kleinere Wert nach B_3(Z_3) kopiert. War B_1(Z_1) der kleinere 
Wert, dann inkrementiere Z_1, sonst Z_2. Inkrementiere Z_3. Ist Z_1 = L, 
dann kopiere nur nock B_2(Z_2) und inkrementiere nur noch Z_2 (analoges 
für Z_2 = L). Dieses Verfahren terminiert nach genau 2*L-Schritten!

Aber am Besten einfach im Buch nachschauen, ist sehr gut bebildert und 
beschrieben.

Ach ja: der Oben vorgeschlagene BubbleSort-Algorithmus ist auch nicht 
einfacher realisierbar, verbraucht aber so wie er Oben beschrieben wurde 
n*n Array-Elemente, was sehr teuer ist.


Gruss und viel Spass/Glück bei der Implementierung,

Jörg


P.S. Die von Matthias gestellte Aufgabe hat (glaube ich) die Teilaufgabe 
der Sortierung bzgl. Character-Häufigkeit (sogenantes 
HistogramSortierung). Da die Character-Menge aber konstant ist (z.B. 128 
bzw. 256), hat man eh nicht das Problem einer variablen Länge n.

@Jörg:

was mich interessiert, haste das schonmal in VHDL gemacht?

Hallo Matthias/Falk,

nein, keineswegs Ketzer, schiesslich kann man ja in jedem Forum vor sich 
hinblubbern wie man lustig ist (lol), drum prüfe stets ob Blubber oder 
nicht Blubber. Ich selbst bin nur gelegenheitsVHDL-ler, habe aber 
jahrelange Erfahrung im Implementieren und Entwerfen von Algorithmen, 
unter anderem auch Automatenalgorithmen, die sich ja meist automatisch 
in VHDL-Code transformieren lassen. Von daher weiss ich um die relativ 
einfache Implementierung von Sortier/Suche-Algorithmen, auch in VHDL.

Das von mir beschriebene Verfahren habe ich zwar schon tausendfach in 
Software gegossen, aber zu meiner Schande nie in Hardware, vielleicht 
mal an einem Wochenende. Ich bin mir sehr sicher, dass das relativ zügig 
umsetzbar ist.

Gruss

Jörg



P.S. klar Falk, BubbleSort hat nur O(n) Speicheraufwand, habe nicht 
drüber nachgedacht. Deshalb: prüfe stets..

Hallo Falk,

ja natürlich sind die meisten der in Programmiersprachen verfassten
Algorithmen sequentiell (und werden es auch noch bleiben), aber nur weil 
sie auf Einprozessorsystemen ablaufen. Also warum mehr Mühe machen als 
notwendig wenn parallele Algorithmen idR wesentlich komplexer in der 
Implementierung/Formulierung sind.

Aber das heisst nicht das eine Unmenge an Algorithmen nicht hochgradig 
parallel formuliert sind. Und gerade die, die sich z.B. in sog. 
zellularen Automaten leicht implementieren lassen/nur für diese 
entworfen wurden (wie z.B. MergeSort,BitonicSort etc.), sind 1:1 in 
VHDL-Code umsetztbar und je nach Bedarf hochgradig parallel. Das hat 
überhaupt nichts mit C->VHDL-Transformation zu tun. Eher im Gegenteil: 
Wird der Algorithmus erst in C implementiert und dann nach VHDL 
transformiert,  woher soll dann der Transformator die Parallelität 
erkennen. Das dann das Ergebnis wenig überzeugt, ist doch kein Wunder, 
in den meisten Fällen sogar selbstverständlich. Statt dessen werden 
zellulare Automaten in einer einfachen Sprache (die Parallelität als 
inherentes Konzept beinhaltet) verfasst und dann direkt in Silikon 
gegossen (siehe fast alle Rechenwerke der meisten Prozessoren, 
insbesondere GPUs, wo ja massiv parallel gearbeitet wird), oder 
Signalprozessoren, die als Zellulare Rechenmonster verschriehen sind.
Für einen guten Einblick in Automaten-/Zellular-Algorithmen empfehle ich 
Dir auf jeden Fall von Roland Vollmar "Algorithmen in 
Zellularautomaten", zwar trocken geschrieben und schon etwas alt, bietet 
aber alles was man für das konzeptionelle Verständnis benötigt.

Nochmal zum Sortieren: Falls Du EIN EINZIGES Array wirklich hochgradig 
parallel sortieren willst, dann explodiert die aus 
komplexitätstheoretische Gründen der Gatteraufwand 
(=Einzelschrittaufwand), siehe z.B. JaJa "Intro. into Par. Algorithms" 
(oder auch Akl,Ritter,etc...), wo eine Menge von 
Sortier/Such-Algorithmen in den verschiedensten parallelen Versionen 
untersucht werden. Egal ob in C oder in VHDL. Und die dann zu 
implementieren ist ausserdem sehr schwer in VHDL. Eine der Ausnahmen ist 
wie gesagt BitonicSort (auch wenns nicht laufzeitoptimal/aufwandsoptimal 
ist), wird auch bei der GPU-Implementierung von Physikengines verwendet 
(siehe NVidia "GPU-Gems I-III").

Zum Pipelining: 256 Chars macht 1024 Bits, davon ca. 20 Stück, jeweils 
durch eine sortierende Controlleinheit verbunden. Ich spiele zZ. mit 
einem Spartan3E rum und hab gerade mal das Grundgerüst animplementiert 
(ohne Sortierung der Teilarrays), ging ohne grössere Probleme. Je 256 
Takte, und dann die jeweiligen Arrays in die nachfolgenden Stufen 
kopieren. Also da sehe ich nicht unbedingt ein Problem (mein Spartan3E 
hat glaube ich 288 KBits an Speicher).


Gruss Jörg,


P.S. ich hoffe "tausendfach/jahrelang" kam nicht als 
Angeberei/Lehrermeierei rüberkam, es ist keineswegs so gemeint/gedacht. 
Ich wollte nur andeuten, das ich es nur einmal gelesen habe aber von der 
Implementierung (in Software) keine Ahnung habe. Allerdings ist VHDL 
alles andere als meine Stärke.

Hallo Matthias,

ich habe just for fun mal einen sogenannten "Odd-Even Merge-Sort" 
Netzwerkalgorithmus ausprobiert. Läst sich sehr einfach implementieren 
und ist auch sehr effizient. Anbei VHDL-Code-Fragment und Png-File für 
n=8.

Für
n =   4:  3 Schritte
n =   8:  6 Schritte
n =  16: 10 Schritte
n =  32: 15 Schritte
n =  64: 21 Schritte
n = 128: 28 Schritte
n = 256: 36 Schritte

bzw. Iterationen bzw. Anzahl Arrays erforderlich. Ausserdem ist der 
Algorithmus voll pipelinefähig. Für eine genauere Beschreibung siehe

Jaja: "An Introduction to Parallel Algorithms" oder
Akl : "The Design and Analysis of Parallel Algorithms" oder
Pharr: "GPU Gems 2",Chapter 46.

Letztes Buch enthält wohl die einfachste Beschreibung, ist aber in fast 
keiner Uni-Bibliothek vorhanden, frag aber mal einen Freund der sich mit 
DirectX-Shader-Programmierung intensiver beschäftigt.



Datei-Anhang funktioniert nicht, deshalb (ohne Garantie):


------------------------------------------------------------------------ 
----------
-- main
------------------------------------------------------------------------ 
----------

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

------------------------------------------------------------------------ 
----------
-- entity main
------------------------------------------------------------------------ 
----------

entity main is
  Port
  (
    CLOCK       : in  std_logic
  );
end main;

------------------------------------------------------------------------ 
----------
-- architecture main::behavioral
------------------------------------------------------------------------ 
----------

architecture behavioral of main is


  -- array tyle

  type ram_type is array (0 to 7) of std_logic_vector (7 downto 0);




  signal A00: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A01: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A02: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A03: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A04: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A05: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");
  signal A06: ram_type :=  (X"00",X"00",X"00",X"00", 
X"00",X"00",X"00",X"00");


begin

  process(CLOCK)
  begin
    if rising_edge(CLOCK) then
      LEDS <= value;


      -- sort A05 => A06
      for j in 0 to 2-2 loop
      for i in 0 to 4-2 loop
        if A05(2*i+1+j) <= A05(2*i+2+j) then
           A06(2*i+1+j) <= A05(2*i+2+j);
           A06(2*i+2+j) <= A05(2*i+1+j);
        else
           A06(2*i+1+j) <= A05(2*i+1+j);
           A06(2*i+2+j) <= A05(2*i+2+j);
        end if;
      end loop;
      end loop;


      -- sort A04 => A05
      for j in 0 to 4-2 loop
      for i in 0 to 2-2 loop
        if A04(4*i+2+j) <= A04(4*i+4+j) then
           A05(4*i+2+j) <= A04(4*i+4+j);
           A05(4*i+4+j) <= A04(4*i+2+j);
        else
           A05(4*i+2+j) <= A04(4*i+2+j);
           A05(4*i+4+j) <= A04(4*i+4+j);
        end if;
      end loop;
      end loop;


      -- sort A03 => A04
      for j in 0 to 4-1 loop
      for i in 0 to 1-1 loop
        if A03(8*i+0+j) <= A03(8*i+4+j) then
           A04(8*i+0+j) <= A03(8*i+4+j);
           A04(8*i+4+j) <= A03(8*i+0+j);
        else
           A04(8*i+0+j) <= A03(8*i+0+j);
           A04(8*i+4+j) <= A03(8*i+4+j);
        end if;
      end loop;
      end loop;


      -- sort A02 => A03
      for j in 0 to 2-2 loop
      for i in 0 to 2-1 loop
        if A02(4*i+1+j) <= A02(4*i+2+j) then
           A03(4*i+1+j) <= A02(4*i+2+j);
           A03(4*i+2+j) <= A02(4*i+1+j);
        else
           A03(4*i+1+j) <= A02(4*i+1+j);
           A03(4*i+2+j) <= A02(4*i+2+j);
        end if;
      end loop;
      end loop;


      -- sort A01 => A02
      for j in 0 to 2-1 loop
      for i in 0 to 2-1 loop
        if A01(4*i+0+j) <= A01(4*i+2+j) then
           A02(4*i+0+j) <= A01(4*i+2+j);
           A02(4*i+2+j) <= A01(4*i+0+j);
        else
           A02(4*i+0+j) <= A01(4*i+0+j);
           A02(4*i+2+j) <= A01(4*i+2+j);
        end if;
      end loop;
      end loop;


      -- sort A00 => A01
      for j in 0 to 1-1 loop
      for i in 0 to 4-1 loop
        if A00(2*i+0+j) <= A00(2*i+1+j) then
           A01(2*i+0+j) <= A00(2*i+1+j);
           A01(2*i+1+j) <= A00(2*i+0+j);
        else
           A01(2*i+0+j) <= A00(2*i+0+j);
           A01(2*i+1+j) <= A00(2*i+1+j);
        end if;
      end loop;
      end loop;






      -- what follows: your job..
      -- what follows: your job..
      -- what follows: your job..
      -- what follows: your job..



    end if;
  end process;

end behavioral;

------------------------------------------------------------------------ 
----------
-- end
------------------------------------------------------------------------ 
----------

Hallo Falk,

das ist aber freundlich. Natürlich ist der Algorithmus eben mal 
reingehackt bzw. generiert, was soll man auch in 30 Minuten erwarten 
können. Soll ja auch nur das Prinzip darstellen.
Wenn er Dir zu parallel ist, lass einfach alle Pipelinestufen bis auf 
eine weg  und passe die Indices an/füge eine weitere For-Schleife hinzu. 
Funktioniert dann einbandfrei für n=256,512 auf Spartan3E und ist 
ausserdem das ca. schnellste Verfahren, falls die die Anzahl 
FPGA-Elemente nicht explodieren soll. Nebenbei bemerkt ist sogar die 
Gatterlaufzeit einigermassen akzeptabel. Und schliesslich wahr Dir mein 
erster Vorschlag zu sequentiell (was er aber definitiv nicht wahr), mein 
zweiter zu parallel, was jetzt? Und ausserdem zu akademisch: natürlich 
sind die meisten dieser Netzwerkalgorithmen in universitären Umfeld 
entstanden. Hiermit biete ich eine dritte Lösung, falls die Dir nicht 
passt, bin ich auf eine geniale Lösung  Deinerseits sehr gespannt.

Gruss,
Jörg


P.S. als Softwerker der klotzt und nicht meckert, ausserdem nebenbei 
Lösungsansätze liefert und in der Sache weiterkommen will muss man sich 
hoffentlich hier nicht schämen, oder?

Um nochmal auf die Frage nach dem Sotieralgorithmus zurück zu kommen: 
Wie wäre es mit radix-sort. Der Vorteil ist das man nur Vergleiche dafür 
braucht.

Bei den ganzen Verfahren hast Du minimum eine Pointer-berechnung. 
Zugegeben, die lässt sich recht gut in FPGAs umsetzen. Bei radixsort 
kann man das durch shiften umgehen.
Außerdem hat es den Vorteil das es ein sehr schnelles Verfahren. 
Schneller als Merge-sort.

Hallo,

die Sache hier wird ganz schön komplex.
Nur aus reiner Neugier, hat das jemand schon mal irgendwann mal das mit 
Sortieren und sogar noch auf einem FPGA, sei es rein mit FSMs oder mit 
irgendwelchen parallelen Algorithmen hingekriegt? Ich meine nicht eine 
laufende Simulation sondern eine reale Schaltung, die man einschalten 
kann, die irgendwas macht, die Daten von irgendwo bekommt, sie sortiert 
und dann irgendwo ausgibt oder was auch immer...

Gruß,
Alex