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

A.Y. Gorchakov, M.A. Posypkin, Y.V. Yamchenko

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.


Full Text:

PDF (Russian)

References


Evtushenko, Y. G., & Posypkin, M. A. (2011). An application of the nonuniform covering method to global optimization of mixed integer nonlinear problems. Computational Mathematics and Mathematical Physics, 51(8), 1286-1298. doi:10.1134/S0965542511080082

Evtushenko Ju. G., Posypkin M. A., Rybak L. A., Turkin A. V. Otyskanie mnozhestv reshenij sistem nelinejnyh neravenstv //Zhurnal vychislitel'noj matematiki i matematicheskoj fiziki. – 2017. – T. 57. – #. 8. – S. 1248-1254. doi:10.7868/S0044466917080075

Gorchakov A. Ju. Primenenie metoda neravnomernyh pokrytij dlja reshenija zadachi poiska maksimuma informativnosti predikata //International Journal of Open Information Technologies. – 2017. – T. 5. – #. 2. – S.29-33.

M.A. Posypkin, N.P. Hrapov, V.N. Filippov «Metod vetvej i granic na grid-sistemah personal'nyh komp'juterov», Programmnye sistemy: teorija i prilozhenija #2(16), 2013, –S. 43-69.

M.A. Posypkin «Arhitektura i programmnaja organizacija biblioteki dlja reshenija zadach diskretnoj optimizacii metodom vetvej i granic na mnogoprocessornyh vychislitel'nyh kompleksah» // Trudy ISA RAN, 2006, T. 25, –S. 18-25.

Bader, D.A.; Hart, W.E.; Phillips, C.A., Parallel Algorithm Design for Branch and Bound. In Tutorials on Emerging Methodologies and Applications in Operations Research: Presented at INFORMS 2004, Denver, CO, International Series in Operations Research & Management Science, Kluwer Academic Publishers: Dordrecht, The Netherlands, 2004, –pp. 5-44.


Refbacks

  • There are currently no refbacks.


Abava   MSU conference 2018

ISSN: 2307-8162