K-frontal method of nonuniform coverings

А.Y. Gorchakov


This paper proposes a parallel implementation of the method of non-uniform coverings, designed for computing systems with shared memory. The method of non-uniform coverings is one of the most well-known deterministic methods for solving global optimization problems, based on the scheme of branches and boundaries. Due to the high computational complexity of the method and the wide availability of high-performance multi-core systems with shared memory, the development of parallel implementations of this method is of particular relevance. There are various approaches to parallelizing the method of non-uniform coverings. First, there are several standards for creating multi-threaded applications such as OpenMP, MPI, C ++ 17 functionality. Secondly, there are different approaches to the organization of storage and access to lists of subtasks and synchronization between threads. Thirdly, the branching procedures and evaluation estimates differ. Earlier, a comparison was made of the indicated approaches to the parallelization of the method of non-uniform coverings. One of the most effective methods is the frontal method of non-uniform coverings, it uses a branching strategy wide, OpenMP technology is used for parallelization, and the data storage structure consists of two arrays of pools / subtasks. This approach has the following advantages - ease of implementation, sufficient speed and stability. As disadvantages of the method, you can specify the high requirements for RAM. To eliminate this drawback, this article proposes a parallel implementation of the K-frontal method of non-uniform coverings. The method was tested using a library of test functions on a hybrid high-performance computing cluster of FRC CS RAS.

Full Text:

PDF (Russian)


Yevtushenko Y. G. Chislennyy metod poiska global'nogo ekstremuma funktsiy (perebor na neravnomernoy setke) //Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki, 1971, vol. 6. – pp.1390-1403.

Hansen E., Walster G. W. Global optimization using interval analysis: revised and expanded. – CRC Press, 2003.

Hickernell F. J., Yuan Y. A simple multistart algorithm for global optimization. – 1997.

Martí R., Moreno-Vega J. M., Duarte A. Advanced multi-start methods //Handbook of metaheuristics. – Springer, Boston, MA, 2010. – С. 265-281.

Martí R. et al. Multi-start methods //Handbook of Heuristics. – 2016. – С. 1-21.

Pagès G. The Quasi-Monte Carlo Method //Numerical Probability. – Springer, Cham, 2018. – С. 95-132.

S. Kirkpatrick, C.D. Gelatt, Jr., and M.P. Vecchi, Optimization by simulated annealing, Science 220 (4598), 671-680 (1983).

Lopatin A. S. Metod otzhiga //Stokhasticheskaya optimizatsiya v informatike. – 2005. – T. 1. – №. 1. – S. 133.

P.V. Matrenin, M.G. Grif, V.G. Sekayev, Metody stokhasticheskoy optimizatsii: uchebnoye posobiye / Novosibirsk: Izd-vo NGTU, 2016. – 67 s.

Gorchakov A.Y. ISPOL'ZOVANIYe OPENMP DLYA REALIZATSII MNOGOPOTOCHNOGO METODA NERAVNOMERNYKH POKRYTIY, Perspektivnyye informatsionnyye tekhnologii, Samara 14-16 aprelya 2018g., izdatel'stvo Samarskogo nauchnogo tsentra RAN, 2018, S.613-617

Gorchakov A. YU., Posypkin M. A. Sravneniye variantov mnogopotochnoy realizatsii metoda vetvey i granits dlya mnogoyadernykh sistem //Sovremennyye informatsionnyye tekhnologii i IT-obrazovaniye. – 2018. – T. 14. – №. 1.

Gorchakov A.Y., Posypkin M.A., Yamchenko Y.V. eksperimental'noye issledovaniye trekh variantov realizatsii metoda neravnomernykh pokrytiy dlya mnogoyadernykh sistem s obshchey pamyat'yu //International Journal of Open Information Technologies. – 2018. – T. 6. – №. 11 – S. 34-41.

Posypkin M., Usov A. Implementation and verification of global optimization benchmark problems //Open Engineering. – 2017. – Т. 7. – №. 1. – С. 470-478.

Global optimization test functions [Electronic resource]: site. – https://github.com/alusov/mathexplib (дата обращения: 19.03.2018).

Federal Research Center Computer Science and Control of Russian

Academy of Sciences [Electronic resource]: site. - Moscow: FRC CS RAS.- URL: http://hhpcc.frccsc.ru (application date: 09/12/2018)"


  • There are currently no refbacks.

Abava  Absolutech Fruct 2020

ISSN: 2307-8162