Подтвердить что ты не робот

Экономьте время с параллельным циклом 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];
        });
    }

Проблема в том, что я хочу сэкономить время, а не тратить его. Со стандартным циклом он вычисляет около 2 минут, но с параллельным циклом он занимает 3 минуты. Почему?

4b9b3361

ОТВЕТЫ

Ответ 1

Parallel.For() может значительно повысить производительность, распараллеливая ваш код, но также имеет накладные расходы (синхронизация между потоками, вызов делегата на каждой итерации). И так как в вашем коде каждая итерация очень короткая (в основном, всего несколько инструкций процессора), эти накладные расходы могут стать заметными.

Из-за этого я думал, что использование Parallel.For() не подходит для вас. Вместо этого, если вы распараллеливаете свой код вручную (что очень просто в этом случае), вы можете увидеть улучшение производительности.

Чтобы проверить это, я выполнил некоторые измерения: я выполнил различные реализации MultiplicateArray() в массиве из 200 000 000 элементов (код, который я использовал ниже). На моей машине последовательная версия последовательно занимала 0,21 с, а Parallel.For() обычно занимала около 0,45 с, но время от времени она увеличивалась до 8-9 с!

Во-первых, я попытаюсь улучшить общий случай, и я приду к этим шипам позже. Мы хотим обработать массив с помощью N процессоров, поэтому мы разложим его на N одинаковых размеров и обработаем каждую часть отдельно. Результат? 0,35 с. Это еще хуже, чем серийная версия. Но цикл for для каждого элемента в массиве является одной из наиболее оптимизированных конструкций. Разве мы не можем что-то сделать, чтобы помочь компилятору? Извлечение вычислений, связанных с циклом, могло бы помочь. Оказывается, он делает: 0,18 с. Это лучше, чем серийная версия, но не намного. И, что интересно, изменение степени parallelism от 4 до 2 на моей 4-ядерной машине (без HyperThreading) не меняет результат: все еще 0,18 с. Это заставляет меня сделать вывод, что процессор не является узким местом здесь, пропускная способность памяти.

Теперь вернемся к шипам: у моего пользовательского распараллеливания их нет, но Parallel.For() делает, почему? Parallel.For() использует разбиение по диапазонам, что означает, что каждый поток обрабатывает свою часть массива. Но если один поток заканчивается раньше, он попытается помочь обработать диапазон другого потока, который еще не завершен. Если это произойдет, вы получите много ложного обмена, что может сильно замедлить код. И мой собственный тест с принудительным ложным обменом, кажется, указывает, что это действительно может быть проблемой. Принуждение степени parallelism к 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

Ответ 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

Btw, ключевое слово для этого, отсутствующее во всех остальных ответах, детализации.

Ответ 3

Parallel.For включает в себя более сложное управление памятью. Этот результат может варьироваться в зависимости от спецификаций процессора, таких как #cores, кеш L1 и L2...

Пожалуйста, взгляните на эту интересную статью:

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

Ответ 4

См. Пользовательские разделители для PLINQ и TPL:

В цикле For тело цикла предоставляется методу в качестве делегата. Стоимость вызова этого делегата примерно такая же, как вызов виртуального метода. В некоторых сценариях тело параллельного цикла может быть достаточно маленьким, чтобы стоимость вызова делегата на каждой итерации цикла становилась значительной. В таких ситуациях вы можете использовать одну из перегрузок Create для создания IEnumerable<T> разделов диапазона над исходными элементами. Затем вы можете передать этот набор диапазонов методу ForEach, тело которого состоит из регулярного цикла. Преимущество этого подхода заключается в том, что стоимость вызова делегата возникает только один раз за диапазон, а не один раз за элемент.

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

Попробуйте следующее:

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 documentation.

Ответ 5

из http://msdn.microsoft.com/en-us/library/system.threading.tasks.parallel.aspx и http://msdn.microsoft.com/en-us/library/dd537608.aspx

вы не создаете три потока/процесса, которые выполняются за вами, но итерация функции for выполняется параллельно, поэтому даже с одним из них вы используете несколько потоков/процессов.

это означает, что одновременно может выполняться взаимодействие с индексом = 0 и index = 1.

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

Попробуйте использовать три обычных варианта, но в трех разных потоках/процессах, если ваша система многоядерна (по крайней мере, на 3 раза), она занимает менее одной минуты