COMPARISON OF VARIANTS OF MULTITHREADING REALIZATION OF METHOD OF BRANCHES AND BORDERS FOR MULTI-CORE SYSTEMS
Abstract
Recently, the main way to improve the performance of computing devices has become an increase in the number of processing cores in the processors, wherefore systems with shared memory have become widespread. Therefore, the development of parallel applications oriented to multi-core systems with shared memory becomes particularly topical. The article considers one of the classes of resource-intensive applications - the task of finding a global extremum of functions of several variables. One of the main approaches to solving such problems is the branch and boundary method. It is distinguished by the following features, essential from the point of view of parallelization: an unknown information graph in advance and the need to exchange information between computational threads. The article suggests several approaches to parallelizing the method of branches and boundaries. Currently, there are several standards for creating multi-threaded applications. The paper considers two such standards: OpenMP and C ++ 14. The OpenMP standard is characterized by higher development speed, but less flexible with respect to multithreaded extensions of C ++ 14, which allows you to vary the different modes of synchronization. We compare these approaches, as well as investigate the impact of various ways of organizing the computing process on application performance. The paper describes the algorithms and their software implementations. A technique for performing experimental studies on the performance of developed applications has been developed, which compares the proposed parallel algorithms on a representative set of test cases. It is shown that all the approaches considered lead to an acceleration of computations in comparison with the sequential variant. The best results are provided by the use of atomic variables for the interaction of threads. As computing platforms for conducting experiments, modern high-performance computing systems were used.
References
[2] Evtushenko Y.G., Posypkin M.A., Turkin A.V., Rybak L.A. Finding sets of solutions to systems of nonlinear inequalities. Computational Mathematics and Mathematical Physics. 2017; 57(8):1241-1247. DOI: https://doi.org/10.1134/S0965542517080073
[3] Gorchakov A.Ju. Application of method nonuniform coverings for maximum information content of predicate search. International Journal of Open Information Technologies. 2017; 5(2):29-33. Available at: https://elibrary.ru/item.asp?id=28314923 (accessed 10.02.18). (In Russian)
[4] Voevodin V.V., Voevodin Vl.V. Parallel computing. SPb.: BHV-Peterburg, 2002. 608 p. (In Russian)
[5] Posypkin M.A. Architecture and program organization of libraries for solving problems of optimization by method of branches and borders on multiprocessor computer complexes. Proceeding of the Institute for Systems Analysis of the Russian Academy of Science. 2006; 25:18-25. Available at: https://elibrary.ru/item.asp?id=11968032& (accessed 10.02.18). (In Russian)
[6] Archibald B., Maier P., McCreesh C., Stewart R., Trinder P. Replicable parallel branch and bound search. Journal of Parallel and Distributed Computing. 2018; 113:92-114. DOI: https://doi.org/10.1016/j.jpdc.2017.10.010
[7] Cordone R., Hosteins P., Righini G. A branch-and-bound algorithm for the prize-collecting single-machine scheduling problem with deadlines and total tardiness minimization. INFORMS Journal on Computing. 2018; 30(1):168-180. DOI: https://doi.org/10.1287/ijoc.2017.0772
[8] Dai Q., Yao C.S. A hierarchical and parallel branch-and-bound ensemble selection algorithm. Applied Intelligence. 2017; 46(1):45-61. DOI: https://doi.org/10.1007/s10489-016-0817-8
[9] Herrera J.F.R., Salmerón J.M.G., Hendrix E.M.T., Asenjo R., Casado L.G. On parallel branch and bound frameworks for global optimization. Journal of Global Optimization. 2017; 69(3):547-560. DOI: https://doi.org/10.1007/s10898-017-0508-y
[10] Melab N., Gmys J., Mezmaz M., Tuyttens D. Multi-core versus many-core computing for many-task branch-and-bound applied to big optimization problems. Future Generation Computer Systems. 2018; 82:472-481. DOI: https://doi.org/10.1016/j.future.2016.12.039
[11] Ozturk O., Begen M.A., Zaric G.S. A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. International Journal of Production Research. 2017; 55(6):1815-1831. DOI: https://doi.org/10.1080/00207543.2016.1253889
[12] Ponz-Tienda J.L., Salcedo-Bernal A., Pellicer E. A parallel branch and bound algorithm for the resource leveling problem with minimal lags. Computer-Aided Civil and Infrastructure Engineering. 2017; 32(6):474-498. DOI: https://doi.org/10.1111/mice.12233
[13] Romanov A., Romanova I., Ivannikov A. Application of exhaustive search, branch and bound, parallel computing and monte-carlo methods for the synthesis of quasi-optimal network-on-chip topologies. Proceedings of 2017 IEEE East-West Design and Test Symposium (EWDTS 2017). 29 Sept. - 2 Oct. 2017, Novi Sad, Serbia, 2017. DOI: https://doi.org/10.1109/EWDTS.2017.8110092
[14] Rosen S., Salemi P., Wickham B., Williams A., Harvey C., Catlett E., …. Xu J. Parallel empirical stochastic branch and bound for large-scale discrete optimization via simulation. Proceedings - Winter Simulation Conference. 2017. p. 626-637. DOI: https://doi.org/10.1109/WSC.2016.7822127
[15] Singhtaun C., Natsupakpong S. A comparison of parallel branch and bound algorithms for location-transportation problems in humanitarian relief. International Journal of GEOMATE. 2017; 12(33):38-44. DOI: https://doi.org/10.21660/2017.33.2563
[16] Bagóczki Z., Bánhelyi B. A parallel interval arithmetic-based reliable computing method on a GPU. Acta Cybernetica. 2017; 23(2):491-501. DOI: https://doi.org/10.14232/actacyb.23.2.2017.4
[17] Borisenko A., Haidl M., Gorlatch S. A GPU parallelization of branch-and-bound for multiproduct batch plants optimization. Journal of Supercomputing. 2017; 73(2):639-651. DOI: https://doi.org/10.1007/s11227-016-1784-x
[18] Dabah A., Bendjoudi A., AitZai A., El-Baz D., Taboudjemat N.N. Hybrid multi-core CPU and GPU-based B&B approaches for the blocking job shop scheduling problem. Journal of Parallel and Distributed Computing. 2018; 117:73-85. DOI: https://doi.org/10.1016/j.jpdc.2018.02.005
[19] Gmys J., Mezmaz M., Melab N., Tuyttens D. IVM-based parallel branch-and-bound using hierarchical work stealing on multi-GPU systems. Concurrency Computation. 2017; 29(9). DOI: https://doi.org/10.1002/cpe.4019
[20] Gonçalves A.D., Pessoa A.A., Bentes C., Farias R., Drummond L.M.D.A. Graphics processing unit algorithm to solve the quadratic assignment problem using level-2 reformulation-linearization technique. INFORMS Journal on Computing. 2017; 29(4):676-687. DOI: https://doi.org/10.1287/ijoc.2017.0754
[21] Saxena R., Jain M., Bhadri S., Khemka S. Parallelizing GA based heuristic approach for TSP over CUDA and OpenMP. Proceedings of 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI 2017). 2017 – January. p. 1934-1939. DOI: https://doi.org/10.1109/ICACCI.2017.8126128
[22] Shen J., Shigeoka K., Ino F., Hagihara K. An Out-of-Core Branch and Bound Method for Solving the 0-1 Knapsack Problem on a GPU. In: Ibrahim S., Choo K.K., Yan Z., Pedrycz W. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2017. Lecture Notes in Computer Science, Springer, Cham, 2017. Vol. 10393. DOI: https://doi.org/10.1007/978-3-319-65482-9_17
[23] Smirnov S., Voloshinov V. Implementation of concurrent parallelization of branch-and-bound algorithm in everest distributed environment. Procedia Computer Science. 2017; 119:83-89. DOI: https://doi.org/10.1016/j.procs.2017.11.163
[24] Posypkin M., Khrapov N. Branch and bound method on desktop grid systems. Proceedings of 2017 IEEE Russia Section Young Researchers in Electrical and Electronic Engineering Conference (ElConRus 2017). 1-3 Feb. 2017, St. Petersburg, Russia, 2017. p. 526-528. DOI: https://doi.org/10.1109/EIConRus.2017.7910607
[25] Evtushenko Y., Posypkin M., Sigal I. A framework for parallel large-scale global optimization. Computer Science - Research and Development. 2009; 23(3-4):211-215. DOI: https://doi.org/10.1007/s00450-009-0083-7
[26] Posypkin M., Usov A. Implementation and verification of global optimization benchmark problems. Open Engineering. 2017; 7(1):470-478. DOI: https://doi.org/10.1515/eng-2017-0050
[27] Global optimization test functions. Available at: https://github.com/alusov/mathexplib (accessed 10.02.18).
[28] Федеральный исследовательский центр «Информатика и управление» Российской академии наук. Available at: http://frccsc.ru (accessed 10.02.18). (In Russian)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
