Слышал, что есть несколько видов сотрировок для GPU (битоническая, поразрядная и еще что-то).
Надо отсортировать большой массив индексов (1 - 10 миллионов int элементов), причем сравнение идет не самих индексов, а связных с ними элементов другого массива (каждый элемент - 2 int`а). Пусть для сравнения написана отдельная ф-я. Вопрос: будет ли сортировка такого массива на GPU быстрее (или хотя бы сравнима) чем qsort на CPU? И какую сортировку лучше использовать?
Видюха довольно слабая - GeForce GT 240.
Заранее спасибо!
Comments
Ну вот для RadixSort и GTX480 получается миллиард 32-битных ключей в секунду: http://code.google.com/p/back40computing/wiki/RadixSorting
Для i7 те же бойцы ссылаются на Intel и 240M ключей в секунду (см. тут: http://forums.nvidia.com/index.php?showtopic=175238 ) т.е. вчетверо медленнее. Но это интеловская неопубликованная реализация.
GT240M - вчетверо меньше по числу ядер, чем 480я и частота чуть пониже. Т.е. результат должен быть сравним с i7.
Как скажется дополнительный индирект (от индекса к данным) я не знаю, может быть проще, если нужны именно сортированные индексы, сложить индекс прямо к данным и считать данные ключом, а индекс - данными.
Не очень понял, что вы имеете ввиду.
Приведу пример.
Есть 2 структуры:
Есть 2 массива:
Теперь надо отсортировать массив index используя след. ф-ю сравнения:
Такое можно реализовать с помощью RadixSort?
Для radix sort соотношения больше-меньше для пары - недостаточно.
Впрочем, если вы рассматриваете пару (C,R) как одно 64-битное число (C<<32|R), то вроде и нормально все, сортируйте "поразрядно" (т.е. Radix)
Глянул пример из SDK, там без поллитра не разберешься, а переделывать придется...
Но главную идею вроде понял, спасибо большое.
Последний вопрос: в примере из SDK и индекс и элемент были одинакового размера - 32 бита. В моем случае надо подгонять все под 64 или для алгоритма это не важно?