MARCO GSRC Calibrating Achievable Design: Bookshelf

Hypergraph Partitioning Slot

(see other slots )

Last updated Fri Mar 3, 2006

Contents

---

I. Introduction and overview

Hypergraph partitioning is important to many application domains including data mining, job scheduling, hardware-software partitioning, VLSI circuit layout and numerical linear algebra. Balanced partitioning typically represents the ``divide'' step of ``divide-and-conquer'' algorithms and seeks to assign the nodes of a [hyper]graph into groups of approximately equal total weight (i.e., satisfying balance constraints) while minimizing the number of [hyper]edges that are cut (i.e., adjacent to nodes in different groups). In some applications (notably in top-down VLSI circuit placement), problem instances have fixed nodes. For a 2006 survey of state-of-the-art hypergraph partitioning algorithms, see ``Hypergraph Partitioning and Clustering'' by David Papa and Igor Markov. A somewhat more comprehensive 1995 partitioning survey is available in ``Recent Directions in Netlist Partitioning: A Survey'' by Charles Alpert and Andrew Kahng. Recent publications can be found online at Univ. of Minnesota, UCSD, Univ. of Michigan, and other groups.

---

II. New Partitioning Formats

The proposed formats have been designed according to general guidelines for data formats in the GSRC bookshelf, and are intended for standardization within the partitioning and placement slot, replacing or coexisting with previously available formats. This slot will provide benchmark instances in the new formats, including instanes earlier available in other formats, as well as a variety of executables and source code for conversion, evaluation and optimization.

Netlists should be represented with .nodes, .nets and .wts files explained in the Hypergraph slot (follow links to "old fomats", i.e., no XML). In addition to those, .blk, .fix and .sol files can be used to represent balance and fixed node constraints for partitioning. Also see this small example.

---

III. Publicly available instances, solutions and reference performance results

The following pages list circuit partitioning benchmarks for both the older MCNC tests, and the new IBM-derived tests. Each testcase is (or will be Real Soon Now) available in both net(D)/are(M) and nodes/nets/wts format. Solutions for some tests are provided in the .sol format.

• The ISPD98 Circuit Benchmark Suite
• The ISPD99 Partitioning with Terminals Benchmark Suit
• MCNC Circuit Bencharks Suite
• UCLA Small Circuit Partitioning Instances

---

IV. Executable Utilities (converters, generators, statistics browsers, evaluators, constraint verifiers)

NetCut Evaluator

Usage: NetCutEval -f file.aux
where file.aux looks like

 PartProb : ibm01.net ibm01.sol 
 or
 PartProb : ibm01.nodes ibm01.nets ibm01.sol 

i.e., it can use both old and new formats, but not mixed formats. Files with extensions .are/.wts, .blk and .fix can also be used, but do not influence the cut. If the .sol file does not contain a legal solution, an error message will be printed preceded with the beginning of the solution.

---

V. Optimizers and other non-trivial executables

UCLA FMPart 7.13.5 (February, 2005) (Sun Solaris 2.7) (Intel-Linux) (Intel-Win95/98/NT)

Usage: UCLA_FMPart -f file.aux
where filename.aux contains one line of the form

 PartProb : ibm10.net ibm10.are 2way10%.blk ibm10.fix 

or

 PartProb : ibm10.nodes ibm10.nets ibm10.wts 2way10%.blk ibm10.fix 

other supported options are

 -help  prints available options
 -num ##  each experiment contains ## independent starts with the best solution and total runtime as its result 
 -runs ##  launches ## independent experiments and reports stats
 -clip  turns on CLIP FM (default is LIFO FM)

UCLA MLPart 5.2.4 (February, 2005) (Sun Solaris 2.7) (Intel-Linux) (Intel-Win95/98/NT)

Usage: UCLA_MLPart -f file.aux
where file.aux contains one line of the form

 PartProb : ibm10.net ibm10.are 2way10%.blk ibm10.fix 

or

 PartProb : ibm10.nodes ibm10.nets ibm10.wts 2way10%.blk ibm10.fix 

other supported options are

 -help  prints available options
 -num ##  each experiment contains ## independent starts with the best solution and total runtime as its result 
 -runs ##  launches ## independent experiments and reports stats
 -skipVCycle turns on classic multi-level partitioning (faster)

More information on MLPart is available here.

---

VI. Performance results for IBM benchmarks: 2%, 10% (from the ASPDAC 2000 paper).

---

VII. Common in-memory representations, parsers and other source codes

UCLA/UMich PD tools release (see also the MLPart page)

---

abk@ucsd.edu, imarkov@eecs.umich.edu