MARCO GSRC C.A.D.: Bookshelf

UMICH Physical Design Tools Saurabh N. Adya, Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov and Jarrod A. Roy Last updated: May 29, 2006 by imarkov

Introduction

This release contains over 170,000 lines in C++ implementing leading-edge industrial-grade VLSI Physical Design tools: the Capo placer, the Parquet floorplanner, the MLPart partitioner, the object-oriented UCLA DB database with LEF/DEF parser and all supporting libraries. Several binary placement utilities are available from the Placement Utilities web page. A list of publications describing algorithms in Capo and MLPart can be found at the bottom of this page, in particular, our papers ``Can Recursive Bisection Alone Produce Routable Placements?'', DAC 2000 (.pdf) and ``Unification of Partitioning, Floorplanning and Placement'', ICCAD 2004 (.pdf) compare Capo with major commercial placers. Capo 10, released in February 2006, reliably produces routable placements for all IBMv2 benchmarks (use the -ROOSTER option) and outperforms all major academic placers which we could obtain or for which published data was available. See our ISPD 2006 paper for more details.

The codes are distributed under a liberal open-source license. All codes conform to the ANSI C++ standard and extensively use the Standard Template Library (STL). This distribution is self-contained in the sense that no additional libraries are required to compile it. It has been successfully compiled with g++2.95, g++3.0.4, g++3.1, g++3.2 (currently not supported), g++3.3, g++3.4, g++4.0, g++4.1, SunPro CC5.1 and MSVC++7.1 and 8 (.NET 2003 and .NET 2005). (see successful platforms reported by users).

Installation requirements

Currently, the installation scripts target Unix systems (Linux, including Debian and RedHat, Solaris 6 and higher) and require PERL 5 or higher. The code requires g++ 2.95.2 or higher, but problems have been reported with g++ 3.0.1 (g++ -v will tell you version number) or SunPro CC 5.1 or higher (Workshop 5.0 and earlier are not supported) that come with Sun Forte C++ (formerly Workshop): CC -V will tell you version number. The code can be compiled with MSVC++7.1 (.NET 2003), but we do not support CygWin. Installation management for Windows is provided by the build files included in new UMpacks, and limited technical support is available via email. For the latest versions of g++, see its official site http://gcc.gnu.org. For PERL downloads, see http://www.perl.org or U. Florida Software Depot. Our software uses gnuplot for visualization. If you are using Windows, you may want to download a gnuplot binary. Linux and Solaris systems usually come with gnuplot installed, but recently released version 4.0 is highly recommended.

Note On at least one platform configuration building Capo executables requires manual intervention (cannot be done out-of-the-box). Contact us if you need help.

At least 300-400Mb of free disk space is required for successful installation and regression testing.

Installation instructions

Start by downloading a "UMpack" from http://vlsicad.eecs.umich.edu/BK/PDtools/tar.gz. UMpacks come in files with names like UMpack-42-042014.tar.gz, where 42 (could be a different number) is the total number of packages inside, and the rest is the date on which UMpack was created (Oct 14, 2004 in this example). Further instructions will use the file name UMpack-42-042014.tar.gz as an example. Type

  gunzip  UMpack-42-042014.tar
  tar xvf UMpack-42-042014.tar.gz

  script install.log
  perl config

  exit

Organization of packages in UMpack

In the process of creating UMpack, package dependencies are traced automatically, and all required packages are included. Therefore, every given UMpack is self-contained, simplifying version management.

Packages are connected through header files and shared libraries (symbolically linked from the lib subdirectory). Every time a shared library is changed, all executables linked against it will automatically accomodate the change. Removal of functions from libraries or changes in function signatures may lead to run-time errors and therefore require a recompilation of all dependent libraires.

Every package contains Makefile that can be used with the following commands: make and makeOpt (to use SunPro CC or other compiler invoked with CC on your system), make-gnu and makeOpt-gnu (to use g++) as well as the distributed versions dmake, dmakeOpt, dmakeOpt-gnu, dmake-gnu and dmakeOpt-gnu that assume the availability of dmake (e.g., Sun's "distributed make"). Note: distributed make is sometimes not good for linking, but only good for compilation.

Every Makefile accomodates [at least] the following targets: all, lib, test. all is typically defined to be lib. make lib produces libraries for this package (necessary to use the package). make test produces regression tests for the package of the form PackageName99.exe, where 99 is a one- or two-digit number. Every .exe file is produced from a .cxx file with the same base name.

Every package has a script called regression, which launches .exe files, compares the "new output" to "precomputed output" and reports the differences. In rare cases, non-trivial but insignificant differences may be caused by processor architecture and compiler subtleties. Segmentation faults and crashes should not happen if the installation went normally.

The files of the form PackageName99.cxx typically demonstrate sample uses of the classes defined in the package and are short "glue files" (i.e., do not define new functionalities, but rather use them). In many cases, those files will be sufficient for many common uses and experiments.

A listing of packages (incomplete)

ABKCommon

basic services (assertions, compatibility, random number generators etc) used in every package

Capo

the Capo placer (fixed-die, standard-cell ASIC placer)

ClusteredHGraph

data structures and algorithms for hypergraph clustering

Combi

combinatorial data structures and algorithms

Constraints

spatial constraints

Ctainers

containers (e.g., BitBoard)

DB

object-oriented back-end VLSI database that stores netlist connectivity, fixed-die site map, and the physical view of standard-cell library.

FilledHier

algorithms for "saturating" a given hierarchy

FixOr

greedy optimization of cell orientations

FMPart

a family of Fiduccia-Mattheyses hypergraph partitioners

GenHier

a generic hierarchy implementation

Geoms

data structures and algorithms for simple geometric objects (points, intervals, rectangles etc)

GeomTrees

data structures and algorithms for geometric trees, primarily Steiner trees

HGraph

generic hypergraph implementations (with parsers)

HGraphWDims

hypergraph with cells that have dimensions and pin offsets

LDPart

an application that reads LEF/DEF, partitions the netlist and saves a partitioning solution

MetaPlacer

a wrapper around Capo, RowIroning and FixOr that automatically adjusts to the input format

MLPart

a leading-edge multi-level hypergraph partitioner

NetTopology

converters from DB, e.g., into HGraph

Partitioning

class PartitioningProblem, its parser and related

Partitioners

a base class for hypergraph partitioners and greedy implementation

PartEvals

a number of evaluations of partitioning solutions, corresponding to various objective functions and methods of incremental evaluation (e.g., net-vector)

PartLegality

randomized generators of legal solutions and fast evaluators of the various legality constraints for incrementally changing partitionings

ParserLEFDEF

a parser of the industry-standard LEF/DEF format (populates UCLA DB)

PlaceEvals

evaluators for placement solutions corresponding to different objective functions

RBPlace

a row-based placement class, parser and related

RBPlFromDB

a converter into RBPlace from DB

RowIroning

a detailed placement improvement technique based on optimal placement

ShellPart

a wrapper around FMPart and SmallPart that uses a time-out for optimal partitioners

SmallPart

optimal partitioners based on enumeration, Gray codes and branch-and-bound

SmallPlacement

data structures for optimal placement

SmallPlacers

optimal branch-and-bound placer implementations

Stats

statistical data structures and algorithms, e.g., linear regression, correlations, random variables with classical distributions, etc.

Documentation and support

Please let us know if your installation went successfully by mailing to capo.request@gmail.com. For Unix systems (Linux, Solaris etc), supply the output of the following commands, uname -a, showrev -p, g++ -v, g++ -print-prog-name=ld, CC -V, ld -V, perl -v, bison --version, flex --version and df -k . (the latter should be run in the installation directory before and after the installation). If your installation failed, please also supply the installation log. For non-Unix systems, supply the name and the version of the system and the compiler as well as the amount of available disk space.

Algorithms used in Capo are described and evaluated in the following publications

• J. A. Roy, S. N. Adya, D. A. Papa and I. L. Markov, ``Min-cut Floorplacement'', (.pdf), IEEE Trans. on Computer-Aided Design, vol. 25, no. 7, pp. 1313-1326, 2006.
• J. A. Roy and I. L. Markov, ``Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement'' (.pdf), to appear in IEEE Trans. on Computer-Aided Design, 2007.
• A. N. Ng, R. Aggarwal, V. Ramachandran, I. L. Markov ``Solving Hard Instances of Floorplacement'', (.pdf), Proc. Int'l Symp. on Physical Design (ISPD), pp. 170-177, San Jose, CA, April 2006.

Journal papers:
1. J. A. Roy and I. L. Markov, ``Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement'' (.pdf), to appear in IEEE Trans. on Computer-Aided Design, 2007.
2. S. N. Adya, I. L. Markov and P. G. Villarrubia, ``On Whitespace and Stability in Min-cut Placement'', (.pdf), Integration: the VLSI Journal, vol. 39/4, pp. 340-362, 2006.
3. J. A. Roy, S. N. Adya, D. A. Papa and I. L. Markov, ``Min-cut Floorplacement'', (.pdf), IEEE Trans. on Computer-Aided Design, vol. 25, no. 7, pp. 1313-1326, 2006.
4. S. N. Adya et al., "Benchmarking for Large-Scale VLSI Placement and Beyond", (.pdf), IEEE Trans. on CAD, April 2004, pp. 472-488.
5. S. N. Adya and I. L. Markov, "Combinatorial Techniques for Mixed-size Placement", (.pdf), ACM Trans. on Design Automation of Electronic Systems , 2004.
6. A. Caldwell, A. B. Kahng and I. L. Markov, ``Hierarchical Whitespace Allocation in Top-down Placement'' (.pdf), IEEE Trans. on CAD, vol. 22(11), November 2003, pp. 716-724.
7. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", (.ps, .pdf), IEEE Trans. on CAD, vol. 19, no. 11, 2000, pp. 1304-1314.
8. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Iterative Partitioning With Varying Node Weights", (.ps, .pdf) VLSI Design, vol. 11, no. 3, 2000, pp. 249-58
9. C. J. Alpert, A. E. Caldwell, A. B. Kahng, I. L. Markov, "Hypergraph Partitioning With Fixed Vertices", (.ps, .pdf), IEEE Trans. on CAD, vol. 19, no. 2, 2000, pp. 267-272.
10. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning", (.ps, .pdf) ACM Journal on Experimental Algorithms, vol. 5, 2000.
11. C. J. Alpert, A. E. Caldwell, T. F. Chan, D. J.-H. Huang, A. B. Kahng, I. L. Markov and M. S. Moroz, "Analytic Engines Are Unnecessary in Top-Down Partitioning-Based Placement" (.ps), VLSI Design, 10(1) (1999), pp. 99-116.  

Conference papers:
1. J. A. Roy and I. L. Markov, ``ECO-system: Embracing the Change in Placement'' (.pdf), to appear in Proc. ASPDAC, 2007.
2. J. A. Roy, D. A. Papa, A. N. Ng, I. L Markov, ``Satisfying Whitespace Requirements in Top-down Placement'', (.pdf), Proc. Int'l Symp. on Physical Design (ISPD 2006), pp. 206-208.
3. J. A. Roy, J. F. Lu and I. L. Markov, ``Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement'' (.pdf), Proc. Int'l Symp. on Physical Design (ISPD 2006), pp. 78-85.
4. A. N. Ng, I. L. Markov, R. Aggarwal and V. Ramachandran, ``Solving Hard Instances of Floorplacement'' (.pdf), Proc. Int'l Symp. on Physical Design (ISPD 2006) (BPA nominee), pp. 170-177.
5. J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, J. F. Lu, A. N. Ng, I. L. Markov, ``Capo: Robust and Scalable Open-Source Min-cut Floorplacer'' (.pdf), Proc. Intl. Symposium on Physical Design (ISPD 2005) .
6. S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa and I. L. Markov, ``Unification of Partitioning, Floorplanning and Placement'' (.pdf, slides), Int'l. Conf. Computer-Aided Design (ICCAD 2004), pp. 550-557.
7. D. A. Papa, S. N. Adya and I. L. Markov, ``Constructive Benchmarking for Placement'' (.pdf), Proc. Great Lakes Symp. on VLSI (GLSVLSI), Boston, Massachusetts, April 2004, pp. 113-118.
8. A. B. Kahng, I. L. Markov and S. Reda, "On Legalization of RowBased Placements", (.pdf), to appear in Proc. Great Lakes Symp. on VLSI (GLSVLSI), Boston, Massachusetts, April 2004.
9. S. N. Adya, I. L. Markov and P. G. Villarrubia, "On Whitespace and Stability in Mixed-Size Placement", (.pdf), in Proc. Intl. Conf. on Computer-Aided Design(ICCAD 2003), pp. 311-318.
10. S. N. Adya and I. L. Markov, "Improving Min-cut Placement for VLSI Using Analytical Techniques", in Proc. IBM ACAS Conference, pp. 55-62, Austin, TX, February, 2003.
11. S. N. Adya and I. L. Markov, "Consistent Placement of Macro-blocks Using Floorplanning and Standard-Cell Placement", (.pdf), in Proc. ACM/IEEE Intl. Symp. on Physical Design (ISPD), pp. 12-17, April 2002.
12. S. N. Adya, M. Yildiz, I. L. Markov, P. G. Villarrubia, P. N. Parakh and P. H. Madden, "Benchmarking For Large-Scale Placement and Beyond", (.pdf, .ppt), Proc. Intl. Symp. on Physical Design (ISPD) , pp. 95-103, Monterey, CA, April 2003.
13. A. E. Caldwell, A. B. Kahng and I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?", (.ps, .pdf), Proc. Design Automation Conf., Los Angeles, June 2000, pp. 693-698.
14. 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.
15. 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.
16. A. E. Caldwell, A. B. Kahng and I. L. Markov, "Optimal Partitioners and End-Case Placers for Standard-Cell Layout", (.ps, .pdf, slides) Proc. ACM Intl. Symp. on Physical Design, April 1999, pp. 90-96.
17. A. E. Caldwell, A. B. Kahng and I. L. Markov, "Relaxed Partitioning Balance Constraints in Top-Down Placement" (.ps, .pdf, slides) Proc. IEEE ASIC Conference, September 1998, pp. 229-232.  Additional publications will be posted at http://www.eecs.umich.edu/~imarkov/pubs/

    ---