www.mikrocontroller.net

Forum: FPGA, VHDL & Co. FPGA zum sortieren von Daten


Autor: Dimitri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Dimitri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Roman65536 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Roman65536 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: .... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Dimitri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christian Leber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Dimitri

Was du optimieren moechtest ist also die Sortierung von gerade mal 100 
Objekten nach einer Fliesskommazahl?

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.