Часть 4 этой серии завершает путешествие по изучению программирования CUDA с нуля с помощью Python.

Введение

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

В этом уроке

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

Нажмите здесь, чтобы получить код в Google Colab.

Начиная

Импортируйте и загружайте библиотеки, убедитесь, что у вас есть графический процессор.

Атомикс

Программирование GPU полностью основано на максимально возможном распараллеливании одних и тех же инструкций. Для многих «досадно параллельных» задач потокам не нужно сотрудничать или использовать ресурсы, которые используются другими потоками. Другие шаблоны, такие как сокращения, за счет разработки алгоритма гарантируют, что один и тот же ресурс когда-либо будет использоваться только подмножеством потоков. В этих случаях мы гарантировали, что все остальные потоки будут обновляться с помощью syncthreads.

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

Когда мы запустим это ядро ​​с одним блоком потока, мы получим значение 1, хранящееся во входном массиве.

Что произойдет, если мы запустим 10 блоков по 16 потоков в каждом? Мы суммируем в общей сложности 10 × 16 × 1 для одного и того же элемента памяти, поэтому мы должны надеяться получить значение 160, хранящееся в dev_val. Верно?

На самом деле мы вряд ли когда-нибудь достигнем 160, хранящихся в dev_val. Почему? Потому что потоки читают и пишут в одну и ту же переменную памяти одновременно!

Ниже приведена схема того, что может произойти, когда четыре потока пытаются читать и писать из одной и той же глобальной памяти. Потоки 1–3 считывают одно и то же значение 0 из глобального регистра разное время (t=0, 2, 2 соответственно). Все они увеличиваются на 1 и записываются обратно в глобальную память в моменты времени t=4, 7 и 8. Поток 4 начинается чуть позже остальных, в момент t=5. В это время поток 1 уже произвел запись в глобальную память, поэтому поток 4 считывает значение 1. В конечном итоге он перезапишет глобальную переменную значением 2 при t=12.

Если мы хотим получить результат, которого изначально ожидали (как показано на рис. 4.2), мы должны заменить нашу неатомарную операцию сложения атомарной операцией. Атомарные операции гарантируют, что любая память, в которую выполняется чтение/запись, выполняется одним потоком за раз. Давайте поговорим о них подробнее.

Atomic Add: вычисление гистограммы

Чтобы лучше понять, где и как использовать атомные числа, мы будем использовать вычисление гистограммы. Предположим, кто-то хочет подсчитать, сколько каждой буквы алфавита встречается в определенном тексте. Простой алгоритм для достижения этого состоит в том, чтобы создать 26 «сегментов», каждое из которых соответствует букве английского алфавита. Затем мы будем перебирать буквы текста, и всякий раз, когда мы встречаем «а», мы будем увеличивать первое ведро на единицу, всякий раз, когда мы встречаем «б», мы будем увеличивать второе ведро на единицу и так далее. так далее.

В стандартном Python эти сегменты могут быть словарями, каждый из которых связывает букву с числом. Поскольку нам нравится работать с массивами, программируя GPU, вместо этого мы будем использовать массив. И вместо того, чтобы группировать 26 букв, мы будем группировать все 128 символов ASCII.

Прежде чем мы это сделаем, нам нужно преобразовать наши строки в массив «чисел». В этом случае имеет смысл преобразовать строки UTF-8 в тип данных uint8.

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

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

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

Поскольку каждый символ ASCII сопоставляется с ячейкой в ​​массиве из 128 элементов, все, что нам нужно сделать, это найти ее ячейку и увеличить ее на 1, если эта ячейка находится в пределах от 0 до 127 (включительно).

Мы готовы к нашей первой версии GPU.

Прохладный! Так что по крайней мере наша функция работает. Ядро очень простое и имеет ту же структуру, что и серийная версия. Он начинается со стандартной одномерной структуры петли шага сетки и, в отличие от последовательной версии, использует атомарное добавление. Атомарное добавление в Numba принимает три параметра: массив, который будет увеличиваться (histo), расположение массива, в котором будет отображаться приращение (arr[iarr], что эквивалентно char в последовательной версии), и, наконец, значение, на которое будет увеличиваться histo[arr[iarr]]. (т. е. 1 в данном случае).

Теперь давайте поднимем ставку и применим это к большему набору данных.

Это около 5,7 миллиона символов, которые мы будем обрабатывать. Давайте запустим и синхронизируем наши три версии.

Взяв за основу нашу версию GPU, мы видим, что версия NumPy как минимум в 40 раз медленнее, а наша наивная версия CPU медленнее в тысячи раз. Мы можем обработать этот набор данных из 5,7 миллионов символов за несколько миллисекунд, тогда как наше наивное решение для ЦП занимает более 10 секунд. Это означает, что мы могли бы потенциально обработать набор данных из 20 миллиардов символов (если бы у нас был графический процессор с оперативной памятью более 20 Гб) за несколько секунд, тогда как в нашей самой медленной версии это заняло бы более часа. Так что у нас уже неплохо получается!

Можем ли мы улучшить его? Что ж, давайте вернемся к схеме доступа к памяти этого ядра.

...
for iarr in range(i, arr.size, threads_per_grid):
    if arr[iarr] < 128:
        cuda.atomic.add(histo, arr[iarr], 1)

histo — это массив из 128 элементов, расположенный в глобальной памяти графического процессора. Каждый поток, запущенный в любой точке, пытается получить доступ к некоторому элементу этого массива (а именно к элементу arr[iarr]). Таким образом, в любой момент у нас есть около threads_per_block * blocks_per_grid = 128 × 32 × 80 = 327 680 потоков, пытающихся получить доступ к 128 элементам. Таким образом, у нас есть в среднем около 32 × 80 = 2560 потоков, конкурирующих за один и тот же адрес глобальной памяти.

Чтобы смягчить это, мы вычисляем локальные гистограммы в массиве общей памяти. Это потому что

  1. Общие массивы находятся на кристалле, поэтому чтение/запись выполняются намного быстрее.
  2. Общие массивы являются локальными для каждого блока потока, поэтому меньшее количество потоков может получить доступ и, следовательно, конкурировать за его ресурсы.

ИНФОРМАЦИЯ. Наши расчеты предполагают, что символы распределены равномерно. Будьте осторожны с такими предположениями, поскольку естественные наборы данных могут им не соответствовать. Например, большинство символов в тексте на естественном языке — это строчные буквы, вместо 2 560 конкурирующих в среднем потоков у нас будет 128 × 32 × 80 ÷ 26 ≈ 12 603 конкурирующих потока, что гораздо более проблематично!

Если раньше у нас было 2560 потоков, конкурирующих за одну и ту же память, то теперь у нас 2560 ÷ 128 = 20 потоков. В конце ядра нам нужно просуммировать все локальные результаты. Поскольку имеется 32 × 80 = 2560 блоков, это означает, что 2560 конкурирующих блоков пытаются записать в глобальную память. Однако мы добились того, что это делается только один раз для каждого потока, тогда как раньше нам приходилось делать это до тех пор, пока мы не исчерпали все элементы входного массива.

Давайте посмотрим, как эта новая версия работает по сравнению с предыдущей!

Так что это ~ 3-кратное улучшение по сравнению с наивной версией!

Мы устанавливаем количество блоков кратным 32 × количество SM, как было предложено в предыдущем уроке. Но какой кратный? Рассчитаем время!

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

  • Первая часть с несколькими потоками, конкурирующими за одну и ту же (быструю) память (часть общего массива).
  • Вторая часть со множеством потоков, конкурирующих за одну и ту же (медленную) память (финальное атомарное добавление).

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

Блокировка ресурсов с помощью мьютекса

В предыдущих примерах мы использовали атомарные операции добавления с целочисленными значениями, чтобы заблокировать определенные ресурсы и гарантировать, что только один поток одновременно ими управляет. Сложение — не единственная атомарная операция, и ее не нужно применять к целочисленным значениям. Numba CUDA поддерживает множество атомарных операций с целыми числами и числами с плавающей запятой. Но когда-то (вычисления CUDA 1.x) атомарных вычислений с плавающей запятой не существовало. Поэтому, если бы мы хотели написать сокращение, используя атомарные числа для чисел с плавающей запятой, нам потребовалась бы другая структура.

Хотя в настоящее время атомарные операции поддерживают числа с плавающей запятой, шаблон кода «мьютекс», который позволяет нам применять произвольные атомарные операции, все еще может быть полезен в некоторых ситуациях.

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

  • 0: 🟢 Зеленый свет, продолжите использование определенной памяти/ресурса
  • 1: 🔴 Красный свет, остановитесь, не пытайтесь использовать/получить доступ к определенной памяти/ресурсу

Чтобы заблокировать память, нужно записать в мьютекс 1, чтобы разблокировать его, нужно написать 0. Но нужно быть осторожным, если вы записываете (неатомарно) в мьютекс, другие потоки могут в данный момент обращаться к этому ресурсу, создавая в минимум неправильных значений или, что еще хуже, создание взаимоблокировки. Другая проблема заключается в том, что мьютекс может быть заблокирован только в том случае, если он ранее не был заблокирован. Поэтому перед записью 1 (для блокировки) нам нужно прочитать мьютекс и убедиться, что он равен 0 (разблокирован). CUDA предоставляет специальную операцию для атомарного выполнения обеих этих задач: atomicCAS. В Numba CUDA это более четко названо:

cuda.atomic.compare_and_swap(array, old, val)

Эта функция будет атомарно присваивать val array[0] (это часть «обмена»), только если текущее значение в array[0] равно old (это часть «сравнения»); в противном случае он теперь поменяется местами. Более того, он возвращает текущее значение array[0] атомарно. Следовательно, чтобы заблокировать мьютекс, мы могли бы применить его с помощью

cuda.atomic.compare_and_swap(mutex, 0, 1)

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

while cuda.atomic.compare_and_swap(mutex, 0, 1) != 0:
    pass

В этом случае поток будет сохраняться до тех пор, пока он не сможет должным образом заблокировать поток. Предположим, поток достигает ранее заблокированного мьютекса. Его текущее значение равно 1. Итак, сначала мы замечаем, что compare_and_swap не сможет заблокировать его, начиная с curr = 1 != old = 0. Он также не выйдет из while, так как текущее значение 1 отличается от 0 (условие while). Он будет оставаться в этом цикле до тех пор, пока, наконец, не сможет прочитать разблокированный мьютекс, текущее значение которого равно 0. В этом случае он также сможет присвоить 1 мьютексу с curr = 0 == old = 0.

Чтобы разблокировать, нам просто нужно атомарно присвоить 0 мьютексу. Мы будем использовать

cuda.atomic.exch(array, idx, val)

Который просто присваивает array[idx] = val атомарно, возвращая старое значение array[idx] (загружено атомарно). Поскольку мы не будем использовать возвращаемое значение этой функции, в этом случае вы можете думать об этом как об атомарном присваивании (т. Е. Тогда как atomic_add(array, idx, val) относится к array[idx] += val, как exch(array, idx, val) к array[idx] = val ).

Теперь, когда у нас есть механизм блокировки и разблокировки, давайте повторим атомарное «добавить единицу», но вместо этого используем мьютекс.

Приведенный выше код довольно прост: у нас есть ядро, которое блокирует выполнение потоков до тех пор, пока они сами не смогут получить разблокированный мьютекс. В этот момент они обновят значение x[0] и разблокируют мьютекс. Ни в коем случае x[0] не будет прочитано или записано более чем одним потоком, таким образом достигается атомарность!

В приведенном выше коде мы не рассмотрели только одну деталь — использование cuda.threadfence(). Для этого примера это не требуется, но убедитесь в правильности механизма блокировки и разблокировки. Мы скоро увидим, почему!

Мьютексный точечный продукт

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

Мы интерпретируем этот пример как скалярное произведение, но на этот раз доводим суммирование до конца. Это означает, что мы не будем возвращать «частичное» скалярное произведение, а будем использовать атомарное суммирование в графическом процессоре с помощью мьютекса. Давайте сначала переинтерпретируем наше сокращение как точечный продукт:

Все проверяется!

Прежде чем мы закончим, я пообещал, что мы вернемся к cuda.threadfence. Из библии CUDA (B.5. Функции ограничения памяти): __threadfence()гарантирует, что записи во всю память, сделанные вызывающим потоком после вызова__threadfence(), не будут наблюдаться любым поток в устройстве, как это происходит перед любой записью во всю память, выполненной вызывающим потоком перед вызовом__threadfence().

Если мы опустим блокировку потоков перед разблокировкой мьютекса, мы можем считывать устаревшую информацию даже при использовании атомарных операций, поскольку другие потоки могут еще не записывать память. Точно так же перед разблокировкой мы должны убедиться, что мы обновляем ссылки на память. Ничто из этого совсем не очевидно, и было много лет до того, как впервые было поднято в Alglave et al. 2015. В конце концов, это исправление было опубликовано в Errata of CUDA by Examples, которое вдохновило эту серию руководств.

Заключение

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

Эпилог

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

Некоторые из тем, которые мы не затронули: динамический параллелизм (позволяющий ядрам запускать ядра), сложная синхронизация (например, на уровне деформации, кооперативные группы), сложное ограждение памяти (которое мы затронули выше), мульти-GPU, текстуры и многие другие темы. Некоторые из них в настоящее время не поддерживаются Numba CUDA (начиная с версии 0.56), а некоторые из них были сочтены слишком сложными для вводного руководства.

Чтобы еще больше улучшить свои навыки работы с CUDA, настоятельно рекомендуется ознакомиться с Руководством по программированию на CUDA C++, а также с сообщениями в блоге Nvidia.

В экосистеме Python важно подчеркнуть, что помимо Numba существует множество решений, которые могут использовать GPU. И они в основном взаимодействуют, поэтому не нужно выбирать только один. PyCUDA, CUDA Python, RAPIDS, PyOptix, CuPy и PyTorch являются примерами библиотек, находящихся в активной разработке.