Hallo, ich möchte 64 Bit Datensätze, die je einen 32 Bit Zeitstempel enthalten parallel aus ca. 60 FIFOs lesen und nach Zeitstempel sortiert in einem Ausgangs-FIFO ablegen. Das ganze sollte mit mindestens 20 Millionen Datensätzen pro Sekunde funktionieren. Das soll auf einem Spartan 6 und später auch auf einem ZYNQ laufen. Die momentane Idee ist es einen Baum aus 2:1 Sortern aufzubauen mit Wurzel am Ausgangs-FIFO. Eigentlich müsste solch ein 2:1 Sorter in 2 Clockzyklen sortiern können, was dann ja sogar schneller als gefordert wäre (100 MHZ Systemtakt). Ist das der richtige Ansatz? Frohe Ostern Michael
Michael S. schrieb: > Eigentlich müsste solch ein 2:1 Sorter in 2 > Clockzyklen sortiern können Bei 60 Datensätzen wäre das eine Tiefe von 6 für die Komparatoren, könnte in 2 Taktzyklen a 20MHz klappen. Allerdings willst Du ja alle ausgeben und nicht nur den höchsten suchen. Im binären Baum, den Du dann hättest, würde der zweithöchste hängen bleiben, wenn er zusammen mit dem höchsten im ersten Blatt zusammentrifft. Du musst Dir nochmal Gedanken machen, in welchem Raster zu sortieren willst, soll z.B. erst alle 60 Fifos geleert und dann sortiert werden oder können neue Werte aus Fifos, die schon geleert wurden auch in die Sortierung miteinbezogen werden. Dann müsstest Du mit 20 MHz entscheiden und das geht nur mit mehr Parallelität und etwas pipelining. Die Fifos bringen jeder für sich - oder insgesamt 20MSPS?
Hallo Jürgen, der Durchsatz soll 20 MSPS am Ausgangs-FIFO sein. Die 30 Sorter am Eingang nehmen einen neuen Eingangs-FIFO Wert auf, sobald sie frei sind. Die Eingangs-FIFO werden ständig mit Daten nachgefüllt, allerdings langsamer und ungleichmäsig. Jede der 6 Sorterstufen braucht für sich 2 Takte (max 5 wären auch OK) und es dauert somit 6 * 2 Takte bis der erste Wert durch ist, aber dann kann am Ausgang alle 2 Takte ein Wert ausgeworfen werden. Zumindest wenn es so läuft wie ich es mir vorstelle ;) Wo siehst Du Spielraum für mehr Parallelität?
Es gibt 60 quellen, die irgendwas mit einem zufaelligen Raster vor sich hin blubbern? Irgendwie macht es wenig sinn unter zeitdruck etwas nach der zeit zu sortieren. Man wuerde annehmen dass die daten schon zeitlich zeitlich gestaffelt erzeugt werden, dann muss man sie nur noch kanalisieren und nacher mit einem zeitstempel versehen.
Baum? Du willst ja sortieren und nicht das "grösste" Element finden (<= Wurzel). Wenn schon, dann Sortiernetzwerk. Aber 20Mill Datensätze implizieren schon massive Parallelität. Einige dieser Netzwerke lassen sich "schön" ins FPGA-Raster eingiessen, so dass das Netzwerk mit >= 100MHz auf z.B. S3 läuft, wenn die Anzahl Daten nicht zu gross wird.
IMHO verkompliziert die Festlegung auf FIFO's's (nur das eine Datenwort am Ende verfügbar) das Design erheblich. Ist der FPGA-interne Ausgang der Eingangsfifo und der interne Eingang der Ausgangsfifo als RAM gebaut, spart man sich das umspeichern und kann das Sortieren quasi als Anlegen einer Pointerliste gestalten. Das: http://www.ise.pw.edu.pl/~wzab/fpga_heapsort/ scheint ein ähnliches Design zu beschreiben. MfG,
Michael S. schrieb: > parallel aus ca. 60 FIFOs lesen und nach Zeitstempel sortiert in einem > Ausgangs-FIFO ablegen. Das ganze sollte mit mindestens 20 Millionen > Datensätzen pro Sekunde funktionieren. Welchen maximalen zeitlichen Versatz haben diese Fifos? Kommen die Daten aus diesen einzelnen Fifos dann jeweils zeitlich nacheinander? Kann also "im zweiten Durchlauf" aus einem der Fifos etwas kommen, das eigentlich zum "ersten Durchlauf" gehört hätte? Hier z.B. mal mit 6 Fifos (Zeitstempel: je kleiner um so älter). Ist es einfach nur so: Fifo A B C D E F Speicherplatz 1 1 5 3 4 2 6 2 7 11 9 8 12 10 3 18 17 15 14 13 16 4 19 20 22 24 23 21 5 26 25 ... Oder kann es auch so sein: Fifo A B C D E F Speicherplatz 1 1 5 3 4 2 6 2 7 8 9 14 13 10 -- 13 14 3 11 12 20 17 18 16 -- 11 12 20 4 26 15 22 24 23 21 -- 15 26 5 19 25 ... -- 19 Oder kann es sogar so sein: Fifo A B C D E F Speicherplatz 1 7 15 9 4 2 10 2 11 8 20 24 18 6 3 1 25 3 17 13 21 4 26 5 22 14 23 16 5 19 12 ...
Könnte gerade noch mit odd-even passen. code + testbench hier : Beitrag "sortieren in VHDL" 64bit * 60 Elemente => 64 * 64 = ~4096 Luts/FF pro Stage. Mit 3-4 Pipelinestufen sollten 20mhz problemlos machbar sein, gibt dann 10.000-15.000 Lut/FF Paare. Für den kleinsten Zynq passt das vielleicht nicht, aber sonst ist das doch ganz ok.
@Sigi, Kuechle Prinzip wäre: das jeweils älteste Element bröselt zuerst durch der Sorter Trichter, aber unten ankommen tun alle irgendwann. Im jedem Eingangs FIFO für sich sind die Daten schon sortiert @Victor Der Zeitstempel muss direkt beim Entstehen der Daten gestempelt werden. Das System kann für Stunden mit einem mittleren Durchsatz von gut 1 Million Datenelementen pro Sekunde laufen, ein späteres Sortieren ist nicht praktikabel. @Lothar Die Daten in den Eingangs FIFOs sind chronologisch also sortiert nach Zeitstempel. Alle FIFOs haben naturgemäss nah beieinander liegende Zeitstempel. Deshalb glaube ich auch dass die Baummethode (Kaskadierte 2:1 sorter) funktionieren sollte. @iulius Das ist zu kompliziert und Resourcenhungrig
Was passiert denn, wenn aus einem Fifo ein hochwertiger Wert nach vorne sortiert wird und dann noch ein höherwertigerer erscheint? Irgendwas passt doch da nicht.
@T.G. Das kann nicht passieren weil die Daten in allen FIFOs mit der selben Zeitquelle gestempelt werden. In der Baumstruktur des Sorters sehe ich allerdings noch ein Risiko dass hier ein späterer Wert einen früheren überholt. Erstes positives Ergebnis: Die 2:1 Sorter Komponente kann in 2 Takten sortieren. Das wären dann 50 MSPS Durchsatz. Jetzt muss sich allerdings noch der Baum bewähren.
Michael S. schrieb: > @T.G. > Das kann nicht passieren weil die Daten in allen FIFOs mit der selben > Zeitquelle gestempelt werden. In der Baumstruktur des Sorters sehe ich > allerdings noch ein Risiko dass hier ein späterer Wert einen früheren > überholt. > > Falls du nur dann ausliest wenn ALLE Eingangsfifos etwas enthalten kann das nicht passieren. Setzt natürlich voraus dass die Datenraten von allen Eingängen ungefähr übereinstimmen sonst riskiert man einen Fifooverflow. Am besten mit einem Softwaremodell simulieren um die erforderlichen Größe der Eingangsfifo zu bestimmen.
Funktioniert und sortiert mit 50,000,000 Datensätzen pro Sekunde :) Danke für Eure Inspirationen!
50 mio zugriffe auf die datensätze ? 50 mio ermittlungen des höchsten wertes ? 50 mio sortierte Tabellen ? worauf bezieht sich die forderung "real time"? findet jedes neue datum, das je 20ns eintrudelt, seinen platz in der Reihe?
http://dl.acm.org/citation.cfm?id=1950427 Etwas angepasst habe ich sowas schon vor 3 Jahren bei der IBM im Praktikum entwickelt für hardware unterstützte Sortierung in Datenbanken. Echtzeitsortierung, Begrenzung war der PCIe BUS. Ein komplett gepipelineter Sortierer, der nach ner gewissen Taktzahl, die Datenworte Takt für Takt sortiert ausspuckte und aufnehmen konnte. Die Größe des Sortierjobs hängt vom verfügbaren Speicher ab. War ganz spaßig :)
ich nehme an, du bist dann der dirk? was genau bedeutet dort: Experiments show a sustainable sorting throughput of 2GB/s 2GB/s sind bei einem 16 datenbus was anderes, als bei einem 64 bit bus ich meine, ich sortiere dir mit einem 4 schritt prozess nur ein 1/4 der daten wie mit einem (eventuell klügeren) pipeline design in einem schritt, kriege aber dennoch die scheinbare doppelte leistung, wenn ich die 8fache vektorbreite habe und mich elegant auf die bandbreite beziehe.
Ja, wenn genug Eingangsdaten da sind, kommt alle 20ns ein sortierter Wert aus dem momentan 6 Stufen tiefen "Sortiertrichter" raus. Wenn über einen längeren Zeitraum allerdings noch mehr Daten in die Eingangsfifos strömen sollten, dann könnten diese natürlich überlaufen.
D.h. Du hast am Ausgang der FiFos einen Entscheider, der die Daten in die Folgeentscheiderpipeline einleitet. Wenn danach, also 5 Schritte vor Ausgabe ein noch höherer Wert einflösse, würde der nicht mehr berücksichtigt?
Das ganze funktioniert nur weil es Zeitstempel sind, nach denen sortiert wird. Da kann nicht plotzlich ein "jüngerer" Wert an einem der Eingänge auftauchen.
CZM schrieb: > ich nehme an, du bist dann der dirk? Nein der bin ich nicht. Der war Doktorand deutlich vor meiner Zeit. Ziemlich abgespaceter Typ. Ein Hardcore FPGA Nerd :) Aber im Wesentlichen ist der Algorithmus relativ simpel, da es quasi Mergesort ist. In einem ersten Schritt baut man sortierte Pakete in der Größe von einer BRAM Einheit durch mehrstufiges mergen und anschließend kaskadiert man Merge-Trees wo an jedem Blatt ein Doppelpuffer mit sortierten Paketen hängt. Der Tree merged dann die kleinen Pakete zu großen Paketen. Das Problem ist halt, dass man durch Doppelpufferung quasi immer nur den halben Speicher effektiv nutzt aber man dafür gleichzeitig lesen und schreiben kann. Das Paper behandelt auch Mechanismen wie man den Faktor 2 verbessern kann, aber das habe ich im Praktikum nicht implementiert, weil da Zeit/Ressourcen/Nutzen in keinem Verhältnis stehen.
D. I. schrieb: > Der war Doktorand deutlich vor meiner Zeit. > Ziemlich abgespaceter Typ. Ein Hardcore FPGA Nerd :) Hei, da freut sich der "abgespacte" Dirk Koch sicher, dass er hier als FPGA-Spezialist und Nerd eingestuft wird :-) Michael S. schrieb: > Das ganze funktioniert nur weil es Zeitstempel sind, nach denen sortiert > wird. Da habe ich aber nun ein Verständnisproblem: Wenn das Sortieren funktionieren soll, müssen in den Eingangsfifos alle Daten bereits mit Zeitstempel vorliegen, denn wenn ein jüngeres Datum später noch reinkommt, nachdem lossortiert wurde und die pipeline läuft, würde es nicht mehr berücksichtigt. Wenn aber keine jüngeren Daten mehr kommen können, dann frage ich mich, warum die Eingangsfifos nicht schon vorsortierte Daten haben und man einfach mit einem Endentscheider merged??
Mark F. schrieb: > Hei, da freut sich der "abgespacte" Dirk Koch sicher, dass er hier als > FPGA-Spezialist und Nerd eingestuft wird :-) Nun ja, ich kenn ihn halt flüchtig persönlich ;) Und finde, dass er gute Forschungsarbeit auf seinem Gebiet leistet.
@Mark: Ja, die 60 Eingangsfifos haben durch die Natur der Zeitstempel in sich sortierte Daten, die dann im Sorter "nur" noch gemerged werden. Allerdings dürfte ein einstufiger Entscheider für 64 Bit Werte auf 60 Eingängen die heutigen FPGA Kapazitäten sprengen. Deshalb habe ich eine Baumstruktur von Entscheidern mit 2 Eingängen gewählt.
Michael S. schrieb: > Allerdings dürfte ein einstufiger Entscheider für Das ist aber dann trotzdem nur eine funktionelle Stufe. Die Frage war doch urspünglich, wie sortiere ich? Hier wird doch garnichts sortiert, sondern nur geschaut, welcher Wert der älteste ist und ins Ausgabe-Fifo geschmissen.
Ich glaube in meinem ersten Beitrag stand ziemlich genau beschrieben was die Aufgabenstellung ist. Und für die Gesamtdaten stellt das nach meiner Auffassung schon eine Sortierung dar, wenn auch eine mit speziellen Randbedingungen. Du machst eine Art enttäuschten Eindruck. Das Ist doch auch gar nicht so trivial hier 50 Millionen Datensätze in sortierter Reihenfolge pro Sekunde am Ausgang rauszubekommen und das mit moderatem Resourcenverbrauch. Oder?
Michael S. schrieb: > Das Ist doch auch gar nicht so > trivial hier 50 Millionen Datensätze in sortierter Reihenfolge pro > Sekunde am Ausgang rauszubekommen Nun, mit einem FPGA >= 50 MHz Taktfrequenz eigentlich schon. Bei einem 40MHz-FPGA steigt dann der Aufwand für 50MHz Datenfrequenz natürlich etwas etwas an. :D
guter Joke mit 40MHz :) Wenn Du mir zeigst wie man mit 50 MHz die 50 MSPS sortiert, dann nehm ich ehrfurchtsvoll den Hut ab. Das wäre dann echt anspruchsvoll.
Michael S. schrieb: > Wenn Du mir zeigst wie man mit 50 MHz die 50 MSPS sortiert, > dann nehm ich ehrfurchtsvoll den Hut ab. > Das wäre dann echt anspruchsvoll. Ich verstehe jetzt das Problem nicht ganz. Bei einem voll "gepipelineten" Design (und das genau wurde ja hier nunmehr aufgebaut, wenn ich richtig lese) gilt immer Datenfrequenz = Taktfrequenz, es sei denn, jemand möchte die pipeline anhalten, wie gerade an anderer Stelle diskutiert wird. Damit wird mit jedem Takt eine Entscheidung über das jeweils älteste Datum gefällt und dieses als "item of interest", wie es heisst, selektert. Der eventuelle Rechenaufwand, der zum mehrstufigen Entscheiden aufgrund der Komplexität der Entscheidung anfällt, wird dann nicht zyklisch erledigt, sondern in die pipeline gedrängt, genau so, wie die zusätzlichen kombinierenden Entscheidungen / Stufen, die nötig sind, weil das FPGA nicht alles in einem Schritt packt. Das geht immer. Du kannst den Hut also aufbehalten :-)
Zum zweiten Teil: > guter Joke mit 40MHz :) Wieso? Du gehst ganz witzlos mit 50 MHz auf einen 1:2 Fifo und liest ihn mit der halben Frequenz und doppelter Wortbreite aus. Dein Fifo pumpt dann mit 8:5 und hat damit noch 3/8 Reserve. Alle nachfolgenden Verarbeitungsstufen bauchst Du dann natürlich doppelt und zeitlich echt parallel, sowie gfs noch etwas Querentscheiderei, wenn nötig. Auch das ist noch ein gängiges Konzept und in der Praxis im high speed design öfters mal von Nöten. (also immer noch: Hut aufbehalten.) Interessant wird es z.B. jetzt: Wenn die Daten längs der Zeitachse verarbeitet werden müssen, wie bei einer umsorierenden Selektion (die oben genannte Mimik ist eine nichtsortierende- und damit eine quer zur Zeitachse arbeitende (transversale) Selektion), oder einer Dezimation bzw. einer sonstigen Filterung der Daten über die Zeit, benötigt man natürlich eine Duplizierung der Architektur für die nächste Zeitebene (die man ja "dank" der halben Frequenz real nicht hat) mit einer explizit ausgeführten Rekursion, in der einmal das Ergebnis dieser aktuellen Zeitebene (mit eben dem einen Wert) sowie der nächsten Zeitebene (mit dem einen Wert sowie dem ja ebenfalls vorhandenen folgenden Wert) berechnet wird. Einfach ausgedrückt: Du antizipierst das Ergebnis der folgenden Rechnung der nichtexistenten Zwischenzeitebene quasi dadurch, indem Du die Rechnung selbst extrapolierst. Selbstredend geht das auch mit mehr Werten, als nur mit 2en. Ich habe das irgendwo hier schon mal im Zusammenhang mit den DDS-Funktionen erwähnt, wo es um die Erzeugung von Daten > Taktfrequenz ging, finde es aber ad hoc nicht. Damals wurden z.B. aus 250MHz DDS Sinus aus dem FPGA 1GHz Daten gewonnen. Dabei wird dann nicht 4x in die Tabelle geguckt, was ja mangels Taktreserve/Zeitebene und einfachem RAM-Zugriff nicht geht, sondern 4x gerechnet, interpoliert und gefiltert. Das Hübsche daran ist, das dabei partiell extrapolierte Werte interpoliert werden :-) Damit produziert das FPGA Nutzdaten weit jenseits seiner eigentlichen Taktfrequenz. Das Spielchen kann man beliebig treiben und zudem auch noch quer zur Zeitachse fortsetzen: Interessant sind in diesem Zusammenhang z.B. diskrete Filter mit Fallunterscheidungen durch harte Abfragen, die ihrerseits wieder auf mehrere Werte blicken, diesbezüglich aber nicht nur auf die (beiden oder mehr), die aktuell visibel in der pipeline stecken, sondern z.B. auf 8 oder mehr, wie z.B. bei einem FIR-Filter. Du brauchst dann eine pipeline längst zur Zeitebene, die quer zur pipeline der Rechung liegt, die aber in Folge der Komplexität meistens getaktet werden-, also ihrerseits wiederum in die Zeitebene gestreckt werden muss. Man kommt dann zu einer pipeline quer zu einer rekursiven pipeline. Diese ist dann logischerweise nur dann überhaupt zu bauen: Wenn 1. die anzipierende Rechnung, wie oben beschrieben, nach n-Schritten abbricht - also selbst keine Iteration oder gar Rekursion darstellt, und 2. die pipeline zur Berechung des Endergebnisses die Bewertung die Filterung zu einem deterministischen, finalen Ergebnis kommt und keine Informationen aus anderen Zeitebenen benötigt, wie z.B. das Ergbnis von irgendeiner konkurrenten state machine oder sonst noch ein Signal kennen muss. Sinnvoll zu bauen hingegen, ist sowas überdies nur dann, wenn die Entscheider-pipeline nicht zu komplex ist, weil der Flächenverbrauch mit der Zahl der Entscheidungen in der n-ten Potenz wächst. Sehr effektiv ist es wiederum, wenn die finale pipe kurz genug ist und die neuen Daten langsam genug kommen, damit rechtzeitig wieder ein neuer Wert eingeworfen werden kann, da man dann die pipes längs der Zeitachse in eine abbilden, also schachteln kann. Damit hat man dann das, was ich eine 3D-pipeline nenne. Umgekehrt gibt es noch den Fall, in denen mehrere parallele Wege mit unterschiedlichen Ansätzen beschritten und berechnet werden müssen, wie bei Korrelatoren, Variationsrechung etc. Dann bekommt man noch eine 4. Dimension, die man aber auch wieder zeitlich schachteln kann. Wenn Du möchstest, kannst Du jetzt den Hut abnehmen :-)
Also ich nehme den Hut schon deswegen ab, weil mir von Deinen beeindruckenden Ausführungen etwas schwindelig geworden ist ;) Ich hab Deine Konzepte bisher nicht in aller Tiefe verstanden, aber angesichts des möglichen Auslesens der Eingangsfifos mit doppelten Wortbreite habe ich den Joke wohl unüberlegt deklariert. Dies würde dann allerdings Sortierzellen bedingen die 4 64 Bit Werte in einem Schritt in 2 in sich sortierte 64 Bit Werte umschaufelt. Das kostet allerdings mindestens 4 mal so viele Resourcen, wenn nicht sogar noch etwas mehr. Nachdem mir mein momentaner Durchsatz reicht nehme ich Deine Anregung erst mal in meinen Hinterkopf auf, falls sich irgendwann einmal meine Requirements verschärfen. Auf jeden Fall Danke für die ausführliche Antwort.
Nun ja, im einfachsten Fall duplizierst Du einfach die Architektur und hast zwei Sortierer der bereits existierenden Art. Am Ende gibt es nochmal einen, der schaut, ob man das linke oder das rechte Ergebnis (der einen oder anderen Sort-pipe) nimmt. Die pipes laufen dann asymmetrisch voll, daher ist eine Vorsortierung schon sinnvoll. Ist aber auch nur ein Vergleicher: "Obere 32 Bit > Untere 32 Bit" then "vertauscht latchen" else "unvertauscht latchen". Den gfs getauschten Wert wieder in eine 64 Bit pipe, die später mit 2x32Bit ausgelesen wird. Dann stimmt die Reihenfolge. Auf diese Weise kommst Du im FPGA ganz GENERELL und IMMER von Timing auf Parallel, verschiebst also den Kompromiss hin zur Fläche. Interessant wäre es, eingehende Datenströme zu haben, die in sich nicht sortiert sind. Diese liessen sich wie beschrieben in eine n:m pipeline (BRAM) schieben und dann mit einem entsprechenden Vertauscher sortieren. Man könnte die volle Bandbreite halten und mit einem 32 auf 1024er RAM (geht bei Xilinx) jeweils 32 Daten komplett in mehreren Schritten umsortieren. Wird aber gross! Einen einkanaligen Umsortierer habe ich hier drin: Digitaler Zufallszahlengenerator in VHDL
Juergen Schuhmacher schrieb: > sondern 4x gerechnet, interpoliert und > gefiltert. Das Hübsche daran ist, das dabei partiell extrapolierte Werte > interpoliert werden :-) wo ist da der Sinn, Werte zunächst zu extrapolieren um sie dann wieder zu interpolieren? Hast Du Deine Konzepte mal irgendwo publiziert? Mir sind die Anwendungsfälle nicht unbedingt klar.
high tec ing schrieb: > wo ist da der Sinn, Werte zunächst zu extrapolieren um sie dann wieder > zu interpolieren? Die Extrapolation erfolgt in eine Zwischenzeitebene und entspricht der Formel "in sich selber eingesetzt", wenn es eine Rekursion ist, bzw im einfachen Fall einem ausdrücklich gerechneten Zwischenwert wenn er nicht vom Vorgänger abhängig ist. Eine Interpolation träte z.B. dann auf, wenn man Werte filtern möchte, z.B. beim resampeln. Das kann man natürlich alles fein ausrechnen und die finalen Formeln hinschreiben, oder man überlässt es der Synthese, das zusammenzufassen, was ich eleganter finde.
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.