Bookshelf Overview

Andrew Caldwell, Andrew B. Kahng and Igor Markov

Overview Contents

I. Motivation
II. Key Types of Bookshelf Entries
III. Language/OS/Compiler/Packaging Issues
IV. Steering, Maintenance and Responsibilities
Appendix A. Sample Bookshelf Slots
Appendix B. Sample Bookshelf Entries

I. Motivation

The growing complexity and breadth of VLSI CAD problems and their cutting-edge solutions results in increased adoption time for algorithm advances. Additionally, the lack of a universally-accepted, widely-distributed feedback mechanism from industry to academia encourages research on outdated problems. The net effect is continually attempting to solve today's problems with yesterday's tools. The CAD-IP Reuse initiative attempts to resolve these problems by addressing the critical issues of time to market and quality of results within the domain of fundamental VLSI CAD algorithms.

A central piece of the CAD-IP Reuse initiative is The GSRC Bookshelf for Fundamental CAD Algorithms. The Bookshelf provides (i) a "one-stop shop" for the latest word in CAD algorithms research; (ii) an interoperable, plug-and-play library of implementations that facilitates methodology innovation and algorithm adoption by CAD organizations; (iii) implicit convergence for the research community to appropriate CAD data models for the 10-year horizon and beyond; and (iv) standards and conventions to facilitate accurate evaluation of new algorithmic ideas and technologies.

The Bookshelf offers benefits for the academic community as well. In particular, the Bookshelf seeks to enable (i) improved effectiveness, rigor, and impact of heuristic algorithm research in VLSI CAD, (ii) improved communication (and competition) between research groups, and (iii) more rapid adoption (and recognition) of research advances by industry.

To achieve these goals, the Bookshelf will contain

  1. Reference implementations - to ensure progress in algorithm research, especially when heuristics are involved. We envision a series of freely available implementations of fundamental VLSI CAD algorithms that solve fundamental problems for which benchmarks are available.

  2. Standardized data representations - to enable easy comparisons to reference implementations.

  3. Standard experimental evaluation techniques (comparison methodologies) - to support collaborative research. Such techniques help 'prune' unpromising approaches and ensure that it is clear which approaches are currently the best.

Of the above, only file formats have been available to the VLSI CAD community with various benchmarks released in last 15 years. Reference implementations are very rare, and their internal data structures are in no way standardized or commonly used.

The GSRC Bookshelf will consist of slots which contain entries. Slots correspond intuitively to "problems", e.g., performance optimization of a multi-terminal interconnect tree with topology design, repeater insertion, and driver/wire/repeater sizing degrees of freedom. Entries in a slot correspond to problem definition, standard data representations and parsers, reference implementations, etc. Key generic types of entries are listed below. Appendix A lists sample slots and Appendix B lists sample entries.

The Bookshelf project is currently underway and growing. Work has begun on size slots and their "charter entries". Researchers from four Universities across the US are actively contributing to this early development effort. More contributors are needed, however. See the instructions if you'd like to get involved.

II. Key Types of Bookshelf Entries

To support collaborative and fast-moving research on optimization heuristics, we distinguish the following basic types of entries.
  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.

III. Language/OS/compiler/packaging issues

An author of a Bookshelf entry that includes software must ensure that users can compile, build, link to and run the software. The main issues here are languages, operating systems, compilers, build systems and code packaging.

  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.

IV. Steering, maintenance and responsibilities

  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.

Appendix A. Initial Bookshelf slots

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.

Note that both syntheses and analyses can be part of the Bookshelf.

Appendix B. Example Bookshelf entries for Hypergraph Partitioning

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.