Hallo zusammen, ich habe in einem BRAM in einem Spartan-6 LX150 insgesamt 256 Werte mit jeweils 16 Bit und möchte diese sortiert in ein anderes BRAM schreiben. Was ich bislang ausprobiert habe, war beispielsweise der Batcher Odd Even Mergesort http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort. In der Simulation als auch im FPGA ist die Implementierung lauffähig. Ein Problem natürlich ist, dass der FF Verbrauch sehr hoch ist, da ich erstmal eine pipelinefähige Implementierung gebaut habe und mehr als 30 Registerstufen mit den 256*16FFs habe ... Frage Nummer 1 wäre, kann ich eigentlich dem Synthesetool sagen, dass ich keine Pipeline haben möchte? Frage Nummer 2 wäre, ob jemand einen Vorschlag hat, welcher Sortieralgorithmus für die Aufgabe gut geeignet wäre. Was die Auswahl einschränkt ist, dass maximal die Laufzeit O(n) sein darf. Speicherplatz habe ich ja schon selbst festgestellt, dass O(n*log(n)) bei meiner Größenordnung explodiert. Also besser einen O(1) vom Speicherplatz her. Unter http://de.wikipedia.org/wiki/Sortierverfahren sind ja die ganzen Verfahren sortiert, jedoch was dürfte auch von dem Implementierungsaufwand her noch halbwegs im Rahmen bleiben? Danke.
spartan6 schrieb: > 256 Werte mit jeweils 16 Bit Die spannende Frage dabei ist: wie schnell möchtest du das machen, und mit welcher Latency? Und auf welche Weise kommen deine Werte an? Seriell, oder liegen die allen in einem Speicher? Wenn du viel Zeit zum Sortieren hast, mach einfach nen Bubblesort in einem BRAM, dann hast du nahezu minimalen Ressourcenverbrauch.
Also die Daten liegen im BRAM, daher erstmal serieller Datenzugriff! Die Anwendung gibt nicht her, dass ich n^2 Taktschritte brauche um zu sortieren, also ist O(n^2) für mich nicht akzeptabel. O(n*log(n)) würde gerade noch gehen, aber besser wäre etwas mit O(n). Kann es auch so sagen, muss jede Millisekunde das BRAM sortieren und darf eigentlich nicht mehr als 500us dafür brauchen. Also Pipelinefähig muss es nicht sein, daher ist Latency gleich Laufzeit.
> n^2 Taktschritte brauche um zu sortieren Ansonsten brauchst du halt soviele FlipFlops+Vergleicher+Multiplexer. So große FPGA gibs nicht (und wird es in endlicher Zeit wohl auch nicht geben). Nur ein Mix aus beiden kann zum Erfolg führen.
Erstmal nur den Größten wert finden mit 256*256 Vergleichern, in ein FIFO schreiben im Original löschen und das ganze wiederholen.
spartan6 schrieb: > Hallo zusammen, > > ich habe in einem BRAM in einem Spartan-6 LX150 insgesamt 256 Werte mit > jeweils 16 Bit und möchte diese sortiert in ein anderes BRAM schreiben. Es geht auch ohne kopieren. Dein Sortieralgorithmus baut einen Adressdecoder zusammen. z.B. Addresse 1 greift dann auf Speicherzelle 35 zu. Im FPGA gehen eben Sachen, die niemals mit ein Mikrocontroller gehen und die können auch etwas trickreich sein.
spartan6 schrieb: > Kann es auch so sagen, muss jede Millisekunde das BRAM sortieren und > darf eigentlich nicht mehr als 500us dafür brauchen. Ja, was denn jetzt? Welche Taktfrequenz hast du im System? Uwe schrieb: > Erstmal nur den Größten wert finden mit 256*256 Vergleichern, in ein > FIFO schreiben im Original löschen und das ganze wiederholen. Mit 100MHz würde die Brute-Force Methode klappen: 100MHz/(256*256) = 1,5kHz. Alle 256 Speicherstellen vom BRAM A durchlaufen und größten Wert finden. Desen Wert Im BRAM B speichern und im BRAM A löschen. Das ganze 256 wiederholen. Fertig. > mit 256*256 Vergleichern Wegen des komplett sequentiellen Verhaltens ist nur 1 einziger Vergleicher nötig... Zum zeitlichen Optimieren: Man könnte pro Durchlauf gleich mehrere aufeinanderfolgende Werte finden: den Maximalwert und den zweitgrößten Wert. Dieser 2. Wert muss natürlich auch laufend verglichen werden, denn es könnte ja einer kommen, der größer als der aktuelle 2. Wert ist, aber kleiner als der Maximalwert. Somit sind also schon 3 Vergleicher nötig. Hier gilt es dann, die Geschwindigkeit gegen den Ressourcenverbauch abzuwägen. René D. schrieb: > Dein Sortieralgorithmus baut einen Adressdecoder zusammen. Das bringt nicht sooo arg viel, denn die Adresse braucht schon 8 Bit, die Daten mit 16 Bit nur doppelt so viel. Und der indirekte Zugriff auf das Sortierergebnis bringt durch die 2 BRAMS hintereinander (Index und Daten) einen Takt Latency...
Vielen Dank für die Vorschläge. Mit der jeden ms und nicht mehr als 500us liegt daran, dass ich maximal 500us Delay haben möchte/darf und jede ms neue Daten anliegen :) Also taktmäßig stehen mir 50, 100 und 200 Mhz erstmal zur Verfügung. Die Idee mit sequentiell durchgehen und beispielsweise die zwei größten Werte finden ist echt gut. Die Laufzeit kann man gut varieren durch beispielsweise die 4 größten finden. Das Ganze müsste sich recht einfach parametrieren lassen.
spartan6 schrieb: > Die Laufzeit kann man gut varieren durch beispielsweise die 4 größten > finden. Allerdings steigt dadurch die Anzahl der benötigten Vergleicher exponentiell an, weil ja zusätzlich jeder zwischengespeicherte Wert jedesmal mit jedem anderen zwischengespeicherten Wert verglichen werden muss.
René D. schrieb: > Dein Sortieralgorithmus baut einen Adressdecoder zusammen. > z.B. Addresse 1 greift dann auf Speicherzelle 35 zu. Nennt sich -> Pointer > Im FPGA gehen eben Sachen, die niemals mit ein Mikrocontroller gehen und > die können auch etwas trickreich sein. Trickreich? Niemals gehen? Das ganze geht über eine -> "linear verkettete Liste" und das Pointersortieren ist Standard in Datenbanken. Gibt es geschätzt 30 Jahre :-) Das habt ihr Hartwerker nur noch nicht mitbekommen:-) Egal ob in Hardware oder SW: in beiden Fällen braucht man noch ein Pointer-RAM und schiebt seriell. Kein Unterschied. Lothar Miller schrieb: > Man könnte pro Durchlauf gleich mehrere aufeinanderfolgende Werte > finden: den Maximalwert und den zweitgrößten Wert. Sehr unünstig. Man nimmt den kleinsten und den Grössten. Erspart Quervergleiche. Beide in eine eigene pipeline und zuerst die big values und ab der Mitte die small values ausgeben. Sind n/2 Durchläufe Latenz x n/2 Druchläufe. Bei 100 MHz und 256 Werten etwa 160us. Ausgabe ab dem ersten Durchlauf = 1,2 us. Wer bietet besser?
Webprogrammer schrieb: > Lothar Miller schrieb: >> Man könnte pro Durchlauf gleich mehrere aufeinanderfolgende Werte >> finden: den Maximalwert und den zweitgrößten Wert. > Sehr unünstig. Man nimmt den kleinsten und den Grössten. Erspart > Quervergleiche. Beide in eine eigene pipeline und zuerst die big values > und ab der Mitte die small values ausgeben. Sind n/2 Durchläufe Latenz x > n/2 Druchläufe. Bei 100 MHz und 256 Werten etwa 160us. Ausgabe ab dem > ersten Durchlauf = 1,2 us. Warum kann ich das mit den 127 Takten nicht nachvollziehen? Kannst du deine Vorgehensweise mal in einen Dreizeiler gießen?
Lothar Miller schrieb: > Warum kann ich das mit den 127 Takten nicht nachvollziehen? Lothar, du bist nicht alleine ;-)
Die Idee mit dem größten und kleinsten Wert ist aber nicht schlecht. Wenn ich die zwei größten und zwei kleinsten Werte nehme, dann ist das mit Vergleich zu den vier größten oder kleinsten vom Schaltungsaufwand deutlich besser oder? Ok ich habe noch ein wenig Overhead wegen dem Speichern beider Adressen (von unten/oben) aber sonst ...
Wenn man ohne Nachzudenken Softwareverfahren auf Hardware überträgt kommt meistens Mist raus (wie beim Mergesort im Eingangsposting). Ein einfaches Verfahren mit O(n*n) lässt sich sehr viel leichter in einen O(n) Teil in der Zeit und einen O(n) Teil in der Hardware splitten. Die Daten liegen ohnehin seriell vor, d.h. O(n) in der Zeit lässt sich ohnehin nicht vermeiden. Den Hardwareteil kann man mit 256x16 Registern und 256 Vergleichern realisieren. Jeder neue Wert wird dabei in die passende Stelle des 256x16 Registerarrays einsortiert, Platz wird mit Schieben geamacht. Ist IMO in einem Takt machbar, und da die Register/Vergleicherstruktur sehr regulär und lokal ist sind auch >100 MHz machbar. Optional kann man nochmal 256x16 Register als Ausgangspipeline spendieren, dann geht das mit voller Datenrate und nur 256 + weinge Takte Latenz.
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.