ПАРАЛЛЕЛЬНЫЙ ПОДХОД К РЕШЕНИЮ ПРОБЛЕМ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ ЛИПШИЦА С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ CUDA

Tian Bo


Аннотация


Рассматривается задача одномерной оптимизации Липшица. Для ее решения предлагается новая статическая стратегия распределения вычислительной нагрузки между варпами в программной платформе CUDA для параллельного метода ветвей и границ на основе оценок алгоритмической сложности подзадач, возникающих в процессе решения. Предлагаемая стратегия может быть использована в структуре CPU-GPU для избежания низкой связности между CPU и GPU. Предлагаемый в данной работе распределенных алгоритм содержит три следующих друг за другом этапа. В ходе первого этапа CPU выполняет заданное число шагов, прибегая к иерархическому разбиению пространства X. CPU генерирует набор подинтервалов. Потом подинтервалы упаковываются в расчетные блоки, которые отправляются GPU (один расчетный блок – одному потоку). В ходе второго этапа GPU решает подинтервалы из полученных расчетных блоков до конца. Третий этап начинается, когда все потоки закончили свою работу. Полученные результаты со всех потоков собираются на CPU, после чего лучший результат сообщается пользователю. Экспериментальные результаты показали преимущество предлагаемой стратегии по сравнению с другими рассмотренными стратегиями.

Ключевые слова


CUDA; Одномерная оптимизация Липшица; метод ветвей и границ

Литература


Бо Тянь, М.А. Посыпкин, И.Х. Сигал «Балансировка нагрузки на основе оценок алгоритмической сложности подзадач» // Информационные технологии и вычислительные системы, № 1, с. 10–18, 2015.

Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Ж. вычисл. матем. и матем. физ. 1971. Т. 11. № 6.

Картак В.М., Рипатти А.В., “Параллельный подход к решению задачи одномерной продолженной упаковки (1cbpp) с использованием технологии cuda”, Вестник башкирского университета, 18:1 (2013), 11–14.

John D. Owens, David Luebke, Naga Govindaraju, Mark Harris, Jens Krüger, Aaron E. Lefohn, and Tim Purcell: A Survey of General-Purpose Computation on Graphics Hardware, Computer Graphics Forum, 26(1):80–113, March 2007.

Evtushenko Y G, Malkova V U, Stanevichyus A A. Parallelization of the global extremum searching process[J]. Automation and Remote Control, 2007, 68(5): 787-798.

Evtushenko Y, Posypkin M, Sigal I. A framework for parallel large-scale global optimization[J]. Computer Science-Research and Development, 2009, 23(3-4): 211-215.

Lalami M E, El-Baz D. GPU implementation of the branch and bound method for knapsack problems[C]//Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International. IEEE, 2012: 1769-1777.

Munos, Rémi. “Optimistic optimization of deterministic functions without the knowledge of its smoothness.” Advances in neural information processing systems. 2011.

Sergeyev Y D. A one-dimensional deterministic global minimization algorithm[J]. Computational mathematics and mathematical physics, 1995, 35(5): 553-562.




DOI: https://doi.org/10.12731/wsd-2015-6.1-580-591

Ссылки

  • На текущий момент ссылки отсутствуют.


Bookmark and Share


(c) 2016 В мире научных открытий



ISSN 2658-6649 (print)

ISSN 2658-6657 (online)

HotLog Яндекс цитирования