Параллельные циклы и Random дают странные результаты

Question

Я только начал играть с библиотекой параллельных задач и столкнулся с интересными проблемами; У меня есть общее представление о том, что происходит, но я хотел бы услышать комментарии от людей, более компетентных, чем я, чтобы помочь понять, что происходит. Мои извинения за довольно длинный код.

Я начал с непараллельного моделирования случайного блуждания:

 var random = new Random();
 Stopwatch stopwatch = new Stopwatch();

 stopwatch.Start();

 var simulations = new List<int>();
 for (var run = 0; run < 20; run++)
 {
    var position = 0;
    for (var step = 0; step < 10000000; step++)
    {
       if (random.Next(0, 2) == 0)
       {
          position--;
       }
       else
       {
          position++;
       }
    }

    Console.WriteLine(string.Format("Terminated run {0} at position {1}.", run, position));
    simulations.Add(position);
 }

 Console.WriteLine(string.Format("Average position: {0} .", simulations.Average()));
 stopwatch.Stop();

 Console.WriteLine(string.Format("Time elapsed: {0}", stopwatch.ElapsedMilliseconds));
 Console.ReadLine();

Затем я написал свою первую попытку параллельного цикла:

 var localRandom = new Random();

 stopwatch.Reset();
 stopwatch.Start();

 var parallelSimulations = new List<int>();
 Parallel.For(0, 20, run =>
 {
    var position = 0;
    for (var step = 0; step < 10000000; step++)
    {
       if (localRandom.Next(0, 2) == 0)
       {
          position--;
       }
       else
       {
          position++;
       }
    }

    Console.WriteLine(string.Format("Terminated run {0} at position {1}.", run, position));
    parallelSimulations.Add(position);
 });


 Console.WriteLine(string.Format("Average position: {0} .", parallelSimulations.Average()));
 stopwatch.Stop();

 Console.WriteLine(string.Format("Time elapsed: {0}", stopwatch.ElapsedMilliseconds));

 Console.ReadLine();

Когда я запускал его на виртуальной машине, настроенной на использование только 1 ядра, я наблюдал аналогичную продолжительность, но прогоны больше не обрабатываются по порядку - неудивительно.

Когда я запустил его на двухъядерной машине, все пошло странно. Я не видел улучшений во времени и наблюдал некоторые очень странные результаты для каждого запуска. Большинство прогонов заканчиваются результатами с -1,000,000 (или очень близко), что указывает на то, что Random.Next все время возвращает 0 квази.

Когда я делаю случайный локальный для каждого цикла, все работает просто отлично, и я получаю ожидаемое улучшение продолжительности:

Parallel.For(0, 20, run =>
         {
            var localRandom = new Random();
            var position = 0; 

Я предполагаю, что проблема связана с тем, что объект Random разделяется между циклами и имеет некоторое состояние. Я полагаю, что отсутствие улучшения продолжительности в версии «с ошибкой параллельной» связано с тем фактом, что вызовы Random не обрабатываются параллельно (хотя я вижу, что в параллельной версии используются оба ядра, в то время как в исходной - нет). , Часть, которую я действительно не получаю, - то, почему результаты моделирования - то, чем они являются.

У меня есть отдельное беспокойство: если я использую экземпляры Random, локальные для каждого цикла, я могу столкнуться с проблемой наличия нескольких циклов, начинающихся с одного и того же начального числа (проблема, возникающая при создании нескольких рандомов слишком близко по времени в результате идентичные последовательности).

Любое понимание происходящего будет для меня очень ценным!

Answer 1

Ни один из этих подходов не даст вам действительно хороших случайных чисел.

Этот пост в блоге охватывает множество подходов для получения лучших случайных чисел с помощью Random

http://blogs.msdn.com/b/pfxteam/archive/2009/02/19/9434171.aspx

Это может быть хорошо для многих повседневных применений.

Однако, если вы используете один и тот же генератор случайных чисел в нескольких потоках даже с разными начальными числами , вы все равно будете влиять на качество ваших случайных чисел. Это потому, что вы генерируете последовательности псевдослучайных чисел, которые могут перекрываться.

Это видео объясняет почему более подробно:

http://software.intel.com/en-us/videos/tim-mattson-use-and-abuse-of-random-numbers/

Если вам нужны действительно случайные числа, вам действительно нужно использовать криптографический генератор случайных чисел System.Security.Cryptography.RNGCryptoServiceProvider. Это потокобезопасно.

Answer 2

Класс Random не является потокобезопасным;если вы используете его в нескольких потоках, это может привести к путанице.

Вы должны создать отдельный экземпляр Random в каждом потоке и убедиться, что они не заканчиваются использованием одного и того же семени.(например, Environment.TickCount * Thread.CurrentThread.ManagedThreadId)

Answer 3

Одна основная проблема:

• random.Next не является поточно-ориентированным.

Два последствия:

1. Качество случайности зависит от расы.
2. Ложное совместное использование нарушает масштабируемость на многоядерных процессорах.

Несколько возможных решений:

• Сделать random.Next потокобезопасным: решает проблему качества, но не масштабируемости.
• Использование нескольких PRNG: решает проблему масштабируемости, но может ухудшать качество.
• ...