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:
- 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:
- 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.
- 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.
- 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.
- S. N. Adya et al., "Benchmarking for Large-Scale VLSI Placement and Beyond",
(.pdf),
IEEE Trans. on CAD, April 2004, pp. 472-488.
- S. N. Adya and I. L. Markov, "Combinatorial Techniques for Mixed-size Placement",
(.pdf),
ACM Trans. on Design Automation of Electronic Systems , 2004.
- 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.
- 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.
- 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
- 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.
- 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.
- 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:
- J. A. Roy and I. L. Markov, ``ECO-system: Embracing the Change
in Placement'' (.pdf),
to appear in Proc. ASPDAC, 2007.
- 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.
- 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.
- 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.
-
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) .
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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,
"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.
-
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/