Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices

Authors

  • A.S. Rusakov
  • M.V. Sheblaev

Keywords:

hypergraph partitioning
Fiduccia-Mattheyses algorithm
clustering
distributed computing systems
parallel programming

Abstract

One of the methods for the decomposition of a large problem to subproblems is its representation as a graph or hypergraph and partition this graph to approximately equal subgraphs with minimal cuts. The balanced hypergraph partitioning with the minimization of the cut size reduces communication cost between decomposed subproblems. The well-known approach to the hypergraph decomposition is the Fiduccia-Mattheyses (FM) algorithm and its hierarchical modifications. In this paper we discuss a key data structure modifications of the FM-algorithm to improve the performance and quality of the hierarchical partitioning algorithms and to reduce the computational overheads during solving large problems by parallel methods.

New computational technologies

Downloads

Published

2014-06-29

Issue

Vol. 15 (2014): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biographies

A.S. Rusakov

Institute for Design Problems in Microelectronics of RAS (IPPM RAS)
• Senior Researcher

M.V. Sheblaev

Institute for Design Problems in Microelectronics of RAS (IPPM RAS)
• Researcher

References

  1. Волков К.Н. Балансировка нагрузки процессоров при решении краевых задач механики жидкости и газа сеточными методами // Вычислительные методы и программирование. 2012. 13. 107-129.
  2. Hendrickson B., Kolda T.G. Graph partitioning models for parallel computing // Parallel Computing. 2000. 26, N 12. 1519-1534.
  3. Головченко Е.Н. Комплекс программ параллельной декомпозиции сеток // Вычислительные методы и программирование. 2010. 11. 360-365.
  4. Копысов С.П., Новиков А.К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Математическое моделирование. 2002. 14, № 9. 91-96.
  5. Якобовский М.В. Инкрементный алгоритм декомпозиции графов // Вестн. Нижегородского ун-та им. Н. И. Лобачевского. Серия «Математическое моделирование и оптимальное управление». 2005. 28, № 1. 243-250.
  6. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed Computing. 1998. 48, N 1. 96-129.
  7. Bichot C.E., Siarry P. (Eds.) Graph partitioning. London-Hoboken: John Wiley &; Sons, 2013.
  8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  9. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // SIAM Journal on Scientific Computing. 1998. 20, N 1. 359-392.
  10. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell System Technical Journal. 1970. 49, N 1. 291-308.
  11. Русаков С.Г., Святский А.Б. Метод автоматического разбиения на подсхемы для машинного анализа больших интегральных схем // Управляющие системы и машины. 1975. 3. 116-119.
  12. Delling D., Goldberg A., Razenshteyn I., Werneck R. Exact combinatorial branch-and-bound for graph bisection // Proc. Meeting on Algorithm Engineering and Experiments. Philadelphia: SIAM Press, 2012. 30-34.
  13. Pothen A., Simon D.H., Liou K. Partitioning sparse matrices with eigenvectors of graphs // SIAM J. of Matrix Analysis and Applications. 1990. 11, N 3. 430-452.
  14. Fiduccia C.M., Mattheyses R.M. A linear-time heuristic for improving network partitions // Proc. of 19th IEEE Design Automation Conference. Piscataway: IEEE Press, 1982. 175-181.
  15. Caldwell A.E., Kahng A.B., Markov I.L. Iterative partitioning with varying node weights // VLSI Design. 2000. 11, N 3. 249-258.
  16. Bui-Xuan B.M., Telle J.A., Vatshelle M. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems // Theoretical Computer Science. 2013. 511. 66-76.
  17. Андреев А.Е., Пависич И., Русаков А.С. Алгоритм глобального размещения структурированных заказных схем // Проблемы разработки перспективных микро- и наноэлектронных систем. М.: ИППМ РАН, 2012. 231-236.
  18. Alpert C.J. The ISPD98 circuit benchmark suite // Proc. of the 1998 ACM International Symposium on Physical Design. New York: ACM Press, 1998. 80-85.
  19. Papa D.A., Markov I.L. Hypergraph partitioning and clustering // Handbook of Approximation Algorithms and Metaheuristics. Boca Raton: CRC Press, 2007. 61. 1-61.19.
  20. Hagen L.W., Huang D.J. H., Kahng A.B. On implementation choices for iterative improvement partitioning algorithms // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1997. 16, N 10. 1199-1205.
  21. Caldwell A.E., Kahng A.B., Markov I.L. Improved algorithms for hypergraph bipartitioning // Proc. of the 2000 ACM Asia and South Pacific Design Automation Conference. New York: ACM Press, 2000. 661-666.
  22. Yoon Y., Kim Y.H. New bucket managements in iterative improvement partitioning algorithms // Applied Mathematics &; Information Sciences. 2013. 7, N 2. 37-57.