Andrew B. Kahng
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.
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)
PartProb : ibm10.net ibm10.are 2way10%.blk ibm10.fixor
PartProb : ibm10.nodes ibm10.nets ibm10.wts 2way10%.blk ibm10.fixother 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)
.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.
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
Algorithms used in MLPart are described in the following publications