Experimental study of three options for implementing of the nonuniform covering method for multicore systems with shared memory

Abstract

In this paper, we consider three effective parallel implementations of the nonuniform method covering intended for computing systems with shared memory. The nonuniform covering method is one of the most well-known deterministic methods for solving global optimization problems based on the branch and bound scheme. Given the computational complexity of the method and the widespread use of high-performance multi-core systems with shared memory, the development of parallel implementations of this method is of particular relevance. The article proposes several approaches to parallelizing the method of nonuniform covering. Currently, there are several standards for creating multi-threaded applications. The paper discusses two such standards: OpenMP 4.0 and C ++ 17. Several modes are used for synchronization between threads. The paper provides a description of the algorithms and their software implementations. An experimental study was carried out on a test problem close to real — the search for the minimum energy of a molecular cluster. As a computational platform for conducting experiments, modern high-performance systems were used. The study showed that for this type of tasks, the performance of the methods (by the number of iterations) is approximately at the same level. In addition, it was shown experimentally that the complexity of the algorithm does not always lead to an increase in its efficiency.