| Generation of Initial Partitions for Hypergraph Balanced Cut Problem |
|
 |
|
|
| Authors |
| | Sheblaev M.V. |
| Date of publication |
| | 2018 |
| DOI |
| | 10.31114/2078-7707-2018-3-148-153 |
|
| 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 |
| Library reference |
| | Sheblaev M.V. Generation of Initial Partitions for Hypergraph Balanced Cut Problem // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 3. P. 148-153. doi:10.31114/2078-7707-2018-3-148-153 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2018/pdf/D058.pdf |
