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
Was glaubst du denn für nen Speedup durch einen anderen Algorithmus zu erhalten bei 9 zu sortierenden Werten?...
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.
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.
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
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
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.
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 :)
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.
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
Nach dem Lesen dieser Lektüre : http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm 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.
vielen dank, das ist schon ok so, dann wünsch ich mal ein frohes fest mfg matzunami
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.