| | Improved Algorithms for Hypergraph Bipartitioning
Andrew Caldwell, Andrew Kahng, Igor Markov
Citation
Andrew Caldwell, Andrew Kahng, Igor Markov. "Improved Algorithms for Hypergraph Bipartitioning". ASPDAC `00, ACM/IEEE, 661-666, January, 2000.
Abstract
Multilevel Fiduccia-Mattheyses (MLFM) hypergraph partitioning
\cite{AlpertHK97,KarypisAKS97,KarypisK99}
is a fundamental optimization in VLSI CAD physical design.
The leading implementation, {\tt hMetis} \cite{KarypisK98}, has since 1997
proved itself substantially superior in both
runtime and solution quality to even very recent works
(e.g., \cite{CongLLSX97,EemC99, WichlundA98}).
In this work, we present two sets of results: (i) new techniques
for flat FM-based hypergraph partitioning (which is the core of
multilevel implementations), and (ii) a new multilevel implementation
that offers leading-edge performance.
Our new techniques for flat partitioning
confirm the conjecture from \cite{CaldwellKM99e}, suggesting that
{\em specialized partitioning heuristics} may be able to
{\em actively exploit} fixed nodes in partitioning instances arising
in the driving top-down placement context. Our FM variant
is competitive with traditional FM on instances without terminals
\cite{ChucksBench} and considerably superior on instances with
fixed nodes (i.e., arising during top-down placement~\cite{CaldwellKM99c}).
Our multilevel FM variant avoids several complex heuristics and non-trivial
tunings that often lead to complex implementations; it achieves trade-offs
between solution quality and run time that are comparable or better
than those achieved by {\tt hMetis-1.5.3} (the latest available version).
Following~\cite{CaldwellKM99a}, we attempt to provide algorithm descriptions
that are as detailed and unambiguous as possible, to allow replicability
and speed improvements in future research.
Electronic downloads
- HTML
Andrew Caldwell, Andrew Kahng, Igor Markov. <a
href="http://www.gigascale.org/pubs/54.html">Improved
Algorithms for Hypergraph Bipartitioning</a>, ASPDAC
`00, ACM/IEEE, 661-666, January, 2000.
- Plain text
Andrew Caldwell, Andrew Kahng, Igor Markov. "Improved
Algorithms for Hypergraph Bipartitioning". ASPDAC `00,
ACM/IEEE, 661-666, January, 2000.
- BibTeX
@inproceedings{CaldwellKahngMarkov00_ImprovedAlgorithmsForHypergraphBipartitioning,
author = {Andrew Caldwell and Andrew Kahng and Igor Markov},
title = {Improved Algorithms for Hypergraph Bipartitioning},
booktitle = {ASPDAC `00},
organization = {ACM/IEEE},
pages = {661-666},
month = {January},
year = {2000},
abstract = {Multilevel Fiduccia-Mattheyses (MLFM) hypergraph
partitioning
\cite{AlpertHK97,KarypisAKS97,KarypisK99} is a
fundamental optimization in VLSI CAD physical
design. The leading implementation, {\tt hMetis}
\cite{KarypisK98}, has since 1997 proved itself
substantially superior in both runtime and
solution quality to even very recent works (e.g.,
\cite{CongLLSX97,EemC99, WichlundA98}). In this
work, we present two sets of results: (i) new
techniques for flat FM-based hypergraph
partitioning (which is the core of multilevel
implementations), and (ii) a new multilevel
implementation that offers leading-edge
performance. Our new techniques for flat
partitioning confirm the conjecture from
\cite{CaldwellKM99e}, suggesting that {\em
specialized partitioning heuristics} may be able
to {\em actively exploit} fixed nodes in
partitioning instances arising in the driving
top-down placement context. Our FM variant is
competitive with traditional FM on instances
without terminals \cite{ChucksBench} and
considerably superior on instances with fixed
nodes (i.e., arising during top-down
placement~\cite{CaldwellKM99c}). Our multilevel FM
variant avoids several complex heuristics and
non-trivial tunings that often lead to complex
implementations; it achieves trade-offs between
solution quality and run time that are comparable
or better than those achieved by {\tt
hMetis-1.5.3} (the latest available version).
Following~\cite{CaldwellKM99a}, we attempt to
provide algorithm descriptions that are as
detailed and unambiguous as possible, to allow
replicability and speed improvements in future
research. },
URL = {http://www.gigascale.org/pubs/54.html}
}
Posted by Igor Markov on 1 Sep 2000..
Notice:
This material is presented to ensure timely dissemination of scholarly
and technical work. Copyright and all rights therein are retained by
authors or by other copyright holders. All persons copying this
information are expected to adhere to the terms and constraints
invoked by each author's copyright.
| |
