Hallo Leute, bisher habe ich einen FPGA nur als billigen PC-Ersatz benutzt, nicht weil ich mit ihm irgendwelche Prozesse beschleunigen konnte. Jetzt stehe ich momentan vor einem kleinen Problem. Ich habe jetzt hier ein Produktionsnetz. Um es mal so zu beschreiben: Ich habe eine Startmenge von Objekten in meinem Pool liegen. Den sortiere ich nach einem vorgegebenen Muster, hole mir die ersten 100 Objekte, lasse die über das Produktionsnetz laufen, anschließend landen die neu erstellten Objekte wieder im Pool und das Spiel fängt von vorne an. Mein Problem ist jetzt, dass das Sortieren (derzeit natural Mergesort) etwa mehr als die Hälfte der gesamten Rechenzeit in Anspruch nimmt. Diese Sortiererei würde ich gerne einem FPGA überlassen. Meine Frage wäre jetzt, ob man dadurch an Performance gewinnen kann?
> bisher habe ich einen FPGA nur als billigen PC-Ersatz benutzt Krass. Das habe ich bisher noch nicht geschafft... :-/ Welches Betriebssystem ist auf deinem FPGA gelaufen? > Ich habe eine Startmenge von Objekten in meinem Pool liegen. Was für Objekte in welchem Pool? > Diese Sortiererei würde ich gerne einem FPGA überlassen. Meine Frage > wäre jetzt, ob man dadurch an Performance gewinnen kann? Ich bekomme deine Anforderungen und ein FPGA als Baustein noch nicht unter einen Hut... :-/ Ich habe den Verdacht, dass du hier auf zwei verschiedenen Abstaktionsebenen unterwegs bist. Mit einem FPGA kannst du elementare Funktionen beschleunigen. Die Verwaltung und die Datenübergabe an den Baustein bekommst du aber nicht kostenlos.
Mein Kollege hat seine Studienarbeit zum Thema "Sortieren auf einem FPGA" verfasst. Resumee: Sortieren geht natürlich sehr sehr schnell, Flaschenhals: Kommunikation, also man muss die Daten intelligent und schnell rüberbekommen, ab ca 400. 8bit Werten lohnt es sich aufs FPGA zu gehen
Lothar Miller schrieb: > Krass. Das habe ich bisher noch nicht geschafft... :-/ > > Welches Betriebssystem ist auf deinem FPGA gelaufen? Mit garkeinem Betriebssystem. Früher habe ich z.B. Embedded Systeme mit Linux verwendet, um sagen wir mal auf einem an der Wand hängendem Terminal Daten anzuzeigen, oder RFIDs zu lesen. Heute nehme ich dafür einen FPGA. Er stellt Daten dar, die er von einem Server (Business Logik) bekommen hat, und schickt ihm widerum Daten zur Verarbeitung. Zugegeben, ein Mikrocontroller hätte auch gereicht, aber für ein FPGA ist das Toolset größer. Lothar Miller schrieb: > Was für Objekte in welchem Pool? Mein Objektpool ist eine Liste, in der alle Objekte liegen. D. I. schrieb: > Resumee: Sortieren geht natürlich sehr sehr schnell, Flaschenhals: > > Kommunikation, also man muss die Daten intelligent und schnell > > rüberbekommen, ab ca 400. 8bit Werten lohnt es sich aufs FPGA zu gehen Ich arbeite hier mit einer Größenordnung von 5k-50k Objekten. Das Problem wird tatsächlich sein, diese Daten auf den FPGA zu bekommen. Aber habe ich da nicht letztens ein FPGA Dev-Board mit einem 16x PCIe Anschluss gesehen? Damit hätte ich doch die Bandbreite?
Es ist immer noch nicht geklärt, welche Objekte das sein sollen. Autos? Oder doch ganz aktuell Aschepartikel? Jetzt nicht böse gemeint, aber FPGA ist nicht das, was Du wahrscheinlich suchst. Schaue Dir NVIDIAs CUDA an, da kannst du alles schön in C/C++ programmieren. Grüße, Kest
Ja, ich denke schon das es etwas bring. Sonst haetten es andere Firmen sicherlich nicht schon probiert. Ich denke jedoch wie andere auch, es kommt darauf an was du sortieren willst? zb. Bei Teradata, hat man custom chips verwendet um die daten die ueber internes netzwerk kommen, zu sortieren. Das war eine art von Baum netzwerk und eine SQL db. Jedoch ... da sortierte man nicht kB von daten... eher so MB bis TB von daten. lg roman
Hmmm... Habe jedoch nach dem googlen herausgefunden, das es nicht mehr mit hardware sondern durch software sortiert wird. Den man hat doch mehr flexibilitaet als bei hw loesung. zb. einmal angenommen du willst etwas nach "datum" sortieren. da brauchst mehr als nur der ueblicher a>b kram. Der Sort muss etwas mehr wissen.
Ich frage mich an dieser Stelle eher, ob sich der ganze Entwicklungsaufwand lohnt - immerhin dürfte es nicht ganz trivial sein, die Daten hinreichend schnell zum FPGA zu transportieren. Aber - wie bereits angemerkt - hat jeder moderne PC mit Nvidia-Grafikchip bereits einen kleinen Hochleistungsrechner an Bord. Mit CUDA kann man die Grafikchips auch für eigene nicht-grafische Berechnungen verwenden und erreicht dabei Geschwindigkeitsgewinne von bis zu 100x gegenüber der CPU. Ich würde mir das zumindest mal ansehen, dürfte die einfachste und schnellste Variante sein, einen Prozess auf dem PC massiv zu beschleunigen.
Dimitri schrieb: > Jetzt stehe ich momentan vor einem kleinen Problem. Ich habe jetzt hier > ein Produktionsnetz. Um es mal so zu beschreiben: Ich habe eine > Startmenge von Objekten in meinem Pool liegen. Den sortiere ich nach > einem vorgegebenen Muster, Das "Muster" bleibt über alle Durchläufe gleich? > hole mir die ersten 100 Objekte, lasse die > über das Produktionsnetz laufen, anschließend landen die neu erstellten > Objekte wieder im Pool und das Spiel fängt von vorne an. Falls meine Frage oben zutrifft: Anstatt dich weiter in die Optimierung der Sortierung zu vertiefen, solltest du mal abchecken, ob nicht eine der diversen Heap-Datenstrukturen besser zu deinem Problem passt. Selbst wenn nicht, braucht es keine vollständige Sortierung, um die niedrigsten (oder höchsten, oder whatever) 100 Objekte zu finden. Geschickt angestellt kannst du das in O(n) hinbekommen (Tradeoff: du brauchst etwas mehr Speicher), während die Sortierung im allgemeinen Fall O(n*log(n)) braucht. Andreas
Also ich habe jetzt nochmal konkret in den Quelltexten nachgelesen, wie das Sortieren momentan realisiert ist. Objekte sind in erster Linie nur Datensätze, in denen Attribute gespeichert sind. Wie ich bereits schon gesagt habe, habe ich ein Produktionsnetz. Dieses Produktionsnetz lasse ich auf n(=100 @tm) Objekte los. Und zwar so, dass ich in 64 Threads auf 8 CPUs gleichzeitig neue Objekte erzeugen kann. Da die Produktion einiger Objekte etwas länger dauert, passen die 100 Stück auch ganz gut. Sicher kann man an dieser Stelle noch etwas optimieren. Wenn alle Threads fertig sind, wird die Qualität berechnet. Das ganze erfolgt in etwas mehr als O(n). Ich habe dann in einem Fließkommazahl das Ergebnis stehen 1 > q > 0. Dann werden alle vorhandenen Objekte nach diesem einen eben errechneten Float-Attribug sortiert. Mit CUDA habe ich mich bisher noch nicht beschäftigt, werde das wohl dieses Wochenende mal nachholen. Allerdings habe ich etwas angst, dass die Billig-Server GraKa nicht wirklich in der Lage ist, Performant zu rechnen. Aber ich probiere es aus!
Dimitri schrieb: > Wie ich bereits schon gesagt habe, habe ich ein Produktionsnetz. Dieses > Produktionsnetz lasse ich auf n(=100 @tm) Objekte los. [...] Das ist ja alles schön und gut, aber was ist das Ziel des ganzen? Ich denke, durch Optimierung des Algorithmus (und damit meine ich jetzt nicht den Sortieralgorithmus) kann man hier viel mehr reissen als durch eine (Hardware-)Beschleunigung an einer einzelnen Stelle. > Dann werden alle vorhandenen Objekte nach diesem einen eben errechneten > Float-Attribug sortiert. OK, aber ist die Sortierung der restlichen 4900 Objekte überhaupt relevant, oder kommt es nur darauf an, die 100 Objekte mit dem niedrigsten (oder höchsten) q auszuwählen? Andreas
@Dimitri Was du optimieren moechtest ist also die Sortierung von gerade mal 100 Objekten nach einer Fliesskommazahl?
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.