Исследование структуры гетерогенного реконфигурируемого вычислителя для эффективной работы матричного метода муравьиных колоний
Аннотация
Развитие современных вычислительных систем направлено на увеличение количества вычислителей и ускорителей, в том числе и разнородных: матричных ускорителей, MIMD, SIMD и др., что требует модернизации вычислительных алгоритмов с учетом структуры компьютера. В работе рассматривается матричная модификация метода муравьиных колоний (ACO) для решения параметрической задачи. Для решения параметрической задачи, поиска оптимальных значений параметров, в методе ACO применяется графовая структура данных, в которой для каждого значения каждого параметра выделяется одна вершина, а муравей-агент должен выбрать по одному значению для каждого параметра. Данная структура позволяет рассматривать работу ACO как операции над матрицами. Предложенная матричная модификация, работающая с оптимизированной графовой структурой, позволяет достичь ускорения от 13 до 22 раз по сравнению с оригинальным методом при выполнении на CPU. Во многом такое ускорение обусловлено работой современного оптимизирующего компилятора C++. Предложен алгоритм представления матричного ACO для SIMD ускорителя и гетерогенного вычислителя. Проведены исследования на ускорителе с применением технологии NVIDIA CUDA, ускорение составило от 7 до 18 раз. Для применения ACO на CUDA требуется пересмотр алгоритма, разделение данных по типам памяти, правильное разделение на потоки и блоки, решения проблем синхронизации и передачи данных между CPU и GPU. Предложен алгоритм для гетерогенного вычислителя, выполняющего матричные преобразования на CPU и вычисление пути муравья-агента на GPU, который показал ускорение от 24 до 38 раз. Проведено теоретическое исследование эффективности применения гетерогенного матричного ACO на гетерогенном вычислителе, состоящем из наборов MIMD ядер и SIMD ускорителей. Предложен подход к определению предела теоретического ускорения алгоритма и оптимальная структура гетерогенного реконфигурируемого вычислителя.
Литература
2. Dorigo M., Stützle T. Ant Colony Optimization. Cambridge, Massachusetts: MIT Press; 2004. 321 p.
3. Uslu M.O., Erdoğdu K. Ant Colony Optimization and Beam-Ant Colony Optimization on Traveling Salesman Problem with Traffic Congestion. DEUFMD. 2024;26(78):519-527. https://doi.org/10.21205/deufmd.2024267820
4. Sagban R.F., Ku-Mahamud K.R., Abu Bakar M.S. Reactive max-min ant system with recursive local search and its application to TSP and QAP. Intelligent Automation & Soft Computing. 2017;23(1):127-134. https://doi.org/10.1080/10798587.2016.1177914
5. Ghimire B., Mahmood A., Elleithy K. Hybrid Parallel Ant Colony Optimization for Application to Quantum Computing to Solve Large-Scale Combinatorial Optimization Problems. Applied Sciences. 2023;13:11817. https://doi.org/10.3390/app132111817
6. Črepinšek M., Liu S.-H., Mernik M. Exploration and Exploitation in Evolutionary Algorithms: A Survey. ACM Computing Surveys. 2013;45:35. https://doi.org/10.1145/2480741.2480752
7. Dorigo M., Birattari M. Swarm intelligence. Scholarpedia. 2007;2(9):1462.
8. Pellegrini P., Stützle T., Birattari M. A critical analysis of parameter adaptation in ant colony optimization. Swarm intelligence. 2012;6:23-48. https://doi.org/10.1007/s11721-011-0061-0
9. Danesh M., Danesh S. Optimal design of adaptive neuro-fuzzy inference system using PSO and ant colony optimization for estimation of uncertain observed values. Soft Computing – A Fusion of Foundations, Methodologies and Applications. 2024;28(1):135-152. https://doi.org/10.1007/s00500-023-09194-6
10. Yin C., Fang Q., Li H., et al. An optimized resource scheduling algorithm based on GA and ACO algorithm in fog computing. The Journal of Supercomputing. 2024;80:4248-4285. https://doi.org/10.1007/s11227-023-05571-y
11. Bullnheimer B., Kotsis G., Strauß C. Parallelization strategies for the ant system. Applied Optimization. 1998;24:87-100. https://doi.org/10.1007/978-1-4613-3279-4_6
12. Randall M., Lewis A. A parallel implementation of ant colony optimization. Journal of Parallel and Distributed Computing. 2002;62(9):421-1432. https://doi.org/10.1006/jpdc.2002.1854
13. Mansour I.B., Alaya I.B., Tagina M. A New Parallel Hybrid MultiObjective Ant Colony Algorithm Based on OpenMP. In: Weghorn H. (Ed.) Proceedings of the 17th International Conference on Applied Computing (AC2020). IADIS Press; 2020. p. 19-26. https://doi.org/10.33965/ac2020_202013l003
14. Skinderowicz R. Implementing a GPU-based parallel MAX–MIN ant system. Future Generation Computer Systems. 2020;106:277-295. https://doi.org/10.1016/j.future.2020.01.011
15. Zeng Z., Cai Y., Chung K.L., Lin H., Wu J. A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP. IET Computers & Digital Techniques. 2023:9915769. https://doi.org/10.1049/2023/9915769
16. Tsutsui S. ACO on Multiple GPUs with CUDA for Faster Solution of QAPs. In: Coello C.A.C., Cutello V., Deb K., Forrest S., Nicosia G., Pavone M. (eds.) Parallel Problem Solving from Nature – PPSN XII. PPSN 2012. Lecture Notes in Computer Science. Vol. 7492. Berlin, Heidelberg: Springer; 2012. p. 174-184. https://doi.org/10.1007/978-3-642-32964-7_18
17. de Melo Menezes B.A., Herrmann N., Kuchen H., et al. High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons. International Journal of Parallel Programming. 2021;49:776-801. https://doi.org/10.1007/s10766-021-00714-1
18. Shan H. A novel travel route planning method based on an ant colony optimization algorithm. Open Geosciences. 2023;15(1):20220541. https://doi.org/10.1515/geo-2022-0541
19. Yang L., Jiang T., Cheng R. Tensorized Ant Colony Optimization for GPU Acceleration. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '24 Companion). New York, NY, USA: Association for Computing Machinery; 2024. p. 755-758. https://doi.org/10.1145/3638530.3654394
20. Dzalbs I., Kalganova T. Accelerating supply chains with Ant Colony Optimization across range of hardware solutions. Computers & Industrial Engineering. 2020;147:106610. https://doi.org/10.1016/j.cie.2020.106610
21. Sudakov V.A., Titov Yu.P. Investigation of the parametric graph model in the ant colony method. Mathematical Models and Computer Simulations. 2025;17(2):126-136. https://doi.org/10.1134/S2070048224700996
22. Sinitsyn I.N., Titov Yu.P. Control of Set of System Parameter Values by the Ant Colony Method. Automation and Remote Control. 2023;84(8):893-903. https://doi.org/10.1134/S0005117923080106
23. Sinitsyn I.N., Titov Yu.P. Investigation of Algorithms for Cyclic Search for Additional Solutions when Optimizing the Order of Hyperparameters by the Ant Colony Method. Sistemy' vy'sokoj dostupnosti = Highly Available Systems. 2023;19(1):59-73. (In Russ., abstract in Eng.) https://doi.org/10.18127/j20729472-202301-05
24. Sinitsyn I.N., Titov Yu.P. Optimization of the Order of Hyperparameters of Computational Cluster by the Ant Colony Method. Sistemy' vy'sokoj dostupnosti = Highly Available Systems. 2022;18(3):23-37. (In Russ., abstract in Eng.) https://doi.org/10.18127/j20729472-202203-02
25. Sudakov V., Titov Y. Matrix-Based ACO for Solving Parametric Problems Using Heterogeneous Reconfigurable Computers and SIMD Accelerators. Mathematics. 2025;13(8):1284. https://doi.org/10.3390/math13081284
26. Sudhanshu M.K. Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method. University Library of Munich, Germany, MPRA Paper. 2006. https://doi.org/10.2139/ssrn.926132
27. Chetverushkin B.N., Sudakov V.A, Titov Y.P. Graph Condensation for Large Factor Models. Doklady Mathematics. 2024;109(3):246-251. https://doi.org/10.1134/S1064562424702090
28. Chetverushkin B.N., Sudakov V.A, Titov Y.P. Modeling of high-dimensional systems based on graph condensation. Matematicheskoe modelirovanie. 2025;37(3):59-74. (In Russ., abstract in Eng.) https://doi.org/10.20948/mm-2025-03-04
Это произведение доступно по лицензии 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.
