www.mikrocontroller.net

Forum: FPGA, VHDL & Co. sortieren in VHDL


Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich habe zwar schon einen Beitrag gefunden, der meinem sehr Ähnlich ist, 
er hilft mir aber nicht wirklich weiter.

Ich möchte in VHDL einen Median Filter implementieren, wo ich momentan 
vor der frage stehe, wie ich meine Daten sortieren soll. (insgesammt 9 - 
3x3 Fenster) Hab es gerade mit dem Bubleshort algorithmus probiert, was 
wohl so wie es aussieht auch funktionieren wird. Mir ist dies allerdings 
etwas umständlich und langsam. Es existieren ja noch diverse andere 
algorithmen, eventuell hat hier jemand ein beispiel eines solchen 
sotieralgorithmus für VHDL???

mfg
matzunami

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was glaubst du denn für nen Speedup durch einen anderen Algorithmus zu 
erhalten bei 9 zu sortierenden Werten?...

Autor: mki (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn dir Bubble Sort zu langsam ist dann nimmst du eben Quick Sort. Also 
Spass beiseite: Sortieren in VHDL halte ich für zu aufwendig. Ich sage 
ja nicht dass es unmöglich ist, jedoch glaube ich nicht dass es so viel 
schneller sein wird gerade weil du nur neun Werte sortieren willst.

Die alternative ist: Bastle dir einen PicoBlaze oder Nios Prozessor, 
lade ihn auf deinen FPGA und löse das ganze in Software. Wenn ich mich 
jetzt nicht irre gibt es dort auch schon fertige Median FIlter IP´s die 
du dann nur noch implementieren mußt.

Mich würde trotzdem mal dein Bubble Sort Algotithmus in VHDL 
interessieren. Vielleicht könnte man ja darauf aufbauen um ihn zu 
verbessern und schneller zu machen.

Autor: Iulius (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
bitonic sort ist ideal geeignet für solch kleine Mengen, da komplett 
parallel gerechnet wird und mit pipeline eine komplette Folge pro Takt 
sortiert werden kann.

Bei 9 Werten (hoffentlich nicht viel breiter als 32bit) erzielt man 
sowohl sehr hohe taktraten als auch einen durchaus akzeptablen 
Logikverbrauch.

für eine erste Idee kann das helfen : 
http://www.myhdl.org/doku.php/cookbook:bitonic

Die Abbildung der englischen wikipedia veranschaulich sehr gut wie es 
funktioniert und wie man es pipelinen kann :

http://en.wikipedia.org/wiki/Bitonic_sorter



Wenn Geschwindigkeit jedoch keine Rolle spielt -> softcore. Der braucht 
deutlich weniger Platz und ist noch universel einsetzbar.
Dürfte jedoch auch um die 20-100 mal langsamer sein.

Da kommts auf deine Prioritäten an.

Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
der filter läuft in "echzeit" ab, also... Video in FPGA -> Offset 
korrektur -> Gain korrektur -> Filter -> Speicher. Da kann und will ich 
keinen MicroBlaze dazwischen haben. Die zu sortierenden 9 werte sind 
übrigens 14 Bit breit. Ich werd mir die Links auf alle fälle mal 
anschauen. Danke

Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
und zu meinen Bubleshort... ich hab drei werte sortiert und schon 2% 
meiner LUT's verbraucht, dass is mir dann doch ein bischen viel - hab 
ein Virtex5 LX50T

Autor: Iulius (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
14bit passt sehr gut dafür, grobe schätzung :

14(bit)*8(stufen)*9(werte) = ~1000 FF, logik nicht relevant.

Wenn dir das nicht zu viel ist kannst du damit sehr gut arbeiten.

Falls doch gibts immer noch die Möglichkeit ohne pipelining mit 1/8 
performance bzw die verschiedenen zwischenstufen.


Aber mMn sollte das sehr gut passen für diese größenordnung. Habe schon 
für deutlich größere Folgen mit größeren Elementen damit gearbeitet und 
selbst da lief das noch akzeptabel.(allerdings ohne pipelining in 
unabhängiger Taktdomäne)

In jedem Fall allen Softwarealgorithmen weit überlegen.

Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ok vielen dank das hört sich ja gut an... gepipelinet muss es wohl 
werden, wenn der algorithmus es nicht schaft die sache in zwei takten zu 
schaffen :)

Autor: mki (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
matzunami schrieb:
> und zu meinen Bubleshort... ich hab drei werte sortiert und schon 2%
> meiner LUT's verbraucht

sowas hab ich mir beinahe gedacht. Ich vermute mal du hast mi einer 
for-Schleife gearbeitet. DU darfst nicht vergessen dass bei einer 
for-Schleife in VHDL alles parrallel abgearbeitet wird und nicht 
sequenziel wie in Software.

Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
nein ohne for schleife... ein bischen vhdl ahnung hab ich mitlerweile 
:)... hab es erstmal rein kombinatorich aufgebaut, aber für jeden 
durchgang mit eigenen variablen, um es später pipelinen zu können. der 
erste for schleifen durchlauf ist dann bei mir:

process (in1, in2, in3, in4, in5, in6, in7, in8, in9)
 variable int1_1 : std_logic_vector(13 downto 0);
 variable int1_2 : std_logic_vector(13 downto 0);
 variable int1_3 : std_logic_vector(13 downto 0);
 variable int1_4 : std_logic_vector(13 downto 0);
 variable int1_5 : std_logic_vector(13 downto 0);
 variable int1_6 : std_logic_vector(13 downto 0);
 variable int1_7 : std_logic_vector(13 downto 0);
 variable int1_8 : std_logic_vector(13 downto 0);
 variable int1_9 : std_logic_vector(13 downto 0);
begin
 --1---------------------------------------------------------
 if (in1 > in2) then int1_1 := in2; int1_2 := in1; else
                     int1_1 := in1; int1_2 := in2; end if;
 if (int1_2 > in3) then int1_3 := int1_2; int1_2 := in3; else
                        int1_3 := in3; end if;
 if (int1_3 > in4) then int1_4 := int1_3; int1_3 := in4; else
                        int1_4 := in4; end if;
 if (int1_4 > in5) then int1_5 := int1_4; int1_4 := in5; else
                        int1_5 := in5; end if;
 if (int1_5 > in6) then int1_6 := int1_5; int1_5 := in6; else
                        int1_6 := in6; end if;
 if (int1_6 > in7) then int1_7 := int1_6; int1_6 := in7; else
                        int1_7 := in7; end if;
 if (int1_7 > in8) then int1_8 := int1_7; int1_7 := in8; else
                        int1_8 := in8; end if;
 if (int1_8 > in9) then int1_9 := int1_8; int1_8 := in9; else
                        int1_9 := in9; end if;

hat eine verzögerung von 21ns und der erste wert ist sortiert...
aber ich seh schon, dass das mit bitonic sort wesentlich konfortabler 
ist, also nochmal schönen dank

Autor: Iulius (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Nach dem Lesen dieser Lektüre : 
http://www.iti.fh-flensburg.de/lang/algorithmen/so...

wollte ichs mal genau wissen...und tatsächlich, odd-even mergesort ist 
tatsächlich sinnvoller als bitonic.

2 Gründe :

- weniger Komperatoren, was aber fast irrelevant ist da eh mehr FF als 
LUTS verbraucht werden

- die wires sind deutlich lokaler, es müssen zwischen den stages keine 
verbindungen zu allen anderen elementen verbaut werden. dadurch steigt 
fmax sehr stark.



hab mal eine halbgenerische Version für 8 Inputs erstellt die 
vollständig gepipelined ist. spuckt also eine sortierte Folge jeden Takt 
aus nach 6 Takten Latenz.

Ergebnis für 8 Inputs / 14 bit auf Cyclone II Speedgrade 7 :

803 Logic Elements mit 784 belegten FFs und 551 belegten LUTs bei 212(!) 
mhz.
macht 4% Device Ressources mit nur 2% wire use.


Fazit : die Vermutung hat sich bestätigt, damit lassen sich tatsächlich 
irrsinnig hohe Taktraten erreichen. Über 200 mhz sind für den Cyclone 
wahnsinn. Auf dem Virtex5 wären das sicher deutlich über 300 mhz.

Der Ressourcenverbrauch bei 9 Elementen pro zu sortierender Folge sollte 
auch irgentwo um die 1000FFs liegen(500 Virtex5 slices ?), also ähnlich 
bitonic.


Achja, code + testbench im Anhang. Falls nötig kann ich auch noch 
Kommentare einfügen.

Autor: matzunami (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
vielen dank, das ist schon ok so, dann wünsch ich mal ein frohes fest

mfg
matzunami

Autor: Moritz G. (mbydq2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
matzunami schrieb:

> Ich möchte in VHDL einen Median Filter implementieren, wo ich momentan
> vor der frage stehe, wie ich meine Daten sortieren soll. (insgesammt 9 -
> 3x3 Fenster)

Ich mache gerade das Selbe und habe nach einer Methode ohne sortieren 
gesucht.

> Es existieren ja noch diverse andere
> algorithmen, eventuell hat hier jemand ein beispiel eines solchen
> sotieralgorithmus für VHDL???

In deinem Fall am besten ganz ohne. Es ist nicht nötig die Werte zu 
sortieren. Es reicht jeweils die (n-1)/2 (=4;n=9) größten und kleinsten 
Werte zu eliminieren.
Suche nach: "median bit voting algorithm elimination OR eliminated"
Da wird beginnend mit dem MSb bitweise gruppiert, dann jeweils die 
kleinsten Werte auf min \ alles 0 oder die größten Werte auf max \ alles 
1 gesetzt, bis nur der Median über bleibt. Der Median ist dabei der 
Wert, der es immer schafft nie in der Anzählig schwächsten Wertegruppe 
zu stehen und damit nie auf max oder min gesetzt zu werden.

Autor: Thomas Werner (tommiw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist das im FPGA besser aufgehoben, als in einer MCU?

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.