CUDA: сокращение или атомные операции?
Я пишу ядро CUDA, которое включает в себя вычисление максимального значения для данной матрицы, и я оцениваю возможности. Лучший способ найти:
Заставить каждый поток хранить значение в общей памяти и использовать алгоритм сокращения после этого для определения максимума (pro: минимальные расхождения минусы: общая память ограничена 48 КБ на устройствах 2.0)
Я не мог использовать атомарные операции, потому что есть и операции чтения, и записи, поэтому потоки не могли быть синхронизированы с помощью синхронных потоков.
Любая другая идея приходит в голову?
7 ответов
Это обычный способ выполнения сокращений в CUDA
Внутри каждого блока
1) Сохраняйте уменьшенное значение в общей памяти для каждого потока. Следовательно, каждый поток будет читать (я лично предпочитаю от 16 до 32) значения из глобальной памяти и обновлять уменьшенное значение из этих
2) Выполните алгоритм уменьшения в пределах блока, чтобы получить одно окончательное уменьшенное значение на блок.
Таким образом, вам не потребуется больше разделяемой памяти, чем (число потоков) * sizeof (datatye) байтов.
Поскольку каждый блок имеет уменьшенное значение, вам нужно будет выполнить второй проход сокращения, чтобы получить окончательное значение.
Например, если вы запускаете 256 потоков на блок и читаете 16 значений на поток, вы сможете уменьшить (256 * 16 = 4096) элементов на блок.
Итак, учитывая 1 миллион элементов, вам нужно будет запустить около 250 блоков на первом проходе и всего один блок на втором.
Вероятно, вам потребуется третий проход для случаев, когда количество элементов> (4096)^2 для этой конфигурации.
Вы должны позаботиться о том, чтобы считывания глобальной памяти были объединены. Вы не можете объединить записи в глобальную память, но это один удар производительности, который вам нужно предпринять.
Вы также можете использовать процедуры сокращения, которые поставляются с CUDA Thrust, который является частью CUDA 4.0 или доступен здесь.
Библиотека написана парой инженеров nVidia и выгодно отличается от сильно оптимизированного кода. Я считаю, что также происходит некоторая автоматическая настройка размера сетки / блока.
Вы можете легко взаимодействовать с вашим собственным ядром, оборачивая ваши сырые указатели устройств.
Это строго с точки зрения быстрой интеграции. Теорию смотрите в ответе tkerwin.
У NVIDIA есть демонстрационная версия CUDA, которая делает сокращение: здесь. Есть документ, который объясняет некоторые мотивы дизайна.
Я нашел этот документ очень полезным для изучения основ параллельного сокращения с помощью CUDA. Это старое, поэтому должны быть дополнительные приемы для дальнейшего повышения производительности.
На самом деле, проблема, которую вы описали, не совсем о матрицах. Двумерное представление входных данных несущественно (при условии, что матричные данные расположены непрерывно в памяти). Это всего лишь сокращение последовательности значений, представляющих собой все элементы матрицы в любом порядке, в котором они появляются в памяти.
Предполагая, что матричное представление непрерывно в памяти, вы просто хотите выполнить простое сокращение. И наилучшая доступная реализация в наши дни - насколько я могу судить - это отличный libcub от Duane Merill из nVIDIA. Вот документация по его функции максимального вычисления для всего устройства.
Тем не менее, обратите внимание, что если матрица не мала, для большей части вычислений это будут просто потоки, считывающие данные и обновляющие свой собственный максимум, зависящий от потока. Только когда поток завершит чтение через большой образец матрицы (или, скорее, с большим шагом), он будет записывать свой локальный максимум где угодно - обычно в разделяемую память для сокращения на уровне блоков. А что касается атомистики, вы, вероятно, будете делать atomicMax() вызывать один раз каждое непристойно большое количество считываний матричного элемента - десятки тысяч, если не больше.
Если у вас K20 или Titan, я предлагаю динамический параллелизм: запускаем одноядерное ядро, которое запускает потоки рабочего ядра #items для получения данных, затем запускает потоки #items/first-round-factor-factor для сокращения первого раунда и продолжаю обедать пока не выйдет результат.
atomicAdd Функцию также можно использовать, но она гораздо менее эффективна, чем упомянутые выше подходы. http://supercomputingblog.com/cuda/cuda-tutorial-4-atomic-operations/