Geschwindigkeitsgewinn von Multithreading Berechnungen

[shmia]

Beim Mandelbrot kann sich das Problem ergeben, dass der eine Thread schon fertig ist während der Andere noch arbeiten muss.
Man müsste das Gesamtbild in kleinere Kacheln (vielleicht 16 * 16 Pixel) zerlegen.
Immer wenn ein Thread fertig ist, bekommt er die nächste Kachel zugeteilt (oder es wird ein neuer Thread mit der der Berechnung für die Kachel gestartet).

[Neutral General]

Zitat:

Zitat von shmia

Beim Mandelbrot kann sich das Problem ergeben, dass der eine Thread schon fertig ist während der Andere noch arbeiten muss.
Man müsste das Gesamtbild in kleinere Kacheln (vielleicht 16 * 16 Pixel) zerlegen.
Immer wenn ein Thread fertig ist, bekommt er die nächste Kachel zugeteilt (oder es wird ein neuer Thread mit der der Berechnung für die Kachel gestartet).

Naja ich habe das Gefühl gehabt dass der 2. Thread fast erst dann anfängt wenn der 1. aufgehört hat. Bzw. anders gesagt hat der 2. Thread fast doppelt so lange gebraucht wie der 1.

[Medium]

Beim Mandelbrot braucht der mittlere Bereich (der, der üblicherweise schwarz ist - die eigentliche Mandelbrotmenge) am längsten, da dort immer die maximale Iterationstiefe erreicht wird, folglich sollte, wenn man an der realen Achse in 2 Teile teilt, der untere Teil weit weniger geschafft haben als der obere, vorausgesetzt beide fangen lokal von oben an. Jedoch sollten sie schon einigermaßen gleichzeitig fertig werden am Ende. Joinst du irgendwo, oder weist du evtl. unterschiedliche Prios zu? Oder evtl. zu hohe Prios?

Ich würde generell schon fast dazu übergehen, für jede Zeile einen Thread zu machen, dann aber so ~4-8 am Stück starten, und jedes Mal wenn einer fertig wird, wieder auffüllen. Das ist aber vermutlich nur ab gewisser Größe des Bildes sinnig, sonst könnte der Verwaltungsoverhead merkbar werden.

Noch ein kleiner Beschleunigungstipp: Das einfache Mandelbrötchen ist spiegelsymmetrisch zur realen Achse -> du musst bei zentrierter Ansicht nur das halbe Bild berechnen.

[Khabarakh]

Zitat:

Zitat von Neutral General

Aber soll ich dann wenn ein Thread fertig ist einen neuen erstellen der die nächsten 10 Zeilen macht?

Wozu einen neuen Thread? Der alte bleibt bestehen und holt sich die nächsten zehn Zeilen. Ohne TPL könnte das etwa so aussehen:

Delphi-Quellcode:

var sharedY := 0;

for var i := 1 to Environment.ProcessorCount do
   new Thread(->
      begin
         while true do
         begin
            var startY := Interlocked.Add(var sharedY, 10);
            if startY >= Height then
               break;
            for var y := startY to Math.Min(startY + 9, Height - 1) do
               for var x ....
         end;
      end;
   ).Start();

[Neutral General]

Hallo,

Hab das ganze nochmal neu implementiert und nun läuft es auf 2 Kernen etwa doppelt so schnell wie auf einem.
Allerdings habe ich hier einen Quadcore und weder bei 3 noch bei 4 Kernen wird er schneller. Diese sind auch im Taskmanager nicht wirklich ausgelastet.

Habe hier einen Intel i5. Kann es sein, dass es an diesem Turboboost liegt? Bzw. muss ich in diesem Fall irgendetwas beachten?

[H4ndy]

Die meisten Core i5 haben nur zwei echte Cores. Die beiden anderen kommen durchs vom Pentium 4 bekannte Hyper Threading zustande.
Nur der i5-750S und i5-750 haben sind echte Quad-Cores (Quelle).

Turbo Boost macht nix anderes, als einzelne Kerne automatisch hochzutakten, wenn nicht alle genutzt werden (z.B. bei rechenintensive Single-Thread-Anwendungen, alte Spiele z.B.). Da musst du also eigentlich nix beachten. Wenn beide Kerne genutzt werden, wird TB nicht aktiviert.

[Khabarakh]

Ja, da würde ich auch auf Hyperthreading tippen. In der Zwischenzeit hab ich mal ein paar Werte von meinem Q6600 gesammelt :) .
http://imgur.com/3J3Rx.png

Wenn ich daraus mal ein Fazit ziehen darf: Zumindest bei diesem Problem ist der Interlocked-Aufruf im Vergleich zur eigentlichen Arbeit so billig, dass man eigentlich mit keiner vernünftigen Batchgröße etwas falsch machen kann :D .

[H4ndy]

Erstaunlich, dass ab 4 Pixeln schon eine brauchbare Effizienz rauskommt.
OT: Was hast du fuer zur Diagramm-Erstellung genutzt? Office?

[Khabarakh]

Jupp, Excel. Ich habe mal die Rechenzeit verzehnfacht, um Schwankungen auszugleichen. Ergebnis siehe oben: Jetzt ist es wirklich ganz egal, ob man nun in 10 oder 10000 Pixel partitioniert.
Die Daten noch dazu: 1920x1080, maximale Iterationstiefe 1000, Abbruchbedingung |z| > 2

[Neutral General]

Hallo,

Danke für eure "Forschungsarbeiten" :)
Ich habe aber tatsächlich einen i5 750 und somit echte 4 Kerne. Hyperthreading unterstützt dieser Prozessor nicht.

Neue Theorien? :mrgreen:

Notfalls kann ich meinen Code mal hochladen. Sind allerdings schon ein paar Zeilen.