3

私は差分進化最適化アルゴリズムの実装に取り​​組んでおり、母集団メンバーを並行して計算することで計算時間を短縮したいと考えています。私は OmniThread ライブラリを使用しており、ループの並列化に成功しましたが、シリアル実装よりも遅いことがわかりました。

並列化をテストするためにコードを本質的に縮小しましたが、縮小バージョンでも同じ問題が発生します。並列バージョンはシリアル バージョンよりも低速です。

重要なのは、母集団のメンバーごとに出力を書き込む複数の動的配列を渡すことです。各配列には母集団メンバー専用の次元が 1 つあるため、母集団メンバーごとに異なる配列インデックスのセットがアクセスされます。これは、並列実装では、2 つのスレッドが同じ配列要素に書き込むことはないことも意味します。

テストに使用したコードの下 (差分進化の実際のコードには、DoWorkさらに多くのconstパラメーターとvar配列を持つプロシージャーがあります)

unit Unit1;

interface

type
  TGoalFunction = reference to function(const X, B: array of extended): extended;
  TArrayExtended1D = array of extended;
  TArrayExtended2D = array of TArrayExtended1D;

  TClassToTest = class abstract
  private
    class procedure DoWork(const AGoalFunction: TGoalFunction; const AInputArray: TArrayExtended2D; var AOutputArray1: TArrayExtended1D; var AOutputArray2: TArrayExtended2D; const AIndex, AIndex2: integer);
  public
    class procedure RunSerial;
    class procedure RunParallel;
  end;

function HyperSphere(const X, B: array of extended): extended;

const
  DIMENSION1 = 5000;
  DIMENSION2 = 5000;
  LOOPS = 10;

implementation

uses
  OtlParallel;

function HyperSphere(const X, B: array of extended): extended;
var
  I: Integer;
begin
  Result := 0;
  for I := 0 to Length(X) - 1 do
    Result := Result + X[I]*X[I];
end;

{ TClassToTest }

class procedure TClassToTest.DoWork(const AGoalFunction: TGoalFunction; const AInputArray: TArrayExtended2D; var AOutputArray1: TArrayExtended1D; var AOutputArray2: TArrayExtended2D; const AIndex, AIndex2: integer);
var
  I: Integer;
begin
  AOutputArray1[AIndex] := AGoalFunction(AInputArray[AIndex], []);
  for I := 0 to Length(AOutputArray2[AIndex]) - 1 do
    AOutputArray2[AIndex, I] := Random*AIndex2;
end;

class procedure TClassToTest.RunParallel;
var
  LGoalFunction: TGoalFunction;
  LInputArray: TArrayExtended2D;
  LOutputArray1: TArrayExtended1D;
  LOutputArray2: TArrayExtended2D;
  I, J, K: Integer;
begin
  SetLength(LInputArray, DIMENSION1, DIMENSION2);
  for I := 0 to DIMENSION1 - 1 do
  begin
    for J := 0 to DIMENSION2 - 1 do
      LInputArray[I, J] := Random;
  end;
  SetLength(LOutputArray1, DIMENSION1);
  SetLength(LOutputArray2, DIMENSION1, DIMENSION2);

  LGoalFunction := HyperSphere;

  for I := 0 to LOOPS - 1 do
  begin
    Parallel.ForEach(0, DIMENSION1 - 1).Execute(
      procedure (const value: integer)
      begin
        DoWork(LGoalFunction, LInputArray, LOutputArray1, LOutputArray2, value, I);
      end
    );

    for J := 0 to DIMENSION1 - 1 do
    begin
      for K := 0 to DIMENSION2 - 1 do
        LInputArray[J, K] := LOutputArray2[J, K];
    end;
  end;
end;

class procedure TClassToTest.RunSerial;
var
  LGoalFunction: TGoalFunction;
  LInputArray: TArrayExtended2D;
  LOutputArray1: TArrayExtended1D;
  LOutputArray2: TArrayExtended2D;
  I, J, K: Integer;
begin
  SetLength(LInputArray, DIMENSION1, DIMENSION2);
  for I := 0 to DIMENSION1 - 1 do
  begin
    for J := 0 to DIMENSION2 - 1 do
      LInputArray[I, J] := Random;
  end;
  SetLength(LOutputArray1, DIMENSION1);
  SetLength(LOutputArray2, DIMENSION1, DIMENSION2);

  LGoalFunction := HyperSphere;

  for I := 0 to LOOPS - 1 do
  begin
    for J := 0 to DIMENSION1 - 1 do
    begin
      DoWork(LGoalFunction, LInputArray, LOutputArray1, LOutputArray2, J, I);
    end;

    for J := 0 to DIMENSION1 - 1 do
    begin
      for K := 0 to DIMENSION2 - 1 do
        LInputArray[J, K] := LOutputArray2[J, K];
    end;
  end;
end;

end.

8 コア プロセッサで約 x6 の速度向上を期待していましたが、わずかな速度低下に直面しました。DoWorkプロシージャを並行して実行することでスピードアップするには、何を変更すればよいですか?

DoWorkメンテナンスを容易にするためにコードの本体を共有しながら、並列化 (ブール値フラグ) の有無にかかわらず同じアルゴリズムを呼び出すことができる必要があるため、実際の作業はプロシージャ内に保持することをお勧めします。

4

3 に答える 3

4

これは、 のスレッド セーフの欠如によるものですRandom。その実装は次のとおりです。

// global var
var
  RandSeed: Longint = 0;    { Base for random number generator }

function Random: Extended;
const
  two2neg32: double = ((1.0/$10000) / $10000);  // 2^-32
var
  Temp: Longint;
  F: Extended;
begin
  Temp := RandSeed * $08088405 + 1;
  RandSeed := Temp;
  F  := Int64(Cardinal(Temp));
  Result := F * two2neg32;
end;

RandSeedは への呼び出しによって変更されるグローバル変数であるためRandom、スレッドは への書き込みが競合することになりRandSeedます。そして、これらの書き込みの競合がパフォーマンスの問題を引き起こします。並列コードを効果的にシリアル化します。真のシリアルコードよりも遅くなるほど深刻です。

以下のコードをユニットの実装セクションの先頭に追加すると、違いがわかります。

threadvar
  RandSeed: Longint;

function Random: Double;
const
  two2neg32: double = ((1.0/$10000) / $10000);  // 2^-32
var
  Temp: Longint;
  F: Double;
begin
  Temp := RandSeed * $08088405 + 1;
  RandSeed := Temp;
  F  := Int64(Cardinal(Temp));
  Result := F * two2neg32;
end;

共有された競合する書き込みを回避するための変更により、並列バージョンが期待どおりに高速であることがわかります。プロセッサ数による線形スケーリングは得られません。私の推測では、並列バージョンのコードではメモリ アクセスのパターンが最適ではないためです。

Randomデータを生成する手段としてのみ使用していると思います。ただし、RNG が必要な場合は、各タスクが RNG の独自のプライベート インスタンスを使用するように調整する必要があります。

Sqr(X)ではなくX*Xを使用して、コードを少し高速化することもできDoubleますExtended。

于 2014-04-03T13:41:54.860 に答える