Хабрахабр

[Перевод] Как GPU справляются с ветвлением

image

О статье

Этот пост — небольшая заметка, предназначенная для программистов, которым хочется больше узнать о том, как GPU обрабатывает ветвление. Можно считать её введением в эту тему. Рекомендую для начала просмотреть [1], [2] и [8], чтобы получить представление о том, как в общем виде выглядит модель выполнения GPU, потому что мы будем рассматривать только одну отдельную деталь. Для любопытных читателей в конце поста есть все ссылки. Если найдёте ошибки, то свяжитесь со мной.

Содержание

  • О статье
  • Содержание
  • Словарь
  • Чем ядро GPU отличается от ядра ЦП?
  • Что такое согласованность/расхождение?
  • Примеры обработки маски выполнения
    • Выдуманная ISA
    • AMD GCN ISA
    • AVX512
  • Как бороться с расхождением?
  • Ссылки

Словарь

  • GPU — Graphics processing unit, графический процессор
  • Классификация Флинна
    • SIMD — Single instruction multiple data, одиночный поток команд, множественный поток данных
    • SIMT — Single instruction multiple threads, одиночный поток команд, множественные потоки
  • Волна (wave) SIMD — поток, выполняемый в режиме SIMD
  • Линия (lane) — отдельный поток данных в модели SIMD
  • SMT — Simultaneous multi-threading, одновременная многопоточность (Intel Hyper-threading)[2]
    • Множественные потоки пользуются общими вычислительными ресурсами ядра
  • IMT — Interleaved multi-threading, чередующаяся многопоточность[2]
    • Множественные потоки пользуются общими вычислительными ресурсами ядра, но за такт выполняется только один
  • BB — Basic Block, базовый блок — линейная последовательность инструкций с единственным переходом в конце
  • ILP — Instruction Level Parallelism, параллелизм на уровне инструкций[3]
  • ISA — Instruction Set Architecture, архитектура набора команд/инструкций

В своём посте я буду придерживаться этой придуманной классификации. Она приблизительно напоминает то, как организован современный GPU.

Оборудование:
GPU -+
|- ядро 0 -+
| |- волна 0 +
| | |- линия 0
| | |- линия 1
| | |- ...
| | +- линия Q-1
| |
| |- ...
| +- волна M-1
|
|- ...
+- ядро N-1

* АЛУ - АЛУ SIMD

Программное обеспечение:
группа +
|- поток 0
|- ...
+- поток N-1

Другие названия:

  • Ядро может называться CU, SM, EU
  • Волна может называться фронтом волны (wavefront), аппаратным потоком (HW thread), warp, контекстом (context)
  • Линия может называться программным потоком (SW thread)

Чем ядро GPU отличается от ядра ЦП?

Любое текущее поколение ядер GPU менее мощно, чем центральные процессоры: простые ILP/multi-issue[6] и предвыборка[5], никакого прогнозирования или предсказания переходов/возвратов. Всё это наряду с крошечным кэшами освобождает довольно большую площадь на кристалле, которая заполняется множеством ядер. Механизмы загрузки/хранения памяти способны справляться с шириной канала на порядок величин больше (это не относится к интегрированным/мобильным GPU), чем обычные ЦП, но за это приходится расплачиваться высокими задержками. Для сокрытия задержек GPU использует SMT[2] — пока одна волна простаивает, другие пользуются свободными вычислительными ресурсами ядра. Обычно количество обрабатываемых одним ядром волн зависит от используемых регистров и определяется динамически, выделением фиксированного файла регистров[8]. Планирование выполнения инструкций гибридное — динамически-статическое[6] [11 4.4]. SMT-ядра, выполняемые в режиме SIMD, достигают высоких значений FLOPS (FLoating-point Operations Per Second, флопс, количество операций с плавающей запятой в секунду).

Figure 1

Чёрный — неактивно, белый — активно, серый — отключено, синий — простаивает, красный — в ожидании Легенда диаграммы.

Рисунок 1. История выполнения 4:2

Если вам это пока вам непонятно, то вернитесь к рисунку после прочтения следующих разделов. На изображении показана история маски выполнения, где на оси x отложено время, идущее слева направо, а на оси y — идентификатор линии, идущий сверху вниз.

Планировщик волн в каждом цикле выпускает по две инструкции от двух волн. Это иллюстрация того, как история выполнения ядра GPU может выглядеть в вымышленной конфигурации: четыре волны совместно используют один сэмплер и два АЛУ. Когда волна простаивает при выполнении доступа к памяти или долгой операции АЛУ, планировщик переключается на другую пару волн, благодаря чему АЛУ постоянно заняты почти на 100%.

Рисунок 2. История выполнения 4:1

Заметьте, что второе АЛУ «голодает». Пример с такой же нагрузкой, но на этот раз в каждом цикле инструкции выпускает только одна волна.

Рисунок 3. История выполнения 4:4

Заметьте, что к АЛУ теперь слишком много запросов, поэтому две волны почти постоянно ожидают (на самом деле это ошибка алгоритма планирования). На этот раз в каждом цикле выпускаются по четыре инструкции.

Обновление Подробнее о трудностях планирования выполнения инструкций можно прочитать в [12].

Всё это зависит от множества факторов и определяется благодаря кропотливому процессу симуляции архитектуры. В реальном мире GPU имеют разные конфигурации ядра: у некоторых может быть до 40 волн на ядро и 4 АЛУ, у других фиксированные 7 волн и 2 АЛУ.

Кроме того, у реальных АЛУ SIMD может быть более узкая ширина, чем у обслуживаемых ими волн, и тогда для обработки одной выпущенной инструкции требуется несколько циклов; множитель называется длиной «chime»[3].

Что такое согласованность/расхождение?

Давайте взглянем на следующий фрагмент кода:

Пример 1

uint lane_id = get_lane_id();
if (lane_id & 1) { // Do smth
}
// Do some more

Здесь мы видим поток инструкций, в котором путь выполнения зависит от идентификатора выполняемой линии. Очевидно, что разные линии имеют разные значения. Что же должно произойти? Существуют разные подходы к решению этой проблемы [4], но в конечном итоге все они делают примерно одно и то же. Один из таких подходов — это маска выполнения, которую я и рассмотрю. Этот подход применялся в GPU Nvidia до Volta и в GPU AMD GCN. Основной смысл маски выполнения заключается в том, что мы храним по биту для каждой линии в волне. Если соответствущий бит выполнения линии имеет значение 0, то для следующей выпущенной инструкции не будут затрагиваться никакие регистры. По сути, линия не должна ощущать влияния всей выполненной инструкции, потому что её бит выполнения равен 0. Это работает следующим образом: волна проходит по графу потока управления в порядке поиска в глубину, сохраняя историю выбранных переходов, пока биты не заданы. Думаю, это лучше показать на примере.

Вот как выглядит маска выполнения для фрагмента кода: Допустим, у нас есть волны шириной 8.

Пример 1. История маски выполнения

// execution mask
uint lane_id = get_lane_id(); // 11111111
if (lane_id & 1) { // 11111111 // Do smth // 01010101
}
// Do some more // 11111111

Теперь рассмотрим более сложные примеры:

Пример 2

uint lane_id = get_lane_id();
for (uint i = lane_id; i < 16; i++) { // Do smth
}

Пример 3

uint lane_id = get_lane_id();
if (lane_id < 16) { // Do smth
} else { // Do smth else
}

Можно заметить, что история необходима. При использовании подхода с маской выполнения оборудование обычно применяет какой-нибудь вид стека. Наивный подход заключается в хранении стека кортежей (exec_mask, address) и добавлении инструкций схождения, которые извлекают маску из стека и изменяют указатель инструкции для волны. В этом случае волна будет иметь достаточно информации для обхода всей CFG для каждой линии.

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

6], что гарантирует достаточность глубины стека масок, равной log2. Обновление. Благодаря @craigkolb я прочитал статью [13], в которой замечается, что инструкции fork/join AMD GCN сначала выбирают путь из меньшего количества потоков [114.

Просмотрев LLVM-бэкенд для AMDGPU, я не нашёл никаких свидетельств обработки стеков, постоянно выпускаемых компилятором. Обновление. Очевидно, что почти всегда можно встроить всё в шейдер/структурировать CFG в шейдере, а потому хранить всю историю масок выполнения в регистрах и планировать обход/схождение CFG статически[15].

Аппаратная поддержка маски выполнения

Теперь взгляните на эти графы потоков управления из Википедии:

Рисунок 4. Некоторые из видов графов потоков управления

Вот как это выглядит в моей искусственной ISA с неявным распараллеливанием, явным управлением масками и полностью динамической синхронизацией конфликтов данных: Какое же минимальное множество инструкций управления масками нам необходимо для обработки всех случаев?

push_mask BRANCH_END ; Push current mask and reconvergence pointer
pop_mask ; Pop mask and jump to reconvergence instruction
mask_nz r0.x ; Set execution bit, pop mask if all bits are zero ; Branch instruction is more complicated
; Push current mask for reconvergence
; Push mask for (r0.x == 0) for else block, if any lane takes the path
; Set mask with (r0.x != 0), fallback to else in case no bit is 1
br_push r0.x, ELSE, CONVERGE

Давайте взглянем, как может выглядеть случай d).

A: br_push r0.x, C, D
B:
C: mask_nz r0.y jmp B
D: ret

Я не специалист в анализе потоков управления или проектировании ISA, поэтому я уверен, что существует случай, с которым моя искусственная ISA справиться не сможет, но это не важно, потому что структурированной CFG должно быть достаточно для всех.

4, а о реализации LLVM — здесь: [15]. Обновление. Подробнее прочитать о поддержке GCN инструкций потоков управления можно здесь: [11] ch.

Вывод:

  • Расхождение — возникающее различие в путях выполнения, выбранных разными линиями одной волны
  • Согласованность — отсутствие расхождения.

Примеры обработки маски выполнения

Вымышленная ISA

Я скомпилировал предыдущие фрагменты кода в своей искусственной ISA и запустил их на симуляторе в SIMD32. Посмотрите, как он обрабатывает маску выполнения.

Обновление. Заметьте, что искусственный симулятор всегда выбирает путь true, а это не самый лучший способ.

Пример 1

; uint lane_id = get_lane_id(); mov r0.x, lane_id
; if (lane_id & 1) { push_mask BRANCH_END and r0.y, r0.x, u(1) mask_nz r0.y
LOOP_BEGIN: ; // Do smth pop_mask ; pop mask and reconverge
BRANCH_END: ; // Do some more ret

Figure 5

История выполнения примера 1 Рисунок 5.

Это время, потраченное впустую. Вы заметили чёрную область? Некоторые линии ждут, пока другие завершать итерацию.

Пример 2

; uint lane_id = get_lane_id(); mov r0.x, lane_id
; for (uint i = lane_id; i < 16; i++) { push_mask LOOP_END ; Push the current mask and the pointer to reconvergence instruction
LOOP_PROLOG: lt.u32 r0.y, r0.x, u(16) ; r0.y <- r0.x < 16 add.u32 r0.x, r0.x, u(1) ; r0.x <- r0.x + 1 mask_nz r0.y ; exec bit <- r0.y != 0 - when all bits are zero next mask is popped
LOOP_BEGIN: ; // Do smth jmp LOOP_PROLOG
LOOP_END: ; // } ret

Figure 6

История выполнения примера 2 Рисунок 6.

Пример 3

mov r0.x, lane_id lt.u32 r0.y, r0.x, u(16) ; if (lane_id < 16) { ; Push (current mask, CONVERGE) and (else mask, ELSE) ; Also set current execution bit to r0.y != 0 br_push r0.y, ELSE, CONVERGE
THEN: ; // Do smth pop_mask ; } else {
ELSE: ; // Do smth else pop_mask ; }
CONVERGE: ret

Figure 7

История выполнения примера 3 Рисунок 7.

AMD GCN ISA

Обновление. GCN тоже использует явную обработку масок, подробнее об этом можно прочитать здесь: [11 4.x]. Я решил стоит показать несколько примеров с их ISA, благодаря shader-playground это сделать легко. Возможно, когда-нибудь я найду симулятор и удастся получить диаграммы.

Я попытался обмануть компилятор, чтобы он не оптимизировал мои ветвления, поместив туда циклы следования за указателями, а затем подчистив ассемблерный код; я не специалист по GCN, поэтому несколько важных nop может быть пропущено. Учтите, что компилятор умный, поэтому вы можете получить другие результаты.

Поэтому, к сожалению, не удалось рассмотреть стек масок. Также заметьте, что в этих фрагментах не используются инструкции S_CBRANCH_I/G_FORK и S_CBRANCH_JOIN, потому что они просты и компилятор их не поддерживает. Если вы знаете, как заставить компилятор выдавать обработку стеков, то сообщите, пожалуйста, мне.

Обновление. Посмотрите этот доклад @SiNGUL4RiTY о реализации векторизованного потока управления в LLVM-бэкенде, используемом AMD.

Пример 1

; uint lane_id = get_lane_id();
; GCN uses 64 wave width, so lane_id = thread_id & 63
; There are scalar s* and vector v* registers
; Executon mask does not affect scalar or branch instructions v_mov_b32 v1, 0x00000400 ; 1024 - group size v_mad_u32_u24 v0, s12, v1, v0 ; thread_id calculation v_and_b32 v1, 63, v0
; if (lane_id & 1) { v_and_b32 v2, 1, v0 s_mov_b64 s[0:1], exec ; Save the execution mask v_cmpx_ne_u32 exec, v2, 0 ; Set the execution bit s_cbranch_execz ELSE ; Jmp if all exec bits are zero
; // Do smth
ELSE:
; }
; // Do some more s_mov_b64 exec, s[0:1] ; Restore the execution mask s_endpgm

Пример 2

; uint lane_id = get_lane_id(); v_mov_b32 v1, 0x00000400 v_mad_u32_u24 v0, s8, v1, v0 ; Not sure why s8 this time and not s12 v_and_b32 v1, 63, v0
; LOOP PROLOG s_mov_b64 s[0:1], exec ; Save the execution mask v_mov_b32 v2, v1 v_cmp_le_u32 vcc, 16, v1 s_andn2_b64 exec, exec, vcc ; Set the execution bit s_cbranch_execz LOOP_END ; Jmp if all exec bits are zero
; for (uint i = lane_id; i < 16; i++) {
LOOP_BEGIN: ; // Do smth v_add_u32 v2, 1, v2 v_cmp_le_u32 vcc, 16, v2 s_andn2_b64 exec, exec, vcc ; Mask out lanes which are beyond loop limit s_cbranch_execnz LOOP_BEGIN ; Jmp if non zero exec mask
LOOP_END: ; // } s_mov_b64 exec, s[0:1] ; Restore the execution mask s_endpgm

Пример 3

; uint lane_id = get_lane_id(); v_mov_b32 v1, 0x00000400 v_mad_u32_u24 v0, s12, v1, v0 v_and_b32 v1, 63, v0 v_and_b32 v2, 1, v0 s_mov_b64 s[0:1], exec ; Save the execution mask
; if (lane_id < 16) { v_cmpx_lt_u32 exec, v1, 16 ; Set the execution bit s_cbranch_execz ELSE ; Jmp if all exec bits are zero
; // Do smth
; } else {
ELSE: s_andn2_b64 exec, s[0:1], exec ; Inverse the mask and & with previous s_cbranch_execz CONVERGE ; Jmp if all exec bits are zero
; // Do smth else
; }
CONVERGE: s_mov_b64 exec, s[0:1] ; Restore the execution mask
; // Do some more s_endpgm

AVX512

Обновление. @tom_forsyth указал мне, что расширение AVX512 тоже имеет явную обработку масок, поэтому вот несколько примеров. Подробнее об этом можно прочитать в [14], 15.x и 15.6.1. Это не совсем GPU, но у него всё равно есть настоящий SIMD16 с 32 битами. Фрагменты кода созданы с помощью ISPC(–target=avx512knl-i32x16) godbolt и сильно переработаны, поэтому могут быть верными не на 100%.

Пример 1

; Imagine zmm0 contains 16 lane_ids ; AVXZ512 comes with k0-k7 mask registers ; Usage: ; op reg1 , reg2, reg3 ; k0 can not be used as a predicate operand, only k1-k7
; if (lane_id & 1) { vpslld zmm0 {k1}, zmm0, 31 ; zmm0[i] = zmm0[i] << 31 kmovw eax, k1 ; Save the execution mask vptestmd k1 {k1}, zmm0, zmm0 ; k1[i] = zmm0[i] != 0 kortestw k1, k1 je ELSE ; Jmp if all exec bits are zero
; // Do smth ; Now k1 contains the execution mask ; We can use it like this: ; vmovdqa32 zmm1 {k1}, zmm0
ELSE:
; } kmovw k1, eax ; Restore the execution mask
; // Do some more ret

Пример 2

; Imagine zmm0 contains 16 lane_ids kmovw eax, k1 ; Save the execution mask vpcmpltud k1 {k1}, zmm0, 16 ; k1[i] = zmm0[i] < 16 kortestw k1, k1 je LOOP_END ; Jmp if all exec bits are zero vpternlogd zmm1 {k1}, zmm1, zmm1, 255 ; zmm1[i] = -1
; for (uint i = lane_id; i < 16; i++) {
LOOP_BEGIN:
; // Do smth vpsubd zmm0 {k1}, zmm0, zmm1 ; zmm0[i] = zmm0[i] + 1 vpcmpltud k1 {k1}, zmm0, 16 ; masked k1[i] = zmm0[i] < 16 kortestw k1, k1 jne LOOP_BEGIN ; Break if all exec bits are zero
LOOP_END:
; // } kmovw k1, eax ; Restore the execution mask
; // Do some more ret

Пример 3

; Imagine zmm0 contains 16 lane_ids
; if (lane_id & 1) { vpslld zmm0 {k1}, zmm0, 31 ; zmm0[i] = zmm0[i] << 31 kmovw eax, k1 ; Save the execution mask vptestmd k1 {k1}, zmm0, zmm0 ; k1[i] = zmm0[i] != 0 kortestw k1, k1 je ELSE ; Jmp if all exec bits are zero
THEN:
; // Do smth
; } else {
ELSE: kmovw ebx, k1 andn ebx, eax, ebx kmovw k1, ebx ; mask = ~mask & old_mask kortestw k1, k1 je CONVERGE ; Jmp if all exec bits are zero
; // Do smth else
; }
CONVERGE:
kmovw k1, eax ; Restore the execution mask
; // Do some more ret

Как бороться с расхождением?

Я попытался создать простую, но полную иллюстрацию того, как возникает неэффективность вследствие комбинирования расходящихся линий.

Представьте простой фрагмент кода:

uint thread_id = get_thread_id();
uint iter_count = memory[thread_id];
for (uint i = 0; i < iter_count; i++) { // Do smth
}

Давайте создадим 256 потоков и измерим их длительность выполнения:

Рисунок 8. Время выполнения расходящихся потоков

Ось x — это идентификатор программного потока, ось y — тактовые циклы; разные столбцы показывают, сколько времени тратится впустую при группировке потоков с разной шириной волн по сравнению с однопоточным выполнением.

Можно увидеть, что производительность сильно падает уже при SIMD8, а дальнейшее расширение просто делает её немного хуже. Время выполнения волны равно максимальному времени выполнения среди содержащихся в ней линий.

Figure 9

Рисунок 9. Время выполнения согласованных потоков

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

Для этого примера выполнение потенциально ускоряется примерно вдвое.

Разумеется, пример слишком простой, но я надеюсь, что вы поняли смысл: расхождение при выполнении проистекает из расхождения данных, поэтому CFG должны быть простыми, а данные — согласованными.

Подробнее см. Например, если вы пишете трассировщик лучей, вам может дать преимущество группировка лучей с одинаковым направлением и позицией, потому что они скорее всего будут проходить по одинаковым узлам в BVH. в [10] и других статьях по теме.

Стоит также упомянуть, что существуют техники борьбы с расхождением и на аппаратном уровне например Dynamic Warp Formation[7] и прогнозируемое выполнение для небольших ветвлений.

[1] A trip through the Graphics Pipeline

[2] Kayvon Fatahalian: PARALLEL COMPUTING

[3] Computer Architecture A Quantitative Approach

[4] Stack-less SIMT reconvergence at low cost

[5] Dissecting GPU memory hierarchy through microbenchmarking

[6] Dissecting the NVIDIA Volta GPU Architecture via Microbenchmarking

[7] Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow

[8] Maurizio Cerrato: GPU Architectures

[9] Toy GPU simulator

[10] Reducing Branch Divergence in GPU Programs

[11] “Vega” Instruction Set Architecture

[12] Joshua Barczak:Simulating Shader Execution for GCN

[13] Tangent Vector: A Digression on Divergence

[14] Intel 64 and IA-32 ArchitecturesSoftware Developer’s Manual

[15] Vectorizing Divergent Control-Flow for SIMD Applications

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть