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