Параллельно не быстрее, чем последовательный?

Question

Попытка придумать стратегии для поиска следующего простого числа:

Алгоритм № 1 (Параллельный):

    private static int NextPrime(int p)
    {
        int nextP = 2 * p; // there is always a prime between n & 2*n !
        Enumerable.Range(p + 1, p)
                  .AsParallel()
                  .ForAll(g =>
                  {
                      bool prime = true;
                      for (int i = 2; i <= Math.Sqrt(g); i++)
                      {
                          if (g % i == 0)
                          {
                              prime = false;
                              break;
                          }
                      }
                      if (prime)
                      {
                          if (g < nextP)
                              nextP = g;
                          return;
                      }
                  });

        return nextP;
    }

Алгоритм № 2 (Последовательный):

    private static int NextPrimeNonParallel(int p)
    {
        int nextP = 2 * p; // there is always a prime between n & 2*n !
        foreach (var g in Enumerable.Range(p + 1, p))
        {
            bool prime = true;
            for (int i = 2; i <= Math.Sqrt(g); i++)
            {
                if (g % i == 0)
                {
                    prime = false;
                    break;
                }
            }
            if (prime)
            {
                if (g < nextP)
                    nextP = g;
                return nextP;
            }
        }
        return 0;
    }

Последовательность значительно быстрее, чем параллельная :) Почему?Или мой параллельный алгоритм действительно хорошо написан?

Спасибо!

Answer 1

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

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

Вместо этого вы, вероятно, захотите использовать эту версию Parallel.ForEach , которая дает вам ParallelLoopState с каждой итерацией.Если вы вызовете Break () (примечание: не Stop () из-за неправильного исполнения ордера, то вы можете получить слишком большое значение) для этого объекта, цикл будет прерван при первой же возможности.Вам также нужно будет синхронизировать запись в nextP (это общее состояние для всех потоков), чтобы он сохранял только наименьшее значение, a'la;

lock(lockObject) {
  if(value<nextP) nextP = value;
}

Что в целом должно позволить вамработать параллельно с большей производительностью.

Answer 2

2 причины, по которым параллельная программа медленнее, чем последовательная.

1: из-за накладных расходов на связь, т. Е. Времени для обмена информацией между процессорами или потоками или синхронизации, а также времени простоя (время, когда процессор не может сделать ничего полезного, кроме как ожидать события);это также может зависеть от того, что распределение работы по каждому процессору не одинаково разделено.

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

Answer 3

@ Иоахим ответил правильно. Я только хочу добавить пару пунктов:

• Ваш алгоритм тестирования простоты наивен. Если вы имеете дело с действительно большими числами и вам нужен действительно быстрый алгоритм, существуют сложные, но асимптотически более быстрые алгоритмы, см., Например, http://en.wikipedia.org/wiki/AKS_primality_test.

• Если вам не нужна такая сложность, но вы хотите просто ускорить свой алгоритм:

  1. Проверяя простоту M, делите его только на простые числа в 2..sqrt (M)
  2. Итак, сначала найдите все простые числа в 2..sqrt (M).
  3. Запомните список на 2-м шаге, чтобы ускорить будущие запросы.

  Предположим, вы хотите найти наименьшее простое число больше 10 ^ 12. Мое предложение предполагает, что у вас достаточно места для хранения всех простых чисел, меньших 10 ^ 6. Предполагается также, что вы выполните много похожих запросов, чтобы найти все простые числа меньше 10 ^ 6 шагов.