Расхождение дивергенции, CUDA и Kinetic Monte Carlo

Question

Итак, у меня есть код, который использует Kinetic Monte Carlo на решетке, чтобы имитировать что-то. Я использую CUDA для запуска этого кода на своем графическом процессоре (хотя я считаю, что тот же вопрос относится и к OpenCl).

Это означает, что я делю мою решетку на маленькие подрешетки, и каждый поток работает на одном из них. Так как я делаю КМК, каждая нить имеет следующий код:

While(condition == true){ 
    *Grab a sample u from U[0,1]* 
     for(i = 0; i < 100;i++){ 
     *Do some stuff here to generate A* 
      if(A > u){ 
       *Do more stuff here, which could include updates to global memory* 
       break(); 
      } 
     } 
    } 

А различны для разных потоков и так и и 100 это просто случайное число. В коде это может быть 1000 или даже 10000.

Итак, разве у нас не будет расхождения ветвей, когда придет время, когда поток пройдет через это, если? Насколько это может повлиять на производительность? Я знаю, что ответ зависит от кода внутри if-clause, но как этот масштаб будет увеличиваться, когда я добавляю все больше потоков?

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

Спасибо!

Answer 1

GPU запускает потоки в виде групп из 32 потоков, называемых перекосами. Дивергенция может произойти только в основе. Итак, если вы можете упорядочить свои потоки таким образом, чтобы условие if оценивалось одинаково во всех деформациях, нет никакой дивергенции.

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

Итак, скажем, что if оценивает true для 10 потоков в определенной деформации. В то время как внутри этого if потенциальная вычислительная производительность основы уменьшается с 100% до 10/32 * 100 = 31%, поскольку 22 потока, которые были отключены if, могли выполнять работу, но теперь просто занимают место в деформация.

После выхода из if отключенные потоки активируются снова, и деформация работает со 100% потенциальной вычислительной производительностью.

if-else ведет себя точно так же. Когда варп попадает на else, потоки, которые были включены в if, отключены, а те, которые были отключены, становятся доступными.

В цикле for, в котором для каждого потока в warp выполняется определенное количество раз, потоки отключены, так как их число итераций достигает их заданных чисел, но деформация в целом должна продолжаться, пока поток с наивысшей итерацией счет делается.

Рассматривая потенциальную пропускную способность памяти, вещи немного сложнее. Если алгоритм связан с памятью, может быть не так много или какая-либо потерянная производительность из-за разницы в warp, поскольку количество транзакций памяти может быть уменьшено. Если каждый поток в warp читается из совершенно другого места в глобальной памяти (плохая ситуация для графического процессора), время будет сохранено для каждого из отключенных потоков, так как их транзакции памяти не должны выполняться. С другой стороны, если потоки читались из массива, который был оптимизирован для доступа к GPU, несколько потоков будут делиться результатами из одной транзакции. В этом случае значения, предназначенные для отключенных потоков, были прочитаны из памяти, а затем отброшены вместе с вычислениями, которые мог бы сделать отключенный поток.

Итак, теперь у вас, вероятно, есть достаточно обзора, чтобы иметь возможность делать довольно здравые рассуждения о том, сколько разницы в деформации повлияет на вашу производительность. Худший случай - когда активен только один поток в warp. Затем вы получаете 1/32 = 3,125% от потенциала для производительности, связанной с вычислением. Лучший случай - 31/32 = 96,875%. Для if, который является полностью случайным, вы получаете 50%. И, как уже упоминалось, производительность памяти зависит от изменения количества требуемых транзакций памяти.