CUDA: сокращение или атомные операции?

Question

Я пишу ядро ​​CUDA, которое включает в себя вычисление максимального значения для данной матрицы, и я оцениваю возможности.Лучший способ, который я мог бы найти, это:

Принудительное выполнение каждым потоком значения в общей памяти и использование алгоритма сокращения после этого для определения максимума (pro: минимальная расходимость минусы: общая память ограничена до 48 КБ наУстройства 2.0)

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

Любая другая идея приходит вам на ум?

Answer 1

Вы также можете использовать процедуры сокращения, которые поставляются с CUDA Thrust, который является частью CUDA 4.0 или доступен здесь .

Библиотека написана парой инженеров nVidia и выгодно отличается от сильно оптимизированного кода.Я полагаю, что также происходит некоторая автоматическая настройка размера сетки / блока.

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

Answer 2

Это обычный способ выполнения сокращений в CUDA

Внутри каждого блока

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

2) Выполните алгоритм уменьшения в блоке, чтобы получить одно окончательное уменьшенное значение на блок.

Таким образом, вам не нужно больше разделяемой памяти, чем (число потоков) * sizeof (datatye) байтов.

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

Например, если вы запускаете 256 потоков на блок и читаете 16 значений на поток, вы сможете уменьшить (256 * 16 = 4096) элементов на блок.

Итак, учитывая 1 миллион элементов, вам нужно будет запустить около 250 блоков на первом проходе и всего один блок на втором.

Вероятно, вам потребуется третий проход для случаев, когда количество элементов> (4096) ^ 2 для этой конфигурации.

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

Answer 3

NVIDIA имеет демонстрационную версию CUDA, которая сокращает: здесь .Есть документ, который объясняет некоторые мотивы дизайна.

Answer 4

Я нашел этот документ очень полезным для изучения основ параллельного сокращения с помощью CUDA.Это старое, поэтому должны быть дополнительные приемы для дальнейшего повышения производительности.

Answer 5

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

Предполагая, что матричное представление непрерывно в памяти, вы просто хотите выполнить простое сокращение. И наилучшая доступная реализация в наши дни - насколько я могу судить - это превосходный libcub от Duane Merill от nVIDIA. Здесь - документация по функции максимального вычисления для всего устройства.

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

Answer 6

Если у вас K20 или Titan, я предлагаю динамический параллелизм: запускаем одноядерное ядро, которое запускает потоки рабочего ядра #items для получения данных, затем запускает потоки # items / first-round-сокращения-factor для первого раунда сокращения,и продолжай обедать, пока не выйдет результат.

Answer 7

Можно также использовать функцию atomicAdd, но она гораздо менее эффективна, чем упомянутые выше подходы. http://supercomputingblog.com/cuda/cuda-tutorial-4-atomic-operations/