CUDA: Как найти индекс экстремумов в подматрицах?

Question

У меня есть большая прямоугольная матрица NxM в памяти графического процессора, которая хранится в виде одномерного массива в представлении строки за строкой. Скажем, что эта матрица фактически состоит из подматриц размера nxm. Для простоты предположим, что N кратно n и такое же с M и m. Скажем, тип данных массива равен float или double.

Что такое эффективный метод определения индекса экстремумов в каждой подматрице? Например, как найти 1-мерный индекс максимального элемента каждой подматрицы и записать эти индексы в некоторый массив.

Answer 1

я с трудом могу себе представить, чтобы быть так самоуверенны (или высокомерным?), Чтобы сказать, что одно частное решение является «самый эффективный способ» сделать что-то.

Однако некоторые мысли (без претензии на покрытие «наиболее эффективное» решения):

Я думаю, что есть в основном два «ортогональный» путь приближения к этому

• Для всех суб- матрицы в параллель: Найти экстремум последовательно
• Для всех суб-матриц последовательно: Найти экстремум в параллельном

The которых один вопрос более вероятно, зависит от размеров матриц. Вы упомянули, что «N кратно n» (аналогично для M и m). Пусть матрица размера M x N состоит из подматриц a*b размера m x n.

Для первого подхода, можно было бы просто позволить каждому потоку заботиться одной подматрицы, с тривиальной петлей как

for (all elements of my sub-matrix) max = element > max ? element : max; 

Предпосылкой здесь является то, что a*b является «достаточно большой». То есть, когда вы можете запустить это ядро, скажем, из 10000 подматриц, то это уже может привести к хорошему ускорению.

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

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

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