TY - JOUR AU - Попов, Михаил Владимирович AU - Посыпкин, Михаил Анатольевич PY - 2018/06/30 TI - ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ ТОЧНЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА ГРАФИЧЕСКИХ УСКОРИТЕЛЯХ JF - Современные информационные технологии и ИТ-образование; Том 14 № 2 (2018): Современные информационные технологии и ИТ-образованиеDO - 10.25559/SITITO.14.201802.408-418 KW - N2 - Большинство задач дискретной оптимизации относятся к классу NP-полных задач. Это означает, что алгоритмы, позволяющие найти их точное решение, вообще говоря могут работать с экспоненциальной сложностью относительно длины входных данных. Благодаря прогрессу, сегодня появились технологии, которые пока еще не достаточно широко использовались для реализации методов прикладной оптимизации. К числу таких технологий можно отнести GP GPU (General Purposed Graphical Processing Unit) . Применение данной технологии к хорошо известным алгоритмам может помочь добиться большей эффективности работы. Цель данной работы – исследование возможностей применения параллельных вычислений на видеокартах для решения задач дискретной оптимизации. В качестве целевой задачи выбрана задача об одномерном булевом ранце. Для решения задачи рассмотрены методы получения точного решения – алгоритм полного перебора, являющийся начальной точкой в исследовании, и метод «ветвей и границ», позволяющему сократить перебор благодаря отсеву заведомо неподходящих решений. Рассмотренные алгоритмы оценены с точки зрения количества операций и времени выполнения, реализованы в однопоточной конфигурации центрального процессора, после чего распараллелены на видеокарте. По результатам реализации данных методов, был создан комбинированный алгоритм, объединяющий в себе оба алгоритма для достижения большей эффективности. Для распараллеливания вычислений на графической карте, выбрана технология CUDA. Алгоритмы реализованы на языке С. После реализации алгоритмов, проведено тестирование на различных наборах данных и разных конфигурациях целевой платформы. Представлены результаты экспериментальных исследований, исследовано ускорение работы при использовании параллельных вычислений и проведён сравнительный анализ эффективности работы алгоритмов. UR - http://sitito.cs.msu.ru/index.php/SITITO/article/view/380