Эффективные частичные сокращения, учитывая массивы элементов, смещения и длины подсписков

Question

Для моего приложения я должен обработать группу объектов (скажем, int s), которые впоследствии разделяются и сортируются в меньшие сегменты. Для этого я храню элементы в одном непрерывном массиве

arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...}

и информация о сегментах (подсписках) задается смещением первого элемента в соответствующем сегменте и длинами подсписка.

Так, например, дано

offsets = {0,3,8,..}
sublist_lengths = {3,5,2,...}

приведет к следующим разбиениям:

0 1 2 || 3 4 5 6 7 || 8 9 || ...

То, что я ищу, - это несколько общий и эффективный способ запуска алгоритмов, таких как редукции, в корзинах только с использованием пользовательских ядер или библиотеки thrust. Суммирование ведер должно дать:

3 || 25 || 17 || ...

Что я придумал:

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

• опция 2 : сгенерировать массив ключей из смещений ({0,0,0,1,1,1,1,1,2,2,3,...} в приведенном выше примере) и использовать thrust::reduce_by_key. Но мне не нравится создание дополнительного списка.

• опция 3 : используйте thrust::transform_iterator вместе с thrust::counting_iterator для генерации указанного выше списка ключей на лету. К сожалению, я не могу придумать реализацию, которая не требует приращений индексов к списку смещений на устройстве и опровергает параллелизм.

Какой самый разумный способ реализовать это?

Answer 1

В Thrust я не могу придумать лучшего решения, чем Вариант 2. Производительность не будет ужасной, но, безусловно, не оптимальной.

Ваша структура данных имеет сходство с форматом Compressed Sparse Row (CSR) для хранения разреженных матриц, поэтому вы можете использовать методы, разработанные для вычисления умножения разреженных матриц-векторов (SpMV) * ​​1006 * для таких матриц, если вы хотите лучшую производительность. Обратите внимание, что массив «смещений» в формате CSR имеет длину (N + 1) для матрицы с N строками (т.е. в вашем случае с сегментами), где последним значением смещения является длина arr. CSR SpMV код в Cusp немного запутан, но он служит хорошей отправной точкой для вашего ядра. Просто удалите любую ссылку на Aj или x из кода и передайте offsets и arr в аргументы Ap и Av соответственно.

Answer 2

Вы не упомянули, насколько велики ведра. Если сегменты достаточно велики, возможно, вам удастся скопировать смещения и sublist_lengths на хост, итерировать их и выполнить отдельный вызов Thrust для каждого сегмента. Fermi может иметь одновременно 16 ядер в полете, поэтому на этой архитектуре вы сможете обрабатывать меньшие сегменты и при этом эффективно использовать их.