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

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

Authors

  • K.A. Barkalov
  • I.G. Lebedev
  • V.V. Sovrasov
  • A.V. Sysoyev

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.

New computational technologies

Downloads

Published

2016-03-22

Issue

Vol. 17 (2016): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

K.A. Barkalov

Lobachevsky State University of Nizhni Novgorod
• Associate Professor

I.G. Lebedev

Lobachevsky State University of Nizhni Novgorod
• Programmer

V.V. Sovrasov

Lobachevsky State University of Nizhni Novgorod
• Junior Researcher

A.V. Sysoyev

Lobachevsky State University of Nizhni Novgorod
• Senior Lecturer

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