Frage zur Parallelisierung

[drm]

Hallo Jungs,

ich hab mal ne Frage zur Parallelisierung meines Programms. Ich werte Textdateien mit einer Funktion aus, die intern Statistiken fuerht (z.B. 'wie viele Atome liegen auf der Proteinoberflaeche', etc.). Momentan laufe ich durch ein Verzeichnis und rufe die "Auswertungsfunktion" fuer jede Datei auf. Nachdem die Datei bearbeitet wurde, werden globale Zaehler aktualisiert ('wie viele Atome lagen insgesamt auf der Proteinoberflaeche', 'wie viele Atome wurden insgesamt in allen Dateien bisher gezaehlt' usw.). Das klappt auch alles sehr gut, allerdings ist mir beim letzten Durchlauf durch das beobachten von top(1) aufgefallen, dass meine CPU nur zu 25% ausgenutzt wird. Ich habe einen Dual-Core Prozessor mit 4 Threads. Offenbar(?) wird nur 1 Thread genutzt. Pro Durchlauf benoetigt das Programm immerhin ca. eine Stunde (ca. 1000 Dateien). Es ist also nicht so effizient, wie es vielleicht sein koennte.

Ich kenne mich mit parallelisierung gar nicht aus, aber fuer mich scheint es im Moment so, als sollte das Programm parallelisierbar sein, denn der einzige "Kontakt", den ein Auswertungsschritt mit dem Hauptprogramm hat, ist die Erhoehung der globalen Zaehler. Das ganze wird in Java programmiert. Meint ihr, dass man das Programm parallelisieren koennte? Falls jemand darueber hinaus noch Hinweise oder Links hat, wie das ganze unter Java zu realisieren ist, waere ich natuerlich auch sehr dankbar. Falls weitere Informationen benoetigt werden, poste ich sie natuerlich.

Viele Gruesse,
drm

Edit: Beim parsen jeder Datei wird eine weitere Funktion aufgerufen, um die Oberflaechenatome des Proteins zu berechnen. Das dauert - je nach Groesse des in der Datei beschriebenen Proteins - bis zu 15 Sekunden. Daher die lange Laufzeit und die Hoffnung auf Besserung durch Parallelisierung

 

[unull]

Du kannst natuerlich gewisse Teile deines Programms in Threads auslagern. Um auf globale Zaehler dann zuzugreifen benutzt man ueblicherweise sowas wie "Mutex" in C/C++, um zu verhindern, dass mehrere Threads gleichzeitig daran rumpfuschen und hinterher Unsinn drinsteht.

Ich denke, Du solltest einfach mal ein Java Threads-Tutorial per Google suchen, dort wird die Locking-Problematik sicher auch erklaert.

Inwiefern man das nun bei dir moeglichst sinnvoll anwenden kann, ist ohne Code schwierig zu sagen. Auf jeden Fall boete es sich doch an, die Berechnungen nach dem Parsen in einen Thread auszulagern, um zeitgleich die naechste Datei wieder zu lesen.

Dieser Link sieht brauchbar aus: http://docs.oracle.com/javase/tutorial/essential/concurrency/

 

[Kamikaze]

Wie groß ist denn der Datenbestand auf dem gearbeitet wird? Es könnte ja durchaus sein, dass die Platte die Daten nicht schnell genug geliefert werden. Dann würde es helfen die Zieldaten auf eine andere Platte zu schreiben.

Ansonsten klingt es tatsächlich ziemlich trivial deine Last zu verteilen.

Dazu nimmst du alle Jobs in eine Queue. Dann hast du 2 Möglichkeiten.

Du startest Workerthreads die sich einen Job aus der Queue holen, den Abarbeiten und danach den nächsten holen, bis sie fertig sind.

Meiner Erfahrung nach ist es performanter einen Prozess zu haben der sich um die Queue kümmert und neue Threads startet, immer wenn einer fertig ist. Einfach weil dann die Queue nicht gelockt werden muss.

 

[drm]

Schonmal vielen Dank fuer die Antworten

Das Tutorial sieht vielversprechend aus, vielen Dank fuer den Link. Ich arbeite momentan mit meinem Laptop, der nur eine Festplatte hat. Allerdings denke ich, dass das Lesen der Dateien die Platte nicht besonders beansprucht. Insgesamt sind es 1088 Dateien, jede zwischen ein paar hundert kB und ein paar MB gross. Wenn ich die Berechnung der Oberflaeche rausnehme, parst das Programm die Dateien auch in ein paar Minuten. Aufwendig ist wirklich nur die Oberflaechenberechnung.

@Kamikaze: Ich verstehe zwar, was du meinst, aber ich hab keine Ahnung, wie ich das in Java oder irgendeiner anderen Sprache implementieren soll. Hast du da irgendwelche Beispiele? Ansonsten denke ich, dass es wirklich sehr einfach sein sollte, das zu parallelisieren, ich muss nur beim Erhoehen der Zaehler aufpassen.

Vielen Dank soweit schonmal!
drm

 

[ernst]

Da wuerde ich auch sowas wie Kamikaze vorschlagen, da ich jetzt nicht wuesste ob's in Java sowas wie parallelisiertes "map" gibt.. haette da an sowas gedacht, da gibt's am Schluss noch ein kurzes Beispiel:
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html

also der Producer schreibt zB immer den Dateinamen in die Queue und die (hier 4) Consumer lesen die aus und verarbeiten jeweils die Datei aus der Queue. Wenn du den globalen Zaehler aktualisisert, muesstet du evtl noch an der richtigen Stelle ein synchronized dran schreiben, dann koennte das schon funktionieren... nehme ich an.

 

[drm]

Vielen Dank fuer den Link

Es hat mir schon gut geholfen, mal vom Producer/Consumer Modell zu hoeren. Hab mir jetzt dieses Buch besorgt, was ein ganzes Kapitel ueber Multithreading beinhaltet. Ich meld mich, wenn ich Fragen habe oder es Erfolge zu vermelden gibt

Viele Gruesse,
drm

 

[drm]

Also ich habs jetzt geschafft Hab als Datenstruktur ein ArrayBlockingQueue genommen und es so gemacht, wie ernst vorgeschlagen hat. Der Producer laeuft in einem eigenen Thread und fuellt die ArrayBlockingQueue, aus der die vier Consumer dann jeweils die Dateinamen entnehmen und damit weiterarbeiten. Den Consumern wird eine Referenz auf die Queue und eine Referenz auf einen "Statistikcontainer" uebergeben, wobei der Statistikcontainer eine 'synchronized'-Methode 'add' enthaelt. Somit werden die Statistiken in einem Objekt gesammelt und es ist sichergestellt, dass immer nur ein Thread die Statistiken aktualisiert.

Vielen Dank fuer all die Antworten, zudem kann ich das o.g. Buch wirklich empfehlen.

Liebe Gruesse,
drm

 

[unull]

Hats denn auch was gebracht? Geschwindigkeitsmaessig?

 

[drm]

Auf jeden Fall! Ich habe zwar zusaetzlich noch andere Dinge im Programm optimiert, aber meine Messung mit time ergab:

Ausgabe:

PHE  4.53    2.41    0.53
LYS  7.92    8.30    1.05
THR  5.31   11.91    2.24
ARG  6.44   11.91    1.85
MET  2.32    0.50    0.21
CYS  0.99    0.71    0.72
ASP  6.20    3.62    0.58
GLU  8.27    4.11    0.50
ASN  4.47    3.62    0.81
GLY  5.65    9.50    1.68
SER  6.12   11.13    1.82
GLN  4.20    1.35    0.32
VAL  5.21    2.98    0.57
TYR  3.99    1.35    0.34
ALA  5.30    3.69    0.70
TRP  1.53    0.71    0.46
PRO  5.24    1.13    0.22
LEU  8.54    0.99    0.12
HIS  3.03    6.24    2.06
ILE  4.74   13.83    2.92

mit einem Consumer-Thread:
real    43m1.448s
user    86m26.712s
sys     0m5.813s

mit vier Consumer-Threads:
real    23m34.837s
user    91m40.371s
sys     0m5.253s

Ganze 20 Minuten

 

[k_e_x]

Ich weiss ja nicht ganz genau was deine Anwendung ist. Bei mir ist oft das Problem das ich mit grossen Datenmengen arbeiten muss und eine Korrelation zwischen gemessenem Signal und Modell bilden muss.

Besonders problematisch ist dabei vor allem das oeffnen/schliessen (d.h. anlegen der file-handles). Deshalb wird nicht 1 messung = 1 datei sondern immer z.b. 10 000 messungen in eine datei gepackt (gerade soviel, dass man es noch 1:1 in den arbeitsspeicher lesen kann).

 

[drm]

Also ich hab wie gesagt ca. 1000 Dateien, die ich bearbeite. Das Ergebnis der Berechnungen kommt am Ende in eine Datei (s.o.). Das einzig Speicherintensive ist das Parsen, da gehen locker 500 MB drauf. Hab den Parser nicht selbst geschrieben, daher weiss ich nicht in wieweit man den Speicherverbrauch senken koennte. Der Grossteil wird von Strings, die den Zeileninhalt speichern, benutzt.