Битоновая сортировочная сеть против 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 обозначает количество битов, необходимых для представления входных данных. Другими словами, радикальная сортировка требует асимптотически меньшего количества операций чтения и записи в глобальную память, чем для битовой сортировки.

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