Implementation of a parallel algorithm for searching the global extremum of a function on Intel Xeon Phi

Authors

DOI:

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

Keywords:

global optimization, multiextremal functions, dimension reduction, parallel computing, Intel Xeon Phi

Abstract

A parallel algorithm for solving multiextremal optimization problems is proposed. An implementation of the algorithm on modern computing systems using Intel Xeon Phi coprocessors is examined. Two approaches to algorithm parallelization are discussed with consideration of the available information on the computational cost for computing a given objective function. A number of numerical results obtained on a Lobachevsky supercomputer are analyzed. It is shown that the implementation of the algorithm using Xeon Phi is more efficient than that using CPU only. Computational experiments confirm this conclusion.

Author Biographies

K.A. Barkalov

I.G. Lebedev

V.V. Sovrasov

A.V. Sysoyev

References

  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).

Published

22-03-2016

How to Cite

Баркалов К., Лебедев И., Соврасов В., Сысоев А. Implementation of a Parallel Algorithm for Searching the Global Extremum of a Function on Intel Xeon Phi // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2016. 17. 101-110. doi 10.26089/NumMet.v17r110

Issue

Section

Section 1. Numerical methods and applications