The Benchmark Archives at CBL
(after 1996)

You may view the benchmarks in the order shown below or you may traverse all available
links to this directory in a single pass. Please use our PosterNotes-based Discussion Group
forum to provide comments and suggestions about this page, and the subject of
benchmarks and benchmarking processes in general. In particular, you may subscribe to
Benchmark-review to keep current.

We introduce EQUIVALENCE CLASSES of benchmarks within each directory as follows:

2 layer graphs in the directory 2-layer-graphs

two-level combinational in the directory PLA

multi-level combinational in the directory ML-COMB

multi-level sequential in the directory ML-SEQ

The directory PLA contains 100 functional descriptions in each equivalence class. The first sets of experiments with some of these PLAs are available in 1996-Thesis-PhD-Zemva.

The directory ML-COMB contains 100+1 combinational mutant circuits in each equivalence class. The procedure for generating the equivalence class mutants is described in 1996-TR@CBL-04-Ghosh. The first sets of experiments with some of these mutants have been described in 1997-TR@CBL-01-Ghosh, 1997-ISPD-Kapur, and the companion documents 1997-DAC-Lavana , 1997-TR@CBL-02-Khetawat.

For location of these documents and other publications see http://www.cbl.ncsu.edu/publications/.

Similar to the directory ML-COMB, the directory ML-SEQ will contain 100+1 sequential mutant circuits in each equivalence class. It is scheduled for release by mid-April 1997. Presently, only descriptions of the reference circuits we plan to use are archived in this directory.

Some of the factors that motivate the introduction of equivalence classes of circuit mutants are the following:

Today, typical experiments that report `performance' of EDA algorithms are based on isolated instances of circuit benchmarks, leading to results that can be inconclusive.

Construction of a large sample of circuits that belong to the same equivalence class is now feasible. We take a signature sigma_0 of a SINGLE reference circuit eta_0 and construct an equivalence class of signature-invariant 'mutants' eta_i in the class N_sigma_0 (i > 0). Such circuits will have the same number of I/Os, the same number of nodes, and the same number of pins, distributed across the same number of levels.

Experiments with the proposed selection of mutants from the respective equivalence classes demonstrate consistently and unambiguously that the design objectives, being optimized by various algorithms, behave as random variables and give rise to well-defined `distributions of circuit mutants'.

Even simple demonstration circuits such as roth'62 from J. P. Roth, R. M. Karp, Minimization over Boolean Graphs, IBM Journal of Research and Development, April 1962 and its mutants can be shown to represent a non-trivial challenge to the current generation of logic optimization algorithms.

While some reference circuits appear easy candidates for generation of canonical ROBDD representations, THEIR MUTANTS MANY NOT BE. Even trivial mutation classes, such as isomorphic netlists in randomized order, can induce unpredictable execution of some ROBDD-based algorithms!!

For further information about the mutants/mutation process contact : ghosh@cbl.ncsu.edu.