Calibrating Achievable Design:
CAD-IP Reuse, Technology Extrapolation, and Metrics
Solving today's design problems with yesterday's tools results in
an inefficient design process.
To improve design productivity, CAD tools must continually integrate
the latest algorithmic and methodological innovations. Yet, today's
industry infrastructure, and today's mechanisms that allow academic
research efforts to intercept future design problems, do not support
continuous improvement of CAD tools "at the leading edge".
Our CAD-IP Reuse initiative addresses the critical
problems of time-to-market and quality of results in
the domain of CAD tools. Here, CAD-IP consists of the basic
algorithms that solve fundamental CAD problems.
We are creating an infrastructure and a culture change that seeks
to reduce barriers to adoption and integration of algorithms research
at the leading edge.
A key piece of the infrastructure is what we call 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
In implementing the GSRC Bookshelf infrastructure, obvious issues
include maintaining benchmark data and reference solvers, adopting
evaluation standards, and adopting standards for software. Currently,
we have established a mechanism of slots and entries.
A slot in the Bookshelf is a "key problem for the VLSI CAD field".
For a given slot, there are several basic types of entries, including
(i) canonical problem definition (e.g., in-memory "class
partitioningProblem", serial I/O format ".netD/.are"), (ii)
reference solver implementations (e.g., "hMetis1.5.3"), (iii)
benchmark data (e.g., "ISPD98/ISPD99 benchmark suites"), and (iv)
heuristic evaluation and comparison methodology.
Technology Extrapolation enables prediction of technology's effects
on the achievable design envelope, at all levels: single switch,
point-to-point interconnect, ... up through function block,
There is a rich heritage of such predictors, including
Bakoglu/Meindl (SUSPENS), Sai-Halasz, Rahmat et al., BACPAC, the
various Roadmap efforts,
as well as innumerable internal efforts. In viewing this body of
efforts, the greatest regret is that none of them has lasted; none
is "canonical" for the design automation community.
The goal of the GSRC Technology Extrapolation effort is to establish a
"repository of first choice" for data, equations, models, facts,
related to technology and technology extrapolation, as well as a system
that allows use of this repository. The system should provide both
feasibility checking and prediction.
Issues include: (i) making a system
that is usable by designers who have confidential data,
(ii) making a system that is adoptable and growable by the community,
with data and models coming in from users (e.g., Rent parameter
calculations, new models and equations, data points for calibration, etc.),
and (iii) the software architecture of the repository and system.
GTX, the GSRC Technology Extrapolation System, provides a
framework that addresses these and other issues.
Metrics -- or, "Measure, then Improve" seek
a new awareness of
design as science or process, rather than design as art.
Metrics enable design process optimization through a
framework of recording, mining, measuring, diagnosing, and
then improving the design process.
Infrastructure for Metrics must be developed by the EDA industry
and its customers. However, the GSRC can serve as a catalyst for
a Metrics initiative in several ways, e.g., (i) helping to achieve
rapid convergence on such issues as metrics schemas,
(ii) creating "demand-pull" by raising awareness of research and
third-party business opportunities in data mining, visualization,
and diagnosis of the design process, (iii) implementing
metricized internal tools and instrumenting GSRC design drivers
and other academic design projects, and (iv) developing data
warehousing infrastructure to pull together metrics data from
all available metrics data warehouses and increase its value
as a testbed for research.
Synergies between the three initiatives include the following.
CAD-IP Reuse (via the Bookshelf) and Technology Extrapolation
- Technology Extrapolation informs the heuristics in the Bookshelf
of their most likely instance characteristics.
- The Bookshelf is the repository for the latest heuristic
best practices, which reciprocally inform Technology Extrapolation of what
can be achieved. This is essential at the
"compound devices/interconnects level", which lies
above individual switches and interconnects, but below such system-level
descriptors as Rent parameter, #watts, #gates, #I/Os.
(There are at least two flavors of "inform": (i) abstract models of
the heuristics correspond to "envelope" or "feasibility" analyses,
while (ii) fitted, parameterized models of specific heuristics corrspond
more to "predictive" analyses.)
CAD-IP Reuse (via the Bookshelf) and Metrics
- Metrics inform the Bookshelf of relevant formulations and objectives,
i.e., only through the metricization and optimization of the design process
can we determine which problems (design tasks) and objectives (design
criteria) are truly critical to success.
- The Bookshelf's heuristic best practices
are modeled via the Metrics infrastructure, which
not only provides fitting and correlation analyses (the traditional
tools by which heuristics are modeled), but at a higher level tells us
which aspects of the heuristic are important to model in the first place.
Metrics and Technology Extrapolation
- Technology Extrapolation yields feasibility and sanity checkers for
various operations within the design process (e.g., an oracle to
determine whether a given netlist can be embedded in a given
interconnect resource while achieving a given clock frequency).
These can be used by Metrics to determine whether distinct phases
of the design process fit together well.
- The Metrics infrastructure determines the instance and tool
parameters that allow us to extend Technology Extrapolation from "feasibility"
and "envelope" checking to more design- and tool-specific prediction.
The unifying themes of design optimization and prediction
are also supported by these three initiatives.
- what are the most relevant formulations and objectives ?
- what are the most relevant parameters of an instance ?
- what are the most relevant models / knobs of heuristics (i.e., tools) ?
- what needs to be passed down/up/between tools ?
CAD-IP Reuse (via the Bookshelf) supports:
- leading-edge research on relevant formulations and objectives
- Bookshelf slots and entries: most critical problems,
robust standard interfaces, data interchange formats, solution
evaluators, methodologies for metaheuristic comparison and evaluation
Technology Extrapolation supports:
- feasibility analysis, i.e., constraint propagation from laws
of physics and ideal tool models
- prediction, i.e., inference chains based on more specific
models and parameters of various tools and instances