Multithreading für kleine Aufgaben

[DerAlbi]

Hallo Leute,
ich verfolge das Forum schon länger, muss nun aber selbst mal meine sorgen los werden :-)
Kurzum: Es geht um einen Iterativen Solver für ein lineares Gleichungssystem mit 1k..2M Unbekannten.
Dabei werden Punktprodule (x dot y), Normen (x dot x), Matrix-Vektormultiplikationen (A*x) und Vektoradditionen (x+c*y) berechnet.
Ein Punktprodukt über sehr große Vektoren geht nur mit hierarchischer Verarbeitung. Also immer nur gruppenweise aufaddieren, dann die Gruppen wieder in Gruppen bis nur noch eine Zahl übrig bleibt.

Ein Lösungsvorgang kann recht lange dauern (10..20min) und dabei rechnet nur eine CPU im ganzen System - das ist sehr schade. Ich würde die Zeit viel lieber halbieren und zwei Threads benutzen, oder sogar mehr, auf Prozessoren mit mehr kernen.
Das Problem ist, dass der algorithmus sehr sequentiell arbeitet. Also berechne ich ein Punktprodukt, wird das auch im nächsten schritt gebraucht. Berechnet ich einen Vektor, wird der auch danach sofort benötigt und hängst selbst vom Schritt vorher ab. bäääh.
Alles was mir übrig bleib ist, die jeweiligen Unteraufgaben in Threads zu unterteilen.
Ich habe versucht das beim Punktprodukt umzusetzen und bin vom ergenis sehr entäuscht. Das Multithreading scheint mehr verwaltungsaufwand zu sein, als die berechnung, sodass ich je mehr Threads ich verwende, umso länger brauche^^ Ich hätte eigentlich lieber das reziproke Verhalten :-D

Zur Zeit gehe ich so vor:

In den Threads:
1) WaitForSingleObject(StartEvent....)
2) Berechnung
3) SetEvent(FertigEvent)

Der Aufrufer macht nur
1) Threaderzeugen
2) Daten aufsetzen
3) SetEvent(StartEvent) für jeden Thread
--- sollte der Thread hier selbst was rechen??
4) WaitForMultipleObjects( bis alle das Threads das FertigEvent gesendet haben)
5) die ergebnisse der einzelnen Threads addieren, fertig.

Ich beobachte nun, dass meine CPU, wenn sie gezwungen ist durchweg sinnlos Punktproduke in Endlosschleife zu berechnen maximal zu ~60% ausgelastet wird.
Die Kommunikation zwischen SetEvent und WaitForSingleObject ist also durchaus mit viel Leerlauf verbunden - die berechnung ist dann schon fast egal. :-(
Richtig krass bemerkbar ist das, wenn der Vektor relativ klein wird.

Die frage ist nun: wie parallelisiert man nun sowas effizient?
Ich selbst habe 6 Kerne / 12 Threads. und keiner bekommt was zu tun :-(

[eXile]

Fragen:

• Erzeugst du neue Threads für jeden Aufruf einer Punktproduktberechnung, oder benutzt du einen Thread-Pool?
• Wie groß sind die Aufgabenblöcke für einen Thread?
  Bedenke, dass die Stackgröße von einem neuen Thread in der Regel ein Megabyte beträgt; da kann man schon viel drauf rechnen.
• Hast du die low-hanging fruit mit SIMD-Berechnungen bereits abgegrast?

Wenn du ganz mutig bist, kannst du ja auch Fibers statt Threads benutzen, da es für mich sich gerade so anhört, als ob bei dir die Kontextwechsel tatsächlich einen Flaschenhals darstellen.

[kimmi]

Wenn du jedes Mal einen Thread erzeugst: nicht machen, lieber einen ThreadPool verwenden.

Du kannst die ganze Sache auch einfach mit Tasks machen. Dafür empfehle ich dir die Threading Building Blocks Lib von Intel ( http://threadingbuildingblocks.org/ ). Gerade Matrix Operationen lassen sich sehr gut durch passende Häppchen cache-freundlich parallelisieren. Aber dazu findest du jede Menge guter Informationen im Netz.

Gruß Kimmi

[dot]

Wirf vielleicht mal einen Blick auf std::async()...

[DerAlbi]

Danke für die Antworten :-)
Ich erzeuge den jeweiligen Thread natürlich nur einmal. Dieser läuft dann in einer Endlosschleife, in der er jedesmal in WaitForSingleObject() hängen bleibt, bis ein Event vom HauptThreads aus gesendet wird. Ich weiß nicht, ob das dann "ThreadPool" genannt wird, oder ob das nochmal ein optimiertes Konstrukt für solche situationen ist.

Der Aufgabenblock eines jeden Threads ist je nach Vektorgröße und Threadanzahl nur ein Bruchteil des gesamten. Also bei 6k Einträgen im Vektor und 12 Threads würde jeder Thread nur das Punktprodukt aus 500 einträgen bilden. SIMD ist noch nicht implementiert - tut imho aber auch nichts zur Sache, da das Prinzip scheiße ist, dass nur ein Kern rechnet :-(

Die Threading Building Blocks Lib klingt sehr interessant, aber erstmal würde ichg ern abklären, ob sich das einarbeiten in eine neue Lib lohnt. Schon alleine das MarketingVideo der Seite spricht meinem Code aus der Seele. Aber ob es effitient ist, ist trotzdem noch die frage.
Was mich beschäftigt: ich nutze echt nur die minimalsten Grundlagen (Endlosschleife, WaitForSingleObject, SetEvent) und damit funktioniert es einfach nicht sinnvoll.

Was machen solche Libs anders, damit es schneller gehen könnte? oder hängen die letztlich wieder am selben problem......

[kimmi]

Ich glaube zusammengefasst kann man sagen: an solchen Libs arbeiten leute, die seit 20-30 Jahren nichts anderes machen als solche Probleme zu lösen :).

Gruß Kimmi

[simbad]

Also ich mache viele Sachen in mehreren Threads und habe normalerweise auch einen Vorteil daraus.
Die Denkweise ist vielleicht eine etwas andere, was vielen Programmierern nicht liegt, so scheint das manchmal.
Aber vielleicht sollte da mal einer draufschauen, was du da machst. Vielleicht ist es einfach nur ungünstig geschrieben?