bsuirДоклады БГУИРDoklady BGUIR1729-76482708-0382БГУИРbsuir-669Research ArticleСтатьиПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА МАКСИМУМА ЦЕЛЕВОЙ ФУНКЦИИ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ ТЕХНОЛОГИИ CUDAPARALLEL ALGORITHM SEARCHING OF THE OBJECTIVE FUNCTION MAXIMUM BY DYNAMIC PROGRAMMING METHOD USING CUDA TECHNOLOGYСерединЭ. Н.SeredinE. N.noemail@neicon.ruОбъединенный институт проблем информатикиBelarus201603062019045460Copyright © Середин Э.Н., 20192019Середин Э.Н.Seredin E.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.bsuir.by/jour/article/view/669

Предлагается параллельный алгоритм поиска максимума целевой функции с помощью технологии программирования видеокарт CUDA на основе модифицированного метода динамического программирования. Описываются основные особенности алгоритма, позволившие сократить на несколько порядков количество требуемых вычислений и объем используемой памяти. Приводятся оценки быстродействия версий алгоритма для выполнения на процессоре и видеокарте.

Parallel algorithm searching the maximum of the objective function using CUDA technology based on the modified method of dynamic programming is presented. Describes the features of parallel software implementations of the algorithm, which allows to reduce by several orders of magnitude the number of required calculations and memory usage. The results of performance software implementations of the algorithm are shown for modern processors and video cards.

параллельный алгоритммаксимум целевой функцииметод динамического программированиятехнология программирования видеокарт CUDAparallel algorithmthe maximum of the objective functiondynamic programming methodCUDAReferencesРастригин Л.А. Статистические методы поиска. М., 1968.Растригин Л.А. Статистические методы поиска. М., 1968.Дорогов В.Г., Теплова Я.О. Введение в методы и алгоритмы принятия решений. М., 2012.Дорогов В.Г., Теплова Я.О. Введение в методы и алгоритмы принятия решений. М., 2012.Гилл Ф. Мюррей У., Райт М. Практическая оптимизация. М., 1985.Гилл Ф. Мюррей У., Райт М. Практическая оптимизация. М., 1985.Середин Э.Н., Залесский Б.А. // Информатика. 2014. № 4. С. 66-73.Середин Э.Н., Залесский Б.А. // Информатика. 2014. № 4. С. 66-73.Zalesky B.A., Seredin E.N. // Proc. of 12th Intern. Conf. PRIP 2014. Minsk, 2014. P. 329-334.Zalesky B.A., Seredin E.N. // Proc. of 12th Intern. Conf. PRIP 2014. Minsk, 2014. P. 329-334.Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М., 2010.Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М., 2010.Сандерс Дж. Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. М., 2011.Сандерс Дж. Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. М., 2011.CUDA Toolkit Documentation. [Электронный ресурс]. - Режим доступа: http://docs.nvidia.com/cuda/index.html. - Дата доступа: 28.01.2016.CUDA Toolkit Documentation. [Электронный ресурс]. - Режим доступа: http://docs.nvidia.com/cuda/index.html. - Дата доступа: 28.01.2016.OpenMP. [Электронный ресурс]. - Режим доступа: http://openmp.org. - Дата доступа: 28.01.2016.OpenMP. [Электронный ресурс]. - Режим доступа: http://openmp.org. - Дата доступа: 28.01.2016.Parallelization Using OpenMP. [Электронный ресурс]. - Режим доступа: https://software.intel.com/en-us/articles/parallelization-using-openmp. - Дата доступа: 28.01.2016.Parallelization Using OpenMP. [Электронный ресурс]. - Режим доступа: https://software.intel.com/en-us/articles/parallelization-using-openmp. - Дата доступа: 28.01.2016.

The authors declare that there are no conflicts of interest present.