Расхождение в ветвях, CUDA и Kinetic Monte Carlo

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

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

   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();
           }
      }
   }

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

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

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

Спасибо!

 Brendan Wood11 июн. 2012 г., 15:49
Будут ли разные потоки иметь разное количество итераций цикла (100/1000/10000, на которые вы ссылаетесь)?
 Konstantinos11 июн. 2012 г., 16:18
@Brendan Wood: Нет, все они будут одинаковыми, но как только поток войдет в блок if, этот поток выйдет из цикла независимо от значения i. О, и тогда этот поток начнется снова с самого начала. Возможно, мне следует отредактировать мой пример кода, чтобы отразить это.

Ответы на вопрос(1)

Решение Вопроса

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

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

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

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

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

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

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

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

 17 авг. 2016 г., 23:47
@ & # XCD; Horm & # xE9; «расхождение может происходить внутри блока, но вне некоторых перекосов или даже больше, вне каких-либо перекосов»; В контексте CUDA я видел только дивергенцию, используемую для описания различий в потоке программы в рамках деформации.
 Konstantinos11 июн. 2012 г., 17:39
Довольно хороший ответ! Спасибо! И да, мы говорим о совершенно случайном, если. Я полагаю, что тогда я должен также работать над балансировкой нагрузки своего кода, чтобы большинство потоков вводили if одновременно.
 19 авг. 2016 г., 03:02
Каждая деформация должна выполнять код, который проверяет расхождение. Тем не менее, полный перекос может оставаться твердым, не расходясь после этого. Очень важно знать, как внутри блока формируются деформации (например, [z] [y] [x] в C-массивах), чтобы иметь возможность реализовать производительный условный код.
 17 авг. 2016 г., 19:16
То, что здесь сказано о конвейере памяти, можно также сказать об арифметическом конвейере. Также обратите внимание, что здесь говорится о деформации. И дивергенция может происходить внутри блока, но вне каких-то перекосов или даже больше, вне каких-либо перекосов. Поэтому, если вам необходимо иметь дивергенцию, в ваших интересах разбить ее между деформациями, а не между нитями внутри одной и той же основы, насколько это возможно.
 20 авг. 2016 г., 01:01
Кроме того, оптимизирующий компилятор может полностью «развернуть» некоторая логика if / case, которая не зависит от #thread или любых других внешних эффектов, но является скорее статической.

Ваш ответ на вопрос