СРАВНЕНИЕ ВАРИАНТОВ МНОГОПОТОЧНОЙ РЕАЛИЗАЦИИ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ МНОГОЯДЕРНЫХ СИСТЕМ
Аннотация
В последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах, в связи с чем, системы с общей памятью получили широкое распространение. Поэтому особую актуальность приобретает разработка параллельных приложений, ориентированных на системы с общей памятью. В статье рассматривается один из классов таких приложений – задача поиска глобального экстремума функций многих переменных. Одним из основных подходов к решению таких задач является метод ветвей и границ. Его особенностями являются неизвестный заранее информационный граф и необходимость обмена информацией между вычислительными потоками, что существенно осложняет параллельную реализацию. В статье предлагаются несколько подходов к распараллеливанию метода ветвей и границ. Для распараллеливания используются различные инструменты (OpenMP, многопоточные расширения современного стандарта С++), различные режимы синхронизации и способы организации вычислительного процесса. Приводится описание алгоритмов и его программных реализаций, а также результатов эксперимента. Производится экспериментальное сравнение предложенных параллельных алгоритмов на представительном наборе тестовых примеров. В качестве вычислительных платформ для проведения экспериментов использовались современные высокопроизводительные вычислительные системы.
Литература
[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)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
