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

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

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

Источник

2 ответа

Решение

Я хотел бы объяснить это на примере, рассмотрим этот массив с 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)
Источник

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

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

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

Источник
Другие вопросы по тегам