Остання редакція: 2026-01-28
Анотація
Розглянуто розробку та програмну реалізацію паралельного алгоритму швидкого сортування з використанням технології CUDA. Проаналізовано існуючі методи сортування з точки зору досягнення високої обчислювальної продуктивності та обґрунтовано вибір інструментів і підходів для створення програмного модуля. Розроблено структуру програмного забезпечення, зокрема діаграми класів, а також визначено доцільне програмне середовище реалізації. У роботі реалізовано паралельний алгоритм із використанням бібліотеки PyTorch та технології CUDA і проведено експериментальне дослідження його продуктивності на наборах даних різного обсягу. Отримані результати підтверджують можливість суттєвого підвищення швидкодії та ефективності програмних систем, що здійснюють обробку великих масивів даних.
Ключові слова
Посилання
1.Кнут Д. Е. Мистецтво програмування, том 3: Сортування та пошук. 2-е видання. Вільямс, 2000. 824 с.
2.Новотарський М. А. Алгоритми та методи обчислень. Київ: КПІ ім. Ігоря Сікорського, 2019. 407 с.
3.Седжвік Р. Алгоритми на C++. Аналіз, структури даних, сортування, пошук. Діасофт, 2001. 496 с.
4.Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, Third Edition. MIT Press, 2009. 1312 p.
5.Kirk D. B., Hwu W. W. Programming Massively Parallel Processors: A Hands-on Approach, Third Edition. Morgan Kaufmann, 2016. 560 p.
6.Sanders J., Kandrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional, 2010. 312 p.
7.Мінайленко Р. М. Паралельні та розподілені обчислення: Навчальний посібник. Кропивницький: Видавець Лисенко В. Ф., 2021. 153 с.
8.Satish N., Harris M., Garland M. Designing Efficient Sorting Algorithms for Manycore GPUs // IEEE International Symposium on Parallel & Distributed Processing. 2009. DOI: 10.1109/IPDPS.2009.5161005
9.Cederman D., Tsigas P. GPU-Quicksort: A practical Quicksort algorithm for graphics processors // Journal of Experimental Algorithmics. 2010. Vol. 14. Article 1.4.
10.Paszke A., Gross S., Massa F., et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library // Advances in Neural Information Processing Systems. 2019. Vol. 32.
11.PyTorch documentation — PyTorch 2.9 documentation [Електронний ресурс] Режим доступу: https://pytorch.org/docs/stable/index.html
12.NVIDIA CUDA C Programming Guide [Електронний ресурс] Режим доступу: https://docs.nvidia.com/cuda/cuda-c- programming-guide/
13.CUDA Toolkit Documentation 12.8 [Електронний ресурс] Режим доступу: https://docs.nvidia.com/cuda/archive/12.8.0/
14.PyTorch CUDA Semantics [Електронний ресурс] Режим доступу: https://pytorch.org/docs/stable/notes/cuda.html