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