K-frontal method of nonuniform coverings

Abstract

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.