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: July 22, 2013 by imarkov

Introduction

This release contains over 200,000 lines in C++ implementing 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 have not been actively maintained since 2006. However, as of 2013, several commercial chips are taped out every year that have been laid out by these tools. Some of these codes are used in commercial products for design validation.

The codes are distributed under a liberal open-source license. are predominantly in C++ and use the Standard Template Library (STL). We have not performed upgrades for C++11, but hope that this does not affect compilation. This distribution is self-contained in the sense that no additional libraries are required to compile it.

Installation requirements

Currently, the installation scripts target Linux systems and require PERL 5 or higher. Some older versions of g++ are known to have optimization bugs exposed by our code. The code is also compatibke with MSVC++, but not actively supported for this target. Installation management for Windows is provided by the build files included in new UMpacks. For the latest versions of g++, see its official site http://gcc.gnu.org. For PERL downloads, see http://www.perl.org. Our software produces gnuplot scripts for visualization. If you are using Windows, you may want to download a gnuplot binary. Linux systems usually come with gnuplot installed.

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
this will create directory UMpack-42-042014 with package subdirectories inside. Other files are README.txt (installation instructions), config (installation script), COPYRIGHT (notice), Versions (of packages), lib/ (symbolic links to shared libraries produced by packages). Read README.txt and then type
  script install.log
  perl config

The first command will log all screen output into the file install.log, and the second command will perform installation. First, it will probe the system and ask you several questions, then it will configure UMpack accordingly. When installation finished, and you see a command prompt, type
  exit
This will finalize the install.log file. Enclose it with your bug reports and installation questions (sent to capo.request@gmail.com). The installation program will check the available disk space (at least 300-400Mbs are required) and compiler versions. It will update Makefiles in all packages for use on your system and then offer to build libraries in all packages. If libraries are built successfully, it will offer testing the packages. The installation program will attempt to produce executables, run them, compare the results to precomputed "expected output" and report how big the differences are. In most cases, there will be no difference, however, several packages may report differences that are not in indicative of errors (those are mentioned under "Known problems" below). The differences are saved in file diffs.notime in every package and can be verified by visual inspection and sent to developers for further analysis. If you would like to build libraries using a different configuration or a different compiler, you can run the installation program more than once.

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

Documentation is provided with source code. Limited support may be available through email.

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

For results of the latest version of Capo, see these papers:
    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. 
  18. Additional publications will be posted at http://www.eecs.umich.edu/~imarkov/pubs/