Привет, Хабр. Подумал, кому-нибудь пригодится параллельная сортировка с относительно простой реализацией и высокой производительностью на платформе CUDA. Таковой является сортировка методом пузырька. Под катом приведено объяснение и код, который может пригодиться (а может и нет… ). Сразу скажу, что представленная прога является бенчмарком по сравнению производительности на GPU и CPU. Если тебе не жалко, читатель, то скомпилируй ее, пожалуйста, и положи результаты расчета в комменты этой статьи. Это не для науки. Просто интересно =)
Суть метода сортировки пузырьком заключается в попарном сравнении элементов и замене их местами в случае выполнения определенного условия, зависящего от направления сортировки. Ниже показаны итерации алгоритма в однопоточном режиме, когда он сортирует возрастающий массив целых чисел по убыванию (каждая строчка — это состояние массива на данный момент) — это таблица 1.
В таблице 2 показаны итерации сортировки пузырьком в многопоточном режиме, который реализуется предельно просто: в то время, как один элемент перемещается в сторону, то через 2 перемещения следующий элемент уже тоже может быть отсортирован методом пузырька и начинает двигаться, а еще через 2 — еще один и т.д. Таким образом начинает «всплывать» весь массив, что существенно снижает время на расчет.
Уже по количеству затраченных действий можно видеть, что параллельная сортировка быстрее. Но это не всегда: при небольших размерах массивов однопоточный режим выполняется быстрее из-за отсутствия проблем с пересылкой данных. Я провел тут немного тестовых расчетов, и вот их результат:
Я привожу код реализации на языке CUDA С, который содержит код, выполняющий сортировку ПО УБЫВАНИЮ на CUDA и CPU (в однопоточном режиме). По сути, это бенчмарк для вашего компа того, как шустро работает сортировка на видеокарте и на проце. Частью этой проги является функция сортировки на видеокарте на платформе CUDA, которую вы можете использовать на здоровье в своих шедеврах элементарным copy'n'past. Код представ��ен ниже таблиц.
Ну, для этого необходимо скачать драйвера для CUDA с сайта Nvidia, установить их, скачать Nvidia Toolkit, установить и Nvidia SDK, тоже установить. К счастью, сейчас все идет уже в одном пакете. Как устанавливать CUDA напишу, если будет спрос, а так просто пожелаю удачи, если ты новичок.
Когда все готово и nvidia CUDA работает на твоем компе, то тогда достаточно лишь скомпилировать файл main.cu(или как там его назвал) и запустить прогу, получить результат и выложить его здесь.
Уот и все на сейчас, спасибо, что прочитал. До скорого.
P.S. Буду супер признателен, если подскажете, как ускорить алгоритм =)
Чуть-чуть напомню
Суть метода сортировки пузырьком заключается в попарном сравнении элементов и замене их местами в случае выполнения определенного условия, зависящего от направления сортировки. Ниже показаны итерации алгоритма в однопоточном режиме, когда он сортирует возрастающий массив целых чисел по убыванию (каждая строчка — это состояние массива на данный момент) — это таблица 1.
В таблице 2 показаны итерации сортировки пузырьком в многопоточном режиме, который реализуется предельно просто: в то время, как один элемент перемещается в сторону, то через 2 перемещения следующий элемент уже тоже может быть отсортирован методом пузырька и начинает двигаться, а еще через 2 — еще один и т.д. Таким образом начинает «всплывать» весь массив, что существенно снижает время на расчет.
Профит
Уже по количеству затраченных действий можно видеть, что параллельная сортировка быстрее. Но это не всегда: при небольших размерах массивов однопоточный режим выполняется быстрее из-за отсутствия проблем с пересылкой данных. Я провел тут немного тестовых расчетов, и вот их результат:
Ось абсцисс — кол-во элементов, ординат — время выполнения в сек.
Реализация
Я привожу код реализации на языке CUDA С, который содержит код, выполняющий сортировку ПО УБЫВАНИЮ на CUDA и CPU (в однопоточном режиме). По сути, это бенчмарк для вашего компа того, как шустро работает сортировка на видеокарте и на проце. Частью этой проги является функция сортировки на видеокарте на платформе CUDA, которую вы можете использовать на здоровье в своих шедеврах элементарным copy'n'past. Код представ��ен ниже таблиц.
Как это компилировать???
Ну, для этого необходимо скачать драйвера для CUDA с сайта Nvidia, установить их, скачать Nvidia Toolkit, установить и Nvidia SDK, тоже установить. К счастью, сейчас все идет уже в одном пакете. Как устанавливать CUDA напишу, если будет спрос, а так просто пожелаю удачи, если ты новичок.
Когда все готово и nvidia CUDA работает на твоем компе, то тогда достаточно лишь скомпилировать файл main.cu(или как там его назвал) и запустить прогу, получить результат и выложить его здесь.
Уот и все на сейчас, спасибо, что прочитал. До скорого.
P.S. Буду супер признателен, если подскажете, как ускорить алгоритм =)
Таблица 1: Сортировка пузырьком в однопоточном режиме
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 0 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 0 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 0 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 0 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 0 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 0 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 0 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 0 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 1 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 1 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 1 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 9 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 10 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 | 11 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 1 | 12 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 1 | 13 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 1 | 14 | 0 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | ||
| 3 | 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 2 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 2 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 2 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 2 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 2 | 10 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 2 | 11 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 2 | 12 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 2 | 13 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 2 | 14 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |||
| 4 | 3 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 3 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 3 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 3 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 3 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 3 | 11 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 3 | 12 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 3 | 13 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 3 | 14 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | 0 | ||
| 5 | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 4 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 4 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 4 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 4 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 4 | 12 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 4 | 13 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 4 | 14 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | 0 | ||
| 6 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 5 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 5 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 5 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 5 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 11 | 5 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 5 | 13 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 5 | 14 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | 0 | ||
| 7 | 6 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 6 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 6 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 6 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 11 | 6 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 11 | 12 | 6 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 6 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | 0 | ||
| 8 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 7 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 7 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 11 | 7 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 11 | 12 | 7 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 11 | 12 | 13 | 7 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 9 | 8 | 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 8 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 11 | 8 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 11 | 12 | 8 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 11 | 12 | 13 | 8 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 10 | 9 | 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 9 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 12 | 9 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 12 | 13 | 9 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 11 | 10 | 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 12 | 10 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 12 | 13 | 10 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 12 | 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 12 | 11 | 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 12 | 13 | 11 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 12 | 13 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 13 | 12 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 13 | 14 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | ||
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Таблица 2: Сортировка пузырьком в многопоточном режиме
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 0 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 1 | 3 | 0 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 1 | 4 | 0 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 2 | 4 | 1 | 5 | 0 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 4 | 2 | 5 | 1 | 6 | 0 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 3 | 5 | 2 | 6 | 1 | 7 | 0 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 5 | 3 | 6 | 2 | 7 | 1 | 8 | 0 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 4 | 6 | 3 | 7 | 2 | 8 | 1 | 9 | 0 | 10 | 11 | 12 | 13 | 14 |
| 5 | 6 | 4 | 7 | 3 | 8 | 2 | 9 | 1 | 10 | 0 | 11 | 12 | 13 | 14 |
| 6 | 5 | 7 | 4 | 8 | 3 | 9 | 2 | 10 | 1 | 11 | 0 | 12 | 13 | 14 |
| 6 | 7 | 5 | 8 | 4 | 9 | 3 | 10 | 2 | 11 | 1 | 12 | 0 | 13 | 14 |
| 7 | 6 | 8 | 5 | 9 | 4 | 10 | 3 | 11 | 2 | 12 | 1 | 13 | 0 | 14 |
| 7 | 8 | 6 | 9 | 5 | 10 | 4 | 11 | 3 | 12 | 2 | 13 | 1 | 14 | 0 |
| 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | 14 | 1 | 0 |
| 8 | 9 | 7 | 10 | 6 | 11 | 5 | 12 | 4 | 13 | 3 | 14 | 2 | 1 | 0 |
| 9 | 8 | 10 | 7 | 11 | 6 | 12 | 5 | 13 | 4 | 14 | 3 | 2 | 1 | 0 |
| 9 | 10 | 8 | 11 | 7 | 12 | 6 | 13 | 5 | 14 | 4 | 3 | 2 | 1 | 0 |
| 10 | 9 | 11 | 8 | 12 | 7 | 13 | 6 | 14 | 5 | 4 | 3 | 2 | 1 | 0 |
| 10 | 11 | 9 | 12 | 8 | 13 | 7 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 10 | 12 | 9 | 13 | 8 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 11 | 12 | 10 | 13 | 9 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 12 | 11 | 13 | 10 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 12 | 13 | 11 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 13 | 12 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 13 | 14 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Код:
#include <stdio.h> #include <time.h> __global__ void bubbleMove(int *array_device, int N, int step){ int idx = blockDim.x * blockIdx.x + threadIdx.x; if (idx<(N-1)) { if (step-2>=idx){ 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; } } } } void bubleSortCUDA(int *array_host,int N, int blockSize){ int *array_device; cudaMalloc((void **)&array_device, N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; cudaMemcpy(array_device,array_host,N*sizeof(int),cudaMemcpyHostToDevice); int nblocks = N / blockSize+1; for (int step = 0; step <= N+N; step++) { bubbleMove<<<nblocks,blockSize>>>(array_device,N,step); cudaThreadSynchronize(); } cudaMemcpy(array_host,array_device,N*sizeof(int),cudaMemcpyDeviceToHost); cudaFree(array_device); } void bubleSortCPU(int *array_host, int N){ for (int i = 0; i < N; i++){ for (int j = 0; j < N-i-1; j++) { if (array_host[j]<array_host[j+1]){ int buffer = array_host[j]; array_host[j]=array_host[j+1]; array_host[j+1] = buffer; } } } } int checkArray(int *array_host, int N){ int good=1; for (int i = 0; i < N-1; i++) if (array_host[i]<array_host[i+1]) {good=0; printf("i=%d a=%d\n", i,array_host[i] );} return good; } float measureCUDA(int N,int blockSize){ int *array_host = (int *)malloc(N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; clock_t start = clock(); bubleSortCUDA(array_host,N,blockSize); clock_t end = clock(); if (checkArray(array_host,N)==1){ free(array_host); return (float)(end - start) / CLOCKS_PER_SEC; } else { free(array_host); return -1; } } float measureCPU(int N) { int *array_host = (int *)malloc(N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; clock_t start = clock(); bubleSortCPU(array_host,N); clock_t end = clock(); if (checkArray(array_host,N)==1){ free(array_host); return (float)(end - start) / CLOCKS_PER_SEC; } else { free(array_host); return -1; } } int main(int argc, char const *argv[]) { for (int i = 1; i < 10000000; i*=2) printf("%d %f\t%f\n",i, measureCUDA(i,256),measureCPU (i )); return 0; }
