Планування Варпу GPU та Розбіжна Керуюча Логіка SIMD

SIMT: Одна інструкція, багато потоків

GPU отримують свою грубу обчислювальну продуктивність завдяки масовій паралельності, яку можна недорого отримати, і ключова техніка полягає в тому, що один запит на отримання та декодування інструкції може одночасно керувати десяками шляхів виконання, оскільки всі потоки у варпі з моменту апаратного забезпечення виконують однакову інструкцію в один і той же момент часу, просто проти різних даних, які містяться в окремих записах кожного шляху за допомогою власних записів у кожному шляху. Це по суті SIMD, однопотокове виконання багатьох даних, але NVIDIA називає свою варіативну SIMT, щоб підкреслити з точки зору програміста, що кожен потік здається незалежним потоком керування, має власний лічильник команд і стеку викликів в абстрактній моделі програмування, незважаючи на те, що основне апаратне забезпечення вимагає синхронного виконання варпу. Це абстракція дозволяє CUDA та подібним моделям програмування відчуватися як звичайний багатопотоковий код: ви пишете ядро, ніби описуєте роботу одного потоку, і апаратне забезпечення запускає тисячі його екземплярів. Вигода від ефективності величезна: один планувальник варпу, одна логіка отримання та декодування інструкції, один доступ до кешу інструкцій керують 32 або 64 шляхами виконання, що означає, що контроль витрати на одиницю обчислень становить невелику частку від того, що вимагало б аналогічна кількість незалежних ядер CPU. Але ця ефективність повністю залежить від того, щоб усі шляхи у варпі дійсно хотіли виконувати одну й ту саму інструкцію в один і той же час, що є саме припущенням, яке порушують умовні гілки.

Що відбувається, коли потоки не згодні

Розгляньте ядро з оператором if/else, де умова залежить від власного індексу або даних кожного потоку, тому деякі потоки в варпі оцінюють умову як істинну, а інші – як хибну, ситуація, відома як розбіжність варпу або розбіжність гілок. Оскільки апаратне забезпечення може видавати лише один потік інструкцій у варп за будь-який цикл, воно не може просто мати деякі ланки виконувати інструкції if-гілки, а інші одночасно виконують інструкції else-гілки. Замість цього планувальник варпу серіалізує обидва шляхи: спочатку він видає інструкції if-гілки всьому варпу, але з активною маскою, яка вимикає або заперечує кожну ланку, чий потік дійсно хотів else-шлях, тому ці ланки виконують інструкції як нічого, що не змінює жодного стану. Потім варп виконує інструкції else-гілки, цього разу з перевернутою маскою, активною точно для ланок, які були вимкнені раніше, і вимкненими для тих, які були активні. Лише після того, як обидва шляхи були видані, варп знову консолідується, тобто кожна ланка знову стає активною знову для будь-якого коду, що слідує за if/else. Критичний наслідок полягає в тому, що загальний час виконання для дивергентної області приблизно дорівнює сумі вартості обох гілок, а не максимальній з двох, як справжнє паралельне виконання б досягло, оскільки апаратне забезпечення витрачає реальні цикли на закриті ланки, викинуті цикли ланок під час кожного етапу.

Визначення вартості серіалізації

Вартість продуктивності від розбіжностей залежить від того, наскільки рівномірно потоки розподіляються між гілками та скільки роботи виконується в кожній гілці. У найкращому випадку всі 32 потоки в варпі погоджуються з однією й тією ж гілкою, немає розбіжностей, і варп просто пропускає інструкції іншого шляху повністю, не платячи жодної додаткової вартості. У найреалістичнішому випадку точно половина варпу бере кожен шлях із гілками приблизно рівної вартості, варп тепер займає приблизно вдвічі більше часу для проходження умовного переходу, ніж повністю збіжний варп, оскільки він повинен повністю виконувати інструкції if-гілки, витрачаючи 16 шляхів вартість циклів, і інструкції else-гілки, витрачаючи інші 16 шляхів вартість циклів. Якщо гілки дуже нерівномірно коштують, наприклад, один шлях виконує сто операцій, а інший - одну, штраф домінує над дорогим шляхом незалежно від того, скільки потоків бере його, оскільки весь варп чекає через усі 100 операцій, навіть якщо лише одному шляху потрібно їх, це пояснює, чому керівництва з програмування GPU послідовно рекомендують організовувати дані та відображення потоку-до-роботи таким чином, щоб потоки всередині одного варпу схилялися до того, щоб брати одну й ту ж гілку разом, властивість, яка іноді називається узгодженістю гілок, замість розсіювання умовних перехідів на випадкові індекси потоків. Сортування або групування даних за тим, яку гілку вони спровокують, перш ніж запускати ядро, є поширеною та ефективною реалійною технікою спеціально для мінімізації цієї вартості серіалізації.

Повернення та вкладена розбіжність

Обробка окремого if/else є концептуально простою, але реальні ядра часто мають вкладені умовні оператори, цикли з умовами виходу залежні від даних і виклики функцій, які також розбігаються всередині, що може створювати більш складні схеми розбіжності, які апаратне забезпечення повинно відстежувати та зрештою узгоджувати. GPU підтримують концептуально стек повернення або подібну структуру, яка записує для кожного місця, де ворп розбігається, як шляхи ланок пішли, і де ці шляхи очікується знову об'єднатися, щоб апаратне забезпечення могло правильно відновити повний активний маску після завершення будь-якого розбіжного шляху. Цикли представляють особливий випадок: якщо різні потоки в ворпі потребують різної кількості ітерацій, можливо, тому що вони проходять по різних за довжиною зв'язаних списках або збігаються у вирішенні на різних швидкостях, весь ворп повинен продовжувати ітеруватися до тих пір, поки кожна індивідуальна умова циклу потоку не буде виконана, а вже завершені потоки просто маскуються для решти ітерацій, знову витрачаючи цикли ланок. Новіші архітектури GPU, починаючи від покоління Volta від NVIDIA, ввели незалежне планування потоків, яке дозволяє більш тонке переплетення між розбіжними шляхами та може допомогти з певними схемами синхронізації між розбіжними потоками, але це не усуває фундаментальну вартість пропускної здатності розбіжності, виконання двох різних потоків інструкцій послідовно на одному наборі шляхів виконання дорожче, ніж виконання одного потоку, на якому всі шляхи погоджуються.

Розробка з урахуванням розбіжностей у виконанні (Divergence)

Оскільки розбіжність варпу є явищем на рівні апаратного забезпечення, невидимим у вихідному коді ядра, питання правильності ніколи не ставиться, але продуктивність може різко та непомітно погіршитися, що робить її улюбленим об’єктом для профілювання GPU, таким як NVIDIA Nsight Compute, який явно повідомляє показники ефективності гілок, показуючи, яка частина виконаних інструкцій насправді була корисною проти тих, які були замасковані як втрачені цикли варпу. Поширені стратегії пом’якшення включають переструктурування умовних тверджень так, щоб рішення про гілку залежало від варп-вирівнених меж, наприклад, розгалуження на варп або індекс блоку замість будь-якого випадкового значення, обчисленого для кожного потоку, сортування або розділення вхідних даних так, щоб групи потоків, які, ймовірно, будуть слідувати однаковому шляху, були згруповані в один варп перед запуском ядра, і в деяких випадках заміна справжньої гілки на передбачену, безгібку арифметику, яка обчислює обидва можливі результати та вибирає між ними за допомогою маски, торгуючи деяким втраченим обчисленням усуненням навантаження від розбіжності, техніка, концептуально схожа на безгібке програмування на CPU, але мотивована глобальним виконанням варпу замість помилки передбачення конвеєра. Трасування променів та робочі навантаження фізично заснованого рендерингу особливо відомі тим, що викликають значну розбіжність, оскільки сусідні промені або пікселі часто слідують дуже різним шляхам коду, що є причиною того, що GPU-трасування променів включає спеціальні блоки для обробки саме цього типу нерегулярного потокового контролю більш граціозно. Розпізнавання розбіжності як першочергового питання продуктивності, а не просто деталі реалізації, є одним із найяскравіших способів, яким GPU-програмування справді відрізняється від написання паралельного коду для CPU.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте GPU Warp Scheduling & SIMD Branch Divergence і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.