Параллельная сортировка данных в GPU

[Kobalt_x]

Ну так поэтому и Бэтчера придумали чтобы сложномть была O(n logn^2)

[Krizai]

Интересно было бы увидеть сравнение скорости выполнения на наборах данных разной длинны и сравнение с аналогичным алгоритмом на CPU.

[khim]

Ага. Это ж самое интересное! Обычно с CPU и GPU всё просто: вначале лидирует CPU, так как «разгоняться» не надо, но начиная с какого-то момента мощь GPU решает.

Тут же при очень больших объёмах GPU — снова «не при делах» из-за медленного алгоритма… Так какого размера вообще ниша у GPU? Интересно…

[mafia8]

Пишут про О большое, а не пишут, что будет, когда оперативной памяти не хватает.

[datacompboy]

Так это же О(N) по памяти: только память на вторую текстуру.

[gnomeby]

Шейдерная реализация более параллельна чем CUDA`вская? Или в чём смысл изврата?

[Kobalt_x]

Шейдерная как минимум будет работать на amd

[gnomeby]

И на Intel с HD Graphics. Если хочется AMD, то есть AMD Firestream. Если хочется универсального, то есть OpenCL.
Вопрос в том, что даёт ли сортировка на шейдерах какие-то преимущества по сравнению CUDA|OpenCL?

[Kobalt_x]

ну она будет работать на всём, что вышло в эпоху до cuda/openCL.

[gnomeby]

Проанализировав блог автора, я увидел, что он просто любитель программировать шейдеры и делает это очень хорошо.

[gnomeby]

Оставлю ссылку на статью Параллельная сортировка методом пузырька на CUDA.

[kvazimoda24]

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

[avp2012]

Если каждый элемент был сравнен с каждым другим, то сортировка завершена. n-1 шагов.

[kvazimoda24]

А если изначально список не так сильно перепутан? Например, только два соседних элемента местами поменяны, то что, всё равно ждать n-1 шагов?

[Kobalt_x]

А за какое количество сравнений вы сможете проверить что массив отсортирован?

[avp2012]

Очевидно, что за n-1. Изначально я давал оценку сверху. Если исхитриться, думаю можно намутить какой-нибудь флаг (например в первом "пикселе" строки вычислять, отсортирована ли входная информация. Мне, кстати, не до конца понятно, почему автор не прерывает вычисления. Похоже, что он таким образом отказывается от ветвления. Ну, я ему доверяю, так что наверное так эффективно. Или как минимум, легко реализовать и объяснить.

[kvazimoda24]

Собственно, у меня поэтому и появился этот вопрос. Потому как в статье об окончании сортировки ничего не говорится, но когда-то же надо остановиться. И если делать какие-то проверки массива на то, отсортирован ли он, то вырастет сложность алгоритма. Производить же гарантированное количество шагов сортировки мне в голову не пришло.

[avp2012]

Ответ, как мне кажется, заложен в самом вашем вопросе. Вы говорите, что "… только два соседних элемента местами поменяны...". У меня вопрос: как вы можете это определить в общем случае? Я подчёркиваю: в общем случае, а не на одном шаге сложного алгоритма, где вы уже многое знаете о данных.

[kvazimoda24]

Я совершенно не разбираюсь в алгоритмах сортировки, да и программист из меня так себе, так, пару скриптов на bash'е написал. Ход мысли у меня был такой: если мы будем работать по подобному алгоритму в один поток, т.е. сначала сравним первый и второй элемент массива, потом второй и третий… То с минимальной перепутанностью (поменяны местами два соседних элемента) нам понадобится пройти по массиву всего два раза — на втором проходе мы замечаем, что не выполнили ни одной перестановки. Но если мы действуем по тому алгоритму, что описан в статье на большом количестве потоков, то уже так просто не узнать, закончена ли сортировка. Надо либо придумывать какие-то алгоритмы межпоточного взаимодействия, либо, как мне выше подсказали, ждать гарантированное количество итераций. Даже мне, далёкому от анализа и оценки сложности алгоритмов, понятно, что любое межпоточное взаимодействие будет сложнее простого счётчика. Но в случае с минимальной перепутанностью алгоритм выглядит не очень оптимальным, зато очень предсказуемым. Мы точно знаем, сколько нам понадобится времени на сортировку. В некоторых задачах, как мне кажется, это может быть полезно.