Эффективная реализация точных алгоритмов решения задач дискретной оптимизации на графических ускорителях
Authors: ПОПОВ М В. , ПОСЫПКИН М А. 
Published: January 2025

Большинство задач дискретной оптимизации относятся к классу NP-полных задач. Это означает, что алгоритмы, позволяющие найти их точное решение, вообще говоря могут работать с экспоненциальной сложностью относительно длины входных данных. Благодаря прогрессу, сегодня появились технологии, которые пока еще не достаточно широко использовались для реализации методов прикладной оптимизации. К числу таких технологий можно отнести GP GPU (General Purposed Graphical Processing Unit) . Применение данной технологии к хорошо известным алгоритмам может помочь добиться большей эффективности работы. Цель данной работы – исследование возможностей применения параллельных вычислений на видеокартах для решения задач дискретной оптимизации. В качестве целевой задачи выбрана задача об одномерном булевом ранце. Для решения задачи рассмотрены методы получения точного решения – алгоритм полного перебора, являющийся начальной точкой в исследовании, и метод «ветвей и границ», позволяющему сократить перебор благодаря отсеву заведомо неподходящих решений. Рассмотренные алгоритмы оценены с точки зрения количества операций и времени выполнения, реализованы в однопоточной конфигурации центрального процессора, после чего распараллелены на видеокарте. По результатам реализации данных методов, был создан комбинированный алгоритм, объединяющий в себе оба алгоритма для достижения большей эффективности. Для распараллеливания вычислений на графической карте, выбрана технология CUDA. Алгоритмы реализованы на языке С. После реализации алгоритмов, проведено тестирование на различных наборах данных и разных конфигурациях целевой платформы. Представлены результаты экспериментальных исследований, исследовано ускорение работы при использовании параллельных вычислений и проведён сравнительный анализ эффективности работы алгоритмов.

Most of the problems of discrete optimization belong to the class of NP-complete problems. This means that algorithms that can find their exact solution, in general, can work with exponential complexity relative to the length of the input data. Thanks to progress, today there are technologies that have not yet been widely used to implement applied optimization methods. Among these technologies is GP GPU (General Purposed Graphical Processing Unit). The application of this technology to well-known algorithms can help to achieve greater efficiency. The purpose of this paper is to investigate the possibilities of using parallel computations on video cards to solve discrete optimization problems. The problem of a one-dimensional Boolean knapsack was chosen as the target problem. To solve the problem, methods for obtaining an exact solution are considered - the full search algorithm, which is the starting point in the study, and the "branches and boundaries" method, which allows to reduce the search by eliminating obviously inappropriate solutions. The algorithms considered are estimated in terms of the number of operations and execution time, implemented in a single-threaded configuration of the central processor, and then parallelized on a video card. Based on the results of these methods, a combined algorithm was created that combines both algorithms to achieve greater efficiency. For parallelizing the calculations on the graphics card, the CUDA technology is chosen. Algorithms are implemented in C. After the implementation of the algorithms, testing was carried out on various data sets and different configurations of the target platform. The results of experimental studies are presented, the acceleration of work is investigated with the use of parallel computations and a comparative analysis of the efficiency of the algorithms is carried out.