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 :?