Multilevel Hypergraph Partitioning: Application In Vlsi Domain

By George Karypis, Rajat Aggarwal, Vipin Kumar, Shashi Shekhar. 1997

In this paper, we present a new hypergraph partitioning algorithmthat is based on the multilevel paradigm. In the multilevel paradigm,a sequence of successively coarser hypergraphs is constructed. Abisection of the smallest hypergraph is computed and it is used toobtain a bisection of the original hypergraph by successively projectingand refining the bisection to the next level finer hypergraph.We evaluate the performance both in terms of the size of the hyper-edgecut on the bisection as well as run time on a number of VLSIcircuits. Our experiments show that our multilevel hypergraph partitioningalgorithm produces high quality partitioning in relativelysmall amount of time. The quality of the partitionings produced byour scheme are on the average 4% to 23% better than those producedby other state-of-the-art schemes. Furthermore, our partitioning algorithmissignificantly faster, often requiring 4 to 15 times less timethan that required by the other schemes. Our multilevel hypergraphpartitioning algorithm scales very well for large hypergraphs. Hypergraphswith over 100,000 vertices can be bisected in a few minuteson today's workstations. Also, on the large hypergraphs, ourscheme outperforms other schemes (in hyperedge cut) quite consistentlywith larger margins (9% to 30%).

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A domain decomposition approach to implementing fault slip in finite‐element models of quasi‐static and dynamic crustal deformation (2013, methodology): “The cell partition balances the number of cells across the processes using ParMetis [ Karypis et al. , 1999] to achieve good balance for the ﬁnite element integration.”
FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space (2004, methodology): “APPROACH The multilevel approach that FastDTW uses is inspir ed by the multilevel approach used for graph bisection [5].”
Comprehensive survey on hierarchical clustering algorithms and the recent developments (2022, methodology): “In the final and most important stage, the Chameleon method uses the interconnectivity and closeness measure to continuously merge the sub-clusters until some criteria are met or only one cluster is formed (Karypis et al. 1999b).”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “[718] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar.”
A Survey of Clustering Data Mining Techniques (2006, methodology): “CHAMELEON strongly relies on graph partitioning implemented in the library HMETIS (see the section Co-Occurrence of Categorical Data).”
Cluster Ensembles A Knowledge Reuse Framework for Combining Partitionings (2002, methodology): “We use the hypergraph partitioning package HMETIS (Karypis et al. 1997), which gives high-quality partitions and is very scalable.”
Toward accurate dynamic time warping in linear time and space (2007, unknown): “Input: X a TimeSeries of length | X | Y a TimeSeries of length | Y | radius distance to search outside of the projected warp path from the previous resolution when refining the warp path Output: 1) A min. distance warp path between X and Y 2) The warped path distance between X and Y 1| // The…”
Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS (2011, background): “The dataset LP illustrates the interesting tradeoﬀ where a coarse partition is beneﬁcial whereas ﬁner grained partitions would be detrimental.”
Cluster Ensembles --- A Knowledge Reuse Framework for Combining Multiple Partitions (2002, methodology): “HMETIS gives high-quality partitions and is very scalable.”
Ltd Registered in England and Wales Registered Number : 1072954 Registered office : (2004, methodology): “We use 45–55% balance tolerance because it is commonly used in digital circuit partitioning to compare different methods [15,16].”
Learning similarity metrics for event identification in social media (2010, background): “Other alternatives such as scalable graph partitioning algorithms [23] do not capture the highly skewed event distribution of social media event data due to their bias towards balanced partitioning (we experimented with graph partitioning algorithms, but do not discuss their results here because of ”
Ensemble learning: A survey (2018, methodology): “Following the creation of the hypergraph, consensus clustering is obtained by solving an optimization problem using different methods (Ben-Hur, Elisseeff, & Guyon, 2001; Karypis, Aggarwal, Kumar, & Shekhar, 1999; Strehl & Ghosh, 2002).”
Advances in Fuzzy Clustering and its Applications (2007, methodology): “This partitioning is performed by the package HMETIS by Karypis et al. (1997) .”