1

パフォーマンスを向上させようとしている小さなプログラムがあります。プログラムは非常に単純で、主に単一の再帰関数に基づいています。ただし、その背後にあるデータセットは非常に大きく、6,000,000,000 回の再帰が必要で、マシンによっては実行に約 4 ～ 6 時間かかります。データを処理するだけの I/O はありません。コードの最適化にかなりの時間を費やし、最大 60% の改善を見つけることができました。

ここで注目したいのは、コードをマルチスレッド化して、ホスト マシンのすべてのコアを活用することです。ただし、スレッド、タスク、および Parallel ライブラリの一部を使用してみましたが、パフォーマンスに悪影響を及ぼさないものを見つけることができませんでした。

私が見ているコードの種類のアイデアを提供するために：

class Program
{
    static void Main(string[] args)
    {
        RecursiveFunction(0);
        Console.ReadLine();
    }
    static void RecursiveFunction(int currentLevel)
    {
        DoWork(currentLevel);

        if (currentLevel < 1000)
            for (int i = 0; i < (currentLevel % 6) + 1; i++)
                RecursiveFunction(currentLevel + 1);
    }
    static void DoWork(int currentLevel)
    {
        Thread.Sleep(42);
    }
}

ご覧のとおり、関数の各実行の実行には時間がかからないため、再帰ごとにスレッドを作成するコストはそれほど価値がありません。再帰の各分岐の長さが異なる可能性があり、各分岐の長さを知る方法がないため、特定のレベルでのスレッド化は正しい方法ではありません。

誰か提案はありますか？

4

3 に答える 3

2

ツリーの上位レベルで並列処理を使用します。各呼び出しには数分から数時間かかるため、スレッドによるオーバーヘッドはほとんどありません。

メソッドを使用してParallel.For*、ループを並列に実行します。

再帰ツリーの下位層では、通常の順次ループを使用します。

並列化されたループの反復が数千回になるように、カットオフ レベルを選択します。

于 2013-01-04T19:54:04.980 に答える
0

アプリケーションを知らずにコメントするのは難しいです。

再帰関数は、レベルの同じ値に対して何度も呼び出されます。level の同じ値に対する以前の実行の結果を収集できますか? ... そうではないと思いますが、おそらく、実行の結果よりも副作用に関心があるでしょう。

.NET 4.5 (VS 2012) TAP を使用してみましたか? async / await、Tasks を使用すると、Task.ContinueWith を試して、同じ ( level % CORE_COUNT ) で再帰呼び出しを連鎖させることができます。これは、すべてのタスク、ひいてはすべてのコアの負荷を分散するのに役立つ場合があります。 MSDN : 複数のタスクを連鎖します。

どの戦略が効果的だったかについて投稿していただければ幸いです。

于 2013-01-04T18:44:08.883 に答える
0

以下のコードを使用していつでもタスクを連鎖させ、タスク スケジューラに作業をスケジュールさせることができます。

class Program
    {
        private static int MaxLevel = 1000;
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            Task mainTask = ParallelRecursiveFunction(0);
            mainTask.Wait();
            stopwatch.Stop();
            Console.WriteLine("Total time of parallel execution  : {0}", stopwatch.ElapsedMilliseconds);


            Console.WriteLine("Press Enter to execute the operation sequentially");
            Console.WriteLine();
            Console.ReadLine();
            stopwatch.Reset();
            stopwatch.Start();

            SequentialRecursiveFunction(0);

            stopwatch.Stop();

            Console.WriteLine("Total time of sequential execution: {0}",stopwatch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        private static void SequentialRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return;
            DoWork(currentLevel);

            SequentialRecursiveFunction(currentLevel +1);
        }

        public static Task ParallelRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return _completedTask;
            Task t1 = Task.Factory.StartNew(() => DoWork(currentLevel));

            Task<Task> t2 = Task.Factory.StartNew(() => ParallelRecursiveFunction(currentLevel + 1));

            return Task.Factory.ContinueWhenAll(new Task[] { t1, t2.Unwrap() }, Task.WaitAll);

        }
        private static Task _completedTask = ((Func<Task>)(() =>
        {
            var tcs = new TaskCompletionSource<object>();
            tcs.SetResult(null);
            return tcs.Task;
        }))();

        static void DoWork(int currentLevel)
        {
            Console.WriteLine("Do work at level {0}", currentLevel);

            Thread.Sleep(42);

        }
    }

シーケンシャル アルゴリズムよりも約 4 倍高速 (= マシン上のプロセッサ数) に実行される並列コードをテストしました。

どう思うか教えてください。

乾杯。

于 2013-01-05T12:17:37.270 に答える