Bookshelf Overview

1. A generic problem -- an in-memory representation that can be passed to various optimization engines, contains "solution slots" and have integrates I/O including parsers of standard benchmark formats.

2. Reference solver implementations that can construct a requested number of solutions for a given "generic problem" instance, and write them into into solution slots. Reference implementations should be comparable to the best reported and usable in successful applications. Ideally, to support fundamental research as well as applications, reference implementations should enable analysis of (their performance on) relevant problem instances. This implies modular designs that can accommodate alternative component implementations and testing to determine the dominating combinations.

3. Evaluators that can evaluate various cost functions on the contents of solution slots, independently of the solver implementations.

4. Heuristic evaluation and comparison methodology consisting of descriptions of testing procedures, precepts for experimental evaluation of metaheuristics, links to relevant benchmarks, best known results and corresponding reference implementations, etc.

1. To maximize the value of academic efforts to industry, software entries in the Bookshelf must be potentially usable in industrial software, or at least easily testable in the industry setting. This entails compatibility with commercial compilers as well as GNU's g++. (see below).

2. The Bookshelf Steering Committe believes that C++ is the most appropriate language for new implementations. It is hoped that researchers/implementers will release their source code in C++. Some converters and installation scripts have been done in PERL or shell scripting languages. Classic C code has a number of significant maintenance drawbacks, and Java code has serious limitations, e.g., in the Fabrics domain speed, quality, and capacity attributes are all viewed as critically important. (Additionally, most C++ implementations can be rewritten in Java for educational purposes, availability on the Web and easier interfaces.)

3. Bookshelf entries should strive to support Solaris, Linux and MS Windows (NT and '98). Implementations within the Bookshelf must compile/run on at least one of these systems.

4. A standard development process might reasonably rely on SunPro CC 4.2 (June '98 patch; SunCC5.0 seems broken) or g++2.95 (or higher). In the former case, one may use a "ported" version of the Silicon Graphics implementation of the Standard Template Library (ver 2.13, October 1997) that is freely available on the Web.

5. A sound build system is pivotal to the development process, as well as to the portability and modularity of Bookshelf entries. The main challenge here seems the transparent support of component-based frameworks made of Bookshelf entries. To our knowledge, there are no standard public domain build systems. Revision control systems such as RCS, CVS and SCCS do not provide build systems. Commercial systems, such as ClearCase from Rational, are expensive and not generally available enough to make their use standard within the Bookshelf.

   Currently, the Bookshelf is using an in-house, minimalistic build system for code releases. The system can be quickly installed on Solaris/Linux systems with a PERL script and that is based on Makefiles, shared and static libraries and a system of directories and symbolic links. This can be a part of a larger arrangement that provides integrated regression testing, semantic revisions and archiving.

   "Canned" revision control systems such as RCS, CVS and SCCS can be transparently used with such a build system for fine-grained backups or as network-based source tree repositories. However, they are not required at the moment.

1. The Bookshelf will consist of two sections. Submissions to the "contrib" section become automatically published and are ranked by the community (the number of downloads or the like). Submissions to the "golden" section are reviewed and ranked by the Steering Committee and independent reviewers from the industry, academia and GSRC stuff. In general, Bookshelf slots and entries should should be implemented on the basis of
   • significance of the slot, and need for improved solutions;
   • clarity of the definition of the slot, and intrastructure entries (interchange formats, parsers, problem/solution classes, etc.)
   • availability of reference implementations that can be assimilated by the Bookshelf (this includes "wrapping" of working codes, i.e. adding a robust C++ interface); and
   • availability of resources that can be directed towards implementation of missing entries for a given slot
   The Steering Committee is, if necessary, be responsible for selecting among multiple competing definitions for a given slot.

2. The Steering Committee is initially responsible for the maintenance of the Bookshelf structure, while the maintenance of entries is the responsibility of the authors.

3. The Steering Committee will accept unsupported entries on a case-by-case basis when such entries are not critical to the structure of the Bookshelf.

Following are the proposed slots for the initial Bookshelf effort. For current GSRC members, it is proposed that this be accommodated within the scope of current efforts, particularly for those T2 Circuit Fabrics team members who have clustered themselves around "limits of current fabrics/methodology" (i.e., the logic-layout synthesis unification) and previously committed to delivering pieces of a "common software base". Other possible names -- outside the current GSRC team -- are also listed. We feel that these investigators are doing leading-edge work in the respective areas, and we hope that these investigators will be willing to contribute by wrapping software and test cases, contributing designs of Bookshelf slots, etc.

• 2-D block packing (C.K. Cheng, Wayne Dai, Majid Sarrafzadeh)
• 2-D block packing with wiring minimization (C.K. Cheng, Wayne Dai)
• Buffered/sized interconnect tree topology and sizing optimization (Jason Cong, Martin Wong, John Lillis)
• Buffered clock topology/embedding optimization (Larry Pileggi, Eby Friedman, Andrew Kahng)
• Clock skew scheduling (Eby Friedman)
• Layout RLC extraction (Wayne Dai, Eby Friedman)
• Gate and interconnect delay calculation (Wayne Dai)
• Gate-level static timing verification (Larry Pileggi, Karem Sakallah)
• Area-delay-power tradeoff driven synthesis and mapping (Bob Brayton)
• Gridless area routing (Jason Cong)
• 1-D and 2-D Global Placement (John Lillis)
• Classic (flat) balanced min-cut hypergraph partitioning (Andrew Kahng)
• Clustering for multilevel balanced min-cut hypergraph partitioning (Andrew Kahng)
• Hypergraph partitioning with geometric / terminals information (Andrew Kahng)
• Timing- and routability-driven standard-cell placement (Andrew Kahng, Majid Sarrafzadeh)

The "slot" of VLSI hypergraph partitioning provides a good example. The field is reasonably mature: standard benchmarks and file formats are well-publicized (Alpert, ISPD98), and an efficient but limited-functionality reference implementation is available on the Web. On the other hand, recent literature has many purported improvements that are hard to replicate, and different researchers report very different performance of their implementations on common benchmarks (and it is impossible to determine what causes these differences).

A fully populated slot might contain

1. A new standard file format that is easily human-readable and contains extensions for common hypergraph partitioning formulations. The hypergraph format is also used as the netlist in the Standard Cell Placement slot.
2. Converters between common file formats and checkers for compliance with formats.
3. A standard hypergraph implementation.
4. A standard class PartitioningProblem with .fix and .blk I/O
5. A competitive Fiduccia-Mattheyses partitioning heuristic implementation
6. A competitive Multi-Level FM partitioning heuristic implementation
7. Various classes of benchmarks in common formats, e.g., the ISPD-98 and ISPD-99 circuit partitioning benchmark suites in .netD, .are, .fix and .blk formats. Instances with fixed vertices may be considered as part of a separate slot (Hypergraph Partitioning With Terminals).
8. Best known results for standard benchmarks. This entry needs continuous maintenance and can naturally be delegated to the owners of the best-known implementations.
9. An experimental methodology for comparing heuristics with references to Bookshelf entries for the same slot; a literature survey; common caveats; etc.

A Partitioning slot is currently available which contains most of the above.