Симуляция дает другой результат с нормальным для цикла Vs Parallel For - PullRequest
Новая
       1

Симуляция дает другой результат с нормальным для цикла Vs Parallel For

4 голосов
/ 20 января 2012

Я немного удивлен различными результатами для одного из моих простых образцов моделирования, когда я попытался с нормальным для цикла (что является правильным результатом) против параллельного For Пожалуйста, помогите мне найти причину. Я заметил, что параллельное выполнение так быстро по сравнению с обычным. 

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace Simulation
{
    class Program
    {

    static void Main(string[] args)
    {
       ParalelSimulation(); // result is .757056
       NormalSimulation();  // result is .508021 which is correct
        Console.ReadLine();
    }

    static void ParalelSimulation()
    {
        DateTime startTime = DateTime.Now;

        int trails = 1000000;
        int numberofpeople = 23;
        Random rnd = new Random();
        int matches = 0;

        Parallel.For(0, trails, i =>
            {
                var taken = new List<int>();
                for (int k = 0; k < numberofpeople; k++)
                {
                   var day = rnd.Next(1, 365);
                    if (taken.Contains(day))
                    {
                        matches += 1;
                        break;
                    }
                    taken.Add(day);
                }
            }
        );
        Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
        TimeSpan ts = DateTime.Now.Subtract(startTime);
        Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
    }
    static void NormalSimulation()
    {
        DateTime startTime = DateTime.Now;

        int trails = 1000000;
        int numberofpeople = 23;
        Random rnd = new Random();
        int matches = 0;

        for (int j = 0; j < trails; j++)
        {
            var taken = new List<int>();
            for (int i = 0; i < numberofpeople; i++)
            {
               var day = rnd.Next(1, 365);
                if (taken.Contains(day))
                {
                    matches += 1;
                    break;
                }
                taken.Add(day);
            }
        }
        Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
        TimeSpan ts = DateTime.Now.Subtract(startTime);
        Console.WriteLine(" Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
    }
}

}

Заранее спасибо

Ответы [ 2 ]

4 голосов
/ 20 января 2012

Несколько вещей:

  1. Класс Random не является потокобезопасным.Вам понадобится новый экземпляр Random для каждого рабочего потока.
  2. Вы увеличиваете переменную matches не потокобезопасным способом.Вы хотите использовать Interlocked.Increment(ref matches), чтобы гарантировать безопасность потока при увеличении переменной.
  3. Ваш цикл for и ваш Parallel :: For не выполняются одинаковое количество раз, потому что вы делаете <= в вашем forВторой параметр loop and Parallel :: For - это <em>exclusive , поэтому вам нужно добавить 1 к трейлам в этом случае, чтобы сделать их эквивалентными.

Попробуйте это: 

static void ParalelSimulationNEW()
{
    DateTime startTime = DateTime.Now;

    int trails = 1000000;
    int numberofpeople = 23;
    int matches = 0;

    Parallel.For(0, trails + 1, _ =>
    {
        Random rnd = new Random();

        var taken = new List<int>();
        for(int k = 0; k < numberofpeople; k++)
        {
            var day = rnd.Next(1, 365);
            if(taken.Contains(day))
            {
                Interlocked.Increment(ref matches);
                break;
            }
            taken.Add(day);
        }
    });
    Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
    TimeSpan ts = DateTime.Now.Subtract(startTime);
    Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
}
2 голосов
/ 20 января 2012

Код содержит данные гонки при обновлении matches. Если два потока делают это одновременно, оба могут прочитать одно и то же значение (скажем, 10), затем оба увеличивают его (до 11) и записывают новое значение обратно. В результате будет меньше зарегистрированных совпадений (в моем примере 11 вместо 12). Решение состоит в том, чтобы использовать System.Threading.Interlocked для этой переменной.

Другие проблемы, которые я вижу:
- ваш последовательный цикл включает в себя итерацию для j, равную trails, а для параллельного цикла - нет (конечный индекс является исключительным в Parallel.For);
- class Random может быть не безопасным для потоков.

Обновление: я думаю, что вы не получите желаемый результат с кодом Дрю Марша, потому что он не обеспечивает достаточной рандомизации. Каждый из 1M экспериментов начинается с одного и того же случайного числа, потому что вы запускаете все локальные экземпляры Random с начальным числом по умолчанию. По сути, вы повторяете один и тот же эксперимент 1M раз, поэтому результат все еще искажен. Чтобы это исправить, вам нужно каждый раз вводить каждый случайный случай с новым значением. Обновление: я был не совсем прав, так как при инициализации по умолчанию для начального числа используются системные часы; однако MSDN предупреждает, что

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

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

Parallel.For(0, trails + 1, j =>
{
    Random rnd = new Random(j); // initialized with different seed each time
    /* ... */          
});

Однако я заметил, что после того, как инициализация Random была перенесена в цикл, все ускорение было потеряно (на моем ноутбуке Intel Core i5). Поскольку я не эксперт по C #, я не знаю почему; но я предполагаю, что класс Random может иметь некоторые данные, совместно используемые всеми экземплярами с синхронизацией доступа.

Обновление 2: с использованием ThreadLocal для хранения одного экземпляра Random на поток, я получил хорошую точность и разумное ускорение: 

ThreadLocal<Random> ThreadRnd = new ThreadLocal<Random>(() =>
{
    return new Random(Thread.CurrentThread.GetHashCode());
});
Parallel.For(0, trails + 1, j =>
{
    Random rnd = ThreadRnd.Value;
    /* ... */          
});

Обратите внимание, как рандомизаторы для каждого потока инициализируются хэш-кодом для текущего запущенного экземпляра Thread.

...