Реалізація паралельного алгоритму сортування за розрядами з використанням технології OpenCL

Abstract

Розглянуто розробку паралельного алгоритму сортування за розрядами. Проаналізовано основні підходи до побудови паралельних обчислень, архітектуру OpenCL та можливості бібліотеки PyOpenCL. Виконано математичне моделювання алгоритму, побудовано потоковий граф алгоритму, розроблено UML-діаграми структури програмного модуля, створено програмну реалізацію та проведено тестування ефективності паралельного сортування. Створений програмний модуль дозволяє суттєво пришвидшити сортування великих масивів даних завдяки обчислювальній потужності графічного процесора. Це рішення доцільно використовувати для оптимізації систем, що потребують швидкої обробки значних обсягів інформації.The development of a parallel radix sort algorithm is considered. The main approaches to constructing parallel computations, the OpenCL architecture, and the capabilities of the PyOpenCL library are analyzed. Mathematical modeling of the algorithm is performed, the algorithm's data flow graph is constructed, UML diagrams of the software module structure are developed, a software implementation is created, and the efficiency of parallel sorting is tested. The created software module allows for significantly accelerating the sorting of large data arrays due to the computational power of the graphics processor. This solution is advisable to use for optimizing systems that require rapid processing of significant volumes of information.