Сортировка

Слышал, что есть несколько видов сотрировок для GPU (битоническая, поразрядная и еще что-то).
Надо отсортировать большой массив индексов (1 - 10 миллионов int элементов), причем сравнение идет не самих индексов, а связных с ними элементов другого массива (каждый элемент - 2 int`а). Пусть для сравнения написана отдельная ф-я. Вопрос: будет ли сортировка такого массива на GPU быстрее (или хотя бы сравнима) чем qsort на CPU? И какую сортировку лучше использовать?
Видюха довольно слабая - GeForce GT 240.

Заранее спасибо!

Forums: 

Ну вот для RadixSort и GTX480

Ну вот для 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 структуры:

  1. struct Circle  { int       C,R; };
  2. struct Index   { short  X,Y;  };

Есть 2 массива:

  1. Circle *circles;  // Одномерный, определяет двумерную матрицу Width*Height
  2. Index  *index;    // Одномерный, содержит координаты всех точек (т.е.  {{0,0},{0,1},{0,2}, ...})

Теперь надо отсортировать массив index используя след. ф-ю сравнения:

  1. bool Comp(Index& ind1, Index& ind2)
  2. {
  3.  Circle c1, c2;
  4.  c1 = circs[ind1.X + ind1.Y*Width];
  5.  c2 = circs[ind2.X + ind2.Y*Width];
  6.  return (c1.C==c2.C) ? (c1.R>c2.R) : (c1.C>c2.C);
  7. }

Такое можно реализовать с помощью RadixSort?

Нет, для radix sort

Для radix sort соотношения больше-меньше для пары - недостаточно.

Впрочем, если вы рассматриваете пару (C,R) как одно 64-битное число (C<<32|R), то вроде и нормально все, сортируйте "поразрядно" (т.е. Radix)

Глянул пример из SDK, там без

Глянул пример из SDK, там без поллитра не разберешься, а переделывать придется...
Но главную идею вроде понял, спасибо большое.
Последний вопрос: в примере из SDK и индекс и элемент были одинакового размера - 32 бита. В моем случае надо подгонять все под 64 или для алгоритма это не важно?