Почему сравнения на GPU так дороги?

Пытаясь улучшить производительность моего класса обнаружения столкновений, я обнаружил, что ~ 80% времени, проведенного в графическом процессоре, тратится на условия if / else, просто пытающиеся определить границы для сегментов, через которые он должен проходить.

Точнее:

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

2. Затем он преобразует вершины в целочисленные точки сетки (в настоящее время 8x8x8) и преобразует их в границы треугольника на этой сетке.

3. Чтобы преобразовать 3 точки в границы, он находит мин / макс каждого измерения среди каждой из точек

Поскольку в используемом мной языке программирования отсутствует внутреннее минимальное значение, я сделал его сам, выглядит так:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

Таким образом, в среднем это должно быть 2,5 * 3 * 3 = 22,5 сравнения, которые заканчиваются тем, что потребляют намного больше времени, чем фактические тесты пересечения треугольника и края (около 100 * 11-50 инструкций).

На самом деле, я обнаружил, что предварительный расчет требуемых сегментов в процессоре (однопоточный, без векторизации), размещение их в представлении gpu вместе с определением сегментов и заставление gpu делать ~ 4 дополнительных чтения на поток выполнялся в 6 раз быстрее, чем попытки выяснить границы на месте. (обратите внимание, что они пересчитываются перед каждым выполнением, так как я имею дело с динамическими сетками)

Так почему сравнение так ужасно медленно на GPU?

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

Таким образом, в вашей MinMaxподпрограмме не только каждый вызов должен извлекать все три инструкции ветвления (даже если в среднем оценивается только 2,5), но и каждый оператор присваивания также занимает цикл (даже если он на самом деле не «выполняется»). ).

Эта проблема иногда называется расхождением потоков . Если ваша машина имеет что-то вроде 32 строк исполнения SIMD, она все равно будет иметь только одну единицу выборки. (Здесь термин «поток» в основном означает «канал выполнения SIMD».) Таким образом, внутренне каждая линия выполнения SIMD имеет бит «Я включен / отключен», и ветви фактически просто управляют этим битом. (Исключением является то, что в тот момент, когда каждая линия SIMD становится отключенной, модуль выборки обычно переходит непосредственно к предложению «else».)

Итак, в вашем коде каждая SIMD-строка выполнения выполняет:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

Может случиться так, что на некоторых графических процессорах это преобразование условных выражений в предикацию происходит медленнее, если графический процессор выполняет это сам. Как отмечает @ PaulA.Clayton, если ваш язык программирования и архитектура имеют предопределенную условную операцию перемещения (особенно одну из форм if (c) x = y else x = z), вы могли бы добиться большего успеха. (Но, вероятно, не намного лучше).

Кроме того, размещение c < minусловных внутри elseобъекта c > maxизлишне. Это, конечно, ничего вам не спасает, и (учитывая, что GPU должен автоматически преобразовывать его в предикацию), может быть больно иметь его в двух разных условных выражениях.