MARCO GSRC Calibrating Achievable Design: Bookshelf

MLPart: high-performance min-cut bisector

Andrew Caldwell Andrew B. Kahng Igor Markov

Last updated: Fri Mar 3, 2006

Introduction

MLPart is a leading-edge min-cut hypergraph/circuit partitioner developped at UCLA and maintained at the University of Michigan. It favorably compares with hMetis. Source code for MLPart is distributed, with all support libraries, under a liberal open-source license. MLPart is used in the Capo placer.

Source code and executables

Complete source code for MLPart in C++ is distributed as a part of UCLA/UMich PD tools release. Currently, the installation scripts target Unix systems (Linux and Solaris) and require PERL 5.002 or higher. The code requires g++ 2.95.2 or higher (configured to use GNU linker) or SunPro CC 5.1 or higher (Workshop 5.0 and earlier are not supported) that come with Sun Forte C++ (formerly Workshop). In order to use Sun compilers, you must have Solaris 2.7 or higher. The code can also be compiled with MSVC++ 6.0, but installation management is difficult and currently is not supported.

Executables are provided for the following systems: (Sun Solaris 2.7) (Intel Linux) (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

   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)

Data formats and benchmarks

.net/.are are the well-publicized partitioning formats (with netD being an extension for pin directionality). .nodes/.nets/.wts are bookshelf hypergraph formats defined here (also see this small example); blk and fix are extensions defined here (also see the Partitioning Slot of the Bookshelf and this ISPD 1999 paper).

Alternatively, follow links to "old" (i.e., no-XML) formats in the Partitioning slot.

Recommendation: browse a sample benchmark before reading formal descriptions.

Performance results

Sample performance on IBM18, 2% in format cut(seconds): 2002(128), 1976(190), 1823(399), 1737(612). Runtime measured on Sun Ultra-10 @300MHz. For a comparison, one start of hMetis 1.5.3 takes 334 seconds and achieves average cut of 1833. More detailed comparisons between hMetis and MLPart are available for 2% and 10% tolerances. Those tables are explained in detail in our paper

A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Improved Algorithms for Hypergraph Bipartitioning", (.ps), (.pdf), (.slides) Proc. Asia and South Pacific Design Automation Conf., Jan. 2000, pp. 661-666.

Documentation and support

Algorithms used in MLPart are described in the following publications

D. A. Papa and I. L. Markov, ``Hypergraph Partitioning and Clustering'' (.pdf), in Approximation Algorithms and Metaheuristics, T. Gonzalez, ed.; CRC Press, 2006, in print.
A. E. Caldwell, A. B. Kahng, I. L. Markov, "Iterative Partitioning With Varying Node Weights", (.ps), (.pdf) to appear in VLSI Design, 2000.
A. E. Caldwell, A. B. Kahng, I. L. Markov, "Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitio ning", (.ps), (.pdf) to appear in ACM Journal of Experimental Algorithms, 2000.
A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Improved Algorithms for Hypergraph Bipartitioning", (.ps), (.pdf), (.slides) Proc. Asia and South Pacific Design Automation Conf., Jan. 2000, pp. 661-666.
A. E. Caldwell, A. B. Kahng, A. A. Kennings and I. L. Markov, "Hypergraph Partitioning for VLSI CAD: Methodology for Reporting, and New Results", (.ps), (.pdf) Proc. ACM/IEEE Design Automation Conf., June 1999, pp. 349-354.
A. E. Caldwell, A. B. Kahng and I. L. Markov, "Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning", (.ps), (.pdf), (slides) Proc. Workshop on Algorithm Engineering and Experimentation (ALENEX), Jan. 1999, pp. 177-193
A. E. Caldwell, A.B. Kahng and I.L. Markov, "Design and implementation of move-based partitioners" (.ps), (.pdf) UCLA TR-990015, March 1999.

Back to the Partitioning Slot

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