Сравнение ускорения параллельной версии алгоритма битонной сортировки на архитектуре CUDA и стандарте MPI

Алгоритм битонной сортировки был разработан американским информатиком Кеннетом Батчером в 1968 году и предназначен для параллельной сортировки данных [1]. Алгоритм основан на сортировке битонных последовательностях. Битонной последовательностью называют последовательность, которая сначала не монотонно убывает, а затем монотонно не возрастает.

Худшее, среднее и лучшее время сортировки данным алгоритмом составляет O(log(n)2).

В настоящее время рост производительности центральных процессоров основан за счёт увеличения ядер на одном процессоре, так как увеличение частоты приводит к большим энергозатратам и увеличению тепловыделения, а в связи с этим будет требоваться больше охлаждения, чтобы не допустить, перегрев процессора. Однако для вычислений общего назначения кроме центральных процессоров используются и графические процессоры.

Для определения наилучшего варианта параллельной версии алгоритма битонной сортировки, были написаны две программы.

Первая программа написана с использованием стандарта MPI и выполняется исключительно на центральном процессоре [3]. Данные считываются с текстового файла. Результатом работы программы был отсортированный массив целых чисел, записанный в файл.

Вторая программа была разработана для выполнения на архитектуре CUDA и запускалась на центральном процессоре [2]. В ходе выполнения, задача сортировки полностью передаётся на графический процессор. После выполнения сортировки графическим процессором, отсортированный массив целых чисел копировался с оперативной памяти графической карты, в оперативную память, установленную на материнской плате. Затем отсортированный массив записывался в текстовый файл.

Все опыты проводились на машине со следующими параметрами:

• •    CPU — AMD FX-8350 с 8-ью ядрами до 4.2 ГГц

• •    ОЗУ — 16GB

• •    GPU — GeForce GTX 760 2GB

• •    ОС: Ubuntu 17.04 x64 разрядная

  Для опытов был создан текстовый файл с 8388608 строк, по одному целому числу на каждую строку. Программы написаны на языке С++11 [4].

Программа, написанная со стандартом MPI, была запущена 8 раз с разным количеством создаваемых процессов. Результат опытов приведен в таблице 1.

Таблица 1. Результат работы программы на стандарте MPI.

Программа, разработанная для архитектуры CUDA, запускалась также 8 раз, но без изменения параметров создаваемых нитей, так как алгоритм был написан с расчётом на то, что каждая нить графического процессора будет обрабатывать свою часть сортировки. Результат опытов приведен в таблице 2.

Таблица 2. Результат работы программы на архитектуре CUDA.

Результаты опытов показывают нам, что реализация алгоритма битонной сортировки написанная на технологии CUDA и исполняемая на графическом процессоре, выполняется в 77 раз быстрее, чем реализация алгоритма на стандарте MPI.

На основе полученных результатов мы можем сделать вывод, что сортировка большого объёма данных алгоритмом битонной сортировки, целесообразно проводить на графических процессорах, нежели на центральных процессорах.