Битоновая сортировочная сеть против Thrust :: sort_by_key

Question

Я реализовал алгоритм, который использовал сортировку. Я попробовал Thrust :: sort_by_key, который занял около 0,4 с, чтобы отсортировать массив с 10 ^ 7 элементами.

Я думал, что сеть битовой сортировки должна быть быстрее, чем Thrust :: sort_by_key. Однако для сортировки того же массива, который упоминался выше, для битовой сортировки потребовалось около 2,5 с. Я использовал сеть битовой сортировки, предоставленную SDK. Я просто немного изменил оригинальную битоническую сортировку.

Не могли бы вы сказать мне, почему? или дать мне совет?

Спасибо

Yik

15 августа 2011 г.

Answer 1

Короткий ответ: пример битовой сортировки, предоставленный CUDA SDK, в первую очередь предназначен для педагогической работы. Он просто не так оптимизирован, как реализация сортировки Thrust, которая основана на очень эффективной сортировке по основанию, предоставляемой Merrill .

Асимптотическая производительность двух алгоритмов также различна. Сеть битовой сортировки имеет сложность O(n lg^2 n), в то время как радикальная сортировка, используемая Thrust, имеет нечто большее, чем O(#bits n) сложность, где #bits обозначает количество битов, необходимых для представления входных данных. Другими словами, радикальная сортировка требует асимптотически меньшего количества операций чтения и записи в глобальную память, чем для битовой сортировки.

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