Geschwindigkeitsgewinn von Multithreading Berechnungen

[Neutral General]

Hallo,

Habe gestern mal testweise ein kleines Programm geschrieben was die Mandelbrotmenge einmal "normal" in 1 Thread berechnet und 1x habe ich die Berechnung auf 2 Threads aufgeteilt. (Jeder die Hälfte).

Habe hier einen Dualcore und die Berechnung in 2 Threads war ca. 29-30% schneller als mit nur 1 Thread.

Allerdings kommt mir das etwas wenig vor. Sind 30% in Ordnung bzw. hat es einen Grund warum es nur 30% sein können oder mache ich vllt. irgendwas falsch/komisch (dann müsste ich euch mehr Details geben) und der Geschwindigkeitszuwachs müsste größer sein?

Gruß
Neutral General

[s.h.a.r.k]

Ich weiß nicht, wie die Berechnung selbst aussieht, was aber zum Flaschenhals werden kann ist der Zugriff auf gemeinsame Daten, der dann entweder synchronisiert oder mit Critical Sections abgefangen werden muss. Das bremst einen der beiden Threads dann unter Umständen aus.

[markusj]

Multicore bedeutet ja nur, dass du zwei Berechnungseinheiten (inklusive Caches etc.) hast.
Bei Anwendungen, die sehr rechenintensiv sind, dabei aber auch einer kleinen Datenmenge operieren (optimal: < Cachegröße), ist tatsächlich ein Speedup von fast Faktor zwei zu erwarten.
Arbeitet dein Algorithmus aber mit großen Datenmengen, hast du neben dem üblichen Synchronisationsaufwand das Problem, dass alle beteiligten Cores sich einen gemeinsamen Flaschenhals teilen: Den Arbeitsspeicher. Solche Algorithmen profitieren daher weniger stark von mehreren Kernen oder können unter Umständen sogar langsamer werden.
Gerade aus diesem Grund wird z.Bsp. stark an parallele Sortieralgorithmen geforscht, die ein gutes Skalierungsverhalten aufweisen - du kannst ja Mal zwei parallele Mergesorts auf deiner Maschine antreten, das Ergebnis sollte relativ bescheiden ausfallen.
Anwendungen bei aufgrund von I/O-Operationen o.ä. viel gewartet wird, können auch Speedups von weit mehr als Faktor zwei erreichen.

mfG
Markus

PS: In diesem Text: Multicore = Dualcore, damit ist der Speedup bei nur rechenintensiven Anwendungen = Faktor 2

[Khabarakh]

Zitat:

Zitat von Neutral General

(Jeder die Hälfte)

Ich weiß zwar nicht, was das genau heißt, aber hier wird wahrscheinlich das Problem liegen. Wenn du nur einzelne Zeilen oder gar Pixel nacheinander von verschiedenen Threads abarbeiten lässt, streiten sich die Threads zu oft um die gleiche Cache Line, wenn du zu viele Zeilen mit einer statischen Zuteilung abarbeiten lässt, muss am Schluss auf die restlichen Threads gewartet werden.
Ich habe es mal schnell mit Threads getestet, die - dynamisch zugeteilt vom .NET-PFX - jeweils 10 Zeilen auf einmal beharken. 3,7-fache Performance auf meine Quad-Core, ohne überhaupt den Profiler zu öffnen und nachzuschauen, was liegen bleibt :) .

[Neutral General]

Ok, vom Faktor 2 bin ich weit enffernt. ich poste mal meinen Code:

Der Thread:

Delphi-Quellcode:

type
  TPointF = record
    X,Y: Extended;
  end;

  TComplex = record
    R: Extended;
    I: Extended;
  end;

  TDataArray = Array of Array of Word;

  TWorkDoneEvent = procedure(Sender: TThread; Data: TDataArray) of object;
  
  TMandelbrotThread = class(TThread)
  private
    FSizeX,FSizeY: Integer;
    FData: TDataArray;
    FMatrix: Array of Array of TComplex;
    FIterations: Integer;
    FOnDataAvailable: TWorkDoneEvent;
    procedure DoWorkDone;
  protected
    procedure Execute; override;
  public
    constructor Create(ASizeX, ASizeY: Integer; P1, P2: TPointF); reintroduce;
    destructor Destroy; override;
    procedure Init(P1,P2: TPointF);
    property Iterations: Integer read FIterations write FIterations;
    property OnDataAvailable: TWorkDoneEvent read FOnDataAvailable write FOnDataAvailable;
  end;

implementation

constructor TMandelbrotThread.Create(ASizeX,ASizeY: Integer; P1,P2: TPointF);
var i: Integer;
begin
  inherited Create(true);
  FSizeX := ASizeX;
  FSizeY := ASizeY;

  SetLength(FData,FSizeY);
  SetLength(FMatrix,FSizeY);
  for i := 0 to FSizeY - 1 do
  begin
    SetLength(FData[i],FSizeX);
    FillChar(FData[i][0],FSizeX*SizeOf(Word),0);
    SetLength(FMatrix[i],FSizeX);
  end;

  Init(P1,P2);
end;

procedure TMandelbrotThread.Init(P1,P2: TPointF);
var i,j: Integer;
    stepX,stepY: Extended;
begin
  stepX := abs(P2.X-P1.X)/FSizeX;
  stepY := abs(P2.Y-P1.Y)/FSizeY;
  for i := 0 to FSizeY - 1 do
    for j := 0 to FSizeX - 1 do
    begin
      FMatrix[i,j].R := P1.X+j*stepX;
      FMatrix[i,j].I := P1.Y-i*stepY;
    end;
end;

procedure TMandelbrotThread.Execute;
var i,j,k: Integer;
    tmp, x: TComplex;
begin
  for i := 0 to FSizeY - 1 do
    for j := 0 to FSizeX - 1 do
    begin
      tmp := FMatrix[i,j];
      for k := 1 to FIterations do
      begin
        if CAbs(tmp) > 2 then // CAbs = Betrag der Komplexen Zahl
        begin
          FData[i,j] := k;
          break;
        end;
        x := CSqr(tmp); // CSqr = Komplexe Zahl "tmp" wird quadriert.
        tmp.R := X.R + FMatrix[i,j].R;
        tmp.I := X.I + FMatrix[i,j].I;
      end;
    end;
  Synchronize(DoWorkDone);
end;

MainThread:

Delphi-Quellcode:

procedure TForm2.Button2Click(Sender: TObject);
var tmp: Array[0..1] of TMandelbrotThread;
    i: Integer;
begin
  // Linke hälfte des Bildes
  tmp[0] := TMandelbrotThread.Create(500,1000,PointF(-2,2),PointF(0,-2));
  tmp[0].FreeOnTerminate := true;
  tmp[0].Iterations := 500;
  tmp[0].OnDataAvailable := MandelbrotEvent1;
  // SetThreadAffinityMask(tmp[0].Handle,1 shl 0);

  // Rechte Hälfte
  tmp[1] := TMandelbrotThread.Create(500,1000,PointF(0,2),PointF(2,-2));
  tmp[1].FreeOnTerminate := true;
  tmp[1].Iterations := 500;
  tmp[1].OnDataAvailable := MandelbrotEvent2;
  // SetThreadAffinityMask(tmp[1].Handle,1 shl 1);

  // Start
  tmp[0].Resume;
  tmp[1].Resume;
end;

[Khabarakh]

Das ist auf jeden Fall zu grobkörnig. Schon mit 100 Zeilen pro Batch komme ich nur noch auf 2,4-fache Geschwindigkeit (wenn man allerdings die Laufzeiten der einzelne Kerne zusammenzählt, kommt man fast an die Zeit des seriellen Algorithmus, Multithreading-Overhead ist also nicht mehr vorhanden).

[Neutral General]

Was heißt zu grobkörnig? Soll ich kleinere Happen machen und jeder Thread bekommt die Hälfte der Happen oder wie?

[Neutral General]

*push*

[Khabarakh]

Zitat:

Zitat von Neutral General

Was heißt zu grobkörnig?

Hm, dafür habe ich eigentlich meine Ergebnisse gepostet ;) . 100 Zeilen pro Batch sind immer noch zu viel, 10 sehen gut aus.

[Neutral General]

Ja.. schon..

Aber soll ich dann wenn ein Thread fertig ist einen neuen erstellen der die nächsten 10 Zeilen macht?
Ich verstehe nicht warum das schneller sein soll :?

[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.

[Namenloser]

Zitat:

Zitat von Neutral General

Neue Theorien? :mrgreen:

Turbo-Boost? :gruebel:

[Neutral General]

Hab ich im BIOS auf Enabled gehabt. Habs testweise auf Disabled gestellt. Hat aber nichts geändert. Es gibt noch "Auto". Das hab ich jetzt noch nicht probiert.. Ich kanns mal versuchen, glaube aber nicht dass es was bringt.