c# - 並列FORループで時間を節約

Question

並列forループについて質問があります。私は次のコードを持っています：

    public static void MultiplicateArray(double[] array, double factor)
    {
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = array[i] * factor;
        }
    }

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication)
    {
        for (int i = 0; i < arrayToChange.Length; i++)
        {
            arrayToChange[i] = arrayToChange[i] * multiplication[i];
        }
    }

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension)
    {
        for (int i = 0; i < arrayToChange.Length; i++)
        {
            arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension];
        }
    }

今、私は並列関数を追加しようとしています：

    public static void MultiplicateArray(double[] array, double factor)
    {
        Parallel.For(0, array.Length, i =>
            {
                array[i] = array[i] * factor;
            });
    }

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication)
    {
        Parallel.For(0, arrayToChange.Length, i =>
        {
            arrayToChange[i] = arrayToChange[i] * multiplication[i];
        });
    }

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension)
    {
        Parallel.For(0, arrayToChange.Length, i =>
        {
            arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension];
        });
    }

問題は、時間を無駄にするのではなく、時間を節約したいということです。標準のforループでは約2分を計算しますが、並列のforループでは3分かかります。なんで？

Answer 1

Parallel.For()コードを並列化することでパフォーマンスを大幅に向上させることができますが、オーバーヘッドもあります（スレッド間の同期、反復ごとにデリゲートを呼び出す）。また、コードでは、各反復が非常に短いため（基本的に、CPU命令が数個しかない）、このオーバーヘッドが顕著になる可能性があります。

このため、使用するParallel.For()ことはあなたにとって正しい解決策ではないと思いました。代わりに、コードを手動で並列化すると（この場合は非常に簡単です）、パフォーマンスが向上する場合があります。

これを確認するために、いくつかの測定を実行しMultiplicateArray()ました。200 000 000アイテムの配列に対してさまざまな実装を実行しました（使用したコードは以下のとおりです）。私のマシンでは、シリアルバージョンは一貫して0.21秒かかり、Parallel.For()通常は約0.45秒かかりましたが、ときどき8〜9秒に急上昇しました。

まず、一般的なケースを改善しようとしますが、後でそれらのスパイクに到達します。配列をN個のCPUで処理したいので、配列をN個の同じサイズのパーツに分割し、各パーツを個別に処理します。結果？0.35秒 それはまだシリアルバージョンよりも悪いです。ただしfor、配列内の各項目のループは、最も最適化された構成の1つです。コンパイラを助けるために何かできることはありませんか？ループの境界の計算を抽出すると役立つ場合があります。それがすることがわかります：0.18秒。これはシリアルバージョンよりも優れていますが、それほどではありません。そして、興味深いことに、4コアマシン（ハイパースレッディングなし）で並列度を4から2に変更しても、結果は変わりません。それでも0.18秒です。これにより、CPUはここでのボトルネックではなく、メモリ帯域幅はボトルネックであると結論付けることができます。

さて、スパイクに戻りましょう。私のカスタム並列化にはスパイクがありませんがParallel.For()、なぜですか？Parallel.For()範囲分割を使用します。これは、各スレッドが配列の独自の部分を処理することを意味します。ただし、1つのスレッドが早期に終了した場合、まだ終了していない別のスレッドの範囲の処理を支援しようとします。その場合、多くの偽共有が発生し、コードの速度が大幅に低下する可能性があります。そして、偽共有を強制する私自身のテストは、これが確かに問題である可能性があることを示しているようです。の並列度を強制するParallel.For()と、スパイクが少し改善されるようです。

もちろん、これらの測定値はすべて私のコンピューターのハードウェアに固有のものであり、ユーザーによって異なるため、独自の測定値を作成する必要があります。

私が使用したコード：

static void Main()
{
    double[] array = new double[200 * 1000 * 1000];

    for (int i = 0; i < array.Length; i++)
        array[i] = 1;

    for (int i = 0; i < 5; i++)
    {
        Stopwatch sw = Stopwatch.StartNew();
        Serial(array, 2);
        Console.WriteLine("Serial: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        ParallelFor(array, 2);
        Console.WriteLine("Parallel.For: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        ParallelForDegreeOfParallelism(array, 2);
        Console.WriteLine("Parallel.For (degree of parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallel(array, 2);
        Console.WriteLine("Custom parallel: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelExtractedMax(array, 2);
        Console.WriteLine("Custom parallel (extracted max): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelExtractedMaxHalfParallelism(array, 2);
        Console.WriteLine("Custom parallel (extracted max, half parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelFalseSharing(array, 2);
        Console.WriteLine("Custom parallel (false sharing): {0:f2} s", sw.Elapsed.TotalSeconds);
    }
}

static void Serial(double[] array, double factor)
{
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = array[i] * factor;
    }
}

static void ParallelFor(double[] array, double factor)
{
    Parallel.For(
        0, array.Length, i => { array[i] = array[i] * factor; });
}

static void ParallelForDegreeOfParallelism(double[] array, double factor)
{
    Parallel.For(
        0, array.Length, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount },
        i => { array[i] = array[i] * factor; });
}

static void CustomParallel(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelExtractedMax(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < max;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelExtractedMaxHalfParallelism(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount / 2;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < max;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelFalseSharing(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    int i = -1;

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                int j = Interlocked.Increment(ref i);
                while (j < array.Length)
                {
                    array[j] = array[j] * factor;
                    j = Interlocked.Increment(ref i);
                }
            });
    }

    Task.WaitAll(tasks);
}

出力例：

Serial: 0,20 s
Parallel.For: 0,50 s
Parallel.For (degree of parallelism): 8,90 s
Custom parallel: 0,33 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,53 s
Serial: 0,21 s
Parallel.For: 0,52 s
Parallel.For (degree of parallelism): 0,36 s
Custom parallel: 0,31 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,19 s
Custom parallel (false sharing): 7,59 s
Serial: 0,21 s
Parallel.For: 11,21 s
Parallel.For (degree of parallelism): 0,36 s
Custom parallel: 0,32 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,76 s
Serial: 0,21 s
Parallel.For: 0,46 s
Parallel.For (degree of parallelism): 0,35 s
Custom parallel: 0,31 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,58 s
Serial: 0,21 s
Parallel.For: 0,45 s
Parallel.For (degree of parallelism): 0,40 s
Custom parallel: 0,38 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,58 s

Answer 2

Svickはすでにすばらしい答えを提供していますが、重要な点は、使用する代わりに「コードを手動で並列化する」ことではなく、より大きなデータのチャンクParallel.For()を処理する必要があることを強調したいと思います。

Parallel.For()これは、次のように使用して実行できます。

static void My(double[] array, double factor)
{
    int degreeOfParallelism = Environment.ProcessorCount;

    Parallel.For(0, degreeOfParallelism, workerId =>
    {
        var max = array.Length * (workerId + 1) / degreeOfParallelism;
        for (int i = array.Length * workerId / degreeOfParallelism; i < max; i++)
            array[i] = array[i] * factor;
    });
}

これはsvicksと同じことをしますCustomParallelExtractedMax()が、より短く、より単純で、（私のマシンでは）わずかに高速です。

Serial: 3,94 s
Parallel.For: 9,28 s
Parallel.For (degree of parallelism): 9,58 s
Custom parallel: 2,05 s
Custom parallel (extracted max): 1,19 s
Custom parallel (extracted max, half parallelism): 1,49 s
Custom parallel (false sharing): 27,88 s
My: 0,95 s

ところで、他のすべての答えから欠落しているこのためのキーワードは粒度です。

Answer 3

PLINQおよびTPLのカスタムパーティショナーを参照してください。

ループでは、Forループの本体がデリゲートとしてメソッドに提供されます。そのデリゲートを呼び出すコストは、仮想メソッド呼び出しとほぼ同じです。シナリオによっては、並列ループの本体が十分に小さいため、各ループの反復でのデリゲート呼び出しのコストが大きくなる場合があります。このような状況では、オーバーロードの1つを使用して、ソース要素上に範囲パーティションCreateを作成できます。次に、この範囲のコレクションを、本体が通常のforループで構成されるメソッドIEnumerable<T>に渡すことができます。ForEachこのアプローチの利点は、デリゲート呼び出しコストが要素ごとに1回ではなく、範囲ごとに1回だけ発生することです。

ループ本体では、単一の乗算を実行しており、デリゲート呼び出しのオーバーヘッドは非常に顕著になります。

これを試して：

public static void MultiplicateArray(double[] array, double factor)
{
    var rangePartitioner = Partitioner.Create(0, array.Length);

    Parallel.ForEach(rangePartitioner, range =>
    {
        for (int i = range.Item1; i < range.Item2; i++)
        {
            array[i] = array[i] * factor;
        }
    });
}

参照：Parallel.ForEachドキュメントおよびPartitioner.Createドキュメント。

Answer 4

Parallel.Forには、より複雑なメモリ管理が含まれます。その結果は、＃cores、L1＆L2キャッシュなどのCPU仕様によって異なる可能性があります...

この興味深い記事をご覧ください：

http://msdn.microsoft.com/en-us/magazine/cc872851.aspx

Answer 5

http://msdn.microsoft.com/en-us/library/system.threading.tasks.parallel.aspxおよびhttp://msdn.microsoft.com/en-us/library/dd537608.aspxから

forを実行する3つのスレッド/プロセスを作成していませんが、forの反復は並行して実行されようとしているため、1つだけでも複数のスレッド/プロセスを使用しています。

これは、インデックス=0とインデックス=1の相互作用が同時に実行される可能性があることを意味します。

おそらくあなたはあまりにも多くのスレッド/プロセスを使用することを余儀なくされており、それらの作成/実行のオーバーヘッドは速度の向上よりも大きくなっています。

3つの通常のスレッド/プロセスを使用してみてください。システムがマルチコア（少なくとも3倍）の場合は、1分未満で完了します。