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


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.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

Documentation and support

Algorithms used in MLPart are described in the following publications

Back to the Partitioning Slot,