Временная сложность алгоритма параллельного сокращения

Question

В настоящее время я изучаю архитектуру GPU и ее концепции.В методе параллельного сокращения, как сложность времени, показанная на 29-м слайде в следующем руководстве NVIDIA, равна O (N / P + log N)?Я знаю, что для N потоков это будет O (log N).Если у нас есть P параллельных потоков, то сложность по времени должна быть O ((N / P) * log P).Правильно?Где я тут не прав?

Методы параллельного сокращения

Answer 1

Я хотел бы объяснить это на примере, рассмотрим этот массив с N = 8 элементами

1  2  3  4  5  6  7  8

Параллельное сокращение будет происходить в следующих шагах

1  2  3  4  5  6  7  8
  3    7      11   15
    10          26
          36

Если вы считаетеКоличество операций сокращения у нас 4,2 и 1 на первом, втором и третьем шаге соответственно.Таким образом, общее количество операций, которое мы имеем, составляет 4 + 2 + 1 = 7 = N-1, и мы делаем все сокращения в O (N), и у нас также есть log (8) = 3 (это log to base 2) шагов, такмы платим за эти шаги стоимость, которая составляет O (logN).Следовательно, если мы использовали один поток для сокращения таким образом, мы добавляем две затраты, поскольку они происходят отдельно друг от друга, и у нас есть O (N + logN).Где O (N) - стоимость выполнения всех операций, а O (logN) - стоимость выполнения всех шагов.Теперь нет способа распараллелить стоимость шагов, поскольку они должны выполняться последовательно.Однако мы можем использовать несколько потоков для выполнения операций и делить стоимость O (N) на O (N / P).Поэтому у нас есть

Total cost = O(N/P + logN)

Answer 2

Я не знаком с cuda, но обычно при параллельных сокращениях вы делаете

• сначала локальное сокращение на каждом процессоре, что потребует O (N / P), а затем
• вычислить уменьшение P локальных результатов, которое принимает шаг O (log P).

Следовательно, вы получаете O (N / P + log P).