Generation of Initial Partitions for Hypergraph Balanced Cut Problem

Sheblaev M.V. ()
Abstract - Abstract — Purpose, Methods, Results, Discussion; Purpose: The balanced cut problem is widely used in the EDA for different stages of design flows. The most used approach to solve this problem for EDA is Fiduccia-Mattheyses’s algorithm. The algorithm is iterative and strongly depends of intial partition which iit improves step-by-step. We study landscape of metric space of partitions with distance function generated from Fiduccia-Mattheyses algorithm. To solve on practice, we approximate the distance function with few first steps of FM’s algorithm and use well known data science algorithm t-SNE to reduce dimension.The result is 2D or 3D landscape where the unsupervised clustering algorithm is run. Final cluster set is a generation set for initial partitions – we use one representer from each cluster to start Fiduccia-Mattheyses algorithm. As result, we significantly increase quality of flat FM algorithm which is used as part of multilevel hierarchical method. The research will be continued with detailed study of metric space and local topologies to deeper understand the optimal way of initial partitions generation.

Keywords - balanced cut, mincut, placement, Fiduccia-Mattheysses

Алгоритм генерации начальных разбиений для решения задачи сбалансированного разбиения гиперграфа

Шеблаев М.В. (eASIC Corporation, г. Москва)
Аннотация - В данной работе мы предлагаем подход к оценке качества начальных данных и алгоритм нахождения начальных данных для алгоритма Фидуччи-Матейсиса, позволяющий получить качественное приближенное решение исходной задачи сбалансированного разбиения гиперграфа, часто используемой для различных стадий маршрутов проектирования в САПР СБИС.

Ключевые слова - сбалансированное разбиение графа, алгоритм Фидуччи-Матейисса, FM-алгоритм, mincut, balanced cut.