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

[maksqwe]

Похоже, после обнуления кармы сегодня некоторые люди достали из закромов лабораторные(курсовые или дипломные), сдули пыль и закопипастили текст на хабр. Хоть оформили бы по-человечески код, есть же теги.

[maksqwe]

У самого где-то курсовик валяется на винте где проводил анализ производительности поразрядной сортировки с другими ее реализациями(из других пакетов). Еще на первых версиях, гонял на своей 9800печ.

[prizzrak]

Подпишите, пожалуйста, оси на графике. Y — время выполненеия, X — число элементов? Почему тогда для однопоточного варианта тесты начинаются с 32-х элементов, а для многопоточного — с одного?
И в самом деле больше похоже на каую-то лабу, только оформленную не так уж и аккуратно :-/

[onto]

Наверное стоит параллельный алгоритм описать подробнее, ибо ваша реализация у меня не сортирует.

[halyavin]

if (array_device[idx]<array_device[idx+1]){
    int buffer = array_device[idx];
    array_device[idx]=array_device[idx+1];
    array_device[idx+1] = buffer;
}

Это рейс кондишен в чистом виде.

[sandello]

Параллелить лучше какой-нибудь mergesort или quicksort. Они из «коробки» под это заточены. Пузырек с его O(N²) подходит только под мелочь, которую параллелить смысла не имеет.

[YourChief]

Поддерживаю, статья просто мусор.

Автор апеллирует к незначительному выигрышу при сортировке больших массивов, но при большом количестве элементов время работы пузырька и сортировки Хоара или сортировки слиянием (и им подобных) различается на порядки. Таким образом просто использование «нормального» алгоритма сортировки оставляет позади сортировку с параллелизмом практически в любое количество ядер.

[beeruser]

Для GPU основными методами сортировки являются Radix и Bitonic

[KvanTTT]

Зачем нужны такие большие таблицы в статье?

[prizzrak]

Чтобы отчет по лабораторной работе в универе выглядел внушительнее =)

[Vest]

Мне вообще не нравится то, что в цикле происходит выделение памяти для устройства, и потом опять же в цикле вызываются операции перемещения элементов. Я думаю, что это затратный код — надо бы его попрофилировать…
А так, NVIDIA предоставляет библиотеку Thrust со своими алгоритмами. Сортировка там, кстати, есть: docs.nvidia.com/cuda/thrust/#sorting