https://doi.org/10.26089/NumMet.v27r321

Выбор наиболее производительного алгоритма сортировки структур данных малого размера по целочисленному полю

Авторы

  • А. А. Галюзов

Ключевые слова:

параллельные вычисления
поразрядная сортировка
сортировка подсчетом
OpenMP
CUDA
CUDA Thrust
CUDA CUB
CPU
GPU

Аннотация

Рассматривается задача многократной сортировки массива переносимых частиц по целочисленному полю, задающему тип физического взаимодействия. Сравниваются 16 реализаций сортировки массива из 2·107 структур на центральных процессорах и графическом ускорителе. Под оптимальным понимается алгоритм с наименьшим средним временем выполнения на фиксированных входных данных и выбранной вычислительной платформе; при близких средних значениях времени выполнения дополнительным преимуществом считается меньший объем вспомогательной памяти. Для всех алгоритмов использовался один и тот же входной массив, в котором целочисленный ключ сортировки принимал случайные значения из множества {−1, 0, 1, 2, 3}. Для GPU сравнивалось только on-device время сортировки, измеренное при помощи CUDA events; выделение памяти, переносы данных между host и device, warm-up и прочие накладные расходы среды выполнения в интервал измерения не включались. Показано, что для рассматриваемой задачи алгоритмы сортировок, основанные на сравнениях, и методы сортировки целочисленных ключей принципиально различаются: из-за малого числа возможных значений ключа сортировки специализированные методы, такие как сортировка подсчетом и поразрядная сортировка, оказываются существенно эффективнее универсальных алгоритмов сравнения. На центральных процессорах лучшие результаты показали специализированный авторский алгоритм TPT3 и схемы с параллельной сортировкой подмассивов, а на GPU NVIDIA Tesla V100 лидером стала DeviceRadixSort из библиотеки CUDA CUB. Полученные выводы относятся к рассматриваемым структуре переносимой частицы и диапазону ключа, on-device сценарию выполнения на GPU, а также вычислительным системам с общей оперативной памятью.


Загрузки

Опубликован

2026-07-01

Выпуск

Том 27 (2026): Выпуск 3.

Раздел

Методы и алгоритмы вычислительной математики и их приложения

Автор

А. А. Галюзов

Всероссийский научно-исследовательский институт автоматики им. Н.Л. Духова

• старший научный сотрудник

Библиографические ссылки

  1. R. M. Bergmann and J. L. Vuji’c, “Algorithmic Choices in WARP – A Framework for Continuous Energy Monte Carlo Neutron Transport in General 3D Geometries on GPUs,” Annals of Nuclear Energy 77, 176–193 (2015).
    doi 10.1016/j.anucene.2014.10.039
  2. C. Liu, “Study on the Particle Sorting Performance for Reactor Monte Carlo Neutron Transport on Apple Unified Memory GPUs,” EPJ Web of Conferences 302, Article Number 04001 (2024).
    doi 10.1051/epjconf/202430204001
  3. J. Tramm, P. Romano, P. Shriwise, et al., “Performance Portable Monte Carlo Particle Transport on Intel, NVIDIA, and AMD GPUs,” EPJ Web of Conferences 302, Article Number 04010 (2024).
    doi 10.1051/epjconf/202430204010
  4. M. S. Egorova, S. A. Dyachkov, A. N. Parshikov, and V. V. Zhakhovsky, “Parallel SPH modeling using dynamic domain decomposition and load balancing displacement of Voronoi subdomains,” Comp. Phys. Comm. 234, 112–125 (2019).
    doi 10.1016/j.cpc.2018.07.019
  5. V. A. Vshivkov, T. V. Markelova, and V. I. Shelehov, “On Sorting Algorithms in the Particle-in-Cell Method,” Nauch. Vestnik NGTU. 33 (4), 79–92 (2008).
    https://cyberleninka.ru/article/n/ob-algoritmah-sortirovki-v-metode-chastits-v-yacheykah Cited June 7, 2026.
  6. A. A. Romanenko and A. V. Snytnikov, “Optimization of Model Reordering Optimization for GPU Implementation of Particle-in-Cell Method,” Vestnik NGU. Ser.: Informat. Technol. 17 (1), 82–89 (2019).
    doi 10.25205/1818-7900-2019-17-1-82-89
  7. N. V. Snytkov, O. P. Stoyanovskaya, and T. A. Glushko, “Parallel Algorithm for Supercomputing Simulation of Dust-Gaseous Gravitating Systems Using Particle-in-Cell and SPH Methods,” Journal of Physics: Conference Series 1336 (1), Article Number 012021 (2019).
    doi 10.1088/1742-6596/1336/1/012021
  8. S. Agostinelli, J. Allison, K. Amako, et al., “Geant4 – A simulation toolkit,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 506 (3), 250–303 (2003).
    doi 10.1016/S0168-9002(03)01368-8
  9. J. Allison, K. Amako, J. Apostolakis, et al., “Geant4 Developments and Applications,” IEEE Transactions on Nuclear Science 53 (1), 270–278 (2006).
    doi 10.1109/TNS.2006.869826
  10. A. A. Galyuzov and M. V. Kosov, “Increasing Performance of the Radiation Transport Simulation: TPT3 Parallel Program,” Software & Systems 38 (2), 269–279 (2025).
    doi 10.15827/0236-235X.150.269-279
  11. A. A. Galyuzov and M. V. Kosov, The TPT3 program for high-performance simulation of radiation transfer, Certificate of RF Registration of Computer Program №. 2024614877. Date of Registration: 29.02.2024.
  12. OpenMP Preprocessor Directive Standard.
    https://www.openmp.org.
  13. NVIDIA CUDA Toolkit.
    https://developer.nvidia.com/cuda/toolkit Cited June 7, 2026.
  14. OpenACC Preprocessor Directive Standard.
    https://www.openacc.org Cited June 7, 2026.
  15. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd ed.(Addison-Wesley, Boston, 1998).
  16. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. 3rd ed.(MIT Press, Cambridge, 2009).
  17. S. J. Ross, “The Spreadsort High-Performance General-Case Sorting Algorithm,” Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications 3, 1100–1106 (2002).
  18. N. Satish, M. Harris, and M. Garland, “Designing efficient sorting algorithms for manycore GPUs,” in 2009 IEEE International Symposium on Parallel & Distributed Processing, Italy, Rome, May 23–29, 2009(IEEE Press, 2009), pp. 1–10.
    doi 10.1109/IPDPS.2009.5161005
  19. D. R. Musser, “Introspective Sorting and Selection Algorithms,” Software: Practice and Experience 27 (8), 983–993 (1997).
  20. A. A. Galyuzov and M. V. Kosov, “Calculation of the Gamma Quanta Yield for the ^(235)U Fission in the Uranium Cube by the TPT3 Program,” Technol. EMC. 89 (2), 26–32 (2024).
  21. The repository with the source code for the examples from the article.
    https://github.com/Agar92/benchmarksortingalgorithms.git Cited June 7, 2026.
  22. Boost.Sort Documentation.
    https://www.boost.org/libs/sort/ Cited June 7, 2026.
  23. The repository with the source code for the CUDA CUB library.
    https://github.com/NVIDIA/cub.git Cited June 7, 2026.

Лицензия

Copyright (c) 2026 А. А. Галюзов

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.