TWO-LEVEL GRAPH PARTITIONING ALGORITHM
Abstract
The paper discusses one of the important clasess of discrete optimization problems, combina-torial and logical problems on graphs. These problems belong to the class of NP-hard and NP-difficult optimization problems. The paper describes the partitioning optimization problem and the problem statement. To effectively solve this problem, the authors propose a new “search-evolution” strategy. On the basis of this strategy, a new search architecture based on a multi-level approach has been proposed. The principal difference of the proposed approach is the division of the search into two stages and the use of different methods at each stage. At the first stage, cluster selection is pro-posed. At the second stage, a genetic algorithm was proposed as an optimization method, which al-lows for efficient rearrangement of the constructed clusters. Based on the proposed architecture, a two-level algorithm has been developed that allows parallelizing the search process and obtaining sets of optimal and quasi-optimal solutions in a time comparable to iterative algorithms. The devel-oped algorithm has been implemented in the C # programming language. Two types of computational experiments have been conducted on benchmarks. This is a division of the graph into 4 and 8 parts.The results of the research show that the developed approach allows you to get more effective solu-tions, because obtained results are on average 5 % better than the partitions obtained using the well-known HMetis PGA Complex algorithms, which indicates the effectiveness of the proposed approach. Time complexity lies within – .
References
2. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition. – Kluwer Academic Publisher, USA, 2013.
3. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. General ques-tions of automated design and engineering // Studies in Computational Intelligence. – 2009. – Vol. 212. – P. 1-22.
4. Курицкий Б.Я. Оптимизация вокруг нас. – Л.: Машиностроение, 1989. – 145 с.
5. Корниенко В.П. Методы оптимизации. – М.: Высшая школа, 2007. – 663 с.
6. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа // Известия Рос-сийской академии наук. Теория и системы управления. – 1999. – № 4. – С. 79-87.
7. Курейчик В.В., Курейчик Вл.Вл. Биоинспирированный алгоритм разбиения схем при проектировании СБИС // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 23-29.
8. Kureichik, V., Zaruba, D., Kureichik, Vl. Hybrid approach for graph partitioning // Advances in Intelligent Systems and Computing. – 2017. – Vol. 573. – P. 64-73.
9. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. – М.: МЦМО, 2000. – 893 c.
10. Мандельброт Б. Фрактальная геометрия природы. – М.: Институт компьютерных ис-следований, 2002. – 656 с.
11. Курейчик Вл.Вл. Многоуровневый подход решения задачи размещения фрагментов СБИС на основе механизма агрегации фракталов // XII Всероссийская научная конфе-ренция молодых ученых, аспирантов и студентов «Информационные технологии, сис-темный анализ и управление» (ИТСАиУ-2015). – Ростов-на-Дону: Изд-во ЮФУ, 2015. – С. 184-188. 12. Hendrickson B., Leland R. A Multilevel Algorithm for Partitioning Graphs // Proceeding Super-computing '95 Proceedings of the 1995 ACM/IEEE conference on Supercomputing Article No. 28. 13. Schloegel K., Karypis G., Kumar V. Multilevel diffusion schemes for repartitioning of adaptive meshes // Technical Report 97-013, University of Minnesota, Department of Computer Sci-ence, 1997.
14. Barnard S.T., Simon H.D. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems // Proceedings 6th SIAM Conf. Parallel Processing for Sci-entific Computing. – 1993. – P. 711-718.
15. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации (обзор) // Кибернетика и программирование. – 2017. – № 3. – С. 51-79.
16. Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик // Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
17. Kurejchik V.V., Kurejchik V.M. On genetic-based control // Автоматика и телемеханика. – 2001. – № 10. – С. 174-187.
18. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. – USA: University of Michigan, 1975.
19. Курейчик Вл.Вл., Курейчик Л.В. Программная реализация гибридного подхода для реше-ния задачи размещения фрагментов СБИС // IV Всероссийская научно-техническая конференция молодых ученых, аспирантов и студентов «Фундаментальные и приклад-ные аспекты компьютерных технологий и информационной безопасности». – Ростов-на-Дону – Таганрог: Изд-во ЮФУ, 2018. – С. 301-305.
20. IBM-PLACE 2.0 benchmark suits. – http://er.cs.ucla.edu/benchmarks/ibm-place2/bookshelf/-ibm-place2-all-bookshelf-nopad.tar.gz.
21. Alpert C.J. The ISPD-98 Circuit Beanchmark Suit // in Proc. ACM/IEEE International Sympo-sium on Physical Design. – April 1998. – P. 80-85.
