Thrust::reduce_by_key производительность с несколькими повторениями клавиш

Мне приходится выполнять ключевое сокращение массивов с множеством разных ключей, которые повторяются только время от времени:

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

// after reduction
result = {1,2,7,5,6,7,17,10,23,13,14}

Использование thrust::reduce_by_key (или любого другого метода сегментированного сокращения) здесь не самый быстрый вариант, так как большинство операций на самом деле являются просто копированием из одного массива в другой.

Что было бы лучшим подходом к этой проблеме?


c cuda thrust reduction
person bbtrb    schedule 23.02.2012    source источник
comment
Можно ли априори знать, какие отрезки имеют длину › 1 ? Если ответ отрицательный, то это кажется сложной проблемой, поскольку стоимость перемещения данных при простом обнаружении сегментов будет сравнима со стоимостью reduce_by_key.   -  person Jared Hoberock    schedule 23.02.2012
comment
@JaredHoberock: Да, на самом деле длина сегментов хранится в другом массиве.   -  person bbtrb    schedule 23.02.2012

Ответы (1)


arrow_upward
3
arrow_downward

Фактически, reduce_by_key является подходящим алгоритмом для использования здесь. Просто текущая реализация в Thrust не такая быстрая, как могла бы быть. Чтобы уточнить, ничто не мешает reduce_by_key выполняться со скоростью memcpy, и я полагаю, что другие реализации уже достигли такого уровня. Наш предварительный план для Thrust v1.7 включает повышение производительности reduce_by_key и других алгоритмов на основе сканирования с использованием кодов из соответствующих проект back40computing.

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

person wnbell    schedule 23.02.2012