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!
H, schau doch mal nach "Bubblesort". Ist nicht der schnellste Algorithmus aber recht einfach umzusetzen.
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
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?
@ 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
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.
@ 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
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
alex wrote: > Man > muss dann bloss genau steuern, wer, wie und wann auf den Speicher > zugreifen darf. Ja, das ist doch immer so, oder?! ;-)
@ 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
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?
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...:-)
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
@ 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
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 (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
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..
@ 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
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.
Angehängte Dateien:
-
Pattern.PNG
514 Bytes
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 ------------------------------------------------------------------------ ----------
@ 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
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?
@ 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
naja, mit
1 | entity main is |
2 | Port
|
3 | (
|
4 | CLOCK : in std_logic |
5 | );
|
6 | end main; |
wird die Synthese ein besonders resourcenschonendes Design produzieren. Passt durchaus auch in ein kleines CPLD. Cheers, Roger
@ 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
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.
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?
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
@ 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
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.