ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ УСКОРЕНИЯ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ RADIX НА GPGPU
Работая с нашим сайтом, вы даете свое согласие на использование файлов cookie. Это необходимо для нормального функционирования сайта, показа целевой рекламы и анализа трафика. Статистика использования сайта отправляется в «Яндекс» и «Google»
Научный журнал Моделирование, оптимизация и информационные технологииThe scientific journal Modeling, Optimization and Information Technology
cетевое издание
issn 2310-6018

ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ УСКОРЕНИЯ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ RADIX НА GPGPU

Воронцов Г.В.   Преображенский А.П.   Чопоров О.Н.  

УДК 04.424.5.032.24
DOI:

  • Аннотация
  • Список литературы
  • Об авторах

В данной работе проводится анализ алгоритма параллельной сортировки RADIX на графических процессорах (GPGPU). Вначале рассматривается наивный алгоритм поразрядной сортировки. При этом используются два вида поразрядной сортировки — по младшим и старшим разрядам. Приведен пример их использования. С тем, чтобы увеличить производительность алгоритма поразрядной сортировки предлагается использовать параллельное решение, хотя при этом возникают дополнительные проблемы, требующие своего решения. Анализируются возможные подходы по распараллеливанию, предложенные различными авторами. В рассматриваемом алгоритме данные хранятся в памяти графического процессора, и сортировка выполняется непосредственно на GPU. Этот алгоритм параллельной Radix сортировки состоит из 3-х подсистем: подсчет двоичных комбинаций в текущем разряде, префикс суммирование, окончательное соответствие ключей с вычисленными позициями. Первым шагом алгоритма является процесс подсчета частоты каждого элемента в последовательности. Для осуществления этого параллельным образом происходит разделение входного массива на блоки. Далее вычисляется локальная частота всех возможных элементов для каждого блока. Затем для каждой маски проводится префиксное суммирование. На следующем шаге получаются из локальных списков частот глобальные. Приведены результаты моделирования, продемонстрировавшие увеличение в несколько раз быстродействие предлагаемого алгоритма по сравнению с известными.

1. Linh Ha Fast 4-way parallel radix sorting on GPUs / Ha Linh, Jens Kruger, Claudio T.Silva [электронный ресурс]: http://www.sci.utah.edu/~csilva/papers/cgf.pdf

2. Wikipedia, Radix Sort [электронный ресурс]: https://en.wikipedia.org/wiki/Radix_sort.

3. Batcher K.Sorting Networks and Their Applications / K. Batcher // Proceedings of the AFIPS Spring Joint Computing Conference, vol. 32, 1968, pp.307-314.

4. Ajtai M. An 0(n log n) sorting network / M.Ajtai, J.Komlós, E.Szemerédi //In: STOC ’83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983, pp. 1– 9.

5. Leighton T. Tight bounds on the complexity of parallel sorting / T.Leighton // In: STOC ’84: Proceedings of the sixteenth annual ACM symposium on Theory of computing (New York, NY, USA, 1984), ACM, pp. 71–80.

6. Zagha M. Radix sort for vector multiprocessors / M.Zagha, G. E.Blelloch // In: Supercomputing ’91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing (New York, NY, USA, 1991), pp. 712–721.

7. Kipfer P. UberFlow: a GPU-based particle engine / P.Kipfer, M.Segal, R.Westermann // In: HWWS ’04: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware (New York, NY, USA, 2004), ACM Press, pp. 115– 122.

8. Sintorn E. Fast parallel GPU-sorting using a hybrid algorithm / E.Sintorn, U.Assarsson //In: Workshop on General Purpose Processing on Graphics Processing Units (GPGPU) (2007). [электронный ресурс]: http://www.cse.chalmers.se/~uffe/hybridsort.pdf

9. Sengupta S. Scan primitives for GPU computing / S.Sengupta, M.Harris, Y.Zhang, J. D.Owens // In: Graphics Hardware 2007 (Aug. 2007), ACM, pp. 97–106.

10. Harris M., Sengupta S., Owens J. D. Parallel prefix sum (scan) with cuda / Harris M., Sengupta S., Owens J. D. // GPU Gems 3. Boston: Addison Wesley, 2007. 851–876.

11. Guy E. Blelloch Prefix Sums and Their Applications / Guy E. Blelloch // [электронный ресурс]: https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf.

Воронцов Глеб Владимирович

Воронежский институт высоких технологий

Воронеж, Российская Федерация

Преображенский Андрей Петрович
доктор технических наук
Email: app@vivt.ru

Воронежский институт высоких технологий

Воронеж, Российская Федерация

Чопоров Олег Николаевич
доктор технических наук профессор
Email: choporov_oleg@mail.ru

Воронежский институт высоких технологий
Воронежский государственный технический университет

Воронеж, Российская Федерация

Ключевые слова: параллельная сортировка, алгоритм, данные, процессор

Для цитирования: Воронцов Г.В. Преображенский А.П. Чопоров О.Н. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ УСКОРЕНИЯ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ RADIX НА GPGPU. Моделирование, оптимизация и информационные технологии. 2018;6(1). Доступно по: https://moit.vivt.ru/wp-content/uploads/2018/01/VoronzovSoavtori_1_1_18.pdf DOI:

529

Полный текст статьи в PDF