Generation of tightly controlled equivalence classes for experimental design of heuristics for graph-based NP-hard problems.

다국어 초록 (Multilingual Abstract)

Computer-aided design (CAD) of VLSI circuits relies on heuristics that optimize cost functions related to a graph model of a circuit. Since the problems are typically NP-hard, the quality of solutions can vary significantly. The current methodology to evaluate the performance of such heuristics is not at the level of <italic>experimental design</italic> that is the norm in disciplines such as bio-medical sciences and others. A major impediment is the lack of well-defined equivalence classes of circuits. Comparison of two heuristics based on a number of unrelated, single instances of circuits is flawed—it can be shown that any incremental improvements that are observed may well be offset by variations induced by a number of isomorphic instances of the same circuit.
The goal of this thesis is to introduce a method to synthesize, for any <italic> reference circuit</italic>, a well-defined and tightly controlled circuit class to support experimental design methodology for problems such as partitioning, placement, and routing. Each member of the class must be sufficiently ‘close’ to its reference circuit: if the reference is a multiplier, all circuits in the class should have a multiplier-like structure. Such tight control has not been achieved in earlier research. Characterizations such as the same number of vertices and nets (hyperedges), the same number of levels, the same Rent's exponent are necessary but not sufficient. The control that we need is achieved by characterizing the graph in terms of a <italic>well-defined order</italic>. Significantly, we demonstrate that an equivalent characteristic graph ordering can be achieved by minimizing any of the following cost functions: (1) crossing number, (2) netspan number, or (3) cellspan number. This brings out the difficulty of the characterization problem: finding such an order is NP-hard.
We address the ordering problem of the reference graph <italic>G</italic> with an effective heuristic that finds the order of the <italic>characteristic spanning tree st</italic>(<italic>G</italic>) and show that the crossing number of <italic>G</italic> and <italic>st</italic>(<italic>G</italic>) are tightly correlated for graphs that represent typical VLSI circuits. The characteristic signature of the graph now includes the order of the spanning tree and the netspan number corresponding to this order.
We develop a synthesis method such that each member of the circuit class, a <italic>sibling</italic>, satisfies this signature. Siblings retain all significant characteristics of their reference circuit. We demonstrate the scalability of the proposed approach through a number of experiments. The sibling classes are shown to have results within ±(4–9)% of the parent circuit—under all physical design tools at our disposal.