www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Sortieralgorithmus in VHDL


Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich bin gerade damit beschäftigt, einen Text nach Shannon zu 
komprimieren. Das Ganze in ist mein erstes Projekt in VHDL und so 
langsam lichtet sich das Dunkel. Komme bisher sehr gut voran, allerdings 
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 
dieses Ziel ohne zuviel Codeaufwand in den Griff bekommen kann.

Vielen Dank!

Autor: Philip Kirchhoff (plip)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
H,

schau doch mal nach "Bubblesort". Ist nicht der schnellste Algorithmus 
aber recht einfach umzusetzen.

Autor: alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Philip Kirchhoff (plip)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo ist das Problem?

Du durchläufst einen Speicher mit Werten, von den Du jeweils zwei 
vergleichst - ist der eine größer/kleiner als der andere, tauscht Du 
sie. Wenn in einem kompletten Durchlauf nichts mehr getauscht wurde, 
bist Du fertig.
Das sollte sich doch wohl mit einer FSM relativ einfach schaffen 
lassen...oder steh ich jetzt total aufm Schlauch?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Philip Kirchhoff (plip)

>Du durchläufst einen Speicher mit Werten, von den Du jeweils zwei
>vergleichst - ist der eine größer/kleiner als der andere, tauscht Du
>sie. Wenn in einem kompletten Durchlauf nichts mehr getauscht wurde,
>bist Du fertig.

Genau so. Wobei Bubblesort nur weiss Gott das langsamste Verfahren ist.

>Das sollte sich doch wohl mit einer FSM relativ einfach schaffen
>lassen...

Ja.

MFG
Falk

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Mathi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Matthias (Gast)

>was die geschwindigkeit angeht ist es nicht so wichtig, einfach wär mir
>lieber ;). ich weiß allerdings auch nicht, was fsm ist. versuche gerade

FSM = Finite State Machine = Endlicher Zustandsautomat

>bubblesort umzusetzen, aber will noch nicht wirklich...find halt leider
>keine beispiele für die vhdl-syntax. desweiteren müssen werte aus dem

Gibs zu. Du hast keine Ahnung von VHDL, denkst aber, dass man das mal 
fix zusammenstricken kann. Versuchs mal mit ein paar Grundlagen.

MFg
Falk

Autor: alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Philip Kirchhoff (plip)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
alex wrote:
> Man
> muss dann bloss genau steuern, wer, wie und wann auf den Speicher
> zugreifen darf.

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

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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 . . . ;-)

MfG
Falk

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>@ 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?

Autor: Philip Kirchhoff (plip)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
alex wrote:

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

Trivial ist relativ. Für den Profi ein Klacks, für mich ne Sache, die 
auf jeden Fall Denken erfordert und für nen Anfänger ein hartes Stück 
Arbeit.

Aber kompliziert eigentlich nicht, wenn Du Dir mal sukzessive überlegst 
was da passieren soll.

Ich fand nur Deine Aussage mit dem Speicher Lustig, weil mir spontan 
keine Anwendung einfällt, bei der egal ist, wer wann auf Speicher 
zugreift.
Ausser vielleicht in der Chaosforschung...:-)

Autor: Sym (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Jörg (Gast)

>persöhnlich würde Dir auch MergeSort empfehlen weil es in VHDL relativ
>einfach implementierbar ist. Zum Algorithmus selbst siehe vieleicht ein

Na, das würde ich ander sehen. Mergesort ist zwar sehr clever und so 
ziemlich der schnellste Algorithmus, aber eben auch relativ komplex. Und 
ausserdem rekursiv. jaja, prinzipiell alles in VHDL machbar, aber nicht 
wirklich der richtige Einstieg in die Thematik. Mein Vorschlag.

- Bubble Sort zum warm werden, FSM, RAM Ansteuerung
- Insert Sort zum Steigern
- Merge Sort als krönenden Abschluss.

MFG
Falk

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Jörg (Gast)

>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

So ein "einfacher" Satz ist alles andere als einfach in VHDL umsetzbar. 
Sinnvoll liegen die Daten in einem RAM, mit viel Glück ist das ein Dual 
Port RAM. Da hat man nicht beliebig viele Arrays. Man hat EINS, nämlich 
den RAM. Und damit muss man arbeiten.

>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

Logisch.

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

???
Er verbraucht KEINERLEI Zusatzarrays, nur einenn einzigen 
Zwischenspeicher zum Tauschen der Daten. Das wars. Un mit Dual Port Ram 
könnte man ggf. sogar das sparen. Aber die Effizienz ist natürlich 
grausam, erst recht wenn man in Hardware das ja schneller machen will 
als in Software.

MFG
Falk

Autor: Mathi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Jörg:

was mich interessiert, haste das schonmal in VHDL gemacht?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Mathi (Gast)

>was mich interessiert, haste das schonmal in VHDL gemacht?

Ketzer! ;-)

SCNR
Falk

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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..

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Jörg (Gast)

>Das von mir beschriebene Verfahren habe ich zwar schon tausendfach in
>Software gegossen, aber zu meiner Schande nie in Hardware, vielleicht

AHA, warum habe ich das geahnt . . . ;-)

Dann wäre ich an deiner Stelle auch mit solchen Aussagen eher 
vorsichtig.

"jahrelange Erfahrung im Implementieren und Entwerfen von Algorithmen,
unter anderem auch Automatenalgorithmen, die sich ja meist automatisch
in VHDL-Code transformieren lassen."

Denn gerade DAS ist IMO nicht der Fall. Die meisten Algorithmen in den 
"normalen" Propgrammiersprachen sind sequentiell. Hardware kann aber 
sein volles Potential erst mit parallelen Algorithmen ausspielen. Von 
Pipelining etc. mal ganz zu schweigen. Klar gibt es viele Compiler die 
von (System) C auf VHDL umsetzen können, aber die Ergebnisse haben die 
Praxisanwender noch nicht sonderlich überzeugt, um es mal vorsichitg zu 
formulieren.

MfG
Falk

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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
------------------------------------------------------------------------ 
----------

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Jörg (Gast)

>Netzwerkalgorithmus ausprobiert. Läst sich sehr einfach implementieren
>und ist auch sehr effizient. Anbei VHDL-Code-Fragment und Png-File für
>n=8.

???
Dir ist schon klar, dass das eine voll parallele Struktur ist?
Hast du das mal synthetisiert?
Ist dir klar, dass loop in VHDL KEINE sequentielle Logik erzeugt 
sondern parallele Strukruren? Ja, in eines Testbench kann man damit 
auch sequentielle Sachen generieren, aber nicht in synthesefähigem Code.

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

Der funktioniert schon, aber immer nur mit einer Datei.

Dein Beispiel mag in der Simulation laufen, ist aber 100% akademisch und 
an der Praxis vorbei. Softwerker! ;-)

MFG
Falk

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Jörg (Gast)

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

Dass das Prinzip funktioniert hast du ja selber schon tausendfach 
festgestellt. Für ein praktische Anwendung taugt dieses Beispiel 
keineswegs.

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

;-)
Schuster bleib bei deinen Leisten. Befass dich mal mit den Grundlagen 
von SYNTHETISIERBEREN VHDL. Dann komm wieder und rede hier mit.

>Funktioniert dann einbandfrei für n=256,512 auf Spartan3E und ist

Hast du DEN Code REAL im FPGA laufen lassen? Das glaub ich kaum.

>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

Theoretisches Geschwätz. Zeig mal deinen Map Und Place & Route Report!

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

Lösungsansätze? Das sind sie NICHT! Schliesslich soll ein 
SYNTHETISIERBARES, resourcenschonendes Design rauskommen. Und da du nach 
eigener Aussage von VHDL nicht soviel verstehst, solltest du über die 
Problematik nachdenken, und nicht nur theortisch aus Softwerkersicht 
diskutieren. Denn genau DAS nützt dem OP wenig bis nichts.

MFG
Falk

Autor: Roger Steiner (edge)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
naja, mit
entity main is
  Port
  (
    CLOCK       : in  std_logic
  );
end main;

wird die Synthese ein besonders resourcenschonendes Design produzieren.
Passt durchaus auch in ein kleines CPLD.

Cheers, Roger

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Roger Steiner (edge)

>wird die Synthese ein besonders resourcenschonendes Design produzieren.
>Passt durchaus auch in ein kleines CPLD.

It's no bug, it's a feature!

;-)
Falk

Autor: Mathi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Philip Kirchhoff (plip)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mathi wrote:
> 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.

Versteh ich nicht. Und was machst Du bei anderen Verfahren?

Autor: Mathi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ alex (Gast)

>kann, die irgendwas macht, die Daten von irgendwo bekommt, sie sortiert
>und dann irgendwo ausgibt oder was auch immer...

Direkt sortieren, nein
Komplexere Daten aus BRAMs lesen und verarbeiten, ja.

MFG
Falk

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.