КОНФЕРЕНЦІЇ ВНТУ електронні наукові видання, 
Молодь в науці: дослідження, проблеми, перспективи (МН-2026)

Розмір шрифта: 
РЕАЛІЗАЦІЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ СОРТУВАННЯ ШЕЛЛА ЗА ДОПОМОГОЮ ТЕХНОЛОГІЇ DIRECT COMPUTE
Валерій Олександрович Денисюк, Денис Романович Долішняк

Остання редакція: 2026-01-26

Анотація


У роботі розглянуто розробку та програмну реалізацію паралельного алгоритму сортування Шелла з використанням технології DirectCompute, що входить до складу API DirectX 11. Проведено аналіз існуючих алгоритмів сортування та підходів до їх паралельної реалізації, обґрунтовано вибір алгоритму Шелла як такого, що має природні передумови до ефективного розпаралелювання. Детально досліджено архітектурні особливості графічних процесорів та модель виконання обчислювальних шейдерів у DirectCompute. Розроблено програмну систему, що включає еталонну CPU-реалізацію та GPU-реалізацію з використанням compute shader, структурованих буферів і constant buffer. Проведено тестування коректності та продуктивності реалізованого алгоритму на різних розмірах вхідних даних і виконано порівняння результатів CPU та GPU. Отримані результати підтверджують доцільність застосування DirectCompute для прискорення операцій сортування великих масивів даних.


Ключові слова


алгоритм Шелла, паралельні обчислення, GPU, DirectX 11, DirectCompute, compute shader, сортування, високопродуктивні обчислення.

Посилання


1.Shell D. L. A High-Speed Sorting Procedure. Communications of the ACM. 1959. Vol. 2, No. 7. P. 30–32.

2.Knuth D. E. The Art of Computer Programming.  Volume 3:  Sorting and Searching.  2nd ed. Boston:  Addison-Wesley, 1998. 800 p.

3.Новотарський М. А. Алгоритми та методи обчислень. Київ: КПІ ім. Ігоря Сікорського, 2019. 407 с. URL: https://ela.kpi.ua/server/api/core/bitstreams/7421218e-d7dd-4e75-aa3e-bd7979db4e6d/content

4.Harris M. GPU Gems:  Programming Techniques, Tips, and Tricks for Real-Time Graphics. Boston:  Addison-Wesley, 2004. 800 p.

5.Microsoft. DirectCompute Overview. URL: https://learn.microsoft.com/en-us/windows/win32/direct3d11/direct3d-11-advanced-stages-compute-shader


Повний текст: PDF