Große Menge Daten möglichst performant verarbeiten!

[Stephan Theisgen]

Hallo!

Ich hoffe auf das Wissen der Cracks hier, um mir bei meiner Aufgabe zu helfen...
Ich habe eine sehr große Datenmenge, locker mal 4 GB oder mehr, auf welcher ich möglichst effizient mathematische Operationen (FFT, MER und andere Manipulationen) ausführen können muß. Außerdem soll die Datenmenge dann je nach Dimension als 2D Diagramm, 2D Höhenliniendiagramm oder 3D Volumengrafik effizient(!) dargestellt werden.

Bisher habe ich das der Einfachheit halber alles in Java implementiert. Die Bedienung und GUI funktionieren (Marching Squares, Marching Cube usw.) super, aber nur für kleiner Datenmengen ist das performant. Auch wenn mich Java da erstaunt hat, wie schnell es sein kann.

Die Frage ist jetzt, wie implementiere ich das jetzt am Besten. Ich dachte mir, ich mache eine Schnittstelle (Interface), welche die Daten repräsentiert und eine, welche allgemein die Manipulationen (FFT, MER usw.) repräsentiert (davon kann man dann mehrere auf die Daten anwenden, ich speichere sie einfach in einer Liste/ einem Vector).

Die konkreten Implementierungen sollen dann die Hardware-Gegebenheiten abfragen und in den Algorithmen berücksichtigen. Und genau hier kommt jetzt die Frage, wie ich das am Besten anstelle. Natürlich muß ich den richtigen Algorithmus auswählen, aber ich muß auch (habe ich bei einigen Profiprogrammen gesehen), die Daten in Blöcke einteilen um möglichst wenig Cache-Mismatchs zu haben etc. und sie nach der Bearbeitung nachladen zu können, bzw. wieder auf die Platte schreiben zu können...
Außerdem brauche ich natürlich auch im Algorithmus die Unterstützung von SSE und anderen Besonderheiten. Wie finde ich diese Gegebenheiten für eine Hardware am besten raus? Beim Programmstart einen kleinen Testlauf machen? Lohnt es sich überhaupt diese Sachen zu ermitteln? Den virtual call der bei der Auswahl der jeweiligen Datenrepräsentation oder Algorithmus auftritt dürfte bei ca. 4GB Daten dann nicht mehr als Performanceverlust ins Gewicht fallen.

Vielleicht hat ja hier jemand ein paar gute Ideen, was man da unterstützen müsste, und wie man am besten die optimale Block-Größe der Daten ermittelt.

Viele Grüße und vielen Dank
Stephan

[Aramis]

Bisher habe ich das der Einfachheit halber alles in Java implementiert. Die Bedienung und GUI funktionieren

Ich wuerde das GUI in Java belassen und den Rest ueber JNI in C/C++ implementieren.

Außerdem brauche ich natürlich auch im Algorithmus die Unterstützung von SSE und anderen Besonderheiten. Wie finde ich diese Gegebenheiten für eine Hardware am besten raus?

SSE, SSE2 usw. kannst du heute als nahezu ueberall vorhanden voraussetzen. Ansonsten, wenn du die entsprechende Optimierung dem Compiler ueberlaesst, kannst du ja einfach jede Implementierung des „Bearbeitungsinterfaces” in eine shared library/DLL auslagern und dann mehrfach compilen und zur Laufzeit die jeweils passende laden.

Das ganze funktioniert auch prima wenn du vorhaben solltest auch CUDA etc. zum Bearbeiten der Daten einzusetzen. Einfach eine weitere Implementierung zur Verfuegung stellen und mit allen ihren Abhaengigkeiten in einer DLL verkapseln.

Natürlich muß ich den richtigen Algorithmus auswählen, aber ich muß auch (habe ich bei einigen Profiprogrammen gesehen), die Daten in Blöcke einteilen um möglichst wenig Cache-Mismatchs zu haben etc. und sie nach der Bearbeitung nachladen zu können, bzw. wieder auf die Platte schreiben zu können...

Nun, die Groesse des Caches kannst du abfragen. Dann die Daten so aufsplitten dass das Working-Set fuer einen Block nicht die Groesse des L2-Caches ueberschreitet (L1 ist so klein dass du ihn vermutlich vergessen kannst - einzig der Maschinencode des Algos koennte/sollte da reinpassen).

Leider ist der Cache ziemlich schlecht vorhersagbar. Da hilft eigentlich nur Profilen und Trial & Error. Z.b. nach einem Dummy-Durchlauf zum Aufwaermen 5 Blockgroessen (mit nicht-ueberlappenden Testdaten ;-)) durchprobieren, jeweils ein paar mal laufen lassen und die Durchgaenge ausmitteln, dann die schnellste der 5 (d.h. die mit der hoechsten Datenmenge pro Zeit) nehmen. Wenn du sowieso ein paar 100k Bloecke verarbeitest, sollte der Aufwand dafuer sich immer noch lohnen - insbesondere wenn man bedenkt wie viel dauernde Cache-Misses eigentlich kosten.


Was du jetzt gar nicht erwaehnt hast: wenn es scheinbar moeglich ist die Daten blockweise zu verarbeiten, muesstest du sie auch auf mehreren Kernen verarbeiten koennen. Da waere es ggf. sinnvoll eine Art Scheduler einzufuehren dem das Bearbeitungsinterface alle zu verarbeitenden Bloecke uebergibt und der dann, auf die Hardware angepasst, mehrere Threads startet und dann wiederum eine Methode des Interfaces aufruft um den jeweiligen Block zu verarbeiten. Auch die Logik um bereits verarbeitende Daten wieder auf die Platte zu schreiben muesstest du dann schoen zentralisieren koennen.

Den virtual call der bei der Auswahl der jeweiligen Datenrepräsentation oder Algorithmus auftritt dürfte bei ca. 4GB Daten dann nicht mehr als Performanceverlust ins Gewicht fallen.

Ja, vergiss den ;-)

Lohnt es sich überhaupt diese Sachen zu ermitteln?

Naja, premature optimization und so … in Anbetracht der grossen Datenmenge wuerde ich aber schon sagen dass es sich lohnt.

[Alexander Kornrumpf]

Hast du schon parallele Verarbeitung angedacht und oder eingesetzt? Vorrausgesetzt du hättest die Algorithmen ohnehin nicht ganz blöd implementiert wirst du auf modernen Multi-Core Prozessoren wohl mehr herausholen, wenn du alle Kerne auch wirklich ausnutzt, als die SSE o.ä. je bringen könnten.

Ich würde ja auch CUDA nennen, dafür gibt es auch sehr schnelle FFT implementierungen aber ich mag mich nicht anfällig für das Shiny-New-Hammer argument anfällig machen.

[Chromanoid]

Ich würde an deiner Stelle ernsthaft überlegen bei Java zu bleiben. Prozessoroptimierungen sollten auch vom JIT Java Compiler vorgenommen werden können. Kannst ja mal hier reinschauen: http://wikis.sun.com/display/HotSpotInt ... Techniques

Bevor du alles auf C++ o.Ä. umstellst, solltest du wirklich mal benchmarken. IMO solltest du mit einer C++ Implementierung wirklich nur dann starten, wenn du weißt was du tust. Ich denke du kannst, wenn du in beiden Sprachen perfomanceorientiert arbeitest, im besten Fall vielleicht so 30% mit C++ rausholen. Und wenn du C++ & Java benutzt kann ich dir JNA empfehlen, das ist angenehmer als das pure JNI.

Wenn du CUDA benutzen willst kannst du dir ja mal http://www.jcuda.org anschauen. Evt. kannst du dir auch mal Scala (läuft in JVM und kann Java Klassen nutzen) anschauen, damit kann man parallele Verarbeitung bequemer unterstützen. Falls du viel mit POJOs arbeiten möchtest könnte ein guter Cache auch was für dich sein. Vor allem wenn du parallele Verarbeitung mit mehreren Computern ermöglichen willst. Dazu könntest du dir mal http://labs.jboss.com/jbosscache/ , ehcache und bigmemory (http://www.terracotta.org) anschauen.

[eXile]

Ich habe eine sehr große Datenmenge, locker mal 4 GB oder mehr, auf welcher ich möglichst effizient mathematische Operationen (FFT, MER und andere Manipulationen) ausführen können muß. Außerdem soll die Datenmenge dann je nach Dimension als 2D Diagramm, 2D Höhenliniendiagramm oder 3D Volumengrafik effizient(!) dargestellt werden.

Erst einmal sind 4 GB nicht "sehr groß", sondern sogar relativ locker handhabbar, weil in der Regel die gesamten Daten, eine Kopie der gesamten Daten und das Programm selber in den RAM passen sollten. Das gibt dann allerdings auch die Großenordnung an, in welcher sich die Zielmaschine bewegen sollte: 12 GB RAM. ;)

Du hast zweierlei Probleme: Einerseits eine Verarbeitung der Daten in eine Zielmenge, welche ungefähr genauso groß ist wie die Quellmenge (FFT, etc.), andererseits eine Verarbeitung in eine Zielmenge, welche erheblich kleiner ist, als die Quellmenge (Plots, etc.).

Die Frage ist jetzt, wie implementiere ich das jetzt am Besten. Ich dachte mir, ich mache eine Schnittstelle (Interface), welche die Daten repräsentiert und eine, welche allgemein die Manipulationen (FFT, MER usw.) repräsentiert (davon kann man dann mehrere auf die Daten anwenden, ich speichere sie einfach in einer Liste/ einem Vector).

Strategy-Pattern? Wäre mein erster Einfall.

die Daten in Blöcke einteilen um möglichst wenig Cache-Mismatchs zu haben etc. und sie nach der Bearbeitung nachladen zu können, bzw. wieder auf die Platte schreiben zu können...

Diese Unterteilung ist aus mehreren Gründen sinnvoll: Zum einen kann man damit gleich für eine parallele Berechnung einsetzen, als nächstes ist die Ausfallsicherheit ein weiterer Grund, zum anderen kann dann das Lahme (nämlich das Laden und Speichern auf die Platte) wiederum parallel durchführen.

Außerdem brauche ich natürlich auch im Algorithmus die Unterstützung von SSE und anderen Besonderheiten. Wie finde ich diese Gegebenheiten für eine Hardware am besten raus? Beim Programmstart einen kleinen Testlauf machen? Lohnt es sich überhaupt diese Sachen zu ermitteln?

Für SSE und solche Geschichten gebe ich einfach mal das Stichwort cpuid vor.

Vielleicht hat ja hier jemand ein paar gute Ideen, was man da unterstützen müsste, und wie man am besten die optimale Block-Größe der Daten ermittelt.

OK, also du kannst eigentlich fast alles vergessen, bis auf eines: Parallelität, Parallelität, Parallelität. ;) Die Anzahl der Blöcke kann man ganz einfach ermitteln: Die Anzahl der möglichen parallelen (Hyper-)Threads auf allen verfügbaren Rechnern (d.h. mehrere Rechner, und Netzwerkanbindung) bestimmt diese. Erst danach kann man überlegen, ob man die Blöcke in weitere handliche Subblöcke für CPU-Berechnungen mit SSEx aufteilt (sollte in den Cache passen) oder eine GPU-Berechnung mit CUDA, etc. aufteilt.

[kimmi]

Ohne zu wissen, welche konkreten Alrorithmen du benutzen willst, kann ich dir da leider keine wirklichen Tipps geben. Beschreibe doch mal deine Algorithmen beziehungsweise Anforderungen und Aufgaben. Daraus kannst du dann versuchen, unabhängige Tasks beziehungweise Datenstrukturen abzuleiten, damit du die Aufgaben möglichst einfach parallelisieren kannst. Dann brich das Ganze herunter, bis du zum Beispiel auf Dinge wie Matrix-Operationen oder FFT's kommst. Hier kannst du dann durch lokale Daten, also beispielsweise eine Blocked-Matrix-Operation, dessen Blocks gut in den L1-Cache passen, einiges an Tempo reissen. Genausogut könnte aber auch eine Sparse-Matrix helfen oder whatever.
Die grundlegenden Datenstrukturen sind hier nun mal sehr wichtig, weswegen ich von einer Diskussion wie "Nimm c++!" oder "Nimm Java!" Abstand nehmen würde. Ich habe sehr grosse Daten sowohl mit C#, Fortran also auch mit C++ verarbeitet. Der Bottleneck wurde selten durch die Sprachwahl als vielmehr durch die Wahl der Datenstrukturen und Algorithmen beeinflusst.

Gruß Kimmi

[Chromanoid]

denk dran java 64bit zu benutzen, wenn du alles in den heap laden möchtest... :)

Die grundlegenden Datenstrukturen sind hier nun mal sehr wichtig, weswegen ich von einer Diskussion wie "Nimm c++!" oder "Nimm Java!" Abstand nehmen würde. Ich habe sehr grosse Daten sowohl mit C#, Fortran also auch mit C++ verarbeitet. Der Bottleneck wurde selten durch die Sprachwahl als vielmehr durch die Wahl der Datenstrukturen und Algorithmen beeinflusst.

sehe ich auch so.

[Stephan Theisgen]

Hallo!

Danke für die vielen Anregungen und Antworten. Also ich fasse das jetzt erstmal so zusammen, dass ich SSE wohl voraussetzen darf. Die GPU würde ich ungerne belasten, da ich die Daten mit Marching Cubes auch darstellen will und vielleicht implementiere ich Marching Cubes und auch Marchings Squares zumindest teilweise in der GPU.

Ich möchte auch keine Diskussion wie Java vs. C++, hatten wir hier schon zur Genüge (auch durch mich schon ausgelöst). Wie gesagt in Java ist es prinzipiell schnell genug funktionsfähig. Ich habe nur minimale Verzögerung auf meinem Rechner, sagen wir 10-20 Sekunden bis die ganze Prozessierung fertig ist. Ich würde das jetzt gerne durch die Optimierung und Aufteilung GPU-CPU quasi auf Echtzeit <1 Sekunde drücken wollen...

Also von den Algorithmen ist es relativ einfach: Ich habe Daten in der Zeitdomäne (1D, 2D, 3D) und diese werden dann manipuliert. Also abgeschnitten, durch Nullen ersetzt, verschoben, anschließend mit einer Funktion multipliziert und dann Fourier transformiert, danach ggf. wieder verschoben und mit einer Funktion multipliziert. Anschließend wir ein beliebiger Ausschnitt, ggf. auch alle Daten als Diagramm, 2D-Höhenliniendiagramm (Marching Squares) bzw. 3D Voxelgraphik mit Marching Cubes angezeigt.

Alle Dimensionen sind immer separierbar (können also nach einander durchgerechnet werden). Die meisten Manipulationen: Verschiebungen, Nullen, mit Funktion multiplizieren sind nur lokal also super parallelisierbar. Die FFT benötigt aber immer alle Daten...

Das Anzeigen kann man unter Umständen optimieren, denn entweder ist nur ein kleiner Teilausschnitt zu sehen, oder aber alle Daten, dann brauche ich aber nicht alle Voxel zu berücksichtigen, das kann die Auflösung meines Bildschirms dann gar nicht mehr darstellen...

Also ich fasse zusammen: Ich soll möglichst viel parallelisieren (Threads...) und dann noch SSE benutzen... Die Daten dazu sinnvoll in Blöcke aufteilen, und Marching Cubes/Squares weiter in die GPU auslagern? Natürlich vorher irgendwie sinnvoll die übermittelten Daten einengen, indem ich den Ausschnitt oder bei Vollansicht LOD berücksichtige?

Viele Grüße
Stephan

[j.klugmann]

Ich würde dir anstatt SSE Compiler Intrinsics empfehlen. Die sind optimiert und lassen sich besser einsetzen als SSE.

[Krishty]

Compiler Intrinsics sind nur eine der vielen Möglichkeiten, SSE-Text zu erzeugen; wenn er auf x64 arbeitet, kommt er daran eh nicht vorbei.

Ich würde noch Prefetching einwerfen – habe vor ein paar Jahren mal ein Beispiel gesehen, wo eine Multiplikation zweier großer float-Arrays damit so schnell wurde, dass 90 % der Speicherbandbreite genutzt wurden. Dazu zählen dann u.a. auch Anweisungen, die direktes Laden und Speichern von 128-Bit-Werten erlauben, so dass einmalig benutzte Werte nicht den Cache verschmutzen. Wenn man bedenkt, dass Laden aus dem Hauptspeicher über hundert Takte Latenz haben kann, sollte man das schon miteinkalkulieren. (Hatte aber nie direkt damit zu tun.)

————

Dann die Daten so aufsplitten dass das Working-Set fuer einen Block nicht die Groesse des L2-Caches ueberschreitet (L1 ist so klein dass du ihn vermutlich vergessen kannst - einzig der Maschinencode des Algos koennte/sollte da reinpassen).

Hiernach machen L1-Verfehlungen – wenn auch deutlich schwächer als beim L2 – einen merklichen Unterschied (14 Takte auf einem Core 2), und hiernach gibt es einen eigenen L1I-(level-1-instruction-)Cache für Programmtext (32 KiB bei Intel, 64 bei AMD) – siehe auch Harvard-Architektur.

(Wahrscheinlich wird das für den OP nie eine Rolle spielen, aber ich wollte es geraderücken.)

[kimmi]

Hm, da ich zirka 4 Jahre im Bereich numerischer Analysen und Solver gearbeitet habe, noch einmal mein Hinweis:
Beschreibe doch hier einfach mal, wie und in welcher Form deine Daten verarbeitet werden. Zum Beispiel so:

• Sammeln der Daten in einem Repo
• Filtern nach Randbedingungen
• Aufarbeitung der Daten in FFT
• Culling
• Visualisierungsset erstellen
• LOD
• Culling nicht sichtbarer Daten

( hier benutzten Architektur-Pattern Repo und Pipes )
Bei solchen Problemen sind in der Regel die Skalierung der benutzen Datenstrukturen vorab abschätzbar. Und da solltest du zunächst einmal Gehirnschmalz reinstecken, bevor du dir über die konkrete Implementierung einzelner Schritte Gedanken machst. Wenn dein Verfahren nicht skaliert, weil du einen quadratischen Algorithmus gebaut hast, ist es eher zweitrangig, ob eine Operation 10ms oder 50ms dauert. Ob du nun 4 Tage oder 10 Tage wartest, ist natürlich nicht egal, aber von der Dimension her ähnlich schmerzhaft, gerade wenn man das auch in 2 Minuten lösen kann. Und ich habe bereits beide Extreme erlebt beziehungsweise durchleben müssen.

Ich bin da gern wie folgt vorgegangen:

• Problem umreissen
• Datenstrukturen skizzieren ( zum Beispiel auf einem Blatt Papier ), braucht man statische, braucht man dynamische Daten? Was ist teuer, wie oft muss man sortieren beziehungsweise suchen, Wie werden die Daten später benutzt etc.
• Hat man einen quadratischen oder kubischen Teil identifiziert, kann man diesen durch einen anderen Entwurf versuchen zu entschärfen.

Ich habe es sehr sehr oft erlebt, dass ein Entwickler ( zum Beispiel ich :) ) genau in dieser Designphase sparte, was nicht selten zu einer weiteren Neu-Implementierung geführt hat. Hier ist jede Stunde, die man ins Design investiert, eine gute Stunde. Je mehr man das komplexe Problem an sich verstanden hat, desto mehr kann man auch versuchen, parallele Tasks zu finden, die man dann einzelnd implementiert. Und erst jetzt ist die zeit, sich darüber Gedanken zu machen, ob SSE das Ganze schnell macht.

Gruss Kimmi

P.S.: http://en.wikipedia.org/wiki/Program_optimization Denke immer an Knuth "premature optimization is the root of all evil"

[Krishty]

Was mir gerade einfällt: Implementiert Java eigentlich mittlerweile IEEE 754? Sonst haben wir hier u.U. tatsächlich ein Sprachproblem, zumal du ja wohl auch mit komplexen Zahlen arbeitest …

[Stephan Theisgen]

Hi!

Erst einmal vielen Dank für die Hilfe, hier sind ja doch ein paar gute Anregungen für mich heraus gekommen.
Mit SSE Compiler Intrinsics und prefatch (gute Idee) habe ich schon gearbeitet.
Die Pattern Repo und Pipes sehen recht gut für mich aus...

Was mir gerade einfällt: Implementiert Java eigentlich mittlerweile IEEE 754? Sonst haben wir hier u.U. tatsächlich ein Sprachproblem, zumal du ja wohl auch mit komplexen Zahlen arbeitest

Das ist ja interessant... (und ja, ich arbeite mit komplexen Zahlen).

@kimmi:

Beschreibe doch hier einfach mal, wie und in welcher Form deine Daten verarbeitet werden.

Also es handelt sich nicht um graphische Daten oder Daten wie bei der Finite Element Method, welche Du erwähnst.
Es handelt sich um NMR (Kernspinresonanz)-Daten. Ein Spektrometer zeichnet das Ergebnis eines NMR-Experimentes den sog. FID (Free Induction Decay) auf. Das ist ein komplexes und gedämpftes Signal, welches sich als Überlagerung vieler Schwingungen ergibt. Nun kann man üblicherweise, die Daten vorne und hinten abschneiden und mit Nullen füllen und den FID anschließend mit einer Funktion (meist einer abfallende e-Funktion), aber auch andere Funktionen kommen in Frage, multiplizieren. Anschließend wird Fourier transformiert, da man eigentlich am Spektrum (ist eine spektroskopische Methode) interessiert ist. Nach der FT werden dann ggf. noch einmal Manipulationen durchgeführt.

Die Arbeitsabfolge ist wie folgt:
FID (Abfolge komplexer Zahlen, konstantes Sampling Intervall) --> vorne/hinten mit Nullen füllen (auch für 2er Potenz zu erreichen) --> mit durchaus komplizierter Funktion multiplizieren, die aber nur von der Position des Messwertes abhängt --> Fourier transformieren --> Darstellen als Spektrum

Wie gesagt, alles schon in Java implementiert und funktioniert auch recht gut, nur etwas langsam...

Viele Grüße
Stephan

[Krishty]

Okay, dann halt dich von der Complex Arithmetic Class Library fern; warum und welche Alternativen es gibt steht im Artikel ab Seite elf. (Mit IEEE 754 hat das noch nichts zu tun.)

Was IEEE 754 angeht, schmeißt Java wohl Exceptions statt Traps und Default-Werte zu erlauben – und das ist genau die Art von Design-Fehler, wegen dem Raketen abstürzen. Sei also in deinem Code ständig auf sowas gefasst und handle entsprechend.

[Jaw]

Ich verstehe die Aufgabe kein bisschen und rechne schwer damit, dass dir das nichts nutzen wird, aber: Falls es möglich ist, könnte man Rechenergebnisse speichern und wieder verwenden. So ein Lookup wäre ggf. wesentlich schneller als alle gleichen Vorkommen x Mal zu rechnen. Setzt aber eben voraus, dass es wiederkehrende Rechnungen oder Teilrechnungen gibt, bei denen es dann performanter ist, die nur ein mal auszurechnen und dann x mal das Ergebnis nachzuschlagen. Kann nicht bewerten, ob das in deiner Welt vorkommen kann.

Teilweise wurden wohl lookup Tabellen sogar für Sachen wie Sinus benutzt, was heutzutage allerdings auch nicht mehr so auf die Last geht.

Ein anderer Faktor dabei ist, inwiefern man grob rechnen darf, z.B. runden, um die Lookuptabelle kleiner zu halten.

-JAW