Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин

Авторы

  • А.С. Русаков
  • М.В. Шеблаев

Ключевые слова:

разбиение гиперграфа
FM-алгоритм
кластеризация
распределенные вычислительные системы
параллельное программирование

Аннотация

Одним из способов декомпозиции задачи большой размерности на подзадачи является представление ее в виде графа или гиперграфа и последующее разбиение на приблизительно равные части, причем число связей между подграфами должно быть минимальным. Если веса ребер графа моделируют объем межпроцессорных связей, а вес узлов гиперграфа — вычислительную сложность, то подзадачи можно эффективно решать на параллельных вычислительных системах. Известные многоуровневые эвристические методы на базе алгоритма Фидуччиа-Мэтьюза позволяют решать такие задачи за приемлемое время. В настоящей статье предложены модификации ключевой структуры данных алгоритма, позволяющие улучшить свойства метода сбалансированного разбиения гиперграфа на подграфы с целью достижения меньшего размера сечения и уменьшения издержек параллельных методов решения исходной задачи. Приведены результаты сравнения нового алгоритма для одноуровневого и иерархического методов разбиения.

Новые вычислительные технологии

Загрузки

Опубликован

2014-06-29

Выпуск

Том 15 (2014): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.С. Русаков

Институт проблем проектирования в микроэлектронике РАН
ул. Советская, 3, 124365, Зеленоград, Москва
• старший научный сотрудник

М.В. Шеблаев

Институт проблем проектирования в микроэлектронике РАН
ул. Советская, 3, 124365, Зеленоград, Москва
• научный сотрудник

Библиографические ссылки

  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.