Реалізація паралельного алгоритму сортування Шелла за допомогою технології DIRECT COMPUTE

Abstract

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

This paper considers the development and software implementation of a parallel Shell sort algorithm using