Реализация параллельного алгоритма поиска глобального экстремума функции на Intel Xeon Phi

Авторы

  • К.А. Баркалов Нижегородский государственный университет им Н.И. Лобачевского https://orcid.org/0000-0001-5273-2471
  • И.Г. Лебедев Нижегородский государственный университет им Н.И. Лобачевского
  • В.В. Соврасов Нижегородский государственный университет им Н.И. Лобачевского https://orcid.org/0000-0001-6525-2602
  • А.В. Сысоев Нижегородский государственный университет им Н.И. Лобачевского https://orcid.org/0000-0003-1542-7624

DOI:

https://doi.org/10.26089/NumMet.v17r110

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

глобальная оптимизация, многоэкстремальные функции, редукция размерности, параллельные алгоритмы, Intel Xeon Phi

Аннотация

Предложен параллельный алгоритм решения задач многоэкстремальной оптимизации. Описывается реализация алгоритма на современных вычислительных системах с использованием сопроцессора Xeon Phi. Обсуждаются два подхода к распараллеливанию алгоритма, учитывающие информацию о трудоемкости вычисления значений оптимизируемой функции. Приводятся результаты вычислительных экспериментов, полученные на суперкомпьютере «Лобачевский». Показано, что реализация для Xeon Phi опережает версию для CPU. Результаты подтверждают ускорение алгоритма с использованием Xeon Phi по сравнению с алгоритмом, реализованным только на CPU.

Авторы

К.А. Баркалов

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• доцент

И.Г. Лебедев

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• программист

В.В. Соврасов

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• младший научный сотрудник

А.В. Сысоев

Нижегородский государственный университет им Н.И. Лобачевского
пр.Гагарина, 23, 603950, Нижний Новгород
• старший преподаватель

Библиографические ссылки

  1. Yu. G. Evtushenko, Methods for Solving Extreme Problems and Their Application in Optimization Systems (Nauka, Moscow, 1982) [in Russian].
  2. J. D. Pintér, Global Optimization in Action. Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications (Kluwer, Dordrecht, 1996).
  3. Ya. D. Sergeyev and D. E. Kvasov, Diagonal Global Optimization Methods (Fizmatlit, Moscow, 2008) [in Russian].
  4. R. G. Strongin and Ya. D. Sergeyev, Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms (Kluwer, Dordrecht, 2000).
  5. R G. Strongin, V. P. Gergel’, V. A. Grishagin, and K. A. Barkalov, Parallel Computing in Global Optimization Problems (Mosk. Gos. Univ., Moscow, 2013) [in Russian].
  6. Ya. D. Sergeyev and D. E. Kvasov, “Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants,” SIAM J. Optim. 16 (3), 910-937 (2006).
  7. J. Žilinskas, “Branch and Bound with Simplicial Partitions for Global Optimization,” Math. Model. Anal. 13 (1), 145-159 (2008).
  8. S. Yu. Gorodetsky and V. A. Grishagin, Nonlinear Programming and Multiextremal Optimization (Nizhni Novgorod Univ., Nizhni Novgorod, 2007) [in Russian].
  9. A. V. Sysoev, K. A. Barkalov, V. P. Gergel, and I. G. Lebedev, “MPI Implementation of Dimension Reduction Multilevel Scheme for Parallel Solving the Global Optimization Problems,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 28-29, 2015 (Mosk. Gos. Univ., Moscow, 2013), pp. 411-419.
  10. M. Gaviano, D. E. Kvasov, D. Lera, and Ya. D. Sergeyev, “Algorithm 829: Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization,” ACM Trans. Math. Softw. 29 (4), 469-480 (2003).
  11. D. R. Jones, C. D. Perttunen, and B. E. Stuckman, “Lipschitzian Optimization without the Lipschitz Constant,” J. Optim. Theory Appl. 79 (1), 157-181 (1993).
  12. J. M. Gablonsky and C. T. Kelley, “A Locally-Biased Form of the DIRECT Algorithm,” J. Global Optim. 21 (1), 27-37 (2001).

Загрузки

Опубликован

22-03-2016

Как цитировать

Баркалов К., Лебедев И., Соврасов В., Сысоев А. Реализация параллельного алгоритма поиска глобального экстремума функции на Intel Xeon Phi // Вычислительные методы и программирование. 2016. 17. 101-110. doi 10.26089/NumMet.v17r110

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения