4

私は並列プログラミングが初めてで、QuickSortParallelメソッドが私の順次バージョン (Parallel.Invoke なし) よりも遅い理由がわかりません。ソートするために渡す 10 万個の 9 桁の数字で構成されるギザギザの配列があります。残念ながら、このQuickSortParallel方法を使用すると、シーケンシャル バージョンよりも約 5 倍遅くなります。

データ ソースで Parallel.Invoke を使用する以上のことはできますか? 

    public static void QuickSort_Parallel<T>(T[] array2) where T : IComparable<T>
    {
        QuickSortParallel(array2, 0, array2.Length - 1);
    }

    private static void QuickSortParallel<T>(T[] array2, int left, int right)
        where T : IComparable<T>
    {
        if (left >= right)
        {
            return;
        }

        SwapElements(array2, left, (left + right) / 2); //median pivot
        int last = left;
        for (int current = left + 1; current <= right; ++current)
        {
            //CompareTo, compares current array index value with
            if (array2[current].CompareTo(array2[left]) < 0)
            {
                ++last;
                SwapElements(array2, last, current);
            }
        }

        SwapElements(array2, left, last);
        //Recursive
        //Executes each of the provided actions in parallel.
        Parallel.Invoke(
            () => QuickSortParallel(array2, left, last - 1),
            () => QuickSortParallel(array2, last + 1, right)
        );
    }

    static void SwapElements<T>(T[] array2, int i, int j)
    {
        T temp = array2[i];
        array2[i] = array2[j];
        array2[j] = temp;
    }
4

3 に答える 3

2

おそらく、問題はスレッドのオーバーヘッドから発生しています。

通常、スレッドを使用するとCPUを集中的に使用する作業が速くなりますが、新しいスレッドを開始するとかなりのオーバーヘッドが発生します。スレッドが多すぎると作業が少なすぎる場合は、プログラムの実行が遅くなる可能性があります。

次の行を実行すると：

    Parallel.Invoke(
        () => QuickSortParallel(array2, left, last - 1),
        () => QuickSortParallel(array2, last + 1, right)
    );

...現在のスレッドがさらに2つのスレッドを生成している可能性があります（Parallel.Invoke実装方法によって異なります）。私の暗算が正しければ（そしてParallel.Invoke実際に新しいスレッドを作成するのであれば）、あなたはn * log(n)スレッドを作成しています-膨大な数です！

パフォーマンスの向上を確認したい場合は、スレッドの数のバランスをとる必要があります。多いほど良いとは限りません。システムスレッドプールを使用してスレッド数を制限する良い方法は次のとおりです。

System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, left, last - 1));
System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, last + 1, right));

...またはそれらの線に沿った何か。必要に応じて、独自のスレッドプールを実装することもできます。a

もう1つのオプションは、再帰の深さを制限して、スレッドの数を制限することです。

于 2012-10-16T00:48:34.300 に答える
2

これらの再帰的な呼び出しはすべてあなたを殺しています。この記事http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel-invoke/は非常に関連性があります。

于 2012-10-16T00:50:46.000 に答える
0

SwapElementsメソッドの使用をめぐる論争？SwapElementsメソッドのロジックを呼び出すのではなく、メソッド/ループに直接ドロップしてみてください...これにより、潜在的なボトルネックではなく、生成される各並列スレッドで発生することの一部にすることができます。それがあなたに何かをもたらすかどうかを確認してください...しかし、それが有用であることが証明されるかどうかはわかりませんが、単なる提案です。

于 2012-10-16T00:37:29.750 に答える