Гібридна реалізація алгоритму сортування за розрядами з використанням DirectCompute

Abstract

У роботі розглянуто розробку гібридного алгоритму сортування за розрядами (Radix Sort), у якому обчислення часткових операцій виконуються на графічному процесорі (GPU) засобами DirectCompute, а завершальний стабільний етап формування відсортованого масиву виконується центральним процесором (CPU). Проаналізовано існуючі сортувальні алгоритми, визначено їх переваги й недоліки у контексті паралельних обчислень, обґрунтовано вибір Radix Sort як базового методу через його природну декомпозицію на незалежні підзадачі. Розроблено структуру програмного модуля, створено класи і програмну логіку взаємодії CPU–GPU, побудовано програмну реалізацію на основі DirectCompute та проведено тестування продуктивності на різних обсягах вхідних даних. Показано, що гібридний підхід забезпечує коректність сортування й здатний покращувати продуктивність для великих масивів, водночас демонструючи характерні ефекти амортизації накладних витрат при зростанні розміру масиву.

The paper addresses the development of a hybrid radix sort algorithm in which partial operations are performed on a graphics processing unit (GPU) using DirectCompute, while the final stable redistribution is carried out on the central processing unit (CPU). Existing sorting methods are analyzed, their applicability to parallel processing is discussed, and Radix Sort is justified as a suitable algorithm due to its natural decomposition properties. A software module structure was developed, CPU–GPU interaction was implemented using DirectCompute, and performance testing was conducted on input arrays of various sizes. The results demonstrate that the hybrid approach provides correct sorting and may improve performance on large datasets, while also showing amortization effects of GPU-related overhead as data size increases.